Что такое шингли?

joost:
Что такое шингли? в Гугле. Если можно дайте пример. Форум читал.

joost:
почитал! ничего не понял! а если в двух словах?

joost:
Что такое шингли? в Гугле. Если можно дайте пример. Форум читал.

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

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

Шинглы

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

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

Встык

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

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

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

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

Внахлест

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

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

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

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

Супершингл

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

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

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

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

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

joost:
MASe, где эту программу взять?