Как Google сжимает и индексирует дубликаты и шаблонный контент для экономии места в индексе (Compressed Tokenspace)

Описание

Какую задачу решает

Патент решает фундаментальную инфраструктурную проблему: неэффективность хранения и индексирования огромных корпусов документов (таких как Веб), содержащих значительное количество дубликатов, почти дубликатов и шаблонного контента (boilerplate). Цель — радикально сократить объем дискового пространства. Изобретение устраняет недостатки традиционной дедупликации (которая просто отбрасывает копии), такие как потеря доступа к документу по его URL и уязвимость к page hijacking. Система обеспечивает экономию места, сохраняя доступность всех документов.

Что запатентовано

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

Как это работает

Система работает следующим образом:

• Токенизация: Документы преобразуются в последовательности токенов (tokens).
• Кластеризация: Похожие документы группируются. Ключевой метод — сортировка по реверсированным URL (например, com.example.www), что группирует страницы с одного хоста. Также упоминается группировка разных версий одного документа.
• Сжатие кластера: Внутри кластера применяется алгоритм сжатия (упоминается метод Bentley-McIlroy). Повторяющиеся последовательности токенов заменяются инструкциями копирования (Copy codes), ссылающимися на первое уникальное вхождение (Add codes).
• Формирование репозитория: Сжатые последовательности всех кластеров объединяются в единый Compressed Tokenspace Repository.
• Индексирование: Создается инвертированный индекс, который мапирует токены на их позиции именно в этой сжатой последовательности.
• Обработка запросов: При поиске система находит токены в сжатом пространстве, а затем использует Document Reconstruction Data, чтобы определить, какие исходные документы содержат эти токены и удовлетворяют ли они запросу.

Актуальность для SEO

Высокая (с точки зрения инфраструктуры). Эффективность хранения данных в масштабах Google остается критически важной задачей. Авторы патента — Jeffrey Dean и Sanjay Ghemawat — являются ключевыми архитекторами базовой инфраструктуры Google (MapReduce, BigTable, GFS). Это указывает на то, что описанные принципы, вероятно, лежат в основе организации хранения данных в индексе Google.

Важность для SEO

Минимальное влияние (2/10). Патент является чисто инфраструктурным и описывает внутренние механизмы хранения и индексирования данных, а не алгоритмы ранжирования или оценки качества. Он не содержит прямых рекомендаций для SEO. Его ценность для Senior-специалистов заключается в глубоком понимании архитектуры индекса и того, как Google обрабатывает дублированный и шаблонный контент на самом низком уровне хранения.

Детальный разбор

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

Token (Токен)

Объект фиксированной или переменной длины, представляющий слово, фразу, символ пунктуации, HTML-тег и т.д. В патенте упоминается использование токенов фиксированной длины (например, 32 бита) для эффективности.

Uncompressed Sequence of Tokens (Несжатая последовательность токенов)

Исходная последовательность токенов, представляющая набор документов до применения сжатия.

Compressed Tokenspace Repository (Репозиторий сжатого пространства токенов)

Основное хранилище, содержащее сжатую последовательность токенов для всего корпуса. Повторяющиеся токены из несжатой последовательности удалены (elided) из этого хранилища.

Cluster (Кластер)

Группа из одного или нескольких документов, объединенных для совместного сжатия. Документы в кластере обычно схожи (по контенту, URL или версии).

Add Code (Код добавления)

Инструкция в данных реконструкции, содержащая последовательность литеральных (уникальных в данном контексте) токенов.

Copy Code (Код копирования)

Инструкция в данных реконструкции, указывающая на диапазон позиций в уже существующей части сжатой последовательности, который нужно скопировать. Заменяет хранение повторяющихся данных.

Document Reconstruction Data (Данные для реконструкции документа)

Набор инструкций (Add codes и Copy codes), необходимый для восстановления исходного документа из сжатого представления.

Bentley-McIlroy data compression method

Алгоритм сжатия, упомянутый в патенте. Основан на поиске длинных общих строк (long common strings) и замене повторений ссылками.

Reversed URLs / Modified Locator (Перевернутые URL / Модифицированный локатор)

Метод преобразования URL для кластеризации. Домены меняются местами, а протокол перемещается в конец (например, com.yahoo.www/index.html:http).

Compressed-Uncompressed Map (Карта сжатого/несжатого пространства)

Структура данных, которая мапирует позиции токенов в сжатой последовательности на соответствующие позиции в исходной (несжатой) последовательности.

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

Claim 1 (Независимый пункт): Описывает основной метод обработки документов.

1. Система группирует набор документов в кластеры.
2. Внутри кластера система определяет, что второй документ содержит дублирующиеся данные (duplicate data), которые повторяют данные из первого документа.
3. Система идентифицирует подмножество данных кластера, которое исключает (excludes) по крайней мере часть этих дублирующихся данных (это процесс сжатия).
4. Система генерирует индекс этого подмножества данных (т.е. индексирует сжатое представление).

Ядро изобретения — это процесс кластеризации, сжатия внутри кластера путем устранения избыточности между документами и индексирования результирующей сжатой структуры.

Claim 7 (Зависимый от 5): Описывает обработку запросов с использованием сжатого индекса.

1. Система хранит document reconstruction data для восстановления документов из сжатых данных.
2. После получения запроса система идентифицирует позиции токенов запроса в сжатых данных на основе индекса.
3. Документы, соответствующие запросу, идентифицируются на основе этих позиций И данных для реконструкции документа.

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

Claim 11, 12, 13 (Зависимые): Детализируют метод кластеризации на основе URL.

• (Claim 11, 12) Документы считаются связанными на основе их URL (resource locator). Группировка включает упорядочивание документов и выбор последовательных документов для кластера.
• (Claim 13) Упорядочивание происходит по модифицированным локаторам (modified locator): домены в URL инвертируются (reversing the domains), а индикатор протокола перемещается в конец.

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

Claim 14 (Зависимый от 1): Указывает на вариант применения для исторического архива, где кластер включает различные версии одного документа в разные моменты времени.

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

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

INDEXING – Индексирование и извлечение признаков
Это основной этап применения патента. Он описывает, как именно структурируется индекс и как данные сохраняются в нем. Процессы токенизации, кластеризации документов, сжатия токенов и построения инвертированного индекса (Compressed Tokenspace Inverted Index) по сжатому репозиторию (Compressed Tokenspace Repository) происходят здесь.

RANKING – Ранжирование (Этап Retrieval)
Процесс отбора кандидатов должен взаимодействовать с этой сжатой структурой. Query Processor использует индекс для поиска токенов в сжатом пространстве, а затем должен использовать Document Reconstruction Data, чтобы определить, каким документам они принадлежат и удовлетворяют ли они условиям запроса (например, фразовому поиску).

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

• Набор документов (после краулинга).
• URL (Resource Locators) этих документов.

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

• Compressed Tokenspace Repository (Сжатое хранилище данных).
• Compressed Tokenspace Inverted Index (Индекс).
• Document Reconstruction Data (Данные для восстановления, Add/Copy codes).
• Compressed-Uncompressed Map (Карта соответствия позиций).

На что влияет

• Типы контента и запросы: Влияет на все типы индексируемого контента и все запросы, так как описывает базовую архитектуру хранения индекса.
• Конкретные ниши: Наиболее эффективно для корпусов с высокой степенью избыточности: крупные веб-сайты с общими шаблонами (e-commerce, новости), форумы, исторические архивы версий документов.

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

• Условия применения: Алгоритм применяется во время основного конвейера индексирования (indexing pipeline).
• Триггеры и Пороговые значения: Сжатие (замена на Copy code) активируется, когда система обнаруживает повторяющиеся последовательности токенов, превышающие минимальную длину (predefined minimum length). В патенте упоминается пример порога в 20 токенов.

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

Процесс Индексирования и Сжатия:

1. Идентификация и Токенизация: Набор документов парсится в несжатую последовательность токенов.
2. Кластеризация Документов: Документы группируются в кластеры.
   • Основной метод: URL преобразуются в Reversed URLs. Документы сортируются лексикографически. Последовательные K документов (например, K=10) объединяются в кластер.
   • Другие методы: группировка по версиям или с использованием similarity-hashing.
3. Кодирование и Сжатие Кластеров: Каждый кластер обрабатывается с использованием метода сжатия (например, Bentley-McIlroy).
   • Система ищет длинные общие последовательности токенов (длиннее порога N).
   • Генерируется сжатое представление и Document Reconstruction Data (операции Add для уникальных данных и Copy для повторяющихся).
4. Генерация Сжатого Пространства: Сжатые последовательности всех кластеров конкатенируются в единый Compressed Tokenspace Repository. (В одном из вариантов реализации, однодокументные кластеры могут размещаться перед многодокументными).
5. Индексирование: Создается Compressed Tokenspace Inverted Index, индексирующий токены по их позициям в сжатом пространстве.
6. Генерация Маппинга: Создается Compressed-Uncompressed Map.

Процесс Обработки Запроса:

1. Получение запроса.
2. Поиск в сжатом индексе: Токены запроса ищутся в инвертированном индексе, который возвращает позиции в сжатом пространстве.
3. Идентификация Кластеров-Кандидатов: Определяются кластеры, содержащие токены запроса. Кластеры, не содержащие всех необходимых токенов (например, для AND запроса), могут быть отброшены.
4. Валидация Документов: Для кластеров-кандидатов система использует Document Reconstruction Data, чтобы определить, какие конкретные документы внутри кластера удовлетворяют запросу (например, проверка порядка слов во фразе, которая может пересекать границы Add/Copy кодов).
5. Возврат результатов.

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

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

• Контентные факторы: Все содержимое документов (текст, HTML-теги, пунктуация), представленное в виде последовательности токенов.
• Технические факторы: URL (Resource Locators). Они критически важны для основного метода кластеризации, описанного в патенте (используются Reversed URLs).

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

Патент фокусируется на инфраструктуре, а не на метриках ранжирования. Используемые параметры:

• Позиции токенов (Token Positions): Используются для индексации и для операций Copy.
• Длина общих строк (Length of common strings): Система ищет повторяющиеся последовательности. Упоминается пороговое значение минимальной длины (например, N=20 токенов) для применения сжатия.
• Размер кластера (K): Количество документов в кластере (например, K=10).
• Алгоритмы кластеризации: Лексикографическая сортировка (для Reversed URLs). Также упоминается возможность использования similarity-hashing.
• Алгоритмы сжатия: Метод Bentley-McIlroy или аналогичные, использующие хеш-таблицы (Hash Table) и скользящие окна для быстрого поиска общих строк.

Выводы

1. Инфраструктура, а не ранжирование: Это фундаментальный инфраструктурный патент (авторы – Dean и Ghemawat). Он объясняет, КАК данные хранятся и индексируются для экономии ресурсов, но не содержит информации о том, КАК они ранжируются или оцениваются.
2. Приоритет эффективности хранения: Google фундаментально решает проблему масштабирования индекса путем агрессивного сжатия похожих документов. Система предпочитает хранить общие элементы (шаблоны, дубликаты) только один раз для всего кластера.
3. Кластеризация по хостам (Host Clustering) подтверждена: Патент явно описывает механизм кластеризации путем сортировки по перевернутым URL (Reversed URLs). Это подтверждает, что Google организует индекс группами, связанными общим хостом. Цель этого, согласно патенту, — повысить эффективность сжатия.
4. Обработка дубликатов и шаблонов (Boilerplate): Механизм Compressed Tokenspace позволяет Google эффективно хранить сайты с большим количеством шаблонного контента. Система сохраняет доступ ко всем версиям документов, но при этом значительно экономит место. Дубликаты сжимаются на уровне хранения, а не обязательно отбрасываются.
5. Сложность обработки запросов: Индексирование сжатого пространства усложняет обработку запросов (особенно фразовых), так как требует этапа валидации с использованием Document Reconstruction Data.

Практика

ВАЖНО: Патент является инфраструктурным и не дает прямых практических выводов для оптимизации сайтов с целью улучшения ранжирования.

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

• Поддержание логичной структуры URL: Поскольку основным методом кластеризации является сортировка по перевернутым URL, поддержание чистой и логичной структуры URL (включая использование поддоменов и директорий) помогает Google эффективно кластеризовать и обрабатывать страницы сайта. Это способствует более эффективному индексированию (но не обязательно лучшему ранжированию).
• Консистентность шаблонов (Техническое SEO): Патент показывает, что Google эффективно идентифицирует и сжимает шаблонный контент (boilerplate). Использование консистентных шаблонов и структуры кода на всем сайте помогает Google эффективнее распознавать эти общие элементы, что оптимизирует обработку сайта.

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

• Массовое создание gần-дубликатов (с точки зрения эффективности хранения): Создание огромного количества страниц с минимальными отличиями неэффективно. Этот патент демонстрирует механизм, который позволяет Google эффективно сжимать такие страницы на уровне хранения, идентифицируя их схожесть в масштабе. (Хотя это не связано напрямую с ранжированием в данном патенте).

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

Стратегическое значение патента для SEO заключается в понимании инфраструктурных возможностей Google. Он демонстрирует, что на этапе индексирования Google рассматривает веб не как набор независимых страниц, а как кластеры контента, организованные в первую очередь по хостам (Host Clustering). Это дает понимание того, как Google справляется с масштабом Интернета и проблемой дублирования контента на техническом уровне хранения.

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

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

Пример работы системы (Индексирование E-commerce сайта):

1. Ситуация: Сайт интернет-магазина содержит 1000 карточек товаров с идентичным шаблоном (шапка, навигация, футер).
2. Кластеризация: Google преобразует URL: com.store.www/product/1, com.store.www/product/2 и т.д. При сортировке эти страницы оказываются рядом и объединяются в кластеры (например, по 10 страниц).
3. Сжатие: Внутри кластера общие элементы шаблона встречаются многократно. Система сохраняет шаблонные элементы только один раз в Compressed Tokenspace. Уникальные описания товаров сохраняются буквально (операция Add), а шаблонные элементы заменяются ссылками (операция Copy).
4. Результат: Google хранит все 1000 страниц, используя объем памяти, значительно меньший, чем при индивидуальном хранении.

Вопросы и ответы