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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм шинглов — алгоритм, разработанный для поиска копий и дубликатов рассматриваемого текста в веб-документе, мощный инструмент, призванный бороться с проявлениями плагиата в интернете.

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

Этапы[править | править исходный текст]

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

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

Канонизация текста[править | править исходный текст]

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

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

Разбиение на шинглы[править | править исходный текст]

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

Вычисление хэшей шинглов[править | править исходный текст]

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

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

Ссылки[править | править исходный текст]