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

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

Full-length video fingerprint (Полноформатный отпечаток видео)

Конечный результат процесса. Очень компактный элемент данных (например, 640 байт), представляющий характеристики всего видео, полученный путем применения Weighted Min-Hash к Master Histogram.

Master Histogram (Мастер-гистограмма)

Агрегированная структура данных, кодирующая частоту признаков субгистограмм для всего видео. Часто является конкатенацией subhistograms. Состоит из "бинов" (Bins) и их счетчиков (Counts).

Min-Hash (Мин-хеш)

Техника для быстрой оценки сходства наборов данных. В контексте патента, это процедура, применяемая к битовому вектору признаков сегмента. Она включает перестановку битов и запись позиции первого ненулевого значения (Min-Hash Value).

Partition (Партиция/Раздел)

Группа (подмножество) Subfingerprints, обычно соответствующая определенному временному интервалу видео (например, 30 секунд), используемая для генерации Subhistogram.

Subfingerprint (SFP) (Суб-отпечаток)

Элемент данных, кодирующий признаки соответствующего короткого сегмента видео (например, 4 секунды). В патенте это вектор значений Min-Hash.

Subhistogram (Субгистограмма)

Структура данных, кодирующая частоту признаков subfingerprint для группы SFP в определенном временном окне (партиции). Например, как часто определенное значение Min-Hash встречается в определенной позиции SFP.

Weighted Min-Hash (Взвешенный Мин-хеш)

Вариант процедуры Min-Hash, применяемый к Master Histogram. Элементам гистограммы (бинам) присваиваются веса (на основе их частоты/Counts), что влияет на вероятность их выбора в качестве минимального значения хеша.

Similarity Factor (Фактор схожести)

Метрика, используемая для сравнения двух финальных отпечатков. В патенте описывается как вариация расстояния Хэмминга (процент совпадающих элементов в векторах отпечатков).

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

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

1. Доступ к множеству subfingerprints (SFP) видео, где каждый SFP кодирует признаки сегмента.
2. Генерация гистограммы (histogram), которая кодирует частоту признаков SFP.
3. Применение процедуры хеширования (hashing procedure) к гистограмме для генерации full-length video fingerprint.

Ядром изобретения является конвейер трансформации от локальных признаков видео (SFP) к высоко сжатому глобальному отпечатку через промежуточное статистическое представление (гистограмму).

Claim 4 (Зависимый от 1): Детализирует иерархическую генерацию гистограммы.

1. Генерация множества subhistograms, каждая из которых кодирует частоту признаков для подмножества SFP (партиции).
2. Конкатенация (объединение) subhistograms.

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

Claim 8 (Зависимый от 1): Детализирует процедуру хеширования как Weighted Min-Hash.

1. Присвоение веса (weight) каждому из множества признаков гистограммы.
2. Применение первой хеш-функции к ряду "измененных версий" (altered versions) каждого признака гистограммы для генерации множества выходных значений.

Claim 9 (Зависимый от 8): Уточняет, что количество "измененных версий" признака основано на присвоенном ему весе.

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

Claim 10 (Зависимый от 8): Детализирует аспект "Min-Hash".

1. Определение наименьшего выходного значения (smallest output) для первой хеш-функции.
2. Заполнение первой записи финального отпечатка тем входным значением (hash input), которое привело к этому наименьшему выходу.

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

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

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

INDEXING – Индексирование и извлечение признаков
Основной этап применения. Процесс генерации full-length fingerprint происходит во время обработки и индексирования видеофайла. Это включает:

1. Извлечение низкоуровневых признаков (например, вейвлет-коэффициенты).
2. Генерацию subfingerprints, histograms и финального отпечатка.
3. Сохранение этих данных в соответствующих базах данных (Fingerprint Database).
4. Кластеризацию отпечатков для идентификации дубликатов.

RANKING / METASEARCH / RERANKING
Сами отпечатки напрямую не являются сигналом ранжирования по качеству или релевантности. Однако результаты кластеризации используются на этих этапах косвенно:

• Дедупликация и Разнообразие: Системы ранжирования используют данные о кластерах для предотвращения показа нескольких почти идентичных видео в ответ на один запрос.
• Каноникализация: Выбор лучшей (канонической) версии видео из кластера дубликатов для показа в выдаче.
• Консолидация сигналов: Потенциальное объединение сигналов ранжирования (просмотры, ссылки) от дубликатов к канонической версии.

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

• Необработанные данные видео (пиксельные значения кадров и, возможно, аудио данные).

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

• Full-length video fingerprint (очень компактный, например, 640 байт).
• Данные кластеризации (идентификаторы кластеров, связывающие похожие видео).

На что влияет

• Конкретные типы контента: Влияет исключительно на видеоконтент.
• Специфические запросы: Не влияет на понимание или обработку поисковых запросов, но влияет на состав выдачи по любым запросам, где есть дублирующиеся видео.
• Конкретные ниши или тематики: Применяется универсально, но особенно важен в нишах с высоким уровнем дублирования (новости, музыка, UGC).

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

• Триггеры активации: Процесс генерации отпечатка активируется при загрузке (ingest) нового видео в систему или при его индексации.
• Частота применения: Генерация отпечатков происходит один раз для видео. Кластеризация может выполняться инкрементально при добавлении новых видео или периодически в пакетном режиме для всей базы данных.

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

Процесс состоит из четырех основных стадий.

Стадия 1: Генерация суб-отпечатков (Subfingerprint Generation)

1. Сегментация: Видео делится на перекрывающиеся сегменты (например, 4 секунды с шагом 0.25 секунды).
2. Извлечение признаков (Transform): К сегменту применяется преобразование (например, Haar wavelet transform) для генерации массива коэффициентов.
3. Квантование (Quantization): Коэффициенты квантуются (например, сохраняются знаки N наибольших по модулю коэффициентов, остальные обнуляются).
4. Кодирование: Квантованный массив преобразуется в разреженный битовый вектор.
5. Применение Min-Hash: К битовому вектору применяется набор из k фиксированных перестановок. Для каждой перестановки определяется позиция первого ненулевого бита (Min-Hash Value). Результат — SFP, состоящий из k значений.

Стадия 2: Генерация гистограмм (Histogram Generation)

1. Партиционирование SFP: Массив всех SFP видео делится на партиции (например, 120 SFP, соответствующие 30 секундам видео).
2. Создание субгистограмм: Для каждой партиции создается subhistogram. Она подсчитывает, как часто конкретное значение Min-Hash встречается на конкретной позиции в SFP внутри этой партиции.
3. Создание мастер-гистограммы: Subhistograms объединяются (конкатенируются) в master histogram. Она представляется в виде набора "бинов" (bins), где каждый бин идентифицирует признак и его частоту (Count).

Стадия 3: Генерация финального отпечатка (Fingerprint Generation)

Применяется процедура Weighted Min-Hash.

1. Присвоение весов: Каждому бину в master histogram присваивается вес (w), обычно равный его счетчику (Count).
2. Применение взвешенного хеширования: Процесс повторяется s раз с использованием s разных начальных значений (seeds) для хеш-функции:
   • Для каждого бина генерируется w его измененных версий.
   • Хеш-функция с текущим seed применяется ко всем версиям всех бинов.
   • Определяется, какая версия какого бина дала наименьший результат хеширования.
   • Идентификатор этого входа записывается как один элемент финального отпечатка.
3. Формирование отпечатка: Набор из s элементов формирует full-length video fingerprint.

Стадия 4: Кластеризация (Clustering)

1. Расчет схожести: Вычисляется фактор схожести (similarity factor) между парами отпечатков (например, процент совпадающих элементов – расстояние Хэмминга).
2. Идентификация пар: Идентифицируются пары видео, чей фактор схожести превышает порог. Может использоваться Locality Sensitive Hashing (LSH).
3. Применение алгоритма кластеризации: Похожие видео группируются в кластеры (например, с помощью leader clustering).

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

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

Система фокусируется исключительно на содержимом видеофайла.

• Мультимедиа факторы / Контентные факторы (Видео): Основные входные данные — это необработанные данные видеокадров (пиксельные значения). Эти данные преобразуются в домен коэффициентов (например, wavelet coefficients), которые характеризуют пространственные и временные особенности видео (границы объектов, яркость, градиенты). Патент упоминает возможность использования audio features, но детализирует обработку визуальных данных.

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

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

• Min-Hash Value: Метрика, получаемая на Стадии 1. Позиция первого ненулевого бита в векторе признаков после применения перестановки.
• Частота признаков (Counts): Метрика, используемая в гистограммах (Стадия 2). Подсчитывает количество вхождений определенных Min-Hash Values.
• Вес (Weight 'w'): Метрика, используемая на Стадии 3. Присваивается бинам гистограммы и обычно равен счетчику (Counts) этого бина. Определяет влияние признака на финальный отпечаток.
• Наименьший результат хеширования (Smallest Hash Output): Значение, определяемое в ходе процедуры Weighted Min-Hash.
• Similarity Factor (Фактор схожести): Метрика для сравнения двух финальных отпечатков (Стадия 4). Рассчитывается как процент совпадающих элементов (вариация расстояния Хэмминга).
• Алгоритмы анализа: Используются Min-Hash, Weighted Min-Hash, Locality Sensitive Hashing (LSH) и алгоритмы кластеризации.

1. Идентификация контента, а не оценка качества: Патент описывает механизм для точной идентификации содержимого видеофайла и поиска дубликатов. Он не предлагает методов для оценки качества, релевантности или авторитетности видеоконтента.
2. Иерархическое сжатие для масштабируемости: Ключевая особенность — многоуровневое сжатие данных (SFP -> Histograms -> Fingerprint). Это позволяет представить видео любой длины в виде очень компактного отпечатка (например, 640 байт), что критически важно для сравнения миллиардов видео.
3. Устойчивость к модификациям и временным сдвигам: Механизм устойчив к различиям в кодировании, разрешении и шуме благодаря использованию вейвлет-преобразований и квантования. Он также устойчив к обрезке видео по времени благодаря анализу перекрывающихся сегментов и агрегации в гистограммы.
4. Роль Weighted Min-Hash: Использование Weighted Min-Hash гарантирует, что наиболее частые и устойчивые признаки видео оказывают наибольшее влияние на финальный отпечаток, повышая точность идентификации.
5. Инфраструктурное значение для SEO: Для SEO-специалистов важно понимать, что Google обладает мощными инструментами для идентификации видеоконтента. Попытки манипулировать выдачей путем загрузки множества слегка измененных копий видео неэффективны, так как система их обнаружит, кластеризует и применит дедупликацию.

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

Хотя патент носит инфраструктурный характер и не дает прямых рекомендаций по ранжированию, он определяет правила игры для Видео SEO:

• Фокус на создании уникального видеоконтента: Поскольку Google может эффективно идентифицировать дубликаты на техническом уровне, стратегический приоритет должен отдаваться созданию уникального визуального ряда, а не переупаковке существующего.
• Понимание каноникализации видео: Необходимо понимать, что если одно и то же видео существует в нескольких местах (YouTube, сайт компании), Google идентифицирует их как дубликаты и выберет каноническую версию для ранжирования. Усилия должны быть направлены на то, чтобы ваша версия была признана канонической.
• Существенная переработка при использовании чужого контента: Если используются фрагменты чужого видео (в рамках добросовестного использования), они должны быть значительно переработаны и дополнены уникальным контентом, чтобы финальный отпечаток существенно отличался от оригинала.

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

• Попытки "уникализации" поверхностными правками: Добавление рамок, логотипов, изменение цветокоррекции или перекодирование видео неэффективны. Система устойчива к этим изменениям и классифицирует видео как дубликат.
• Добавление коротких интро/аутро к дублированному контенту: Если основная часть видео (например, 90%) является дубликатом, добавление уникальных заставок не сделает все видео уникальным. Большинство Subfingerprints совпадут, что приведет к высокому фактору схожести финальных отпечатков.
• Массовая загрузка слегка измененных копий: Создание множества копий одного видео с небольшими изменениями не даст преимуществ в ранжировании. Система кластеризует их вместе.

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

Патент подтверждает технические возможности Google по идентификации и управлению видеоконтентом в огромных масштабах. Он подчеркивает, что Google анализирует фактическое содержание видео на глубоком уровне, а не полагается только на метаданные. Это фундаментальная технология для систем типа Content ID и обеспечения качества поиска за счет дедупликации. Для долгосрочной стратегии Video SEO это означает, что инвестиции в уникальность самого видеоряда имеют первостепенное значение.

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

Сценарий: Каноникализация вирусного видео

1. Ситуация: Появляется популярное вирусное видео. Пользователь А загружает оригинал. Пользователи Б и В скачивают его и перезагружают на свои каналы. Пользователь Б добавляет 5-секундное интро. Пользователь В меняет битрейт.
2. Обработка (Индексация): Google обрабатывает все три видео. Для каждого генерируются Subfingerprints, Master Histogram и Full-length fingerprint.
3. Кластеризация: Система сравнивает отпечатки. Несмотря на интро у Б и изменение битрейта у В, факторы схожести между всеми тремя видео превышают порог (например, 95% совпадение отпечатков).
4. Результат: Все три видео помещаются в один кластер. Google выбирает каноническую версию (вероятно, видео Пользователя А).
5. Влияние на SEO: В результатах поиска преимущественно будет показываться каноническая версия (Пользователь А). Сигналы от видео Б и В могут быть консолидированы к версии А.