Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Проблема поиска в больших информационных массивах
Содержание
- 1. Проблема поиска в больших информационных массивах
- 2. Содержание: Проблема поиска Сортировка — от хаоса к порядку Последовательный поиск Двоичный поиск Хэширование Параллельные сортировки
- 3. Определение информации Информация (от лат. informatio –
- 4. Рост информацииИнформационное общество — историческая фаза развития
- 5. Вывод:Поиск информации является одной из наиболее распространенных
- 6. Сортировка — от хаоса к порядкуСортировка является
- 7. Сортировка — от хаоса к порядкуИтак, две
- 8. Сортировка — от хаоса к порядкуВычислительная трудоемкость
- 9. Сортировка выбором
- 10. Сортировка выбором
- 11. В задачах поиска предполагается, что все данные
- 12. Пусть нам необходимо организовать доступ к файлу,
- 13. Сортировка записей в файле также неприменима, поскольку
- 14. При доступе к данным вначале в этой
- 15. Алгоритм поиска: вначале аргумент поиска сравнивается с
- 16. Поиск по бинарному дереву
- 17. Еще один интересный подход, применяемый для повышения
- 18. Имея такую функцию можно вычислить адрес записи
- 19. Если множество ключей заранее неизвестно или очень
- 20. Общая задача:Заключается в хранении некоторого множества записей,
- 21. Основная идея – использование несколько отдельных списков
- 22. Пусть вспомогательные таблицыFIRST[i] – содержит для каждого
- 23. Пусть вспомогательные таблицыFIRST[i] – содержит для каждого
- 24. Итак, пусть ключи – имена. Зададим функцию: 1 для А-Е 2 для Ж-Л 3 для М-Р 4 для С-Я.Хешированиеh(Имя)=
- 25. ХешированиеKEY[1] = Ольга Алексеевна NEXT[1] = 0
- 26. KEY[1] = Ольга Алексеевна NEXT[1] = 0
- 27. KEY[1] = Ольга Алексеевна NEXT[1] = 0
- 28. Хеширование
- 29. ХешированиеАлгоритмы хэширования, или хэш-функции, применяются в схемах
- 30. Чет-нечетная перестановка
- 31. Проблемы организации поискаКнига «Введение в информационный поиск»
- 32. Организация поиска в ИСПроблема эффективной организации информационного
- 33. Удачи!Кто ищет — тот найдет!Кто ищет грамотно — тот найдет быстро!!!
- 34. Скачать презентанцию
Содержание: Проблема поиска Сортировка — от хаоса к порядку Последовательный поиск Двоичный поиск Хэширование Параллельные сортировки
Слайды и текст этой презентации
Слайд 1
Проблемы поиска в больших информационных массивах
Ольга Алексеевна Юфрякова
Старший преподаватель кафедры
программирования и высокопроизводительных вычислений института математики, информационных и космических технологий
Слайд 2Содержание:
Проблема поиска
Сортировка — от хаоса к порядку
Последовательный
поиск
Двоичный поиск
Хэширование
Параллельные сортировки
Слайд 3Определение информации
Информация (от лат. informatio – разъяснение, осведомление, изложение)
– сведения об объектах и явлениях окружающей среды, их параметрах,
свойствах и состоянии, которые уменьшают имеющуюся о них степень неопределенности, неполноты знаний.
Слайд 4Рост информации
Информационное общество — историческая фаза развития цивилизации, в которой
основным продуктом производства является информация (в том числе знания).
Слайд 5Вывод:
Поиск информации является одной из наиболее распространенных и одновременно наиболее
сложных задач, с которыми приходится сталкиваться в мире любому человеку.
Слайд 6Сортировка — от хаоса к порядку
Сортировка является одной из типовых
проблем обработки данных, и обычно понимается как задача размещения элементов
неупорядоченного набора значений в порядке монотонного возрастания или убывания.
Слайд 7Сортировка — от хаоса к порядку
Итак, две важнейшие операции над
массивами информации: сортировка и поиск. Д.Кнут посвятил этой проблеме весь
3 т. «Искусства программирования».C:\Users\800941\Desktop\Экзафлопсное будущее\Threads\thrddemo.exe
Слайд 8Сортировка — от хаоса к порядку
Вычислительная трудоемкость процедуры упорядочивания является
достаточно высокой. Так, для ряда известных простых методов (пузырьковая сортировка,
сортировка включением и др.) количество необходимых операций определяется квадратичной зависимостью от числа упорядочиваемых данных.
Слайд 11В задачах поиска предполагается, что все данные хранятся в памяти
с определенной идентификацией и, говоря о доступе, имеют в виду
прежде всего доступ к данным (называемым ключами), однозначно идентифицирующим связанные с ними совокупности данных.Доступ к данным
Слайд 12Пусть нам необходимо организовать доступ к файлу, содержащему набор одинаковых
записей, каждая из которых имеет уникальное значение ключевого поля.
Самый
простой способ поиска – последовательно просматривать каждую запись в файле до тех пор, пока не будет найдена та, значение ключа которой удовлетворяет критерию поиска. Очевидно, этот способ весьма неэффективен, поскольку записи в файле не упорядочены по значению ключевого поля.
Методы доступа к данным
Слайд 13Сортировка записей в файле также неприменима, поскольку требует еще больших
затрат времени и должна выполняться после каждого добавления записи.
Поэтому,
поступают следующим образом – ключи вместе с указателями на соответствующие записи в файле копируют в другую структуру, которая позволяет быстро выполнять операции сортировки и поиска.Методы доступа к данным
Слайд 14При доступе к данным вначале в этой структуре находят соответствующее
значение ключа, а затем по хранящемуся вместе с ним указателю
получают запись из файла.Существуют два класса методов, реализующих доступ к данным по ключу:
методы поиска по двоичному дереву,
методы хеширования.
Методы доступа к данным
Слайд 15Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в
корне. Если аргумент совпадает с ключом, поиск закончен, если же
не совпадает, то в случае, когда аргумент оказывается меньше ключа, поиск продолжается в левом поддереве, а в случае, когда больше ключа – в правом поддереве. Увеличив уровень на 1, повторяют сравнение, считая текущий узел корнем.Двоичный поиск
Слайд 17Еще один интересный подход, применяемый для повышения эффективности доступа к
данным, – хеширование
Этот метод используется тогда, когда все множество ключей
заранее известно и на время обработки может быть размещено в оперативной памяти. В этом случае строится специальная функция, однозначно отображающая множество ключей на множество указателей, называемая хеш-функцией (от английского "to hash" – резать, измельчать).
Хеширование
Слайд 18Имея такую функцию можно вычислить адрес записи в файле по
заданному ключу поиска. В
общем случае ключевые данные, используемые для определения
адреса записи, организуются в виде таблицы, называемой хеш-таблицей. Хеширование
Слайд 19
Если множество ключей заранее неизвестно или очень велико, то от
идеи однозначного вычисления адреса записи по ее ключу отказываются, а
хеш-функцию рассматривают просто как функцию, рассеивающую множество ключей во множество адресов.Хеширование
Слайд 20Общая задача:
Заключается в хранении некоторого множества записей, каждая их которых
содержит значение ключа и некоторые данные об этом ключе.
Мы хотели
быстро находить данные по заданному ключу К.Пусть KEY[j] – ключи; DATA[j] – данные.
Хеширование
Слайд 21Основная идея – использование несколько отдельных списков вместо одного огромного.
Хэш-функция
преобразует любой возможный ключ К в номер списка h(K), где
далее произойдет поиск.Хеширование
Слайд 22Пусть вспомогательные таблицы
FIRST[i] – содержит для каждого i=1..m, указатель на
1-ый элемент в списке i.
NEXT[j] – j=1..N, указатели на
запись, следующую за записью j в том списке, которому эта запись принадлежит.Если список i пуст, то FIRST[i] = -1.
Если запись последняя в списке, то NEXT[j] =0.
Хеширование
![Пусть вспомогательные таблицыFIRST[i] – содержит для каждого i=1..m, указатель на 1-ый элемент в списке i. NEXT[j] –](/img/thumbs/98a6d6792f65e52ca28574215bdf1103-800x.jpg "Проблема поиска в больших информационных массивах Пусть вспомогательные таблицыFIRST[i] – содержит для каждого i=1..m, указатель на 1-ый")
Слайд 23Пусть вспомогательные таблицы
FIRST[i] – содержит для каждого i=1..m, указатель на
1-ый элемент в списке i.
NEXT[j] – j=1..N, указатели на
запись, следующую за записью j в том списке, которому эта запись принадлежит.Если список i пуст, то FIRST[i] = -1.
Если запись последняя в списке, то NEXT[j] =0.
Хеширование
![Пусть вспомогательные таблицыFIRST[i] – содержит для каждого i=1..m, указатель на 1-ый элемент в списке i. NEXT[j] –](/img/thumbs/6b1973bb1d1e47b3d8bef3a4252ff268-800x.jpg "Проблема поиска в больших информационных массивах Пусть вспомогательные таблицыFIRST[i] – содержит для каждого i=1..m, указатель на 1-ый")
Слайд 24Итак, пусть ключи – имена.
Зададим функцию:
1 для А-Е
2 для
Ж-Л
3 для М-Р
4 для С-Я.
Хеширование
h(Имя)=
Слайд 25Хеширование
KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3
KEY[2] = Лев
NEXT[2] = 0
KEY[3] =Жанна NEXT[3] = 0
FIRST[1] FIRST[2] FIRST[3] FIRST[4]
-1 -1 -1 -1
![ХешированиеKEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3KEY[2] = Лев NEXT[2] = 0 KEY[3] =Жанна NEXT[3] = 0 FIRST[1]](/img/thumbs/566fb2bd3bbc2f65c53940aeaab638c1-800x.jpg "Проблема поиска в больших информационных массивах ХешированиеKEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3KEY[2] = Лев NEXT[2]")
Слайд 26KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3
KEY[2] = Лев
NEXT[2] = 0
KEY[3] =Жанна NEXT[3] = 0
FIRST[1] FIRST[2] FIRST[3] FIRST[4]
-1 -1 1 -1
Хеширование
![KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3KEY[2] = Лев NEXT[2] = 0 KEY[3] =Жанна NEXT[3] = 0 FIRST[1]](/img/thumbs/38fcf33068849155aef3e078a6c11389-800x.jpg "Проблема поиска в больших информационных массивах KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3KEY[2] = Лев NEXT[2]")
Слайд 27KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3
KEY[2] = Лев
NEXT[2] = 0 h(Лев)=2
KEY[3] =Жанна NEXT[3] = 0
FIRST[1] FIRST[2] FIRST[3]
FIRST[4] -1 2 1 -1
Хеширование
![KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3KEY[2] = Лев NEXT[2] = 0 h(Лев)=2KEY[3] =Жанна NEXT[3] =](/img/thumbs/be34fcb5138324bd8fb6bb562099a28e-800x.jpg "Проблема поиска в больших информационных массивах KEY[1] = Ольга Алексеевна NEXT[1] = 0 h(Ольга)=3KEY[2] = Лев NEXT[2]")
Слайд 29Хеширование
Алгоритмы хэширования, или хэш-функции, применяются в схемах электронно-цифровой подписи, в
схемах защиты информации. Например, с их помощью можно вырабатывать ключ
шифрования из пароля. В системах криптографических стандартов России и США содержатся определения алгоритмов хэширования. В России он устанавливается стандартом ГОСТ Р34.11-94 [9], а в США - документами FIPS 180-1 и FIPS 180-2 [10|. Отечественный стандарт хэширования был принят в 1994 году и с тех пор не изменялся, размер хэш-блока для него составляет 256 бит..
Слайд 31Проблемы организации поиска
Книга «Введение в информационный поиск» несет некий элемент
вступления в тему и содержит достаточно глубокий анализ проблем организации
поиска информации. Выпущенная в Cambridge University Press и переведенная издательским домом «Вильямс» для русскоязычного читателя книга, предназначена для пользователей средней и высокой квалификации.
Слайд 32Организация поиска в ИС
Проблема эффективной организации информационного поиска давно занимает
умы практиков и исследователей, но если в последние двадцать лет
эта проблема привлекала внимание пользователей различного рода информационных систем, применяющих глобальные сети для доставки информации, то чуть более полувека назад серьезные исследования проводились специалистами, занятыми автоматизацией библиотечной деятельности.
