Как Google использует компактные Trie-структуры для локального поиска и автодополнения на мобильных устройствах

Термины и определения

Trie (Префиксное дерево)

Упорядоченная древовидная структура данных, используемая для хранения динамического набора или ассоциативного массива, где ключами обычно являются строки.

Nodes Array (Первый массив)

Массив, содержащий все узлы дерева: Root Node (корневой), Intermediate Nodes (промежуточные) и Leaf Nodes (листовые).

Nexts Array (Второй массив)

Массив, состоящий из срезов (Slices). Каждый элемент среза хранит следующий байт (символ) ключа и указатель обратно на Nodes Array.

Suffixes Array (Третий массив)

Массив, хранящий оставшиеся части ключей (суффиксы), завершающиеся нулем (null-terminated), и связанные с ними значения (Values).

Slice (Срез)

Непрерывный блок элементов в Nexts Array. Промежуточные узлы указывают на срезы с помощью пары (offset, length). Размеры срезов предпочтительно являются степенью двойки (power of two) для оптимизации памяти.

Value (Значение)

Данные, связанные с полным ключом, хранящиеся в Suffixes Array. Обычно это указатель на секцию файла, содержащую список идентификаторов документов (listing of documents), в которых встречается данный ключ.

Find Function

Функция для поиска заданного ключа в структуре данных Trie.

Insertion Function

Функция для динамического добавления новых ключей в Trie.

Prefix Function

Функция для поиска всех ключей в Trie, которые начинаются с заданного префикса (используется для автодополнения).

Ключевые утверждения (Анализ Claims)

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

Claim 1 (Независимый пункт): Описывает вычислительное устройство, использующее данную структуру для поиска.

1. Устройство хранит поисковую структуру данных, состоящую из трех массивов (Первый, Второй, Третий) с определенными взаимосвязями (Узлы -> Срезы -> Узлы -> Суффиксы).
2. Элементы Третьего массива хранят подстроку (суффикс) и значение (Value), указывающее на секцию файла.
3. Устройство ищет совпадение по введенному пользователем ключу.
4. Если совпадение найдено, возвращается Value, и на дисплее отображается список документов, содержащих ключ (полученный из файла по указателю Value).

Это определение самой структуры и ее применения для локального поиска документов на устройстве.

Claim 8 (Независимый пункт): Описывает использование структуры для функции автодополнения (Suggest).

1. Устройство ищет возможные совпадения в ответ на ввод пользователем первой части поискового ключа (префикса).
2. Найденные совпадения отображаются на дисплее как предлагаемые поисковые термины (suggested search terms).

Описывается применение Trie для функции префиксного поиска на устройстве.

Claim 16 (Независимый пункт): Описывает изменяемость (mutability) структуры и процесс обновления индекса.

1. Устройство обновляет структуру данных, когда ключ из дополнительного документа отражается в файле (индексация нового контента).
2. Процессор ищет новый ключ. Если ключ уже присутствует в структуре, процессор обновляет соответствующее Value (т.е. обновляет список документов). Если ключ отсутствует, он добавляется в структуру (детализировано в зависимых пунктах 17-20).

Описывается механизм поддержания актуальности локального индекса при появлении новых данных.

Где и как применяется

Патент описывает инфраструктуру хранения данных. Он не вписывается в стандартную архитектуру веб-поиска Google (Crawling, Indexing, Ranking и т.д.), так как предназначен для локального индексирования и поиска на клиентском устройстве (смартфоне, планшете).

Область применения: Локальный поиск в приложениях (например, Gmail, Контакты, Поиск по устройству).

Взаимодействие компонентов (Локальное):

• Индексирование: Insertion Function используется для построения и динамического обновления локального индекса (Trie Data Structure) при поступлении новых документов (например, писем).
• Поиск (Retrieval): Find Function используется приложением (Call Interface Program) для быстрого извлечения списка документов из локального файла (File), связанных с введенным ключом.
• Автодополнение: Prefix Function используется для генерации поисковых подсказок в реальном времени.

Входные данные:

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

Выходные данные:

• Указатели на списки локальных документов (Values).
• Предлагаемые поисковые термины (подсказки).

На что влияет

Изобретение влияет исключительно на производительность и эффективность использования ресурсов при выполнении локальных операций на устройстве:

• Скорость локального поиска по точным совпадениям.
• Скорость генерации подсказок (автодополнения).
• Эффективность использования памяти и дискового пространства для хранения локального индекса.

Патент не влияет на ранжирование веб-сайтов в поиске Google.

Когда применяется

Алгоритмы применяются в следующих сценариях на устройстве:

• Find function: Когда пользователь вводит полный поисковый запрос в локальном приложении.
• Prefix function: В реальном времени, когда пользователь вводит символы для получения автодополнения.
• Insertion function: Когда приложение получает новые данные (например, новые электронные письма), требующие локальной индексации или обновления индекса.

Пошаговый алгоритм

Процесс А: Поиск ключа (Find Function)

1. Начало поиска: Функция начинает обход Trie с корневого узла (Root Node) в первом массиве (Nodes).
2. Определение среза: Определяется срез во втором массиве (Nexts), на который указывает текущий узел (используя его offset и length).
3. Бинарный поиск символа: Выполняется бинарный поиск текущего символа ключа в этом срезе. (Срезы поддерживаются в отсортированном виде).
4. Обработка результата поиска:
   • Если совпадение не найдено: Поиск прекращается, результат не возвращается.
   • Если совпадение найдено: Система использует указатель, связанный с совпавшим элементом среза, чтобы перейти к следующему узлу в первом массиве.
5. Итерация или завершение:
   • Если новый узел промежуточный (Intermediate Node): Процесс повторяется с шага 2 для следующего символа ключа.
   • Если новый узел листовой (Leaf Node): Система переходит к третьему массиву (Suffixes).
6. Сравнение суффикса: Оставшаяся часть ключа сравнивается (Directly Compare) с подстрокой, хранящейся в элементе третьего массива, на который указывает листовой узел.
7. Финальный результат:
   • Если суффиксы совпадают: Совпадение найдено. Возвращается значение (Value), прикрепленное к суффиксу.
   • Если суффиксы не совпадают: Совпадение не найдено.

Процесс Б: Автодополнение (Prefix Function)

1. Поиск префикса: Выполняется обход Trie (аналогично Процессу А) для сопоставления введенного префикса.
2. Достижение узла:
   • Если достигнут листовой узел: Сравнивается подстрока в третьем массиве с оставшимися байтами префикса. Если есть совпадение, которое покрывает длину оставшегося префикса, вернуть только этот ключ как подсказку. Иначе, не возвращать ничего.
   • Если достигнут промежуточный узел (и весь префикс совпал): Перейти к шагу 3.
3. Обход в глубину (Depth-first Traversal): Выполнить обход в глубину для всех ключей, находящихся под этим промежуточным узлом. Вернуть все найденные ключи как предложенные поисковые термины.

Какие данные и как использует

Данные на входе

Патент сугубо инфраструктурный и не описывает факторы ранжирования веб-поиска (контентные, ссылочные, поведенческие и т.д.). Он оперирует следующими данными:

• Структурные данные: Сама структура Trie (массивы Nodes, Nexts, Suffixes, узлы, срезы, указатели).
• Контентные факторы (Локальные): Ключи (слова), извлеченные из локальных документов (например, электронных писем) для построения индекса.
• Пользовательские факторы: Введенный пользователем поисковый запрос (search key) или префикс.

Какие метрики используются и как они считаются

Метрики ранжирования (Ranking Scores) в патенте не упоминаются. Используются структурные параметры и методы для оптимизации:

• Offset и Length: Используются для определения точного положения и размера среза (Slice) во втором массиве.
• Размер среза (Slice Size): Оптимизирован как степень двойки (1, 2, 4, 8...). Это позволяет уменьшить фрагментацию памяти и ускорить аллокацию. В патенте упоминается использование списков свободных пространств (free lists) для управления памятью при перемещении срезов.
• Методы поиска:
  • Binary Search (Бинарный поиск): Используется для быстрого поиска нужного байта внутри отсортированного среза во втором массиве.
  • Direct Compare (Прямое сравнение): Используется для сравнения суффиксов в третьем массиве.
• Методы обхода:
  • Depth-first Traversal (Обход в глубину): Используется функцией Prefix для генерации списка подсказок.

1. Фокус на локальной оптимизации: Патент описывает исключительно внутренние инженерные решения Google для оптимизации хранения и поиска данных на клиентских устройствах с ограниченными ресурсами.
2. Цель — Эффективность и Компактность: Основная цель — обеспечить быстрый поиск (Find), автодополнение (Prefix) и обновление индекса (Insertion) при минимальном потреблении памяти. Это достигается за счет трехуровневой структуры, бинарного поиска и оптимизированной аллокации памяти (степень двойки).
3. Изменяемость (Mutability): Структура спроектирована так, чтобы поддерживать динамическое добавление новых данных (например, новых писем) без необходимости полной перестройки индекса.
4. Отсутствие связи с веб-поиском: Патент не содержит абсолютно никакой информации об алгоритмах веб-ранжирования, сигналах качества, E-E-A-T или любых других факторах, влияющих на SEO продвижение сайтов в глобальном поиске Google.
5. Нет практической ценности для SEO: Практических выводов для SEO-специалистов, занимающихся оптимизацией сайтов, этот патент не несет.

ВАЖНО: Патент является инфраструктурным, описывает локальное хранение данных и не дает практических выводов для SEO.

Best practices (это мы делаем)

Не применимо к SEO. Рекомендации из этого патента актуальны для разработчиков мобильных приложений, создающих собственные локальные поисковые индексы, но не для SEO-специалистов.

Worst practices (это делать не надо)

Не применимо к SEO.

Стратегическое значение

Стратегическое значение для SEO отсутствует. Патент интересен с точки зрения компьютерных наук и понимания того, как Google решает инженерные задачи локального поиска и индексирования. Он никак не влияет на понимание приоритетов Google в веб-ранжировании и не должен учитываться при разработке SEO-стратегии.

Практические примеры

Практических примеров для SEO нет. Ниже приведен пример, демонстрирующий работу механизма в контексте локального поиска.

Сценарий: Поиск электронного письма на смартфоне

1. Индексация (Фон): Приложение на телефоне получило новые письма. Функция Insertion обработала их и добавила новые слова (ключи) в локальную структуру Trie.
2. Ввод пользователя: Пользователь открывает поиск и начинает вводить префикс (например, "goo").
3. Автодополнение (Prefix Function): Система использует функцию Prefix. Она быстро обходит Trie по пути 'g' -> 'o' -> 'o'. Достигнув соответствующего узла, она выполняет обход в глубину (Depth-first Traversal) и находит все возможные завершения (например, "good" и "goose"). Они отображаются как подсказки.
4. Выбор пользователя: Пользователь выбирает "good".
5. Поиск (Find Function): Система использует функцию Find. Она проходит тот же путь в Trie. Достигнув листового узла для "good", она проверяет суффикс.
6. Результат: Совпадение найдено. Система извлекает Value, связанное с ключом "good". Это Value является указателем на список ID всех писем, содержащих это слово. Письма отображаются пользователю.