Ранее я показал элементарную реализацию алгоритма шинглов, позволяющую определять, являются ли два документа почти дубликатами или нет. В этот раз я поясню реализацию алгоритма, описанную Зеленковым Ю. Г. и Сегаловичем И.В. в публикации «Сравнительный анализ методов определения нечетких дубликатов для Web-документов».
Этим я начинаю серию из трех теоретических статей, в которых постараюсь доступным языком описать принцип алгоритмов шинглов, супершинглов и мегашинглов для сравнение веб-документов.
В публикации об алгоритмах поиска почти дубликатов предлагается версия алгоритма шинглов, использующая сигнатуру из 84 значений, рассчитанных по фиксированным для сравниваемых документов преобразованиям.
В первоначальном изложении выбран размер сигнатуры 84. Это параметр рассматриваемой схемы, а не универсально необходимое число для любого сравнения текстов. Ниже важно фиксировать одни и те же преобразования для всех документов и брать минимум каждого преобразования.
Рекомендую вооружиться ручкой и листком бумаги и фигурально представлять в виде рисунка каждый из этапов, описанных ниже.
Итак, алгоритм шинглов для веб-документов
Разберем, через какие этапы проходит текст, подвергшийся сравнению:
- канонизация текста;
- разбиение на шинглы;
- вычисление хэшей шинглов с помощью 84х статических функций;
- выбор минимумов 84 значений контрольных сумм;
- сравнение, определение результата.
1. Канонизация текста
Что такое канонизация текста я описывал в своей прошлой статье об алгоритме шинглов. Но в коротко повторюсь. Канонизация текста приводит оригинальный текст к единой нормальной форме.
Текст очищается от предлогов, союзов, знаков препинания, HTML тегов, и прочего не нужного «мусора», который не должен участвовать в сравнении. Удаление прилагательных не является обязательным этапом: они могут нести важный смысл. Нормализацию выбирают под задачу и применяют одинаково к обоим документам.
Так же на этапе канонизации текста можно приводить существительные к именительному падежу, единственному числу, либо оставлять от них только корни.
С канонизацию текста можно экспериментировать и экспериментировать, простор для действий тут широк.
На выходе имеем текст, очищенный от «мусора», и готовый для сравнения.
2. Разбиение на шинглы
Шинглы (англ) — чешуйки, выделенные из статьи подпоследовательности слов.
Необходимо из сравниваемых текстов выделить подпоследовательности слов, идущих друг за другом по 10 штук (длина шингла). Выборка происходит внахлест, а не встык.
Таким образом, разбивая текст на подпоследовательности, мы получим набор шинглов в количестве равному количеству слов минус длина шингла плюс один (кол_во_слов — длина_шингла + 1).
Напоминаю, что действия по каждому из пунктов выполняются для каждого из сравниваемых текстов.
3. Вычисление хэшей шинглов с помощью 84х статических функций
Вместо хранения полного множества шинглов можно построить короткую сигнатуру. Для каждого заранее выбранного хеш-преобразования вычисляют минимум по всем шинглам документа. Одно и то же преобразование применяется ко всем сравниваемым документам; это не независимый случайный выбор шинглов для каждого текста.
Проблема алгоритма заключается в количестве сравнений, ведь это напрямую отражается на производительности. При прямом попарном сравнении наборов размеров n и m потребуется до n × m сравнений. Это не экспоненциальный рост. Множества позволяют вычислять точное пересечение без полного попарного перебора.
Для каждого документа получаем 84 компоненты по одному общему правилу: компонента с номером i — минимум функции h_i по шинглам документа.
Нужен фиксированный набор параметризованных преобразований. Это не требование найти 84 разных криптографических алгоритма наподобие SHA1, MD5 и CRC32. Выбор семейства функций влияет на свойства приближения и должен быть одинаковым для всего корпуса.
После построения двух сигнатур сравниваются соответствующие 84 компоненты. Само сравнение занимает 84 проверки равенства; подготовка сигнатур всё равно требует обработки шинглов и не становится бесплатной.
4. Выбор минимумов 84 значений контрольных сумм
Для каждого преобразования h_i просмотрите шинглы документа и сохраните наименьший результат. При одинаковом документе и тех же фиксированных преобразованиях сигнатура воспроизводится. Случайность относится к выбору семейства преобразований, а не к произвольному выбору нового значения при каждом сравнении.
Итак, на выходе имеем набор из минимальных значений контрольных сумм шинглов для каждой из хэш функций.
5. Сравнение, определение результата
Разделите число совпавших компонентов на длину сигнатуры. Это приближённая оценка сходства множеств при подходящих MinHash-преобразованиях, а не точный Dice из учебного Python-примера. Точное значение Jaccard получают через пересечение и объединение полных множеств. Размер сигнатуры и свойства выбранных преобразований влияют на погрешность.
Заключение
Надеюсь, я доступно смог изложить теорию нахождения почти дубликатов для веб-документов, описанную в публикации Зеленкова Ю. Г. и Сегаловича И.В. не вдаваясь в особенности реализации на конкретном языке программирования.
Во второй статье цикла я собираюсь описать алгоритм супершинглов для веб-документов.
Надеюсь было интересно, удачи.
Разницу между точным Jaccard и MinHash-сигнатурой также показывает материал курса Stanford CS336: Jaccard и MinHash. Здесь он используется для уточнения понятия сигнатуры, а не как источник числа 84 из первоначальной статьи.