Поиск слов в PDF/ на сайте
Какой алгоритм используется веб-браузерами и программами чтения PDF для поиска определенного слова в огромном текстовом документе? Чтобы уточнить, когда я читаю электронную книгу, нажимаю Ctrl-F и ввожу поисковый термин, он находит подходящие слова довольно быстро. Какой алгоритм используется и какая структура данных используется для хранения всего текста книги / сайта?
1 ответ
Текст, вероятно, является простой строкой, а сам поиск - это, вероятно, KMP или Boyer-Moore. Обычный текст обычно не такой большой, и поисковые запросы в этих случаях выполняются с "человеческой скоростью" (т. Е. Медленно, редко), поэтому индексы используются не часто, за исключением случаев, когда ожидается много поисковых запросов по одному и тому же тексту (как в тексте). базы данных). Например, даже большая книга, такая как Библия короля Джеймса, содержит менее 4 миллионов писем, что в наши дни совсем немного для компьютера. Для больших текстов поиск иногда занимает заметное время.
Для больших текстов (возможно, генома, но обычно их ищут приблизительно, например, с помощью FASTA или BLAST), вы можете использовать индекс FM-индекса или сжатый суффиксный массив (возможен обычный суффиксный массив, но больше, чем исходный текст, поэтому наверное слишком большой).
Для особенно быстрого поиска в тексте нормального размера вы можете использовать, например, массив суффиксов, инвертированный индекс или словарь триграмм.