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

(Реализация на Python)

В этой статье я расскажу об алгоритме поиска нечетких дубликатов под названием «Алгоритм Шинглов». А так же реализую данный алгоритм на языке Python.

Почему я решил изучить данный алгоритм? Сам я являюсь SEO-шником, занимаюсь продвижением сайтов и так далее… Соответственно, моя работа заключается в изменении выдачи поисковой системы по определенному запросу. Но проработав более года в этом направлении меня заинтересовала внутренняя часть поисковых систем. Как они борются с поисковым спамом, как ранжируют документы и т.д. Поиск нечетких дубликатов позволяет поисковой системе исключить из выдачи клоны или частично похожие страницы (под словом частично я подразумеваю некоторое значение, при котором в конкретной поисковой системе два документа будут определяться как почти одинаковыми).

Одним из таких алгоритмов является «Алгоритм Шинглов» (шингл на английском означает чешуйка).

Немного теории

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

Обратите внимание, задачей не стоит определить абсолютное значение схожести объектов, а так же выделения в каждом из объектов схожих частей. Нам необходимо только предположить, являются ли объекты почти дубликатами или нет.

Где может применяться данный алгоритм?

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

Почти одинаковый текст

Рассмотрим задачу алгоритма на примере текста. Допустим, мы имеем файл с текстом в 8 абзацев. Делаем его полную копию, а затем переписываем только последний абзац. 7 из 8 абзацев второго файла являются полной копией оригинала.

Другой пример, посложнее. Если мы в копии оригинального текста перепишем каждое 5-6е предложение, то текст по-прежнему будет являться почти дублем.

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

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

И таким образом, при наличии множества почти одинакового текста мы распределим его на группы и предоставим пользователю ссылку на эти группы, вместо того, чтобы сваливать все в кучу.

Как работает алгоритм Шинглов?

Итак, мы имеем 2 текста и нам нужно предположить, являются ли они почти дубликатами. Реализация алгоритма подразумевает несколько этапов:

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

Теперь поконкретнее. В алгоритме шинглов реализовано сравнение контрольных сумм текстов. В своей реализации я использую CRC32, но применимы и другие, например SHA1 или MD5 и т.д. Как известно, контрольные суммы статических функций очень чувствительны к изменениям. Например, контрольные суммы двух следующих текстов будут в корне отличаться:

• Текст: «My war is over.» Контрольная сумма: 1759088479
• Текст: «My war is over!» Контрольная сумма: -127495474

Как сказал Джон Рэмбо: «My war is over». Но сказать он это мог по-разному, громко восклицая или тихо шепча, так и у нас, отличие второй фразы от первой заключается всего лишь в восклицательном знаке в конце фразы, но как видим, контрольные суммы абсолютно разные.

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

Следовательно, ставится задача: очистить текст от ненужных нам знаков и слов, которые не несут смысла при сравнении, это и называется «привести текст к канонической форме».

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

Давайте что-нибудь напрограммируем. Допустим, мы имеем два текста, занесем их в 2 переменных: source1 и source2. Нужно их почистить от ненужных символов и слов. Определим наборы стоп-слов и стоп-символов.

stop_symbols = '.,!?:;-\n\r()'

stop_words = (u'это', u'как', u'так',

u'и', u'в', u'над',

u'к', u'до', u'не',

u'на', u'но', u'за',

u'то', u'с', u'ли',

u'а', u'во', u'от',

u'со', u'для', u'о',

u'же', u'ну', u'вы',

u'бы', u'что', u'кто',

u'он', u'она')

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

Создадим функцию, которая будет производить канонизацию текста:

def canonize(source):

stop_symbols = '.,!?:;-\n\r()'

stop_words = (u'это', u'как', u'так',

u'и', u'в', u'над',

u'к', u'до', u'не',

u'на', u'но', u'за',

u'то', u'с', u'ли',

u'а', u'во', u'от',

u'со', u'для', u'о',

u'же', u'ну', u'вы',

u'бы', u'что', u'кто',

u'он', u'она')

return ( [x for x in [y.strip(stop_symbols) for y in source.lower().split()] if x and (x not in stop_words)] )

Функция canonize очищает текст от стоп-символов и стоп-слов, приводит все символы строки к нижнему регистру и возвращает список, оставшихся после чистки слов.

Вообще, приведение текста к единой канонической форме не ограничено действиями, которые я описал. Можно, например, каждое из существительных приводить к единственному числу, именительному падежу и т.д., для этого нужно подключать морфологические анализаторы русского языка (или других языков, где необходимы эти действия).

Итак, тексты у нас очищены от всего лишнего. Теперь необходимо разбить каждый из них на подпоследовательности — шинглы. На практике я применяю подпоследовательности длинной в 10 слов. Из выделенных нами шинглов далее будут находиться контрольные суммы.

Разбиение на шинглы будет происходить внахлест через одно слово, а не встык, т.е., имеем текст:

«Разум дан человеку для того, чтобы он разумно жил, а не для того только, чтобы он понимал, что он неразумно живет.»© В. Г. Белинский

После обработки нашей функцией текст примет следующий вид:

разум дан человеку того чтобы разумно жил того только чтобы понимал неразумно живет

Это и есть каноническая форма. Теперь нужно разбить ее на шинглы длиной в 10 слов. Так как шинглы составляются внахлест, то всего шинглов len(source)-(shingleLen-1), т.е. количество слов в тексте минус длина шинглов плюс 1.

Шинглы будут выглядеть следующим образом:

• Sh1 = разум дан человеку того чтобы разумно жил того только чтобы
• Sh2 = дан человеку того чтобы разумно жил того только чтобы понимал
• Sh3 = человеку того чтобы разумно жил того только чтобы понимал неразумно
• Sh4 = того чтобы разумно жил того только чтобы понимал неразумно живет

Напишем функцию, которая производит разбиение текста на шинглы:

def genshingle(source):

shingleLen = 10 #длина шингла

out = []

for i in range(len(source)-(shingleLen-1)):

out.append (' '.join( [x for x in source[i:i+shingleLen]] ).encode('utf-8'))

return out

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

Измененная функция:

def genshingle(source):

import binascii

shingleLen = 10 #длина шингла

out = []

for i in range(len(source)-(shingleLen-1)):

out.append (binascii.crc32(' '.join( [x for x in source[i:i+shingleLen]] ).encode('utf-8')))

return out

Наш пример выдаст следующие наборы контрольных сумм:

[1313803605, -1077944445, -2009290115, 1772759749]

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

def compaire (source1,source2):

same = 0

for i in range(len(source1)):

if source1[i] in source2:

same = same + 1

return same*2/float(len(source1) + len(source2))*100

Вот и все, функция нам вернет процент схожести двух текстов.

Скомпонованный код

# -*- coding: UTF-8 -*-

if __name__ == '__build__':

raise Exception

def canonize(source):

stop_symbols = '.,!?:;-\n\r()'

stop_words = (u'это', u'как', u'так',

u'и', u'в', u'над',

u'к', u'до', u'не',

u'на', u'но', u'за',

u'то', u'с', u'ли',

u'а', u'во', u'от',

u'со', u'для', u'о',

u'же', u'ну', u'вы',

u'бы', u'что', u'кто',

u'он', u'она')

return ( [x for x in [y.strip(stop_symbols) for y in source.lower().split()] if x and (x not in stop_words)] )

def genshingle(source):

import binascii

shingleLen = 10 #длина шингла

out = []

for i in range(len(source)-(shingleLen-1)):

out.append (binascii.crc32(' '.join( [x for x in source[i:i+shingleLen]] ).encode('utf-8')))

return out

def compaire (source1,source2):

same = 0

for i in range(len(source1)):

if source1[i] in source2:

same = same + 1

return same*2/float(len(source1) + len(source2))*100

def main():

text1 = u'' # Текст 1 для сравнения

text2 = u'' # Текст 2 для сравнения

cmp1 = genshingle(canonize(text1))

cmp2 = genshingle(canonize(text2))

print compaire(cmp1,cmp2)

# Start program

main()

Я показал именно реализацию ядра алгоритма, но его можно дорабатывать до бесконечности, увеличивая его производительность и точность сравнения.

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

Так же, для увеличения производительности при обработке больших объемов текста можно сравнивать не все полученные контрольные суммы, а только те, которые, например, делятся на 25, или любое целое число в пределах от 10 до 40. Как показали тесты, это дает значительный(!) прирост скорости и не сильно уменьшает точность, но только при обработке больших объемов.

Существуют модифицированные версии «Алгоритма шинглов» — «Алгоритм супершинглов» и «Алгоритма мегашинглов», их реализацию я представлю позже.

Материалы по теме:

1. Сравнительный анализ методов определения нечетких дубликатов для Web-документов Зеленков Ю.Г, Сегалович И.В. 2007

http://rcdl2007.pereslavl.ru/papers/paper_65_v1.pdf

2. Как работают поисковые системы Сегалович И.В.

http://company.yandex.ru/articles/article10.xml

3. Поиск нечетких дубликатов. Алгоритм шинглов для веб-документов

http://habrahabr.ru/blogs/algorithm/65944/