Эта статья написанаyanglbmeОригинал, впервые опубликованный в публичном аккаунте"Сообщество открытого исходного кода Doocs", несанкционированное воспроизведение запрещено.
Сила автоматического завершения поиска Google, я думаю, многие друзья могут это почувствовать, это помогает нам быстрее «завершать» поисковые ключевые слова, которые мы хотим ввести. Так как же он узнает, что мы собираемся напечатать? Как это работает? В этой статье давайте посмотрим.
Использовать автозаполнение
Автозаполнение поиска Google доступно в большинстве мест приложения Google Search, в том числеGoogleДомашняя страница, приложение Google для IOS и Android, нам просто нужно начать вводить ключевое слово в поле поиска Google, и мы увидим связанные слова.
В приведенном выше примере мы видим, что ввод ключевого словаjuej, поиск Google будет ассоциировать «Наггетс», «Буклет Наггетс», «Предложения Quatan» и т. д. Преимущество состоит в том, что мы можем легко выполнить поиск по этим темам, не вводя полное ключевое слово.
Функция автозаполнения Поиска Google особенно полезна для пользователей мобильных устройств, где пользователи могут легко выполнять поиск на маленьких экранах, которые трудно набирать. Конечно, это огромная экономия времени как для мобильных, так и для настольных пользователей. Согласно официальному отчету Google, автозаполнение может сократить ввод текста примерно на 25%, и в совокупности ожидается, что он сэкономит более 200 часов набора текста в день. Да, каждый день!
Обратите внимание, что "ассоциативное слово"и"предсказывать", что означает одно и то же.
Основано на "предсказаниях", а не на "предложениях"
Google официально называет автозаполнение «прогнозом», а не «предложением», почему? На самом деле есть веская причина. автозаполнение дляПомогите пользователям выполнить намеченный поиск, а не предлагать, какой поиск должен выполнить пользователь.
Так как же Google определяет эти «прогнозы»? На самом деле, Google будет искать на основе тенденцийtrendsДайте нам эти "предсказания". Проще говоря, тот, который популярен и имеет высокую частоту поиска, с большей вероятностью попадет к нам. Конечно, это также имеет отношение к тому, где мы находимся в настоящее время, и к нашей истории поиска.
Кроме того, эти «предсказания» меняются по мере изменения вводимых нами ключевых слов. Например, когда мы помещаем типизированное ключевое слово изjuejизменить наjuex, предсказания, связанные с «Наггетсами», «исчезнут», и в то же время появятся слова, связанные с «пробуждением» и «решимостью».
Почему мы не можем видеть некоторые ассоциативные слова?
Если мы не видим ассоциативного слова при вводе ключевого слова, это означает, что алгоритм Google мог обнаружить:
- Это ключевое слово не является популярным словом;
- Условия поиска настолько новые, что нам, возможно, придется ждать дни или недели, чтобы увидеть связанные условия;
- Это оскорбительный или деликатный термин, и этот поисковый запрос нарушает политику Google. Более подробно вы можете узнатьПолитика автозаполнения поиска Google.
Почему мы видим некоторые неуместные ассоциативные слова?
У Google есть системы, предназначенные для автоматического обнаружения неуместных прогнозов без их отображения. Однако Google обрабатывает миллиарды поисковых запросов каждый день, а это означает, что Google ежедневно показывает миллиарды или даже десятки миллиардов прогнозов. Какой бы хорошей ни была система, в ней могут быть недостатки, и в любой момент могут появиться неверные прогнозы.
Как пользователи поиска Google, если мы считаем, что подсказка нарушает соответствующую политику автозаполнения поиска, мы можем сообщить об этом и нажать "Сообщить о недопустимых прогнозах” и отметьте соответствующие опции.
Как реализовать алгоритм автодополнения?
В настоящее время Google, похоже, публично не объявлял о внедрении алгоритма автозаполнения поиска, но отрасль уже провела много исследований в этом отношении.
Хороший автозаполнение должен быть быстрым и обновлять список ассоциативных слов, как только пользователь вводит следующий символ.В основе автозаполнения лежит функция, которая принимает входной префикс и ищет в списке слов или утверждений, начинающихся с заданного префикса.. Как правило, требуется вернуть лишь небольшое количество чисел.
Далее мы начнем с простой и неэффективной реализации и на ее основе создадим более эффективные методы.
Глоссарий реализации
ОдинПростая и грубая реализацияДа: последовательно искать словарь, проверяя каждый по очереди, чтобы увидеть, начинается ли он с заданного префикса.
Однако этот подход требует сопоставления префикса с каждым словарем, что вряд ли сработает, если словарь небольшой. Однако, если размер словаря велик, эффективность слишком низка.
ОдинЛучшей реализацией будет: Сортировка слов лексикографически. С помощью алгоритма бинарного поиска можно быстро найти префиксы в упорядоченных словарях. Поскольку каждый шаг бинарного поиска уменьшает объем поиска вдвое, общее время поиска пропорционально логарифму количества слов в словаре, т. е. временная сложность равнаO(log N). Производительность бинарного поиска хорошая, но есть ли лучшая реализация? Конечно есть, см. ниже.
Реализация префиксного дерева
Часто многие слова начинаются с одного и того же префикса, напримерneed,nestedоба сneначало,seed,speedоба сsначало. Представляется расточительным хранить общий префикс для каждого слова отдельно.
Дерево префиксов — это структура данных, в которой используются общие префиксы для ускорения выполнения. Префиксное дерево упорядочивает набор слов в дереве узлов, слова хранятся на пути от корневого узла к конечному узлу, а уровни дерева соответствуют позициям букв префиксов.
Завершение префикса ищется по пути, определяемому префиксом. Например, в приведенном выше дереве префиксов префиксneсоответствует взятию левого края из дочернего узлаNи только крайEмаршрут из. затем можно пройти отEВсе конечные узлы, до которых узел может добраться, чтобы сгенерировать список завершения. На картинке,neЗавершение может быть двух ветвей:-edи-sted. Если путь, определенный префиксом, не найден в списке, словарь не содержит слова, начинающегося с этого префикса.
Реализация конечных автоматов (DFA)
Дерево префиксов может эффективно обрабатывать общие префиксы, однако другие общие части слова по-прежнему хранятся отдельно в каждой ветви. Например, суффиксed,ing,tionОсобенно распространены в английских словах. В предыдущем примереe,dхранятся отдельно на каждой ветке.
Есть ли способ сэкономить больше места для хранения? Да, это ДФА.
В приведенном выше примере словоneed,nested,seedиspeedСостоит всего из 9 узлов, в то время как префиксное дерево на предыдущем рисунке содержит 17 узлов.
Можно видеть, что минимизация DFA префиксного дерева может значительно уменьшить размер структуры данных. Даже с большими словарями минимизированный DFA обычно подходит для хранения в памяти, а отказ от дорогостоящих обращений к диску является ключом к достижению быстрого автозаполнения.
некоторые расширения
Выше описано, как использовать разумные структуры данных для реализации основных функций автозаполнения. Эти структуры данных могут быть расширены различными способами для улучшения взаимодействия с пользователем.
В общем, может быть много слов, которые удовлетворяют определенному префиксу, но не многие из них могут отображаться в пользовательском интерфейсе.Мы предпочитаем отображать наиболее часто искомые или наиболее ценные слова. Обычно это можно сделать, добавив значение, представляющее значение слова, к каждому слову в словаре.Веса weightи отсортировать список автозаполнения по весу.
- Для отсортированного словаря увеличьте каждый элемент словаря
weightСвойства не сложны; - Для префиксного дерева
weightЭто также очень простая реализация для хранения в листовых узлах; - за
DFA, это сложнее. Потому что к листовому узлу можно добраться несколькими путями. Одно из решений состоит в том, чтобы связать веса с путями, а не с конечными узлами.
В настоящее время многие библиотеки с открытым исходным кодом предоставляют эту функцию, например основные платформы поисковых систем.Elasticsearch,SolrИ т. д., на основе этого мы можем реализовать эффективную и мощную функцию автодополнения.
Добро пожаловать в мою общедоступную учетную запись WeChat «Сообщество открытого исходного кода Doocs». Оригинальные технические статьи будут опубликованы как можно скорее.