Информационно-поисковые системы. Сычев А.В. 2006 г. 1 Алгоритмы документального поиска Воронежский государственный университет Факультет компьютерных наук. - презентация

1 Информационно-поисковые системы. Сычев А.В г. 1 Алгоритмы документального поиска Воронежский государственный университет Факультет компьютерных наук Кафедра информационных систем

2 Информационно-поисковые системы. Сычев А.В г. 2 Алгоритмы документального поиска Полнотекстовое сканирование Файлы сигнатур Инверсия Кластеризация Обработка естественного языка (NLP) Латентно-семантическое индексирование (LSI)

3 Информационно-поисковые системы. Сычев А.В г. 3 Полнотекстовое сканирование Заключается в поиске всех документов, содержащих искомую строку, представляющую собой последовательность символов. В случае запросов, содержащих булевское выражение из нескольких строк, требуется дополнительная проверка терминов, найденных при поиске строк, на соответствие булевскому выражению.

4 Информационно-поисковые системы. Сычев А.В г. 4 Полнотекстовое сканирование Простейший вариант алгоритма включается в себя шаги: Посимвольное сравнение искомой строки с соответствующими символами документа. В случае несовпадения выполняется сдвиг искомой строки относительно документа вправо на одну позицию Цикл повторяется до тех пор пока либо не будет найдена в какой-либо позиции документа искомая строка, либо не будет достигнут конец документа. При всей простоте данный вариант алгоритма является очень медленным. Количество необходимых операций сравнения составляет O (m*n), где m – длина искомой строки, а n – размер документа (длина документа в символах).

5 Информационно-поисковые системы. Сычев А.В г. 5 Полнотекстовое сканирование Имеются также более быстрые алгоритмы, для которых требуется выполнить O(m+n) сравнений и дополнительно необходимо затратить O(m) операций на предобработку искомой строки.

6 Информационно-поисковые системы. Сычев А.В г. 6 Полнотекстовое сканирование Достоинства: Минимальные затраты памяти и легкость выполнения вставок и удалений Недостатки: неудовлетворительное время отклика особенно при работе с большими массивами документов. Однако может вполне эффективно работать на специализированном оборудовании или в сочетании с другими методами доступа (например с инверсией), ограничивающими область поиска.

7 Информационно-поисковые системы. Сычев А.В г. 7 Файлы сигнатур Идея: Все термины документа представляются в виде битовых последовательностей, полученных в резльтате применения хэш-функции к исходным строкам-терминам. Сигнатуры документов размещаются последовательно в отдельном файле – файле сигнатур. Данный подход позволяет уменьшить исходный размер файла и ускорить поиск. Вариант метода: Файл сигнатур хранится в транспонированном виде, что позволяет сократить число операций чтения записей с диска.

8 Информационно-поисковые системы. Сычев А.В г. 8 Путем применения применения хэш-функции к слову получается целое число в интервале от 1 до 16. После применения 3-х хэш-функций получается 3 числа, указывающие номера позиций в 16-битовом идентификаторе, которые будут установлены. Например, если для слова сеть были получены значения 2, 7, 13, то его сигнатура будет выглядеть как При соответствующем подборе хэш-функций вероятность совпадения сигнатур у разных слов (коллизия) очень мала. Сигнатуры слов

9 Информационно-поисковые системы. Сычев А.В г. 9 Для построения сигнатуры документа используется суперпозиция сигнатур слов, входящих в документ, например логическая операция ИЛИ. Для проверки вхождения слова в документ сначала вычисляется сигнатура слова. Затем, если соответствующие биты в установлены в сигнатуре документа, то велика вероятность того, что документ содержит искомое слово. Сигнатуры документов

10 Информационно-поисковые системы. Сычев А.В г. 10 Ложные совпадения Для сокращения вероятности ложного совпадения необходимо увеличивать разрядность сигнатуры. Эффективность увеличивается для многословных запросов (уменьшается вероятность ложных совпадений)

11 Информационно-поисковые системы. Сычев А.В г. 11 Файлы сигнатур Достоинства: простота реализации, легкость управления вставками, подходит для работы с большими коллекциями документов (легкость масштабирования), возможности для распараллеливания. Недостатки: увеличение времени реакции системы на запрос при большом размере файла.

12 Информационно-поисковые системы. Сычев А.В г. 12 Инверсия Идея: каждый документ представляется списком терминов, которые хранятся упорядоченными в алфавитном порядке в индексном файле. Для каждого термина в данном файле имеется указатель на список содержащих его документов. Для ускорения поиска при организации индексного файла используются B-деревья, хэширование и другие подходы.

13 Информационно-поисковые системы. Сычев А.В г. 13 Состоит из 2-х частей: ­ Словарь. Содержит множество всех индексируемых единиц в данной коллекции. ­ Инвертированный файл. Совокупность списков, каждый элемент которого указывает на текст, содержащий индексируемую единицу, и соответствующую статистическую информацию. Можно представить себе как транспонированную матрицу документ-термин. Инвертированая индексная структура

14 Информационно-поисковые системы. Сычев А.В г. 14 Инверсия Достоинства: относительная простота реализации, высокая скорость работы, поддержка работы с синонимами Недостатки: превышения размера инверсного файла над размером исходного (хотя возможно применения сжатия списков), сложность обновления и реорганизации индекса.

15 Информационно-поисковые системы. Сычев А.В г. 15 Кластеризация В основой методов кластеризации является кластерная гипотеза (C.J. van Rijsbergen), которая гласит: Тесно связанные между собой документы оказываются релевантными по отношению к тем же запросам. Кластеризация может быть использована для распределения документов в коллекции по классам (автоматической классификации), что позволяет повысить скорость поиска документов и точность ответа. Кроме того, кластеризация может использоваться для улучшения представления результатов поиска на основе приведенных ранее алгоритмов. Кластеризация включает в себя две процедуры: генерацию кластеров и поиск кластеров по запросу пользователя. Инвертированный список можно рассматривать как одну из форм кластеризации документов.

16 Информационно-поисковые системы. Сычев А.В г. 16 Поиск кластера Входной запрос представляется в виде t- мерного вектора и сравнивается с центроидами кластеров. Поиск продолжается в кластерах степень подобия для которых превысила заданный порог. Для вычисления степени подобия часто используется косинусная метрика.

17 Информационно-поисковые системы. Сычев А.В г. 17 Использование семантической информации Методы основанные на использовании грамматического анализа, семантической информации и NLP(natural language processing) в общем. Латентно-семантическое индексирование. Методы, использующие нейронные сети.

18 Информационно-поисковые системы. Сычев А.В г. 18 Обработка естественного языка (NLP) Идея заключается в повышении эффективности путем сопоставления семантического содержания запросов семантическому содержанию документов. Вместо терминов могут использоваться целые фразы Расширяется поиск за счет привлечения близких терминов/понятий Возможность использования контролируемого словаря.

19 Информационно-поисковые системы. Сычев А.В г. 19 Общая структура NLP Морфологическая и лексическая обработка Синтаксический анализ Семантический анализ Обработка контекста. Интерпретация

20 Информационно-поисковые системы. Сычев А.В г. 20 Несмотря на интуитивное ожидание улучшения в описании документов существенного улучшения в производительности продемонстрировано не было. На самом деле, нет четкой границы между NLP и поверхностными методами информационного поиска. Например, стоп-списки терминов отфильтровывают слова с низким семантическим содержанием. Конечно, NLP лучше выражает сементическое содержание, но возможное увеличение специфичности может понизить эффективность ранжирования или поиска документов. Обработка естественного языка (NLP)

21 Информационно-поисковые системы. Сычев А.В г. 21 Латентно-семантическое индексирование (LSI) Актуальность: Термины, содержащиеся в запросе часто не совпадают с теми, что используются авторами документов по интересующей тематике. Широко распространенные в естественных языках явления синонимии, омонимии и полисемии.

22 Информационно-поисковые системы. Сычев А.В г. 22 Является реализацией двухмодового факторного анализа, позволяющего выявлять значения/модели лежащие в основе больших массивов наблюдаемых данных Термины и документы представляются в виде векторов в пространстве выбираемой размерности k. Временная сложность реализующих алгоритмов равна O(N 2 *k 3 ). Латентно-семантическое индексирование (LSI)

23 Информационно-поисковые системы. Сычев А.В г. 23 Исходной является матрица X сопряженности типа термин-документ. К ней применяется SVD-декомпозиция, при которой устраняются малые сингулярные величины, тем самым сокращается размерность пространства до первых главных компонентов ( факторов). Латентно-семантическое индексирование (LSI)

24 Информационно-поисковые системы. Сычев А.В г. 24 Латентно-семантическое индексирование (LSI) XT0T0 S0S0 DoTDoT = xx XT SDTDT = x x

25 Информационно-поисковые системы. Сычев А.В г. 25 c1: Human machine interface for ABC computer applications c2: A survey of user opinion of computer system response time c3: The EPS user interface management system c4: System and human system engineering testing of EPS c5: Relation of user-perceived response time to error measurement m1: The generation of random, binary, ordered trees m2: The intersection graph of paths in trees m3: Graph minors IV: Widths of trees and well-quasi-ordering m4: Graph minors: A survey Латентно-семантическое индексирование (LSI)

26 Информационно-поисковые системы. Сычев А.В г. 26 Латентно-семантическое индексирование (LSI) r (human, user) = -0.38

27 Информационно-поисковые системы. Сычев А.В г. 27 Латентно-семантическое индексирование (LSI) k = 2

28 Информационно-поисковые системы. Сычев А.В г. 28 Латентно-семантическое индексирование (LSI) r (human, user) = 0.94

29 Информационно-поисковые системы. Сычев А.В г. 29 При устранении малых сингулярных значений из S 0 удается редуцировать пространство характеристик документа вконцептуальное документальное пространство. При этом устраняетсяшум, возникающий вследствие вариации в употреблении терминов. Латентно-семантическое индексирование (LSI)

30 Информационно-поисковые системы. Сычев А.В г. 30 Литература 1.C.Faloutsos, D.OardA survey of Information Retrieval and Filtering Methods. Technical Report, University of Maryland Computer Science Dept., College Park, MD.C.Faloutsos, D.OardA survey of Information Retrieval and Filtering Methods. Technical Report, University of Maryland Computer Science Dept., College Park, MD 2.J.Zobel, R.A.Moffat, K.Ramamohanarao. Inverted Files Versus Signature Files for Text Indexing - ACM Transactions on Database Systems, Vol. 23, No. 4, December 1998, Pages 453–490.J.Zobel, R.A.Moffat, K.Ramamohanarao. Inverted Files Versus Signature Files for Text Indexing - ACM Transactions on Database Systems, Vol. 23, No. 4, December 1998, Pages 453– S. Chakrabarti Mining the Web. Discovering Knowledge from Hypertext Data. Morgan Kaufmann Publishers, 2003.S. Chakrabarti Mining the Web. Discovering Knowledge from Hypertext Data. Morgan Kaufmann Publishers, D.Lewis, K. Sparck JonesNatural Language Processing for Information Retrieval. Communications of the ACM, 39(1) Jan D.Lewis, K. Sparck JonesNatural Language Processing for Information Retrieval. Communications of the ACM, 39(1) Jan S.Deerwester,S.T.Dumais,G.W.Furnas,T.K.Landauer,R.HarshmanIndexing by Latent Semantic Indexing. JASIS, 1990.S.Deerwester,S.T.Dumais,G.W.Furnas,T.K.Landauer,R.Harshman Indexing by Latent Semantic Indexing. JASIS, 1990