Пошук нечітких дублікатів

Опишемо доступною мовою принцип алгоритмів шинглів, супершинглів та мегашинглів для порівняння веб-документів.

Чому саме 84? Використання 84-х випадково обраних значень контрольних сум дозволить легко модифікувати алгоритм до алгоритму супершинглів і мегашинглів, які набагато менш ресурсомісткі. Їх я опишу найближчим часом.

Рекомендую озброїтися ручкою та листком паперу та фігурально представляти у вигляді малюнка кожен із етапів, описаних нижче.

Отже, алгоритм шинглів для веб-документів

Розберемо, через які етапи проходить текст, який зазнав порівняння:

  1. канонізація тексту;
  2. розбиття на шингли;
  3. обчислення хешів шинглів за допомогою 84 статичних функцій;
  4. випадкова вибірка 84 значень контрольних сум;
  5. порівняння, визначення результату.

1. Канонізація тексту

Що таке канонізація тексту я описував у своїй колишній статті про алгоритм шинглів. Але коротко повторюся. Канонізація тексту наводить оригінальний текст до єдиної нормальної форми.

Текст очищається від прийменників, спілок, розділових знаків, HTML тегів, та іншого не потрібного «сміття», який не повинен брати участь у порівнянні. Найчастіше також пропонується видаляти з тексту прикметники, оскільки де вони несуть смислового навантаження.

Так само на етапі канонізації тексту можна приводити іменники до називного відмінка, однини, або залишати від них тільки коріння.

З канонізацію тексту можна експериментувати і експериментувати, простір дій тут широкий.

На виході маємо текст, очищений від «сміття», готовий для порівняння.

дублікатів

2.Розбиття на шингли

Шингли (англ) - лусочки, виділені із статті підпослідовності слів.

Необхідно з текстів, що порівнюються, виділити підпослідовності слів, що йдуть один за одним по 10 штук (довжина шингла). Вибірка відбувається внахлест, а чи не встик.

Таким чином, розбиваючи текст на підпослідовності, ми отримаємо набір шинглів у кількості рівної кількості слів мінус довжина шингла плюс один (кількість слів — довжина шингла + 1).

Нагадую, що дії щодо кожного з пунктів виконуються для кожного з порівнюваних текстів.

пошук

3. Обчислення хешів шинглів за допомогою 84 статичних функцій

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

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

Пропонується представити текст у вигляді набору контрольних сум, розрахованих через 84-х унікальні між собою статичні хеш функції.

Поясню: для кожного шингла розраховується 84 значення контрольної суми через різні функції (наприклад, SHA1, MD5, CRC32 і т.д., всього 84 функції). Отже кожен із текстів буде представлений, можна сказати, у вигляді двовимірного масиву з 84х рядків, де кожен рядок характеризує відповідну з 84х функцій контрольних сум.

З отриманих наборів будуть випадково відібрані 84 значення для кожного з текстів і порівняні між собою відповідно до функції контрольної суми, через яку кожен з них був розрахований. Таким чином, для порівняннябуде необхідно виконати лише 84 операції.

дублікатів

4. Випадкова вибірка 84 значень контрольних сум

Як я описував вище, порівнювати елементи кожного з 84 масивів між собою — ресурсомістко. Для збільшення продуктивності виконаємо випадкову вибірку контрольних сум для кожного з 84-х рядків двовимірного масиву для обох текстів. Наприклад, вибиратимемо найменше значення з кожного рядка.

Отже, на виході маємо набір із мінімальних значень контрольних сум шинглів для кожної з хеш функцій.

нечітких

5. Порівняння, визначення результату

І останній етап – порівняння. Порівнюємо між собою 84 елементи першого масиву з відповідними 84 елементами другого масиву, вважаємо відношення однакових значень, з цього отримуємо результат.

шинглів

Алгоритм шинглів на PHP

Алгоритм шинглів використовується для пошуку схожих документів і визначення ступеня схожості двох текстів. Наприклад, у вас є сотня текстів (припустимо, це статті чи новини) і вам потрібно знайти рерайти. Тобто. тексти, які абсолютно ідентичні між собою, але певною мірою схожі. Алгоритм шинглів можна використовувати, щоб знайти “передрук” текстів або, наприклад, щоб згрупувати новини за сюжетами (привіт сервісу Яндекс.Новини). Незважаючи на те, що у своєму базовому виконанні алгоритм досить простий, існує безліч способів зробити його складним і безліч різних варіацій - супершингли, мегашингли ... Ми реалізуємо базовий варіант цього алгоритму без особливих проблем на PHP.

Опис алгоритму

Отже, ми маємо два тексти. Нам потрібно визначити, чи вони схожі. Що ми робимо?

  1. Очищаємо тексти від будь-якого "сміття". Це називається нормалізація чи канонізація.Суть у тому, щоб прибрати з тексту всі розділові знаки, прийменники, перевести слова в нижній регістр.
  2. Розбиваємо текст на шингли. Це означає розбити текст на послідовності слів. Один шингл (послідовність) міститиме припустимо 4 слова.
  3. Обчислюємо контрольні суми шинглів. За допомогою функцій crc32, md5 чи sha1.
  4. Дивимося скільки шинглів (послідовностей слів) присутні в обох текстах. Для цього потрібно лише знайти контрольні суми, які є і в першому тексті і в другому.

Демонстрація алгоритму

Давайте подивимося, як працює алгоритм на невеликому прикладі. Припустимо, у нас є два якихось тексти.

Щоб мати струнку фігуру, ви повинні займатися спортом та правильно харчуватися. Приходьте в спортивний зал "Вогник" - будьте здоровими та красивими!

Дівчата! Приходьте до спортивного клубу “Метелик”. У нас багато тренажерів та досвідчені інструктори, які підкажуть вам як займатися спортом та правильно харчуватися, щоб мати струнку фігуру та бадьорий дух.

В наявності рерайт. Тексти не однакові, але схожі. Візьмемо перший текст і очистимо його, вийде таке:

щоб мати струнку фігуру ви повинні займатися спортом правильно харчуватися приходьте спортивний зал вогник будьте здоровими здоровими

дівчата приходьте спортивний клуб метелик нас багато тренажерів досвідчені інструктори які підкажуть вам займатися спортом правильно харчуватися щоб мати струнку фігуру бадьорий дух

Складаємо шингли (послідовності слів). Нехай один шингл у нас складатиметься з 3 слів. Тоді для першого тексту ми отримаємо такі послідовності: