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

Question

Какая структура данных или алгоритм используются в браузерах для поиска слова? Будут ли браузеры строить дерево trie или суффикс?

Спасибо
Bala

Answer 1

Поиск по дереву trie/suffix выполняется быстро, но построение trie для начала происходит значительно медленнее. Это означает, что они имеют смысл только тогда, когда ожидают для выполнения большого количества поисков по тем же данным, поэтому вы можете амортизировать время для создания trie для многих поисков.

Среднее количество поисковых запросов внутри веб-страницы, вероятно, является дробным (т. Е. Вы ожидаете, что пользователь загрузит несколько страниц, прежде чем выполнять поиск даже один раз). Даже если вы просматриваете страницу, выполнение большого количества запросов на одной странице, вероятно, довольно редко.

Это означает, что линейный поиск почти всегда будет по существу более эффективен в целом, чем дерево trie или суффикс. Я предполагаю, что если они потрудились оптимизировать его за простым обращением к strstr(), то они только доходят до чего-то в семействе поисковых запросов Boyer-Moore. Учитывая количество поисков, которые вы ожидаете на веб-странице, обычно это закончите их всех, прежде чем вы сможете просто сделать первоначальную сборку trie, чтобы вы могли начать, ища с ней.

Для интерактивного использования вашей основной задачей является получение результатов достаточно быстро, чтобы они выглядели мгновенно. Это обычно означает результаты в пределах 100 мс или около того. С хорошей реализацией Boyer-Moore-Horspool достаточно времени для поиска текста, который был бы безумным, чтобы включить его в одну веб-страницу (порядка сотен мегабайт или гигабайт).

Если вы хотите проверить это, я бы порекомендовал реализацию Рея Гарднера Boyer-Moore-Horspool (Bmhsrch.C, с сайта 8) Боба Стаута). Я бы действительно ненавидел, чтобы увидеть веб-страницу достаточно большую, чтобы она занимала даже 20 мс, не говоря уже о 100 (хотя я первый, кто признал, что эта конкретная реализация исключительно быстро).

Answer 2

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

В целом, я не думаю, что это одна из больших проблем в алгоритмах браузера.

Answer 3

Чтобы понять, почему линейное сканирование достаточно быстро, рассмотрите, насколько более сложный рендеринг страницы (что, очевидно, требует, по крайней мере, линейного сканирования HTML) и как быстро это делается. Я думаю, что браузер будет тратить гораздо больше времени, выделяя случаи, чем искать их, так или иначе.

Кроме того, поиск может быть выполнен поэтапно. Скажем, я ищу «алгоритм». Когда я набираю «a», браузер может найти (или асинхронно начать поиск) вхождения буквы «a», а последующие символы только уточняют текущие выводы.

Answer 4

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