Скрыть
Раскрыть

ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

English version: ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Фролов Д. С. 1
  • 1 НИУ ВШЭ, 101000, Россия, Москва, ул. Мясницкая, д.20

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

2015. № 4 (34). С. 63–70 [содержание номера]

Фролов Дмитрий Сергеевич - аспирант, департамент анализа данных и искусственного интеллекта, Национальный исследовательский университет «Высшая школа экономики» 
Адрес: 101000, г. Москва, ул. Мясницкая, д. 20.
E-mail: dfrolov@hse.ru, dmitsf@gmail.com
     
      В работе представлен метод информационного поиска в коллекциях текстовых документов, основанный на аннотированных суффиксных деревьях (АСД). В методе используется определение степени вхождения строки в АСД, полученные для документов, а также обратный индекс, построенный по фрагментам документов (с целью улучшения производительности). На основе представленного метода реализована поисковая система и произведено ее сравнение с алгоритмами поиска, использующими другие способы агрегированного представления текстов (всей коллекции целиком) – вероятностным латентно-семантическим индексированием (PLSI) и скрытым размещением Дирихле (LDA).
      Для проведения вычислительных экспериментов использованы реальные данные: коллекция xml-каталогов онлайн-магазина и коллекция веб-страниц (обе – на русском языке), а также пользовательские поисковые запросы, полученные с помощью сервиса Yandex.Wordstat. Исследованы качественные метрики рассматриваемых систем: получены точечные оценки и графические характеристики. Метод поиска, основанный на АСД, в целом показывает результаты, сравнимые с другими алгоритмами, однако, на неточных запросах существенно превосходит их. Была исследована производительность сравниваемых поисковых систем, в результате отмечено, что метод на основе АСД несколько уступает другим по скорости поиска. Также изучена зависимость между временем выполнения запроса и длиной строк текста, используемых для построения АСД: для улучшения производительности необходимо выбирать минимально возможную длину строк, принимая во внимание тот факт, что слишком короткие строки могут ухудшить качественные характеристики метода. Отдельно отмечен факт применимости метода на основе АСД к задачам нечеткого поиска, что должно стать предметом будущих исследований.

Библиографическое описание: Frolov D.S. Annotated suffix tree as a way of text representation for information retrieval in text collections //Business Informatics. 2015. No. 4 (34). P. 63–70. DOI: 10.17323/1998-0663.2015.4.63.70.
BiBTeX
RIS
 
 
Rambler's Top100 rss