Модели и методы представления текстового документа в системах информационного поиска тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Губин, Максим Вадимович

• Губин, Максим Вадимович
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Губин, Максим Вадимович

1 Введение

1.1 Задачи информационного поиска.

1.2 Оценка качества информационного поиска.

1.3 Основные вопросы, рассмотренные в данной работе

2 Модели и методы информационного поиска

2.1 Описание моделей представления документа.

2.2 Модель „множество слов" (bag-of-words).

2.2.1 Бинарная модель

2.2.2 Модель с „весами" слов.

2.3 Учет взаимного положения слов.

2.3.1 Формирование многословных терминов.

2.3.2 Разбиение документа на фрагменты.

2.4 Гипертекстовые ссылки между документами.

2.5 Перспективы.

2.6 Выводы.

3 Реализация модели документа

3.1 Использование пар слов.

3.1.1 Обоснование выбора.

3.1.2 Особенности реализации.

3.2 „Скользящее" по тексту окно.

3.2.1 Обоснование выбора.

3.2.2 Реализация информационного поиска с использованием данной модели.

3.2.3 Выбор и обоснование функции взвешивания документа.

3.2.4 Использование индексной информации.

3.3 Выводы.

4 Индексные структуры

4.1 Организация инвертированного файла.

4.2 Сжатие инвертированного файла.

4.2.1 Алгоритмы сжатия инвертированных файлов.

4.2.2 Сжатие пост-листов редко встречающихся слов

4.2.3 Сжатие инвертироваииого файла, построенного на базе В+дерева.

4.3 Эффективность операций с индексными структурами.

4.3.1 Эффективность поиска.

4.3.2 Изменение индекса

4.4 Индексирование многоверсионных документов

4.4.1 Постановка задачи.

4.4.2 Реализация.

4.5 Выводы.

5 Экспериментальная часть

5.1 Использование пар.

5.1.1 Используемые коллекции.

5.1.2 Описание эксперимента.

5.1.3 Результаты эксперимента.

5.2 Использование „скользящего окна".

5.2.1 Данные для эксперимента.

5.2.2 Результаты.

5.3 Сжатие инвертированного файла.

5.3.1 Характеристики коллекций.

5.3.2 Методика исследования статистики слов и пар слов

5.3.3 Размеры словарей.

5.3.4 Исследование характеристик пост-листов

5.3.5 Исследование алгоритма сжатия.

5.4 Индексирование изменяющихся документов.

5.4.1 Использованные коллекции.

5.4.2 Описание эксперимента.

5.5 Выводы по экспериментальной части.

Введение диссертации (часть автореферата) на тему «Модели и методы представления текстового документа в системах информационного поиска»

В течение последних десятилетий наблюдается постоянно ускоряющийся рост объемов текстовой информации, хранящейся в виде электронных документов. Для эффективной работы с ними требуются современные инструменты, важную роль среди которых играют различные средства информационного поиска. Основная цель информационного поиска -помочь пользователю найти информацию, в которой он заинтересован.Система отбирает из всего имеющегося множества информации подмножество, удовлетворяющее пользователя.1.1 Задачи информационного поиска За десятилетия развития технологий в этой области было предложено множество задач информационного поиска. Рассмотрим некоторые, наиболее распространенные: • классический информационный поиск. Пользователь формулирует запрос в виде нескольких слов или фразы и получает список документов. Документ при этом виде поиска обычно определяется как некоторый текст, выделенный его автором(ами) в качестве единого фрагмента. В информационной системе хранится некоторое представление этого текста, используемое при обработке запроса. Запрос представляет собой осмысленную фразу или набор слов, описывающих информационную потребность.Результатом поиска является список документов, которые отобраны системой как потенциально содержащие полезную для пользователя информацию. Этот список, как правило, упорядочен по мере уменьшения некой метрики, которую называют „весом", „степенью похожести" или оценкой вероятности того, что документ удовлетворяет запросу; • автоматическая кластеризация, рубрикация или фильтрация документов. При этом система объединяет документы коллекции в группы, которые содержат схожую информацию. Пользователь ищет информацию, выбирая из относительно небольшого числа кластеров или рубрик. Рубрикация отличается от кластеризации тем, что рубрики, на которые разбиваются документы, заранее задаются пользователем или экспертом, а кластеры формируются системой автоматически при анализе коллекции. Одним из вариантов рубрикации является фильтрация, когда имеется всего две рубрики: документы, соответствующие некоторой информационной потребности, и документы, этой потребности не соответствующие; • Выделение информации из текста (text mining). Система производит анализ текстов документов и формирует выдержку из текста или массив текстовых фрагментов, которые, по оценке системы, содержат интересующую пользователя информацию.Широко распространенными и активно развивающимися вариантами этой задачи в настоящее время являются: автоматическое аннотирование, когда система формирует краткое содержание большого текста; фактографический поиск, когда по названию объекта система возвращает фрагменты с описанием некоторых атрибутов заданного объекта; поиск ответа на вопрос, когда запросом является сформулированный на естественном языке вопрос, а система выдает фрагменты текста, содержащие возможные на него ответы.Это далеко не полный перечень задач, на сегодняшний день постоянно предлагаются и реализуются новые задачи. В последнее время все чаще реализуют смешанные варианты информационного поиска. Например, система автоматически кластеризует документы, которые возвращены как результат классического информационного поиска, или в качестве результата поиска выводится не список документов, а список созданных из текста документов аннотаций.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Губин, Максим Вадимович

5.5 Выводы по экспериментальной части

Из описанных экспериментов можно сделать следующие выводы:

1 использование контактных пар с небольшим расстоянием между словами для информационного поиска приводит к снижению качества информационного поиска. Причиной этого является слишком сильное ограничение, которое приводит к уменьшению количества релевантных документов в выдаче, тем самым снижается полнота и качество поиска. Экспериментальные данные показывают, что для того, чтобы не происходило ухудшение полноты, требуется увеличить расстояние между словами при формировании пар. Устойчивое увеличение качества информационного поиска достигается только при использовании достаточно большого расстояния между словами -10-15 слов. При таком расстоянии количество пар слов становится неприемлемо большим для построения индекса, содержащего все пары.

Невозможность использования специального индекса делает поиск по парам намного менее привлекательным, так как при сканировании или храпении в индексе полной координатной информации можно использовать значительно более сложные алгоритмы выделения и обработки словосочетаний;

2 использование функции взвешивания на основе „скользящего" окна позволяет увеличить качество информационного поиска;

3 в инвертированных файлах, построенных по коллекциям относительно больших документов, основной объем занимают короткие постлисты. Из-за этого алгоритмы, основанные на сжатии каждого из них отдельно, не могут дать необходимого коэффициента сжатия. Предложенный алгоритм совместного сжатия коротких пост-листов позволяет уменьшить объем памяти, требуемый для пост-листов, почти в два раза;

4 реализация инвертированного файла, когда листы вхождения слов содержат позиции в текстах относительно специальных отметок, устойчивых к изменениям версий, позволяют значительно уменьшить объем изменяемой индексной информации при создании новой версии текста документа. Эксперименты показали, что в этом случае лучшим является формирование отметок с использованием хэш-функции от скользящего по тексту окна.

Заключение

В рабоге получены следующие основные результаты:

1 разработан вариант реализации функции взвешивания документов при информационном поиске, учитывающий взаимное положение слов, который позволил значительно увеличить качество информационного поиска;

2 предложена оригинальная реализация индексных структур, позволяющая эффективно выполнять информационный поиск с использованием описанных моделей, учитывающих взаимное положение слов;

3 разработан новый алгоритм сжатия индексной информации, позволяющий уменьшить ее объем и ускорить обработку запросов за счет уменьшения количества операций ввода-вывода;

4 предложен оригинальный алгоритм разбиения документа при индексации, который минимизирует изменение индекса при создании новой редакции документа;

5 реализован прототип системы, осуществляющий информационный поиск с использованием описываемых моделей документов;

6 проведена серия экспериментов по оценке качества поиска системы с использованием собственных методик и методики Российского семинара по Оценке Методов Информационного Поиска (РОМИП);

7 проведена серия экспериментов по оценке эффективности сжатия индексной информации и обьемам изменения индекса при создании новых редакций документов;

8 показано, что использование при информационном поиске моделей документа, учитывающих взаимное положение слов, улучшает качество поиска;

9 показано, что поиск с использованием предлагаемых моделей документов может быть эффективно реализован только с использованием специальных индексных структур.

Предложенные алгоритмы и полученные результаты использованы при разработке информационно-поисковой системы „Кодекс".

Список литературы диссертационного исследования кандидат физико-математических наук Губин, Максим Вадимович, 2005 год

1. Яндекс: Директ. http://direct .yandex.ru/.

2. Российский Семинар по Оценке Методов Информационного Поиска, http://romip.narod.ru.

3. Некрестьянов И. Корявко А. МЕТОДЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ ДЛЯ АЛГОРИТМА КЛЕЙНБЕРГА. In Труды четвертой всероссийской конференция RCDL'2002, volume 2, pages 215-231, 2001.

4. Автоматическое определение кодировки текста. Иван Рощин. Радиомир. Ваш компьютер, (5,6), 2002.

5. Некрестьянов И.С. Кураленок И.Е. Оценка систем текстового поиска. Программирование, 28:226-242, 2002.

6. Google buys new algorithm, http://www.search-marketing.info/ newsletter/articles/google-continued.htm.

7. Google: Welcome to adwords. http://adwords.google.com.

8. Яш1ех: Детальное описание языка запросов, http://www.yandex. ru/yadetail.html.

9. Unicode home page, http://www.unicode.org.

10. Губин M.B. Изучение статистики встречаемости терминов и пар терминов в текстах для выбора методов сжатия инвертированного файла. In Труды RCDL-2002, volume 2, pages 26-38, 2002.

11. Губин M.B. Исследование качества информационного поиска с использованием пар слов. In Труды RCDL-2003, pages 186-191, 2003.

12. Б.П. Кобрицов. МОРФОЛОГИЯ И СИНТАКСИС В ПРОЕКТЕ "РУССКИЙ СТАНДАРТ" (СОЗДАНИЕ КОРПУСА ГРАММАТИЧЕСКИ РАЗМЕЧЕННЫХ РУССКИХ ТЕКСТОВ). In Статьи международной конференции Диалог'2003, 2003.

13. Губин М.В. Опыт участия ИС „Кодекс" в РОМИП 2003. In Труды РОМИП'2003, pages 31-42, 2003.

14. Губин М.В. Электронная библиотека многоверсионных текстовых документов. In Труды RCDL-2004, pages 169-174, 2004.

15. Губин М.В. Участие ИПС „Кодекс" в семинаре РОМИП 2004. In Труды РОМИП'2004, pages 28-39, 2004.

16. Adobe solutions network | adobe pdf specifications, http: //partners. adobe.com/asn/tech/pdf/specifications.jsp, 2000.

17. Rakesh Agrawal and Ramakrishnan Srikant. Searching with numbers. In Proceedings of the eleventh international conference on World Wide Web, pages 420-431. ACM Press, 2002.

18. Akiko Aizawa. The feature quantity: an information theoretic perspective of tfidf-like measures. In Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, pages 104-111. ACM Press, 2000.

19. Grigori Sidorov Alexander Gelbukh. Zipf and heaps laws' coefficients depend on language. In Proceeding of Conference on Intelligent Text Processing and Computational Linguistics (CICLing'2001), pages 332335, 2001.

20. A. Arampatzis, T. van der Weide, C. Koster, and P. van Bommel. Linguistically motivated information retrieval. 69, December 2000. To appear. Currently available on-line from http://www.cs.kun.nl/ avgeri-no/encyclopTR.ps.Z.

21. Chris Buckley. Implementation of the smart information retrieval system. Technical report, 1985.

22. Abdur Chowdhury and M. Catherine McCabe. Improving information retrieval systems using part of speech tagging. Technical Report TR 1998-48, 1998.

23. James A. Danowski. Wordij: A word-pair approach to information retrieval. In TREC, pages 131-136, 1992.

24. G. Dias, S. Guillore, J-C. Bassano, and J.G. Pereira Lopes. Combining linguistics with statistics for multiword term extraction: A fruitful association? In Proc. of Recherche d'Informations Assistee par Ordinateur 2000 (RIAO'2000), 2000.

25. Massimo Melucci Franco Crivellari. Web document retrieval using passage retrieval, connectivity information, and automatic link weighting. In The Tenth Text REtrieval Conference (TREC 2001), pages 624-633, 2001.

26. Donna Harman. What we have learned, and not learned, from tree. In Proc. of the BCS IRSG'2000, pages 2-20.

27. T. Haveliwala. Topic-sensitive pagerank. In Proceedings of the Eleventh International World Wide Web Conference, 2002.

28. Monika Henzinger. Link analysis in web information retrieval. IEEE Data Engineering. Bulletin, 23(3):3-8, 2000.

29. David A. Hull. Stemming algorithms: A ease study for detailed evaluation. Journal of the American Society of Information Science, 47(1):70-84, 1996.

30. Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, and Gene H. Golub. Extrapolation methods for accelerating pagerank computations. In Proceedings of the twelfth international conference on World Wide Web, pages 261-270. ACM Press, 2003.

31. Marcin Kaszkiel and Justin Zobel. Effective ranking with arbitrary passages. Journal of the American Society of Information Science, 52(4):344-364, 2001.

32. Hideki Kozima. Text segmentation based on similarity between words. In Meeting of the Association for Computational Linguistics, pages 286288, 1993.

33. George A. Mihaila Krishna Bharat. Hilltop: A search engine based on expert documents, http: //www. cs.toronto. edu/~georgem/hilltop/, 2003.

34. Robert Krovetz and W. Bruce Croft. Lexical ambiguity and information retrieval. Information Systems, 10(2):115-141, 1992.

35. Lipyeow Lim, Min Wang, Sriram Padmanabhan, and et al. Dynamic maintenance of web indexes using landmarks.

36. J.B. Lovins. Development of a stemming algorithm. Mechanical Translation and Computation, (ll(l-2)):22—31, 1968.

37. M.L. Mauldin. Lycos: Design choices in an internet search service. Technical report, 1997.

38. M.F.Porter. An algorithm for suffix stripping. Program, (14):130-137, July 1980.

39. Shaoping Ma Min Zhang, Ruihua Song. Df or idf?on the use of html primary feature fields for web ir. In The Twelfth International World Wide Web Conference, 2003.

40. Markus Mittendorfer and Werner Winiwarter. Exploiting syntactic analysis of queries for information retrieval. Data Knowl. Eng., 42(3) :315—325, 2002.

41. Christof Monz. Computational semantics and information retrieval. In Proceedings of the 2nd Workshop on Inference in Computational Semantics (ICoS-2), pages 1-5, 2000.

42. G.B. Newby. Information space baaed on html structure. In Proceedings of TREC9, pages 600-601, 2000.

43. Jay M. Ponte and W. Bruce Croft. Text segmentation by topic. In European Conference on Digital Libraries, pages 113-125, 1997.

44. G. Salton, J. Allan, and C. Buckley. Approaches to Passage Retrieval in Full Text Information Systems. In Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 49-58, 1993.

45. F. Scholer, H. Williams, J. Yiannis, and J. Zobel. Compression of inverted indexes for fast query evaluation, 2002.

46. Katsuhiko Momoi Shanjian Li. A composite approach to language/encoding detection. In Nineteenth International Unicode Conference, 2002. http://www.mozilla.org/projects/intl/ UniversalCharsetDetection.html.

47. M. Cutler Y. Shih and W. Meng. Using the structure of html documents to improve retrieval. In USENIX symposium on Internet Technologies and Systems (NISTS'97'), pages 241-251, 1997.

48. Amit Singhal and Marcin Kaszkiel. A case study in web search using tree algorithms, pages 708-716, 2001.

49. Alan F. Smeaton, Ruairi O'Donnell, and Fergus Kelledy. Indexing structures derived from syntax in TREC-3: System description, pages 100110, 1994.

50. Fei Song and W. Bruce Croft. A general language model for information retrieval (poster abstract). In Research and Development in Information Retrieval, pages 279-280, 1999.

51. T. Takaki. Ntt data: Overview of system approach at trec-8 ad-hoc and question answering. In Proc. of the 8'th Text REtrieval Conference, 2000.

52. Jaines P. Fry Toby J. Teorey. Design of database structures. Prentice-Hall, Inc., Englewood Cliffs, 1982.

53. Andrew Trotman. Compressing inverted files. Inf. Retr., 6(1):5-19, 2003.

54. C. J. Van Rijsbergen. Information Retrieval, 2nd edition. Butter-worths,London, 1979.

55. Ellen M. Voorhees. Natural language processing and information retrieval. In Information Extraction: Towards Scalable, Adaptable Systems, pages 32-48, 1999.

56. Martin Ann Houston W. A. Woods, Stephen Green Paul. Aggressive morphology and lexical relations for query expansion. Technical report, 2001.

57. Н. Е. Williams, J. Zobel, and P. Anderson. What's next? Index structures for efficient phrase querying. In J. Roddick, editor, Proceedings of the Australasian Database Conference, pages 141-152, Auckland, New Zealand, 1999.

58. Hugh E. Williams and Justin Zobel. Compressing integers for fast file access. The Computer Journal, 42(3):193-201, 1999.

59. C. Zhai, X. Tong, N. Milic-Frayling, and D. Evans. Evaluation of syntactic phrase indexing clarit nip track report. In The Fifth Text Retrieval Conference (TREC-5). NIST Special Publication, 1997.

60. Justin Zobel. How reliable are the results of large-scale information retrieval experiments? In Research and Development in Information Retrieval, pages 307-314, 1998.

61. Justin Zobel, Alistair Moffat, Ross Wilkinson, and Ron Sacks-Davis. Efficient retrieval of partial documents. In Proceedings of the second conference on Text retrieval conference, pages 361-377. Pergamon Press, Inc., 1995.