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

Алгоритм шинглов (от англ. shingles — чешуйки) — алгоритм, разработанный для поиска копий и дубликатов рассматриваемого текста в веб-документе. Инструмент для выявления плагиата.

Уди Манбер (англ.)русск. в 1994 г. первым в мире выразил идею поиска дубликатов, а в 1997 г. Андрей Бродер (англ.)русск. оптимизировал и довел её до логического завершения, дав имя данной системе — «алгоритм шинглов».

Этапы

Этапы, которые проходит текст, подвергшийся сравнению:

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

Канонизация текста

Канонизация текста приводит оригинальный текст к единой нормальной форме. Текст очищается от предлогов, союзов, знаков препинания, HTML тегов, и прочего ненужного «мусора», который не должен участвовать в сравнении. В большинстве случаев также предлагается удалять из текста прилагательные, так как они не несут смысловой нагрузки.

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

Разбиение на шинглы

Шинглы — выделенные из статьи подпоследовательности слов. Необходимо из сравниваемых текстов выделить подпоследовательности слов, идущих друг за другом по 10 штук (длина шингла). Выборка происходит внахлест, а не встык. Таким образом, разбивая текст на подпоследовательности, мы получим набор шинглов в количестве равному количеству слов минус длина шингла плюс один (кол_во_слов − длина_шингла + 1).

Вычисление хэшей шинглов

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

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

Литература

Manber, Udi, Finding Similar Files in a Large File System, USENIX Winter Technical conference, January, 1994, CA.