Алгоритм шинглов (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.