Применение трехкомпонентных ключей для полнотекстового поиска с учетом расстояния с гарантированным временем отклика
Автор: Веретенников Александр Борисович
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 1 т.7, 2018 года.
Бесплатный доступ
Рассматриваются задачи поиска фраз и наборов слов в большом объеме текстов. В результате поиска получаем список документов, содержащих заданные слова, при этом документы, где слова располагаются ближе друг к другу, считаются более релевантными. Поскольку эта задача требует сохранения в индексе информации о каждом вхождении каждого слова в текстах, запросы, включающие часто встречающиеся слова, требуют для своего выполнения длительного времени. В некоторых поисковых системах предлагается ввести список стоп слов, которые не учитываются при поиске, но этот подход снижает качество поиска. В данной работе при поиске обрабатываются все слова и применяются дополнительные индексы. С помощью дополнительных индексов время выполнения поискового запроса, включающего часто встречающиеся слова, может быть снижено в десятки раз. Разработан новый вид индекса с трехкомпонентными ключами. Приведены алгоритмы поиска и результаты экспериментов поиска в сравнении с обычными индексами. Эксперименты показывают, что при применении разработанных индексов для определенного класса запросов, состоящих из самых часто встречающихся слов, скорость поиска возрастает более чем в 90 раз.
Полнотекстовый поиск, поисковые системы, инвертированные файлы, дополнительные индексы, поиск с учетом близости слов
Короткий адрес: https://sciup.org/147160640
IDR: 147160640 | DOI: 10.14529/cmse180105
Список литературы Применение трехкомпонентных ключей для полнотекстового поиска с учетом расстояния с гарантированным временем отклика
- Miller R.B. Response Time in Man-Computer Conversational Transactions//Proceedings: AFIPS Fall Joint Computer Conference. San Francisco, California, December 09-11, 1968. Vol. 33. P. 267-277 DOI: 10.1145/1476589.1476628
- Zobel J., Moffat A. Inverted Files for Text Search Engines//ACM Computing Surveys, 2006. Vol. 38, No. 2. Article 6 DOI: 10.1145/1132956.1132959
- Tomasic A., Garcia-Molina H., Shoens K. Incremental Updates of Inverted Lists for Text Document Retrieval//SIGMOD ’94 Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. Minneapolis, Minnesota, May 24-27 1994. P. 289-300 DOI: 10.1145/191839.191896
- Brown E.W., Callan J.P., Croft W.B. Fast Incremental Indexing for Full-Text Information Retrieval//VLDB ’94 Proceedings of the 20th International Conference on Very Large Data Bases. Santiago de Chile, Chile, September 12-15, 1994. P. 192-202.
- Zipf G. Relative Frequency as a Determinant of Phonetic Change//Harvard Studies in Classical Philology. 1929. Vol. 40. P. 1-95 DOI: 10.2307/408772
- Williams H.E., Zobel J., Bahle D. Fast Phrase Querying with Combined Indexes//ACM Transactions on Information Systems (TOIS). 2004. Vol. 22, No. 4. P. 573-594 DOI: 10.1145/1028099.1028102
- Bahle D., Williams H.E., Zobel J. Efficient Phrase Querying with an Auxiliary Index//SIGIR ’02 Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Tampere, Finland, August 11-15, 2002, P. 215-221 DOI: 10.1145/564376.564415
- Anh V.N., Moffat A. Pruned Query Evaluation Using Pre-computed Impacts//SIGIR ’06 Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Seattle, Washington, USA, August 06-11, 2006. P. 372-379. ACM Press DOI: 10.1145/1148170.1148235
- Anh V.N., de Kretser O., Moffat A. Vector-Space Ranking with Effective Early Termination//SIGIR ’01 Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New Orleans, Louisiana, USA, September 9-12, 2001. P. 35-42 DOI: 10.1145/383952.383957
- Garcia S, Williams H.E., Cannane A. Access-Ordered Indexes//ACSC ’04 Proceedings of the 27th Australasian Conference on Computer Science. Dunedin, New Zealand, January 18-22, 2004. P. 7-14.
- Yan H., Shi S., Zhang F., Suel T., Wen J.-R. Efficient Term Proximity Search with Term-Pair Indexes//CIKM ’10 Proceedings of the 19th ACM International Conference on Information and Knowledge Management. Toronto, ON, Canada, October 26-30, 2010. P. 1229-1238 DOI: 10.1145/1871437.1871593
- Веретенников А.Б. Использование дополнительных индексов для более быстрого полнотекстового поиска фраз, включающих часто встречающиеся слова//Системы управления и информационные технологии. 2013. № 2(52). С. 61-66.
- Веретенников А.Б. Эффективный полнотекстовый поиск с использованием дополнительных индексов часто встречающихся слов//Системы управления и информационные технологии. 2016. № 4(66). С. 52-60.
- Williams J.W.J. Algorithm 232 -Heapsort//Communications of the ACM. 1964. Vol. 7, No. 6. P. 347-348.
- Schenkel R., Broschart A., Hwang S., Theobald M., Weikum G. Efficient Text Proximity Search//String Processing and Information Retrieval. 14th International Symposium. SPIRE 2007. Lecture Notes in Computer Science. Santiago de Chile, Chile, October 29-31, 2007. Vol. 4726. Springer, Berlin, Heidelberg. P. 287-299 DOI: 10.1007/978-3-540-75530-2_26
