Как работает автозаполнение Google Chrome Omnibox?
Комментарий в следующем посте особенно полезен для понимания части алгоритма.
Как Chrome обновляет дополнения в строке URL?
Все же вопросы остаются здесь. Я провел некоторый эксперимент на Chrome:
Когда я ввожу "eddit", он предлагает только "reddit" для общего поиска в Google, в то время как, если я ввожу "reddit" полностью, всплывает исторический URL-адрес reddit.
Если я введу подстроку "facebook", "google" или "youtube", то URL-адреса будут отображаться успешно. Скажите "ceb", "ogl", "utu". Следовательно, попытки не должны быть (единственной) структурой данных, используемой здесь.
Кроме того, я знаю, что в Chrome для полнотекстового поиска используется fts sqlite (атрибут sqlite fts 3/4 для Google). Поэтому я предполагаю, что Chrome использует инвертированный индекс URL в sqlite.
Мой вопрос:
Как Chrome удается автозаполнить "utu" -> "youtube"?(На основе моих локальных URL-адресов истории)
- Я знаю, что суффикс массив / дерево может эффективно соответствовать подстроке. Но нахождение конкретного слова "YouTube" будет линейным.
- Я думаю, что индивидуальный токенизатор (для fts3/4) может достичь этого. Скажите "google" -> {"g",..., "gle", ..}. Но будет создано слишком много токенов.