Алгоритм шинглів
Алгоритм шинглів (від англ. shingles — лусочки) — алгоритм, розроблений для пошуку копій та дублікатів розглянутого тексту в веб-документі. Інструмент для виявлення плагіату.
Уді Манбер в 1994 р. першим у світі висловив ідею пошуку дублікатів, а в 1997 р. Андрій Бродер оптимізував і довів її до логічного завершення, дав ім'я даній системі — «алгоритм шинглів».
Етапи
Етапи, які проходить текст, піддавшийся порівнянню:
- канонізація тексту;
- розбиття на шингли;
- обчислення гешів шинглів;
- випадкова вибірка 84 значень контрольних сум;
- порівняння, визначення результату.
Канонизація тексту
Канонизація тексту приводить оригінальний текст до єдиної нормальної форми. Текст очищається від прийменників, займенників, розділових знаків, HTML тегів, та іншого непотрібного «сміття», котрий не повинен брати участь у порівнянні. В більшості випадків також пропонується видаляти із тексту прикметники, так як вони не несуть смислового навантаження.
Також на етапі канонізації тексту можна приводити іменники до називному відмінку, однини, або залишати від них лише корінь.
Розбиття на шингли
Шингли — виділені із статті підпослідовності слів. Необхідино із порівнюваних текстів виділити підпослідовності слів, що йдуть один за одним по 10 штук (довжина шинглу). Вибірка відбувається внахлест, а не встик. Таким чином, розбиваючи текст на підпослідовності, ми отримаємо набір шинглів в кількості рівній кількості слів мінус довжина шингли плюс один (кіл_ть_слів - довж_шинглу + 1).
Обчислення гешів шинглів
Принцип алгоритму шинглів полягає в порівнянні випадкової вибірки контрольних сум шинглів (підпослідовностей) двох текстів між собою.
Проблема алгоритму полягає в кількості порівнянь, адже це безпосередньо позначається на продуктивності. Збільшення кількості шинглів для порівняння характеризується ростом операцій, що критично відіб'ється на продуктивності.
Література
- Manber, Udi, Finding Similar Files in a Large File System, USENIX Winter Technical conference, January, 1994, CA.