Как Google объединяет разрозненные данные о сущностях (Entity Resolution) с помощью хеширования и нечеткого сравнения

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

Collision (Коллизия)

Ситуация, когда два значения поля из разных записей имеют одинаковое Hash Value. Это указывает на точное совпадение значения и является триггером для проверки на дублирование.

Conflict (Конфликт)

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

Duplicate Entries (Дублирующиеся записи)

Две или более записей, которые система идентифицировала как относящиеся к одной и той же сущности.

Entry (Запись)

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

Field Type (Тип поля)

Категория данных в записи (например, Имя, Телефон, Адрес). Определяет правила обработки и допустимость множественных значений.

Field Value (Значение поля)

Конкретные данные в поле (например, «Джон Смит»). Алгоритм фокусируется на непустых значениях (Non-blank Field Values).

Hamming Distance (Расстояние Хэмминга)

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

Hash Value (Хеш-значение)

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

Needleman-Wunsch Algorithm (Алгоритм Нидлмана-Вунша)

Алгоритм для вычисления глобального выравнивания последовательностей (Sequence Alignment). Используется для измерения степени схожести строк разной длины (например, сокращенных и полных имен).

Sequence Alignment (Выравнивание последовательностей)

Мера схожести двух строк. Используется для нечеткого сравнения (Fuzzy Matching).

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

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

1. Система получает набор записей (set of entries).
2. Вычисляются хеш-значения (hash value) для непустых полей.
3. Обнаруживается коллизия: хеш-значение поля в первой записи соответствует хеш-значению поля во второй записи.
4. Определяется отсутствие конфликтов между всеми непустыми полями первой и второй записей. Механизм определения отсутствия конфликта включает:
   • Идентификацию типа поля (Field Type), который не может содержать несколько разных значений для одной записи (например, Имя).
   • Вычисление выравнивания последовательностей (Sequence Alignment) между значениями этого типа поля в первой и второй записях.
   • Определение того, что конфликт отсутствует, если вычисленное выравнивание превышает пороговое значение (sequence alignment threshold), то есть значения достаточно похожи.
5. Если коллизия найдена и конфликтов нет, система предоставляет индикацию, что записи являются дубликатами.

Claim 10 (Зависимый): Детализирует условие отсутствия конфликта, когда значения полей различны.

Если записи имеют разные значения для определенного типа поля, конфликт отсутствует, если система определяет, что этот тип поля допускает наличие нескольких значений в одной записи (например, несколько телефонных номеров или email-адресов).

Claim 11 (Зависимый): Детализирует альтернативный метод определения отсутствия конфликта с использованием $\text{Hamming Distance}$.

Вычисляется расстояние Хэмминга между значениями полей. Если расстояние меньше порогового значения (Hamming distance threshold), конфликт отсутствует (например, при наличии опечаток).

Claim 12 (Зависимый): Уточняет, что для расчета Sequence Alignment может использоваться алгоритм $\text{Needleman-Wunsch}$.

Claim 25 (Зависимый): Вводит специальное правило для обработки конфликтов.

Система проверяет, что поле не содержит подстроки «&» или «and» только в одной из двух сравниваемых записей. Это направлено на предотвращение ошибочного слияния индивидуальных и групповых записей (например, «Jenny Baker» и «Tom & Jenny Baker»).

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

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

INDEXING – Индексирование и извлечение признаков
Это основной этап применения. Когда поисковая система извлекает данные о сущностях (Entity Extraction) из веб-страниц, она должна выполнить процесс разрешения сущностей (Entity Resolution). Описанный механизм используется для:

• Дедупликации: Определения того, что информация, извлеченная из разных источников (например, разных каталогов или сайтов), относится к одной и той же сущности (компании, автору).
• Связывания с базой знаний: Сопоставления новой информации с уже существующими записями в Knowledge Graph.

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

• Набор структурированных или полуструктурированных записей (set of entries).
• Правила для Field Types (допустимость множественных значений).
• Пороговые значения для алгоритмов нечеткого сравнения.

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

• Идентификация дублирующихся записей.
• Объединенные канонические записи (single entry) о сущности.

На что влияет

• Конкретные типы контента и Сущности: Наибольшее влияние оказывается на обработку данных о сущностях (Entities) — компаниях (Local SEO), людях (E-E-A-T, авторы), продуктах (E-commerce).
• Конкретные ниши или тематики: Критично для локального бизнеса, где консистентность NAP-данных (Name, Address, Phone) необходима для видимости, а также для любых ниш, где важна точная идентификация авторов и организаций.
• Структурированные данные: Эффективность работы алгоритма повышается при наличии четко определенных типов полей (например, через Schema.org).

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

• Условия работы алгоритма: Применяется при обработке больших наборов данных для их очистки и консолидации (например, при обновлении Knowledge Graph).
• Триггеры активации: Процесс детального сравнения двух записей (анализ конфликтов) активируется только при обнаружении коллизии (Collision) — когда две разные записи имеют как минимум одно идентичное значение ключевого поля (анкоря), например, одинаковый телефон, email или URL.

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

1. Получение данных: Система получает набор записей для анализа (например, данные о бизнесах, извлеченные из разных сайтов).
2. Хеширование значений: Для всех непустых значений полей (non-blank field values) вычисляются Hash Values.
3. Обнаружение коллизий (Collision Detection): Система ищет совпадения хеш-значений между полями разных записей. Нахождение коллизии идентифицирует пару как потенциальный дубликат и запускает следующий этап.
4. Анализ конфликтов (Conflict Detection): Для пары потенциальных дубликатов система проверяет все остальные поля на наличие конфликтов. Проверка включает несколько стратегий:
   • Проверка допустимости множественных значений: Если значения полей различаются (например, разные адреса), проверяется, допускает ли Field Type множественные значения. Если да, конфликта нет.
   • Нечеткое сравнение (Fuzzy Matching): Если Field Type требует уникальности (например, Имя), система вычисляет метрики схожести:
     • $\text{Hamming Distance}$ (для оценки опечаток).
     • $\text{Sequence Alignment}$ (например, по алгоритму $\text{Needleman-Wunsch}$).
   • Проверка порогов: Метрики схожести сравниваются с порогами (Thresholds). Если схожесть достаточна, конфликт игнорируется.
   • Применение специальных правил: Проверка исключений, например, наличия «&» или «and» только в одной из записей (Claim 25).
5. Идентификация дубликатов: Если коллизия найдена и неразрешимые конфликты отсутствуют, записи помечаются как дубликаты.
6. Объединение (Опционально): Дублирующиеся записи могут быть автоматически объединены в одну каноническую запись.

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

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

Патент фокусируется на обработке структурированных или полуструктурированных данных.

• Структурные факторы: Система требует данные, представленные в виде записей с полями (Field Types) и значениями (Field Values). Это могут быть данные из баз данных, микроразметки Schema.org, каталогов.
• Контентные факторы (Значения Полей): Конкретные строковые или числовые значения полей (Имена, Адреса, Телефоны, Email, Идентификаторы). Эти данные используются как для хеширования (поиск точных совпадений), так и для анализа схожести (нечеткое сравнение).

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

• Hash Value: Вычисляется для быстрого выявления точных совпадений (коллизий).
• Hamming Distance: Измеряет количество различий в символах между двумя строками. Используется для оценки схожести при небольших расхождениях (опечатках).
  • Порог: Hamming Distance Threshold. Если расстояние меньше порога, строки считаются похожими.
• Sequence Alignment (Выравнивание последовательности): Измеряет глобальное выравнивание двух строк, часто с помощью алгоритма $\text{Needleman-Wunsch}$. Позволяет оценить схожесть при более сложных вариациях (сокращения, аббревиатуры).
  • Порог: Sequence Alignment Threshold. Если оценка выравнивания выше порога, строки считаются похожими.
• Правила Типов Полей (Field Type Rules): Предопределенные правила, указывающие, может ли данный тип поля иметь несколько значений для одной сущности.

1. Entity Resolution как комбинация точности и гибкости: Процесс разрешения сущностей требует баланса. Хеширование обеспечивает эффективность и точность поиска (через коллизии), в то время как анализ конфликтов с использованием нечеткого сравнения обеспечивает гибкость обработки реальных данных.
2. Точные совпадения как необходимый триггер: Алгоритм требует наличия хотя бы одного точно совпадающего поля (коллизии хешей) для инициации проверки. Это подчеркивает важность уникальных идентификаторов (Email, Телефон, GTIN) как анкорей для связывания данных.
3. Интеллектуальное разрешение конфликтов (Fuzzy Matching): Ядро изобретения — способность системы игнорировать незначительные различия. Использование $\text{Hamming Distance}$ и $\text{Sequence Alignment}$ позволяет обрабатывать опечатки, сокращения и вариации в форматировании.
4. Важность типизации данных (Field Types): Успешность объединения зависит от правил, привязанных к типу поля. Система различает поля, допускающие множественные значения (Телефоны), и поля с уникальным значением (Основное Имя).
5. Защита от ложных слияний: Наличие специальных правил (например, обработка символа «&» в Claim 25) указывает на то, что система настроена на высокую точность и предотвращение ошибочного объединения разных сущностей.

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

• Обеспечение абсолютной консистентности NAP (Local SEO): Критически важно использовать идентичные данные (Name, Address, Phone) во всех точках присутствия (сайт, Google Business Profile, каталоги). Точные совпадения (хеш-коллизии) являются основным триггером для запуска процесса объединения данных (Entity Resolution).
• Использование сильных уникальных идентификаторов: Всегда включайте уникальные идентификаторы (Email, ИНН/ОГРН, GTIN для товаров, @id и sameAs в Schema.org). Это обеспечивает надежные точки привязки для Collision Detection и гарантирует, что Google точно сопоставит записи.
• Стандартизация форматирования данных: Используйте полные и стандартизированные форматы для адресов, телефонов и имен авторов. Хотя система устойчива к небольшим вариациям благодаря Sequence Alignment, стандартизация снижает риск ошибок интерпретации и повышает уверенность системы.
• Четкое разделение сущностей: Убедитесь, что разные сущности (например, разные филиалы или разные авторы) имеют уникальные контактные данные. Использование общего телефона для разных филиалов может привести к некорректному слиянию данных, если система не сможет четко различить их по другим атрибутам.

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

• Использование вариативных данных для одной локации: Использование разных вариантов адреса или названия для одного и того же филиала в разных источниках. Это может привести к тому, что алгоритмы нечеткого сравнения не достигнут порога схожести, и система классифицирует данные как конфликтующие.
• Частое изменение ключевых идентификаторов: Регулярное изменение основных телефонных номеров, email или URL усложняет процесс Entity Resolution, так как теряются стабильные анкоря для хеш-коллизий.
• Создание «групповых» записей для индивидуумов: Не используйте символы «&» или «and» в именах авторов или названиях брендов, если речь идет об одной сущности. Патент явно указывает (Claim 25), что это может быть интерпретировано как признак разных сущностей (индивидуум против группы) и заблокировать слияние.

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

Патент подтверждает фундаментальную важность разрешения сущностей (Entity Resolution) для построения Knowledge Graph. В эру Entity-based SEO предоставление Google четких, непротиворечивых и легко сопоставимых данных является ключом к авторитетности и видимости. Долгосрочная стратегия должна включать управление цифровым следом бренда (Digital Footprint Management), гарантируя, что все упоминания во всех источниках могут быть корректно объединены Google в единый, авторитетный профиль сущности.

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

Сценарий: Разрешение сущности локального бизнеса (Entity Resolution в Local SEO)

1. Данные на входе: Google обрабатывает две записи из разных каталогов.
   • Запись А: «Ромашка ООО», ул. Ленина 10, +7(495)555-1212.
   • Запись Б: «ООО Ромашка Плюс», Ленина 10, +7(495)555-1212.
2. Хеширование и Коллизия: Система вычисляет хеши для телефонных номеров. Хеши совпадают (коллизия). Это запускает анализ конфликтов.
3. Анализ конфликтов (Адрес): Адреса совпадают (или имеют очень высокое выравнивание). Конфликта нет.
4. Анализ конфликтов (Имя): Система видит разные названия. Тип поля «Имя» требует уникальности. Система применяет алгоритм $\text{Needleman-Wunsch}$ к «Ромашка ООО» и «ООО Ромашка Плюс».
5. Результат: Алгоритм показывает высокое выравнивание последовательности (Sequence Alignment), превышающее порог. Конфликт не обнаружен.
6. Итог: Google идентифицирует записи как дубликаты и объединяет их в одну сущность, консолидируя сигналы ранжирования с обоих источников.