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

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

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

Этапы

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

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

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

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

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

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

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

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

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

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

Ссылки

• http://rcdl2007.pereslavl.ru/papers/paper_65_v1.pdf Сравнительный анализ методов определения нечетких дубликатов для Web-документов

Связать^?

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