Алгоритм шинглов

Два отрывка про шинглы:

Происхождение копий документов в Интернете может быть различным. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам: быть представлен в разных кодировках и форматах; может содержать переменные вставки – рекламу или текущую дату.

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

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

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

Для решения этой задачи Udi Manber (Уди Манбер) (автор известной программы приближенного прямого поиска agrep) в 1994 году предложил идею [manber1994], а Andrei Broder (Андрей Бродер) в 1997 [broder] придумал название и довел до ума алгоритм «шинглов» (от слова shingles, «черепички, чешуйки»). Вот его примерное описание.

Для каждого десятисловия текста рассчитывается контрольная сумма (шингл). Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25. Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия – весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте!

Очевидно, что так можно определять процент перекрытия текстов, выявлять все его источники и т.п. Этот изящный алгоритм воплотил давнюю мечту доцентов: отныне мучительный вопрос «у кого студент списывал этот курсовик» можно считать решенным! Легко оценить долю плагиата в любой статье.

Чтобы у читателя не создалось впечатление, что информационный поиск исключительно западная наука, упомяну про альтернативный алгоритм определения почти-дубликатов, придуманый и воплощенный у нас в Яндексе [ilyinsky]. В нем используется тот факт, что большинство поисковых систем уже обладают индексом в виде инвертировнного файла (или инвертировнным индексом) и этот факт удобно использовать в процедуре нахождения почти-дубликатов.

Илья Сегалович. (с) Как работают поисковые системы. Качество индекса.
http://company.yandex.ru/articles/article10.html

* * *

Что такое контрольная сумма? fnv, md5, crc

Контрольная сумма (или “сигнатура”) - это уникальное число, поставленное в соответствие некоторому тексту и/или функция его вычисления. Функция вычисления контрольных сумм может преследовать несколько целей: например “невзламываемость” (минимизируется вероятность того, что по значению контрольной суммы можно подобрать исходный текст) или “неповторяемость” (минимизируется вероятность того, что два разных текста могут иметь одну контрольную сумму). Существует обширная литература по алгоритмам вычисления контрольных сумм, я упомяну здесь самые известные: fnv, md5, crc. Обычно более-менее все равно, какой из них выбрать, но в любом случае при выборе алгоритма его положительной стороной можно считать хорошее быстродействие.

…

Шинглы

Наиболее известным способом обработки почти-дубликатов в веб-поиске, изящно представленным Андреем Бродером в 1997 году, является метод “шинглов”. Очевидно, чтобы повысить вероятность того , чтобы в результате небольших изменения текста контрольная сумма не изменилась, можно попытаться выбрать из текста несколько подстрок. Шингл (от английского shingle - чешуйка, черепичка) это и есть подстрока текста, по которой происходит вычислений контрольной суммы.

Выбирать такие подстроки можно по-разному. Во-первых, можно брать разный шаг, например: символ, слово, предложение. Во-вторых, решить, как они должны идти - внахлест (как раз так и получаются именно “шинглы”), или встык. В-третьих, следует понять, какого размера должны быть подстроки (выбранный размер должен свести к минимуму случайные повторы, то есть должен быть достаточно большим, но при этом оставаться достаточно малым, чтобы типичные изменения текста не разрушили все сигнатуры, конкретные цифры я здесь не привожу, по понятным причинам они не должны афишироваться), и делать ли их фиксированного размера. И, в-четвертых, поскольку возможных подстрочек в тексте чересчур много, надо решить - какие запоминать, а какие выбрасывать.

Встык

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

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

Когда заведомо известно, что документ изменяется, пусть и сильно, но в малом количестве мест, этот тип сигнатур успешно применяют. Например: передача HTML-файлов или синхронизация репозитория исходных текстов программ и т.п.

К сожалению, в этом варианте сигнатур остается слишком много, если, конечно, не выбирать характерные точки, отстоящие друг от друга в среднем далеко. Но тогда строчки становятся слишком большого размера и алгоритм слишком неустойчив к небольшим изменениям в тексте. Для вероятностного сравнения двух документов все равно необходимо как-то сокращать выборку, и об этом позже.

Внахлест

Поначалу кажется, что считать контрольные суммы по всем строчкам внахлест - странная идея. Нам же нужно сократить объем данных для сравнения, а в таком варианте он страшно возрастает? Однако именно так мы гарантируем, что не пропускаем ни одной подстроки текста (заданной длины) и, при условии, что удастся придумать устойчивый способ отбирать шинглы, нам удастся очень точно отождествлять документы, имеющие совпадающие части.

Выборка. Какие шинглы запоминать?

Классический алгоритм Бродера предлагает отбирать либо фиксированное количество минимальных по значению шинглов, либо все шинглы, значение которых делятся на какое-нибудь небольшое число (10-30). В первом случае мы получаем фиксированную по размеру выборку (что иногда удобно) и приличный по размеру набор шинглов даже для относительно коротких документов, но нельзя будет судить о вложенности документов. Во втором случае число шинглов пропорционально размеру документа, то есть оно переменное, зато можно по набору шинглов оценивать такие интересные вещи, как вложение документов друг в друга или процент их пересечения. Наконец, последний самый “модный” алгоритм формирует фиксированную выборку, размер которой определяется заданным числом (например, 85 для веб-документов) разных независимых случайных функций, для каждой из которых запоминается ровно один шингл, минимальный по значению контрольной суммы. Этот подход комбинирует преимущества двух предыдущих.

Короткие документы. Что можно сделать?

Что делать с совсем короткими документами, для которых алгоритм отбора шинглов (например, второй) может вообще не выбрать ни одного подходящего? Или выбрать слишком мало? Я знаю два альтернативных решения: одно из них: закольцевать текст документа, то есть виртуально продолжить его начало после окончания, чтобы добиться получения необходимого количества шинглов даже в таких условиях. Второй подход, применяемый в Яндекс-Почте, состоит в использовании выборки, размер которой имеет логарифмическую зависимость от размера документа.

Супершингл

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

Поэтому на практике часто над набором шинглов документа считают еще одну контрольную сумму, так называемый “супершингл”. Очевидно, в этом случае совпавшими будут считаться только документы с полностью совпавшими наборами шинглов. Однако при правильном подборе алгоритма и его параметров этого может оказаться достаточно и для работы неплохого детектора рассылок. Задача будет сводиться к вычислению всего одного числа и нахождению его в простейшей базе данных.

Замена супершингла: лексические сигнатуры

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

Если локальные сигнатуры рассматривают документ изолированно от коллекции и пытаются извлечь несколько характерных слов, основываясь только на их статистике в самом документе - TF (характерный пример: взять 5 самых частотных слов в документе длиннее пяти букв и упорядочить их по убыванию частоты), то глобальные либо пытаются при анализе документа учитывать информацию о глобальной статистике слова - IDF, либо, вообще выбирают опорные слова, опираясь исключительно на уже существующий инвертированный индекс (см. метод Яндекса). Для работы глобальных методов необходимо как-то считать глобальную статистику слов, что в интенсивной антиспамовой системе вполне возможно, например в рамках байесовского подхода.

Илья Сегалович, Дмитрий Тейблюм, Александр Дилевский (с) Принципы и технические методы работы с незапрашиваемой корреспонденцией. http://company.yandex.ru/articles/spamooborona.xml