Python: Алгоритм Шинглов — поиск нечетких дубликатов текста

Сравнение шинглов помогает искать тексты с общими фрагментами: дубли публикаций, слегка отредактированные копии и близкие версии документа. Шингл — последовательность соседних слов. Мы сравним множества таких последовательностей и получим две явно названные метрики. Они оценивают совпадение формы текста, а не тождество смысла.

Нормализация под задачу

Пример принимает обычный текст, приводит Unicode к NFKC, регистр — через casefold, выделяет последовательности букв и цифр. Подчёркивание и пунктуация разделяют слова. Стоп-слова и морфологию намеренно не удаляем: потеря слова «не» может изменить смысл. Другие правила можно выбрать отдельно, но они должны совпадать для обоих документов.

HTML предварительно преобразуют в основной текст страницы подходящим парсером. Показанный токенизатор не очищает HTML и не отличает меню от статьи.

Окна перекрываются

Для слов a b c d и размера 2 получаем (a,b), (b,c), (c,d). Число окон равно max(0, n-k+1). Множество хранит каждый уникальный шингл один раз: повторение фрагмента не увеличивает его вес.

Dice и Jaccard дают разные числа

Пусть A и B — множества уникальных шинглов. Dice равен 2 × |A ∩ B| / (|A| + |B|); Jaccard — |A ∩ B| / |A ∪ B|. Оба симметричны и лежат между 0 и 1. Если в A и B по три шингла, а общих два, Dice равен 2/3, Jaccard — 1/2. «Процент похожести» без названия метрики неоднозначен.

Для коротких текстов обе выборки могут оказаться пустыми. Это не свидетельствует о стопроцентном совпадении. Здесь сравнение отклоняет такой вход: уменьшите размер окна осознанно или выберите другой метод.

Реализация на Python 3

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

"""Exact word shingles for plain text. Own reference, never executes archived code."""
import re
import unicodedata


def words(text):
    if not isinstance(text, str):
        raise TypeError('Expected plain text')
    normalized = unicodedata.normalize('NFKC', text).casefold()
    return re.findall(r'[^\W_]+', normalized, flags=re.UNICODE)


def shingles(tokens, size):
    if type(size) is not int or size < 1:
        raise ValueError('Shingle size must be a positive integer')
    return {tuple(tokens[i:i + size]) for i in range(max(0, len(tokens) - size + 1))}


def compare_texts(first, second, size=3):
    # Reject undersized texts: two empty sets do not establish text similarity.
    a_words, b_words = words(first), words(second)
    a, b = shingles(a_words, size), shingles(b_words, size)
    if not a or not b:
        raise ValueError('Both texts must contain at least size words')
    common = len(a & b)
    return {
        'first_shingles': len(a),
        'second_shingles': len(b),
        'common': common,
        'dice': 2 * common / (len(a) + len(b)),
        'jaccard': common / len(a | b),
    }


if __name__ == '__main__':
    result = compare_texts('раз два три четыре пять', 'раз два три четыре шесть', size=2)
    print(f"Dice: {result['dice']:.1%}; Jaccard: {result['jaccard']:.1%}")

Проверяем известный результат

result = compare_texts('a b c d', 'a b c e', size=2)
print(result['common'])   # 2
print(result['dice'])     # 0.6666666666666666
print(result['jaccard'])  # 0.5

Общие окна — (a,b) и (b,c). Объединение содержит четыре окна: Jaccard равен 50%. Пример в конце модуля использует другие тексты и получает другие значения.

Границы метода

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

Связь с алгоритмом сигнатур

В статье об алгоритме шинглов для веб-документов рассматривается сокращённая сигнатура из минимумов фиксированных хеш-преобразований. Это отдельный приближённый способ оценки сходства; он не равен произвольному случайному выбору любых шинглов каждого текста.

Наш браузерный инструмент использует Jaccard. Сравнивать его ответ с полем jaccard можно только при одинаковой нормализации и размере окна. Эта Python-реализация задаёт собственные правила разбора слов, поэтому различие настроек закономерно меняет ответ.

Научная публикация: Зеленков Ю. Г., Сегалович И. В. «Сравнительный анализ методов определения нечетких дубликатов для Web-документов», 2007. Код выше решает учебную задачу самостоятельно и не выдаёт себя за дословную реализацию публикации.