Почти обнаружение дубликатов в потоках данных

В настоящее время я работаю над потоковым API, который генерирует много текстового контента. Как и ожидалось, API выдает много дубликатов, и у нас также есть бизнес-требование фильтровать почти дублирующиеся данные.

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

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

Я как бы застрял и ищу указатели о том, как действовать, и документы/реализации, на которые я мог бы посмотреть?


streaming duplicates filtering bloom-filter
person thickblood    schedule 27.04.2012    source источник
comment
Не могли бы вы дать некоторую информацию о текстовом содержании? Является ли содержимое большим или маленьким документом (100-1K символов), это только английский язык или смесь языков, это текст или html или xml или ..., сколько документов генерируется в час, какова продолжительность временного окна вам нужно провести дедупликацию?   -  person Jeff Kubina    schedule 29.04.2012
comment
Привет, текстовое содержимое просто маленький текст! наверное меньше 200 символов. Есть около 100-200 документов в секунду. надеюсь, это поможет   -  person thickblood    schedule 29.04.2012

Ответы (2)


arrow_upward
6
arrow_downward

  1. Во-первых, нормализуйте текст до всех строчных (или прописных) символов, замените все небуквенные пробелы пробелами, сожмите все множественные пробелы в один, удалите начальные и конечные пробелы; для скорости я бы проделал все эти операции за один проход текста. Затем возьмите хэш MD5 (или что-то более быстрое) полученной строки. Выполните поиск в базе данных хэша MD5 (в виде двух 64-битных целых чисел) в таблице, если он существует, это точный дубликат, если нет, добавьте его в таблицу и перейдите к следующему шагу. . Вы захотите состарить старые хэши в зависимости от времени или использования памяти.

  2. Чтобы найти близкие дубликаты, нормализованную строку необходимо преобразовать в потенциальные подписи (хэши подстрок), см. документ SpotSigs и запись в блоге Грега Линдена. Предположим, что подпрограмма Sigs() делает это для заданной строки, то есть, учитывая нормализованную строку x, Sigs(x) возвращает небольшой (1-5) набор 64-битных целых чисел. Вы можете использовать что-то вроде алгоритма SpotSigs для выбора подстрок в тексте для подписей, но создание собственного метода выбора может работать лучше, если вы знаете что-то о своих данных. Вы также можете ознакомиться с алгоритмом simhash (код находится здесь).

  3. Учитывая Sigs(), проблему эффективного поиска ближайших дубликатов обычно называют проблемой соединений по сходству. В статье SpotSigs описываются некоторые эвристики для сокращения количества наборов, с которыми необходимо сравнивать новый набор, как и в методе simhash.

person Jeff Kubina    schedule 01.05.2012

arrow_upward
1
arrow_downward

http://micvog.com/2013/09/08/storm-first-story-detection/ содержит несколько замечаний по реализации

person Ashwin Jayaprakash    schedule 18.09.2013