Как Google использует шинглирование для обнаружения дубликатов и связывания повторяющихся фрагментов текста в разных документах

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

Corpus (Корпус)

Набор цифровых документов (например, книги, веб-страницы), хранящихся в системе.

Passage Mining Engine (Система анализа отрывков)

Компонент, который анализирует текст документов в корпусе для выявления похожих отрывков.

Sequence (Последовательность)

Один или несколько смежных шинглов, которые появляются в том же порядке как в исходном документе (Source Document), так и хотя бы в одном целевом документе (Target Document).

Shingle (Шингл)

Группа смежных слов в порядке чтения текста (N-грамма). Смежные шинглы перекрываются (скользящее окно).

Shingle Table (Таблица шинглов)

Индекс, который сопоставляет каждый уникальный шингл (Shingle ID) с документами (Doc ID) и позициями (Pos ID), где этот шингл встречается.

Shingle Bucket (Корзина шинглов)

Запись в Shingle Table, содержащая список всех вхождений для конкретного Shingle ID.

Similar Passage (Похожий отрывок)

Отрывок в исходном документе, который также встречается в похожей (часто идентичной) форме в одном или нескольких целевых документах. Формируется путем объединения (Merging) перекрывающихся Sequences.

Source Gap (Разрыв в источнике)

Шингл в исходном документе, который не встречается в других документах корпуса (или исключен из Shingle Table). Определяет границы между группами последовательностей.

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

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

1. Построение Shingle Table для корпуса.
2. Для целевого шингла в исходном документе, идентификация других документов, содержащих его.
3. Идентификация следующего шингла в исходном документе (расположенного сразу после целевого).
4. Идентификация подмножества документов, которые также содержат этот следующий шингл сразу после целевого.
5. Определение Sequence смежных шинглов, общей для исходного документа и подмножества документов.
6. Объединение (Merging) перекрывающихся шинглов в последовательности для формирования объединенной последовательности.
7. Определение Similar Passage на основе объединенной последовательности и его сохранение.

Это алгоритмический процесс поиска точных совпадений текстовых сегментов. Ключевым моментом является требование смежности и сохранения порядка: система итеративно проверяет, что шинглы следуют друг за другом в одинаковом порядке как в исходном, так и в целевом документе. Это обеспечивает высокую точность при поиске дубликатов и цитат.

Claim 5 (Зависимый от 1): Уточняет роль Source Gap.

Шингл, который встречается только в исходном документе (Source Gap), используется для определения границы (завершения) текущей Sequence.

Claim 6 и 7 (Зависимые от 1): Детализируют механизм ранжирования отрывков.

Similar Passage ранжируется относительно других отрывков в документе. Ранжирование основано на вычислении оценки (score), которая учитывает длину отрывка и частоту его появления в других документах корпуса.

Claim 8 и 9 (Зависимые от 1): Описывают применение результатов в пользовательском интерфейсе.

Система отображает найденный Similar Passage и предоставляет гиперссылку, позволяющую пользователю перейти к другому документу, содержащему этот отрывок.

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

Изобретение применяется на этапе обработки данных после их сбора.

INDEXING – Индексирование и извлечение признаков
Это основная фаза применения патента. Passage Mining Engine обрабатывает Corpus для извлечения признаков (похожих отрывков) и построения базы данных Similar Passage DB. Это включает:

• Анализ текста: Процессы Shingling и Sequencing анализируют содержимое для выявления общих последовательностей.
• Обнаружение дубликатов: Технология фундаментальна для систем обнаружения дубликатов и почти дубликатов.
• Ранжирование отрывков: Процессы Merging и Ranking определяют границы и значимость общих отрывков.

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

METASEARCH (Уровень представления UI)
Результаты работы (Similar Passage DB) используются веб-сервером для генерации пользовательского интерфейса (например, в Google Books), отображения популярных фрагментов и создания гиперссылок.

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

• Цифровой текстовый Corpus (документы с Doc ID и позициями слов Pos ID).

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

• Similar Passage DB, хранящая идентифицированные отрывки, их местоположение в разных документах и их ранги (scores).

На что влияет

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

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

• Условия работы: Алгоритм применяется во время обработки корпуса (индексирования).
• Триггеры активации: Процесс анализа запускается при обнаружении шингла, присутствующего более чем в одном документе (т.е. не являющегося Source Gap).
• Частота применения: Офлайн. Периодически для обновления корпуса или инкрементально при добавлении новых документов.

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

Процесс работы Passage Mining Engine:

1. Подготовка и Шинглирование (Shingling):
   1. Нормализация текста (нижний регистр, токенизация, возможное удаление стоп-слов).
   2. Разбивка документов на перекрывающиеся шинглы фиксированного размера (например, 8 слов).
2. Генерация Таблицы Шинглов (Generate Shingle Table):
   1. Создание индекса (Shingle Table), который сопоставляет каждый уникальный Shingle ID со списком (Shingle Bucket) его вхождений (Doc ID, Pos ID).
   2. Шинглы, встречающиеся только один раз, могут быть исключены (они определяют Source Gap).
3. Построение Последовательностей (Build Shingle Sequences): Для каждого исходного документа:
   1. Итерация по шинглам документа в порядке их следования.
   2. Если шингл определяет Source Gap, завершить все активные последовательности.
   3. Если это не разрыв, найти целевые документы, содержащие этот шингл.
   4. Проверить, расширяет ли текущий шингл существующую активную последовательность в целевом документе (т.е. следует ли он непосредственно за предыдущим шинглом).
   5. Если расширяет, обновить последовательность. Если нет, завершить старую и/или начать новую.
4. Объединение Последовательностей в Отрывки (Merge Sequences into Passages):
   1. Группировка идентифицированных последовательностей (границы часто определяются Source Gaps).
   2. Объединение перекрывающихся последовательностей внутри группы. Например, если Документ А и Б имеют общее совпадение 1-20, а Документ А и В — совпадение 10-30, они объединяются, чтобы идентифицировать полный отрывок 1-30 в Документе А.
   3. Короткие последовательности (например, менее 12 слов) могут быть отброшены.
5. Ранжирование Отрывков (Rank Passages):
   1. Вычисление оценки (score) для каждого похожего отрывка на основе эвристик длины и частоты встречаемости.
   2. Фильтрация отрывков, которые слишком короткие/длинные или слишком частые/редкие.

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

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

• Контентные факторы: Основным входным сигналом является сырой текст документов. Применяется нормализация. Стоп-слова и пунктуация могут быть исключены из шинглов.
• Структурные факторы: Система критически зависит от последовательного порядка слов (использование Pos ID) для идентификации смежных шинглов и построения последовательностей.

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

• Shingle Size: Предопределенное количество слов в шингле (например, 8).
• Minimum Sequence Length: Порог минимальной длины последовательности (например, 12 слов) для фильтрации общих фраз.
• Passage Score (Оценка отрывка): Метрика для ранжирования «интересности» отрывка. Рассчитывается на основе оценки длины (LS) и оценки частоты (FS).
• Формула оценки: Патент предлагает использовать взвешенное геометрическое среднее: