Алгоритм шинглов (Glikjnmb onuilkf)

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

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

Этапы

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

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

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

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

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

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

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

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

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

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

Литература

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

Ссылки

• Сравнительный анализ методов определения нечетких дубликатов для Web-документов
• Реализация алгоритма на языке Erlang