Как "удивительный" бар Firefox соответствует строкам?
Вопрос в том, как сделать сопоставление строк, чтобы найти подходящие записи с помощью панели URL Firefox 3. Сопоставление подстроки в каждой записи может быть медленным. Какой алгоритм можно использовать для быстрого сопоставления в любом месте?
4 ответа
Обычный способ выполнить быстрое сопоставление подстрок - создать структуру данных, которая содержит все суффиксы всех строк, которые вы хотите найти. В зависимости от организации это можно назвать "деревом суффиксов" или "массивом суффиксов". Например, если у вас есть 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"), вы можете выполнить простой лексикографический поиск по порядку во время регистрации, так как вы сейчас ищете начальное совпадение в массиве суффиксов.
Это основной принцип быстрого поиска текста, когда шаблон поиска не содержит символов подстановки.
Алгоритм определения местоположения в Firefox 3.0 немного сложен. Он будет получать данные из двух (три для Firefox 3.5 и более поздних) разных запросов:
Для первого запроса он проверяет таблицу moz_inputhistory, чтобы увидеть, сохранена ли текущая строка поиска в этой таблице. Эти результаты сортируются по "рангу", который является числом, определяющим, как недавно он использовался. Это число ухудшается один раз в день. Этот поиск позволяет адаптировать адресную строку к тому, что вы выбираете с течением времени (реализовано в ошибке 95739).
В Firefox 3.5 и более поздних версиях он проверяет таблицу moz_keyword на наличие закладок с ключевым словом, которое точно соответствует тексту поиска.
Последний запрос проходит через каждую запись в moz_places, которая будет включать все истории посещений и закладки. Эти результаты упорядочены по частоте.
Для всех трех этих случаев для сопоставления с тегами, заголовком и URL-адресом используется следующий алгоритм (называемый "текст с возможностью поиска" ниже). Это немного сложно объяснить словами, поэтому может быть проще взглянуть на исходный код.
- Строка поиска разбивается на токены, определяемые пробелами (каждое непропущенное "слово" является токеном).
- Для каждого токена начните сравнивать каждый символ текста с возможностью поиска и токен в Юникоде без учета регистра, пока он не совпадет полностью. Если один набор символов не совпадает, перейдите к следующей " границе слова " в доступном для поиска тексте и повторите попытку.
- Если мы сопоставим какой-либо текст с возможностью поиска, он отобразится в строке адреса.
- Если у нас недостаточно результатов (по умолчанию 12), мы затем повторим поиск запроса, проходящего через каждую закладку и историю посещений, и протестируем доступный для поиска текст в Unicode без учета регистра для каждого токена в любом месте (не только на словесных границах).
Надеюсь, это объясняет это понятным образом!
Awesomebar предлагает URL-адреса с помощью алгоритма, который называется алгоритм Frecescy.
По словам разработчиков сайта Mozilla:
Само слово "вежливость" является сочетанием слов "частота" и "свежесть".
Я думаю, что это остается за основным хранилищем: база данных SQLite, где Firefox хранит страницы, которые вы посетили, предлагает быструю функцию для сравнения подстрок.
Я думаю, что Firefox выдает SQL-запрос к базе данных. Это довольно быстро, потому что база данных кэшируется в вашей памяти.