Как «удивительные» строки Firefox соответствуют строкам?

Question

Вопрос в том, как сделать сопоставление строк, чтобы найти соответствующие записи с помощью firefox 3 url bar . Сопоставление подстроки в каждой записи может быть медленным. Какой алгоритм можно использовать для быстрого сопоставления в любом месте?

Answer 1

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

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

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

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

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

1. Строка поиска разбивается на токены, определяемые пробелами (каждое непропущенное «слово» является токеном).
2. Для каждого токена начните сравнивать каждый символ искомого текста и токен в Юникоде без учета регистра, пока он не совпадет полностью. Если один набор символов не совпадает, перейдите к следующему « границам слов » в тексте с возможностью поиска и повторите попытку.
3. Если мы сопоставим любой текст с возможностью поиска, он отобразится в строке адреса.
4. Если у нас недостаточно результатов (по умолчанию 12), мы затем повторим поиск запроса, проходящего через каждую закладку и историю посещений, и протестируем доступный для поиска текст в Unicode без учета регистра для каждого токена в любом месте (не только на границах слов).

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

Answer 2

Обычный способ быстрого сопоставления подстрок состоит в создании структуры данных, которая содержит все суффиксы всех строк, которые вы хотите найти. В зависимости от организации это можно назвать «деревом суффиксов» или «массивом суффиксов». Например, если у вас есть 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

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

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

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

Answer 3

Awesomebar предлагает URL-адреса с помощью алгоритма, называемого Алгоритм размещения Places .

По данным сайта разработчиков Mozilla:

Само слово «частота» само по себе является комбинацией слов «частота» и «свежесть».

Answer 4

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

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