Алгоритм используется браузером для поиска слов на веб-странице
Какая структура данных или алгоритм используются в браузерах для поиска слова? Браузеры создадут trie или суффиксное дерево?
Спасибо
Бала
4 ответа
Поиск с помощью дерева тройки/суффикса быстр - но построение тройки для начала значительно медленнее. Это означает, что они имеют смысл только тогда, когда вы ожидаете провести большое количество поисков по одним и тем же данным, чтобы амортизировать время на построение тройки в течение многих поисков.
Среднее количество поисков на веб-странице, вероятно, будет дробным (т.е. вы ожидаете, что пользователь загрузит несколько страниц, прежде чем выполнить поиск хотя бы один раз). Даже когда вы выполняете поиск на странице, много поисков на одной странице, вероятно, довольно редки.
Это означает, что линейный поиск почти всегда будет существенно эффективнее , чем трие или суффиксное дерево. Я полагаю, что если они потрудятся оптимизировать его сверх простого вызова strstr(), то они дойдут только до чего-то из семейства Бойера-Мура для поиска строк. Учитывая количество поисковых запросов, ожидаемых на веб-странице, это обычно завершит их все раньше, чем вы сможете просто выполнить начальное построение тройки, чтобы начать поиск с ее помощью.
Для интерактивного использования вашей главной задачей является получение результатов достаточно быстро, чтобы они казались мгновенными. Обычно это означает получение результатов в течение 100 мс или около того. При хорошей реализации Boyer-Moore-Horspool этого времени достаточно для поиска в объеме текста, который было бы безумием включать в одну веб-страницу (порядка сотен мегабайт или гигабайт).
Если вы хотите проверить это на практике, я рекомендую реализацию Boyer-Moore-Horspool (Bmhsrch.C, с сайта Snippets Боба Стаута) Рэя Гарднера. Мне бы очень не хотелось увидеть веб-страницу достаточно большого размера, чтобы она продержалась даже 20 мс, не говоря уже о 100 (хотя я первый признаю, что эта конкретная реализация исключительно быстрая).
Чтобы понять, почему линейное сканирование достаточно быстрое, подумайте, насколько сложнее рендеринг страницы (что, очевидно, требует как минимум линейного сканирования HTML) и как быстро это делается. Я думаю, что браузер в любом случае будет тратить гораздо больше времени на выделение событий, чем на их поиск.
Кроме того, поиск может выполняться постепенно. Скажем, я ищу "алгоритм". Когда я набираю «а», браузер может найти (или начать поиск в асинхронном режиме) вхождения буквы «а» и последующих символов только для уточнения текущих результатов.
Простого использования регулярных выражений более чем достаточно. Взгляните на различные онлайн-инструменты.
Веб-страницы обычно недостаточно велики, чтобы нуждаться в сложных алгоритмах поиска, по крайней мере, при первом сканировании. Я имею в виду, что вы, вероятно, можете найти любое слово с помощью простого линейного поиска всего за несколько мс. Оптимизация может заключаться в том, чтобы построить трие во время первого сканирования, а затем использовать его для последующих поисков.
В целом, я не думаю, что это одна из больших проблем в алгоритмах браузера.