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

VitaliyRodnenko, 19.01.2009

В этой статье я расскажу об алгоритме поиска нечетких дубликатов под названием «Алгоритм Шинглов». А так же реализую данный алгоритм на языке 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. Как показали тесты, это дает значительный(!) прирост скорости и не сильно уменьшает точность, но только при обработке больших объемов.

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

Скачать алгоритм шинглов на Python.

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

Спонсор поста: Агентство «Web++» — продвижение и создание сайтов в Волгограде.

Подписаться на обновления блога

Вам понравился наш блог, хотите следить за обновлениями? Подпишитесь на RSS рассылку или рассылку по электронной почте. Так же вы можете следить за нами в Twitter.

Категории: Python | Комментировать

Комментарии (31)

  1. Николай / 19.01.2009 в 23:22

    Большое спасибо, очень качественный пост (я бы даже сказал, полноценная статья). Что сейчас редкость в рунете. Давно искал нечно подобное для сравнения текстов.

  2. Сергей / 22.01.2009 в 01:32

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

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

    какие-то либы можете порекомендовать на эту тему ?

  3. GogA / 22.01.2009 в 05:28

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

    Но эта статья заслуживает глубого прочтения, а не поверхностного изучения в 4 утра :) Добавил в закладки, почитаю про алгоритм Шилингов днём. Спасибо за примеры.

  4. Skaizer / 22.01.2009 в 11:17

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

  5. Андрей / 22.01.2009 в 11:56

    Возникает вопрос: а раз этот алгоритм известен, то как его обмануть с минимальным вмешательством в исходный текст?

  6. Skaizer / 22.01.2009 в 12:10

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

  7. стас агарков / 22.01.2009 в 12:44

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

  8. Skaizer / 22.01.2009 в 13:05

    Стас агарков, смотря что вы понимаете под понятием «текст разной длины».
    Если сравнения двух текстов разной длины, то изменения в алгоритм можно никакие не вносить.
    А если особенности сравнения текстов различной длины данным алгоритмом, то нужно проводить тестирование: сравнивать производительность и точность при изменении длины шингла на различных объемах текста. Тогда можно будет построить оптимальную таблицу соответствия параметров алгоритма к длинам текстов.

  9. aRs / 22.01.2009 в 14:00

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

  10. Skaizer / 22.01.2009 в 14:19

    В случае сравнении текстов категорично разной длины может нужно фиксировать позицию шингла (слов)?

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

  11. lightcaster / 22.01.2009 в 15:07

    Хорошая статья. Метод прост и сердит. Однако, для качественного поиска — очень грубый . Для лучших результатов можно подключить токенизацию и морфологию:
    1) Выделить токены, отсеев лишнее
    2) Разбить на блоки
    3) Провести лематизацию (и, возможно, морфологическую разметку)
    4) На основе этих данных строить сигнатуры для блоков

    ps на счет морфологии лучше смотреть в сторону http://www.aot.ru. В морфологии статистические методы значительно уступают словарным, так что pymmorph не будет эффективен.

  12. Skaizer / 22.01.2009 в 18:36

    lightcaster, спасибо, полезные советы! Я реализовал крайне простую канонизацию текста, чтобы показать ее смысл.

  13. Max Stoun / 25.01.2009 в 00:27

    Здравствуйте.

    Подскажите пожалуйста. Я пытаюсь написать аналогичный код на c#(для саморазвития — я начинающий программист). Объясните строки:

    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

    Я так понимаю — на вход получаем, к примеру

    source1 = 10204
    soruce2 = 54321

    потом получим цикл i=0…4, и будем сравнивать
    если source1[0] in source2 // то есть 1 in 54321 = true
    если source1[1] in source2 //то есть 0 in 54321 = false
    и тд ?

    С уважением Максим
    P.S. Просто python я не особо понимаю, а попытка поюзать гугл у меня провалилась..

  14. Skaizer / 25.01.2009 в 01:31

    Здравствуйте, Максим. В качестве аргументов функции compaire поступают 2 списка с хэшами выделенных ранее подпоследовательностей для двух текстов. Далее мы находим пересечение этих списков, т.е. количество вхождений одного списка в другой. В переменной same хранится это количество.
    А строкой:

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

    мы считаем в процентах отношение найденных одинаковых хэшей к общему количеству хэшей для двух текстов. И так как одинаковые хэши у нас встречаются как в первом, так и во втором текстах, то удваиваем переменную same:

    same*2

    PS: список в python чем-то похож на массив в C++ :-)

  15. Skaizer / 25.01.2009 в 01:37

    PPS: можете постучать в аську 86пять883 или в GTalk simskaiz[at]gmail.com, расскажу поподробнее.

  16. Андрей / 29.01.2009 в 12:06

    2 Андрей:

    Делаем дор, наполняем его распространёнными модифицированными текстами с разной «глубиной» шинглирования, смотрим на результат его работы, на основе статистики определяем оптимальный алгоритм модификации текста :)

  17. Jack / 26.02.2009 в 00:11

    Друзья, а если тексты достаточно короткие?
    Ну скажем от 5 до 50 слов :) Анекдоты, цитаты, афоризмы и пр.
    Можно ли как-нибудь выявить схожесть двух таких текстов между собой?

  18. Skaizer / 26.02.2009 в 00:34

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

  19. Владимир / 31.03.2009 в 10:00

    Skaizer вы обещали рассказать об алгоритме супершинглов, когда от вас можно ждать его? Или хотя бы скажите где можно посмотреть? Спасибо.

  20. Skaizer / 31.03.2009 в 11:18

    Да, к сожалению времени сейчас нет абсолютно, посты в блог пишу реже. Как загружен буду поменьше, обязательно напишу про него. А пока почитать про него можно по ссылкам: http://www.spamtest.ru/document.html?context=15932&pubid=32 и http://rcdl2007.pereslavl.ru/papers/paper_65_v1.pdf .
    В статье постараюсь поподробнее расписать метод реализации этого алгоритма.

  21. Дмитрий / 16.05.2009 в 10:12

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

  22. Dennis / 02.08.2009 в 13:04

    Т.е. как я понял здесь не применяется семантика. Думаю посиковики должны стремиться к оценке дубликатов в которых была сделана подмена слов синонимами.

  23. Skaizer / 06.08.2009 в 11:38

    Да, в данном варианте семантика не применяется.

  24. Проект 110 кв / 08.12.2009 в 00:54

    Это что получается, что теперь не возможно написать уникальную статью и попробовать размножить её?

  25. Евгений / 26.12.2009 в 14:05

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

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

    Вопрос: а как ответить на вопрос являются ли объекты почти дубликатами или нет? Если % схожести больше некоторого заданного m, то тексты считать почти одинаковыми, иначе — разными? Или есть более изощренные методы?)

  26. dron / 28.02.2010 в 13:18

    Клиника! Зачем так сильно уникалить? Смысл? 80 процентов отличается от возможных дубликатов, уже нормально! Никто ничего не склит из ПС.

  27. Дмитрий / 08.04.2010 в 18:01

    А какой версией Python можно запустить эту программку? у меня на данный момент последняя и выдаёт синтаксические ошибки.

  28. Skaizer / 08.04.2010 в 21:56

    Запускайте в ветке 2.* : 2.5 или 2.6. ну и на ранних тоже должна работать. В ветке 3.* не будет, под нее нужно специально переписывать.

  29. Антон / 18.07.2010 в 00:57

    Такой момент.. если имеем два совершенно непохожих текста (или запускаем алгоритм с большой длиной шинглов/малыми текстами), то получаем ексепшн ZeroDivisionError.
    Собственно неплохо было бы его ловить.
    Ну и еще момент производительности.. мне кажется выражения-генераторы будут предпочтительнее генераторов списков.

  30. Иван / 11.09.2012 в 14:37

    Я думаю что фрагмент


    for i in range(len(source1)):
    if source1[i] in source2:

    следует заменить на


    for i in range(len(source1)):
    if source1[i] == source2[i]:

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

    Если же позиция шингла не учитывается, то разницу списков проще было посчитать через сеты.

  31. Костя / 12.12.2012 в 01:13

    Хотелось бы кое-что добавить. Чувствительность алгоритма сравнения зависит от длины шингла, чем более длинный шингл тем хуже точность сравнения, но и больше скорость и наоборот. Наиболее точное сравнение при длине шингла в одно слово, но это такое же сравнение как и попарно всех слов, плюс еще вычисление контрольных сум. Кроме того, простое изменение слов (использование синонимов — синомайз), даст отличный результат для веб спаммеров при таком алгоритме. Так что здесь нет каких-либо радужных перспектив, без возможности определения синомайза. Кроме того, в статье Сегаловича на которую вы ссылаетесь вообще используется другой метод самим Сегаловичем — .. для каждого документа формируется множество U различных слов, входящих в него, и определяется пересечение U и словаря L (был раньше сформирован из всей коллекции со слов со средним IDF) и т.д.

Оставить комментарий

480×60
480×60