Как Firefox "awesome" bar соответствует строкам?

Ответ 1

Обычным способом быстрого подстроки является создание структуры данных, содержащей все суффиксы всех строк, которые вы хотите найти. В зависимости от организации это можно назвать "суффиксом" или "суффиксным массивом". Например, если у вас 1000 строк, и каждый из них имеет длину 50 символов, у вас есть 1 000 x 50 нетривиальных суффиксов, т.е. Ваш массив суффикса будет иметь 50 000 записей.

Затем, чтобы выполнить сопоставление, вы выполняете двоичный поиск (если массив) или поиск по дереву (если дерево), чтобы найти все эти суффиксы в структуре данных, начало которых соответствует строке, написанной в окне поиска. Поскольку это начало суффикса, которое вы сопоставляете, вы можете использовать стандартные процедуры поиска (двоичный поиск, спуск по течению), чтобы быстро получить результат. Каждый суффикс связан с теми строками, в которых он появляется.

Пример: у вас две строки: "CAT" и "DOT" . Ваш массив суффиксов выглядит так (обратите внимание на лексиографию = буквенное упорядочение):

#1 AT  --> CAT
#2 CAT --> CAT
#3 DOT --> DOT
#4 OT  --> DOT
#5 T   --> DOT, CAT

Обратите внимание, что есть шесть суффиксов, но два из них одинаковы (последний "Т" в "CAT" и "DOT" ), и оба они представлены одной и той же записью (# 5).

Теперь, когда пользователь вводит в поиск, например. "OT" (который должен соответствовать "DOT" ), вы можете выполнить простой поиск по лексиографическому упорядочению во время регистрации, поскольку теперь вы ищете начальное совпадение в массиве суффиксов.

Это основной принцип быстрого поиска текста, когда шаблон поиска не содержит подстановочных знаков.

Ответ 2

Алгоритм расположения в Firefox 3.0 немного сложнее. Он получит данные от двух (три для Firefox 3.5 и более поздних) разных запросов:

• Для первого запроса он проверяет таблицу moz_inputhistory, чтобы увидеть, сохраняется ли текущая строка поиска в этой таблице. Эти результаты сортируются по "рангу", который является числом, которое определяет, как недавно оно используется. Это число разлагается один раз в день. Этот поиск делает панель местоположений адаптивной к тому, что вы выбираете с течением времени (реализован в ошибка 95739).

• В Firefox 3.5 и более поздних версиях он проверяет таблицу moz_keyword для закладок с ключевым словом, соответствующим тексту поиска.

• Последний запрос, он проходит через каждую запись в moz_places, которая будет включать в себя все посещения истории и закладки. Эти результаты упорядочиваются frecency.

Для всех трех этих случаев для сопоставления с тегами, заголовком и URL-адресом используется следующий алгоритм (называемый "текст с возможностью поиска" ниже). Это немного сложно объяснить словами, поэтому было бы легче посмотреть исходный код.

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

Надеюсь, это объяснит это понятным образом!

Ответ 3

В awesomebar предлагается URLS с помощью алгоритма алгоритм рассылки Places.

Согласно сайту разработчика Mozilla:

Слово "frecency" само по себе представляет собой комбинацию слов "частота" и "регентство".

Ответ 4

Я думаю, что это осталось для базового хранилища: база данных SQLite, в которой Firefox хранит страницы, которые вы посетили, предлагает быструю функцию для сравнения подстроки.

Я думаю, что Firefox выдает SQL-запрос в базу данных. Это довольно быстро, потому что база данных кэшируется в вашей памяти.