автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Модели и методы представления текстового документа в системах информационного поиска

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Губин Максим Вадимович

Модели и методы представления текстового документа в системах информационного поиска

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2005

Работа выполнена на кафедре информатики математико-механического факультета Санкт-Петербургского Государственного Университета.

Научный руководитель: доктор физико-математических наук, профессор Новиков Борис Асенович

Официальные оппоненты:

доктор физико-математических наук, профессор Тузов Виталий Алексеевич кандидат физико-математических наук, доцент Капустин Виктор Андреевич

Ведущая организация: Научно-исследовательский

вычислительный центр Московского государственного университета им. М.В.Ломоносова (НИВЦ МГУ)

Защита диссертации состоится "28_"_апрлеля_2005 года

в 14:00 часов на заседании диссертационного совета Д 212.232.51 по защите диссертаций на соискание ученой степени доктора наук при Санкт-Петербургском государственном университете по адресу 198504, Санкт-Петербург, Старый Петергоф, Университетский пр.,28, Математико-механический факультет.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб. 7/9.

Автореферат разослан " ^Я^Сй._ 2005 года.

Ученый секретарь диссертационного совета

доктор физико-математических наук Б. К. Мартыненко

Общая характеристика работы

Актуальность темы

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

Первые системы, реализующие информационный поиск, были созданы в 1950-е годы. По мере развития информационных систем размеры и количество хранящихся документов постоянно росли. Помимо самого текста, стали хранить параметры его форматирования, гипертекстовые связи между документами и другую информацию. Так, объем первых коллекций конференции TREC, посвященной вопросам информационного поиска, составлял единицы мегабайт, в то время как сейчас используются даже терабайтные коллекции [Наг]. Возрастающие требования к качеству информационного поиска привели к тому, что разработчики систем стали использовать более сложные модели документа, пытаясь максимально использовать имеющееся о нем данные {JWR00, TakOO, AvdWKvBOO, MonOO, Dan92, Kar, VR79, WAW01, FC01, KZ01, SOK94, SAB93, SM97]. Текст стал рассматриваться не просто как набор терминов, а как объект с более сложной структурой, стали анализироваться и учитываться при поиске элементы форматирования текста, его структура. Развитие сети Интернет привело к появлению стандартного представления гипертекста в виде формата HTML, и сделало возможным эффективное использование при поиске анализа связей между документами [ВР98, KHMG03, КВОЗ, HavO2, HenOO, KopOl, WVS+96].

Все развитие современных методов информационного поиска

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

Несмотря на высокое быстродействие современных компьютеров, невозможно обеспечить обработку запроса за приемлемое время для больших коллекций документов без использования специальных индексных структур. Актуальным вопросом является обеспечение заданных параметров эффективности, для чего постоянно предлагаются новые варианты' индексных структур, алгоритмы их построения и использования ^85, BWZ02, KABL96, JamOO, WZA99, ВР98].

Большое внимание современных исследователей привлекает проблема обеспечения компактного представления индексных структур [BWZOla, SWYZ02, BWZOlb, ТгоОЗ, WZ99, SG]. Алгоритмы сжатия позволяют устранить избыточность и достичь заданную эффективность поиска с точки зрения требований к дисковому пространству и быстродействию.

Актуальной является задача поддержки работы с документами, текст которых может меняться в течении времени [KABL96, "УУ94, LWPea]. Это связано с динамическим характером многих коллекций, изменяющихся во времени, таких как Web-страницы, ленты новостей, хранилища систем документооборота.

Цели работы

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

Общая методика

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

которая потом проверялась с помощью эксперимента. Для проверки использовались стандартные тестовые наборы данных РОМИП [гот].

Для анализа индексных структур и алгоритмов использовалась методика, при которой показывалась эквивалентность с заданными допущениями, структурам и алгоритмам, для которых есть общепринятые методы анализа. Результаты в последующем проверялись с помощью экспериментальных исследований.

Основные результаты

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

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

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

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

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

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

6. проведена серия экспериментов по оценке качества поиска системы с использованием собственных методик и методики

Российского семинара по Оценке Методов Информационного Поиска (РОМИП);

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

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

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

Научная новизна

Все основные научные результаты диссертации являются новыми.

Практическая и теоретическая ценность

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

На практике исследованные модели и индексные структуры могут быть использованы для создания различных информационно-поисковых систем.

Апробация работы

Результаты диссертации докладывались на конференциях по электронным библиотекам (RCDL'2002, Дубна, Россия, RCDL'2003, Санкт-Петербург, Россия и RCDL'2005, Пущино, Россия), Российский семинар по оценке методов информационного поиска (РОМИП'2003, Санкт-Петербург, Россия и РОМИП'2004, Пущино, Россия). Рассмотренные модели и методы представления текстового документа в системах информационного поиска были

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

Публикации

Основные результаты диссертации изложены в шести работах [1, 2, 4, 3, 6, 5], перечисленных в конце автореферата.

Структура и объем диссертации

Диссертация состоит из 5 глав со сквозной нумерацией разделов, рисунков и таблиц. Текст диссертации изложен на 95 страницах. Список литературы содержит 68 наименований.

Содержание работы

В первой главе кратко охарактеризован общий контекст исследований. В частности, перечислены и кратко описаны основные задачи информационного поиска. Описываются подходы и методы оценки качества информационного поиска. Формулируются определение модели документа в системе информационного поиска и задачи проведенного исследования.

Во второй главе приводится обзор известных моделей документов в системах информационного поиска. В ней делается вывод, что первая, и самая простая, модель множества слов (bag of words) уступила свое место более сложным, но позволяющим достичь повышения качества информационного поиска.

Наиболее распространенными и известными моделями, дающими большое увеличение качества при относительно малых накладных расходах и простоте реализации являются:

1. документ, как множество весов терминов;

2. документ, как множество фрагментов;

3. документ, как узел гипертекстового графа.

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

положение слов. В данной работе исследовались две модели, которые показались наиболее перспективными:

• выделение „контактных" пар слов;

• модель с разбиением документа, при которой оценка релевантности документа производится с помощью функции, вычисляемой по „скользящему" окну.

Каждая рассматривается как гипотеза, которая в последующем будет экспериментально проверена. В данной главе приведены обоснования выбора и описаны особенности реализации. Формулируются требования к индексной структуре, которая должна использоваться для рассматриваемых моделей. Описывается алгоритм, использующий индексную структуру, и показывается, что результат, полученный с помощью этого алгоритма, совпадает с результатом, полученным при анализе текстов документов без использования индексных структур.

В четвертой главе рассмотрены вопросы выбора и организации индексной структуры, позволяющей эффективно реализовывать модели, рассмотренные в предыдущей главе. Формулируются и в дальнейшем анализируются требования эффективности. Кратко описываются известные в настоящее время индексные структуры и обосновывается выбор инвертированного файла в качестве такой структуры.

Рассматриваются подходы к реализации инвертированного файла и указываются преимущества его реализации с использованием B-f дерева.

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

Формулируется проблема индексирования документов, которые изменяются во времени. Предлагается решение этой проблемы, основанное на допущении, что изменения обычно затрагивают

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

Показывается, что предлагаемая индексная структура имеет характеристики эффективности удовлетворяющие требованиям, сформулированным в данной главе

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

Для оценки качества информационного поиска использовались собственные методики и методики Российского семинара по Оценке Методов Информационного Поиска (РОМИП) На основании этих методик было показано что модель, основанная на „парах счов" не позволяет добиться устойчивого улучшения качества поиска Модель, основанная на использовании „скользящего окна" показала устойчиво хорошие результаты На рисунках 1 и 2 приведены эти результаты в виде 11-точечных графиков точность/полнота, построенных по методике TREC, для коллекций РОМИП

123456789 10 11 Полнота

Рис 1 Результаты web-коллекции

Рис 2 Результаты legal-коллекции

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

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

Литература

[KopOl] Некрестьянов И Корявко А Методы

предварительной обработки данных для алгоритма клейнберга In Труды четвертой всероссийской конференция RCDL'2002, volume 2, pages 215-231, 2001

[AvdWKvBOO] A Arampatzis, T van der Weide, G Koster, and P van Bommel Linguistically motivated information retrieval 69, December 2000 To appear Current-

ly available on-lme from http //www cs kun nl/ avgen-no/encyclopTR ps Z

[BP98] Sergey Bnn and Lawrence Page The anatomy of a large-

scale hypertextual Web search engine Computer Networks and ISDN Systems, 30(1-7) 107-117, 1998

[Buc85] Chris Buckley Implementation of the smart information

retrieval system Technical report, 1985

[BWZOla] D Bahle, H E Williams, and J Zobel Compaction techniques for nextword indexes In Proceedings of the SPIRE Conference on String Processing and Information Retrieval, pages 33-45, San Rafael, Chile, 2001

[BWZOlb] D Bahle, H E Williams, and J Zobel Compaction techniques for nextword indexes, November 2001

[BWZ02] D Bahle, H E Williams, and J Zobel Efficient phrase querying with an auxiliary index In К Jarvelm, M Beauheu, R Baeza-Yates, and S H Myaeng, editors, Proceedings of the ACM-SIGIR Conference on Research and Development m Information Retrieval, pages 215 221, Tampere, Finland, August 2002

fDan92] James A Danowski Wordij A word-pair approach to

information retrieval In TREC, pages 131 136, 1992

[FCOlJ Massimo Melucci Franco Cnvellan Web document re

tneval using passage retrieval, connectivity information, and automatic link weighting In The Tenth Text RE-trteval Conference (TREC 2001), pages 624-633, 2001

[Har] Donna Harman What we have learned, and not learned

from tree In Proc of the BCS IRSG'2000, pages 2-20

[HavO2] T Havehwala Topic-sensitive pagerank In Proceedings

of the Eleventh International World Wide Web Confer ence, 2002

[HenOO] Monika Henzinger. Link analysis in web information

retrieval. IEEE Data Engineering. Bulletin, 23(3) :3~8, 2000.

[JamOO] Allison Powell James. The impact of database selection

on distributed searching. In Proc. of the SIGIR'OO, 2000.

[JWR00] K. Sparck Jones, S. Walker, and S. E. Robertson. A probabilistic model of information retrieval: development and comparative experiments. Inf. Process. Manage., 36(6):779-808, 2000.

[KABL96J T. Koch, A. Ardo, A. Bremmer, and S. Lundberg. The building and maintenance of robot based internet search services: A review of current indexing and data collection methods. Technical report, Lund University Library, Sweden, 1996.

[KarJ Jussi Karlgren. The basics of information retrieval: Sta-

tistics and linguistics.

[KB03] George A. Mihaila Krishna Bharat. Hilltop: A search

engine based on expert documents, http://www.es. toronto. edu/~georgem/hilltop/, 2003.

[KHMG03] 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.

[KZ01] Marcin Kaszkiel and Justin Zobel. Effective ranking with

arbitrary passages. Journal of the American Society of Information Science, 52(4):344-364, 2001.

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

[MonOO] Chnstof Monz Computational semantics and information retrieval In Proceedings of the 2nd Workshop on Inference in Computational Semantics (ICoS-2), pages 1-5, 2000

[rom] Российский Семинар по Оценке Методов

Информационного Поиска http://romip.narod.ru

[SAB93J G Salton, J Allan and С Buckley Approaches to Pas-

sage Retrieval in Full Text Information Systems In Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Informa twn Retrieval, pages 49-58 1993

[SG] Satya Mahesh Rachakonda Susan Gauch, Jianymg Wang

A corpus analysis approach for automatic query expansion and its extension to multiple databases

[SM97] M Cutler Y Shih and W Meng Using the structure of

html documents to improve retneval In USENIXsympo siurn on Internet Technologies and Systems (NISTS'97) pages 241 251, 1997

[SOK94J Alan F Srneaton, Ruain O'Donnell, and Fergus Kelledy Indexing structures derived from syntax m TREC-3 System description pages 100-110, 1994

[SWYZ02] F Scholer, H Williams, J Yiannis, and J Zobel Compression of inverted indexes for fast query evaluation, 2002

[TakOOj T Takaki Ntt data Overview of system approach at

trec-8 ad-hoc and question answering In Proc of the 84h Text REtneval Conference, 2000

[ТгоОЗ] Andrew Trotman Compressing inverted files Inf Retr

6(1) 5-19, 2003

[VR79J С. J. Van Rijsbergen. Information Retrieval, 2nd edition.

Butterworths,London, 1979.

[W94] Peter J. Varman and Rakesh M. Verma. Optimal storage

and access to multiversion data, pages 1605-1620, 1994.

[WAW01] Martin Ann Houston W. A. Woods, Stephen Green Paul.

Aggressive morphology and lexical relations for query expansion. Technical report, 2001.

[WVS+96] Ron Weiss, Bienvenido Velez, Mark Sheldon, Chanathip.

Nemprempre, Peter Szilagyi, Andrzey Duda, and David Gilford. HyPursuit: A hierarchical network search engine that exploits content-link hypertext clustering. In Proc. of Seventh ACM Conference on Hypertext, March 1996.

[WZ99] Hugh E. Williams and Justin Zobel. Compressing in-

tegers for fast file access. The Computer Journal, 42(3):193-201, 1999.

[WZA99] H. E. 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.

Работы автора по теме диссертации

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

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

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

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

[5] Губин М.В. Модели и методы представления текстовых документов в системах информационного поиска. Научно-Техническая Информация, 1(12):12-23, 2004.

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

Подписано к печати 18.03.2005. Бумага офсетная. Печать ризографическая. Объем 1 усл. п.л. Тираж 100 экз. Заказ 3401. Отпечатано в ООО "Акрон"с оригинал-макета заказчика. 191186, Санкт-Петербург, ул. Малая Морская, д. 26,тел./факс: 312-6500

OS. /z - 05. /3

Бесплатно

962

? ? ri:

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 показано, что поиск с использованием предлагаемых моделей документов может быть эффективно реализован только с использованием специальных индексных структур.

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

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.