Python: Алгоритм Шинглов — поиск нечетких дубликатов текста http://www.codeisart.ru/python-shingles-algorithm/

http://www.codeisart.ru/python-shingles-algorithm/

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-документов Зеленков Ю.Г, Сегалович И.В. 2007
• Как работают поисковые системы Сегалович И.В.
  Похожие темы

• Часть 1. Алгоритм шинглов для веб-документов
• Python: Получение последнего сообщения из Twitter
• 301 редирект для 1800 страниц на одном домене
• Сравнение значений в шаблонах Django
• Python, Django: Автоматический ресайз загружаемых изображений

Насколько похожи объекты на Python http://pkolt.ru/pages/168/

http://pkolt.ru/pages/168/

Определить на сколько отличаются(похожи) объекты

Практическое применение:

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

Добавлю от себя, я практическое применение еще вижу в анализе данных, например текстовых, определении в этих данных ключевых слов, их подсчет...а далее определение например близких и схожих статей опубликованных в электронном журнале или блоге(где угодно).
Рассмотрим 2 алгоритма для определения похожести Эвклидово расстояние и коэффициент корреляции Пирсона.

Twitter RSS Бот На Python

http://www.spoofi.ru/2011/10/30/twitter-rss-bot-python/

Twitter RSS Бот На Python

30 октября, 2011 г. Категория: Python

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

Что получилось из моей задумки смотрим под катом. 

И так, для начала я поставил для себя следующие задачи:

1. Бот должен уметь читать RSS ленты и уметь их парсить.
2. Бот должен быть написан только на питоне.
3. Бот должен автоматически фолловить всех, кто фолловит его и отписываться от тех, кто его перестал читать.

Немного посмотрев примеры на других блогах, я попробовал написать отдельно «читалку» RSS,  саму авторизацию и постинг сообщений, фолловинг/анфолловинг твиттерян.

Для всего бота понадобились следующие библиотеки:

• feedparser — для обработки RSS лент
• tweepy — для работы с APIлками твиттера
• oauth — зависимость tweepy — работа с oauth авторизацией
• cPickle, time — стандартные библиотеки для работы с файлами и временем
• googl — для сокращения ссылок через сервис goo.gl

Как устанавливать библиотеки я говорить не буду, есть очень много способов, описанных в интернете.  Я использовал easy_install (гугл вам о нём расскажет (: ).

Когда набор для создания бота готов, можно приступить к работе.

Для начала нужно создать приложение и твиттер аккаунт для бота. Делается всё просто — просто заходим на страницу регистрации предложения (я использовал свою учетную запись твиттера для создания приложения, но можно создать аккаунт бота и делать все действия от его имени — так будет даже удобнее) и заполняем все данные. Там же нам нужно будет получить Consumer key и Consumer Secret, а такжеустановить права на Чтение и Запись во вкладке Settings:

В случае если Вы будете использовать для бота ту же учетную запись, от которой и создали приложение — нажимаем на кнопку «Create my access token» и сохраняем полученные Access token и Access token secret.

Если приложение  создано от другого пользователя, который ботом не будет, то нужно проделать следующие операции:

1. Залогинится под аккаунтом бота

2. Написать следующий скрипт, заполнив переменные CONSUMER_KEY и CONSUMER_SECRET:

import tweepy, webbrowser

CONSUMER_KEY = 'paste your Consumer Key here'

CONSUMER_SECRET = 'paste your Consumer Secret here'

auth = tweepy.OAuthHandler (CONSUMER_KEY, CONSUMER_SECRET)

auth_url = auth.get_authorization_url ()

webbrowser.open (auth_url)

verifier = raw_input('PIN: ').strip ()

auth.get_access_token (verifier)

print «ACCESS_KEY = '%s'» % auth.access_token.key

print «ACCESS_SECRET = '%s'» % auth.access_token.secret

3. Запустить написанный скрипт. Откроется браузер и Вам будет выдан ПИН код.

4.  Ввести ПИН код в терминале

5. Сохранить Access token и Access token secret, выданные скриптом.

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

import oauth, tweepy, feedparser, cPickle, time, googl

def Sleep(sec): # функция для приостановки скрипта на заданное время
    print "Ждём %d секунд" % sec
    time.sleep (sec)
    return True
    
def Short(longurl): # сокращает ссылки
    url = short.shorten (longurl)
    return url["id"]

def Tweet(twit): # обновляет статус в твиттере
    if len(twit)<=140 and len(twit)>0:
        res = api.update_status (twit) #обновляем статус
        return True
    else:
        return False

def bot(feedurl):
    feed = feedparser.parse (feedurl) # парсим фид 
    file = open("db.txt", "r") # подключаем бд, получаем отправленные ссылки
    posted = cPickle.load (file)
    file.close ()    
    ok = 1
    newposted = posted
    for item in feed.entries:
            for i in posted: # перебираем отправленные и новые ссылки
                    if i == item.link:
                            ok = 0
                            break
                    ok = 1
            if ok:
                text = item.title + " " + Short (item.link)
                print "Твитим: ", text
                Tweet (text) # если такая ссылка не отправлялась - отправляем
                Sleep (300)
                newposted.append (item.link)
    file = open("db.txt","w") # сохраняем в файл отправленные ссылки
    cPickle.dump (newposted, file)
    file.close ()
    return True

def refollow(): # подписывается на всех, кто читает бота
    followers = api.followers ()
    following = api.friends ()
    fnames = []
    for user in following:
        fnames.append (user.screen_name)    
    for follower in followers:
        if (not follower.screen_name in fnames):
            print "Подписываюсь на @",follower.screen_name
            follower.follow ()
    return True

def reunfollow(): # отподписывается от всех, кто не читает бота, но есть в нашем френд листе
    followers = api.followers ()
    following = api.friends ()
    fnames = []
    for user in followers:
        fnames.append (user.screen_name)    
    for follower in following:
        if (not follower.screen_name in fnames):
            print "Отписываюсь от @",follower.screen_name
            follower.unfollow ()
    return True

def init(): 
    global api
    global short
    consumer_key = "" # ваш consumer key
    consumer_secret = "" # ваш consumer secret 
    access_key="" # access key
    access_secret="" # и access secret
    auth = tweepy.OAuthHandler (consumer_key, consumer_secret)
    auth.set_access_token (access_key, access_secret)
    api=tweepy.API (auth)
    short = googl.Googl ("") # ключ для API goo.gl

init () # старт
while 1: #вечный цикл
    bot ("http://feeds2.feedburner.com/spoofi") # запускаем обработку фида
    Sleep (20*60) # спим 20*60 (1800) секунд
    refollow () # фолловим новых читателей
    Sleep (20*60) # опять спим
    bot ("http://prodigger.ru/rss/index/") # можно добавить еще один фид
    Sleep (20*60)
    reunfollow () # удаляем не читающих нас
    Sleep (20*60)

И да, для получения ключа APIлок goo.gl: проходим в консоль API, жмем «Add project», почти в самом низу выбираем «URL Shortener API». В подпункте «API access» будет ваш ключ для APIлок:

Собственно на этом всё, вставляем в код все ключи, сохраняем в файл, например bot.py и, предварительно дав права на запуск, запускаем его.
Наблюдаем за ботом в твиттере (:

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

UPD: исходники можно скачать архивом.
P.S. вот что получилось у меня — @pytbot

Ну, а если Вы решили транслировать RSS ленту в твиттер, то у Вас явно есть сайт, на котором можно заработать. Биржи купли-продажи ссылок могут помочь с этим!

Простой Twitter-бот на Python

http://habrahabr.ru/post/127237/

Простой Twitter-бот на Python

В данной статье я бы хотел поделиться опытом написания небольшого твиттер-бота на Python.

Вступление

На написание бота меня натолкнул известный многим «пичалька-бот» в Twitter, который автоматически шлет реплаи всем, кто упомянит слово «пичалька» в своем твите. Поскольку в тот момент я занимался активным изучением Python, было решено писать на нем.

Подготовка

В качестве библиотеки для работы с API твиттера я взял tweepy. Это достаточно простая и удобная библиотека; к тому же в ее репозитории в Google Code есть несколько примеров кода и хорошаядокументация. Еще она есть в репозиториях Ubuntu и Debian, поэтому ее можно легко установить командой sudo apt-get install python-tweepy.

Разработка

1. Для работы бота необходимо зарегистрировать новое приложение в Twitter. Перейдите по ссылке и заполняем все поля.



После этого вы получите 2 ключа для OAuth авторизации.



Также необходимо изменить права приложения. Вкладка «Settings», Access -> Read and Write



2. Теперь необходимо получить еще 2 ключа, индивидуальные для каждого пользователя. Для этого можно нажать кнопку «Create access token» на странице приложения, либо воспользоваться небольшим примером кода из документации tweepy.



Вариант с примером кода:

import tweepy, webbrowser

CONSUMER_KEY = 'paste your Consumer Key here'
CONSUMER_SECRET = 'paste your Consumer Secret here'

auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET)
auth_url = auth.get_authorization_url()
webbrowser.open(auth_url)
verifier = raw_input('PIN: ').strip()
auth.get_access_token(verifier)
print "ACCESS_KEY = '%s'" % auth.access_token.key
print "ACCESS_SECRET = '%s'" % auth.access_token.secret

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



3. Теперь можно перейти к коду самого бота:

#coding: utf-8
import oauth, tweepy, sys, locale, threading 
from time import localtime, strftime, sleep

replyed=['']
search_reply_words={'печалька':' каждый раз, когда вы говорите "печалька", умирают хомячки.','пичалька':' каждый раз, когда вы говорите "пичалька", умирают хомячки.'}
update_time=60 #время обновления

def Tweet(twit,id_reply):
    if len(twit)<=140 and len(twit)>0:
        api.update_status(twit,id_reply) #обновляем статус (постим твит)
        return True
    else:
        return False

def init(): #инициализируемся
    global api
    #consumer_key = ""
    #consumer_secret = ""
    #access_key=""
    #access_secret=""
    auth = tweepy.OAuthHandler(consumer_key, consumer_secret)
    auth.set_access_token(access_key, access_secret)
    api=tweepy.API(auth)

class TwiBot(threading.Thread): 
    def __init__ (self, keyword,answer):
        self.keyword = keyword
        self.answer=answer
        threading.Thread.__init__(self)

    def run (self):
        global replyed,api
        request=api.search(self.keyword) #ищем твиты с указанным словом
        for i in request:
            if i.from_user!='thevar1able' and i.id not in replyed: # если твит не наш и мы на него еще не отвечали...
          try:
           Tweet('@'+i.from_user+self.answer,i.id) #...отвечаем
           print strftime('[%d/%m %H:%M:%S]',localtime())+' Reply to @'+i.from_user+'('+str(i.from_user_id)+')'
          except:
           print strftime('DUP [%d/%m %H:%M:%S]',localtime())+' Reply to @'+i.from_user+'('+str(i.from_user_id)+')'
          replyed.append(i.id)
        return True



init() # инициализируемся
while not False: # вечно
    for word in search_reply_words: 
        TwiBot(word, search_reply_words[word]).start() #запускаем поток с нужным словом для поиска
        print strftime('[%d/%m %H:%M:%S]',localtime())+' Updating for word "'+str(word)+'"...'
        sleep(1) 
    sleep(update_time)

Для корректной работы нужно вставить полученные ключи в переменные в коде: ключи со страницы приложения — consumer_key и consumer_secret, пользовательские ключи — access_key и access_secret. Также нужно поправить ключевые слова для поиска твитов и ответы на них в переменной search_reply_words.

Вот и все на сегодня.

Спасибо за внимание! Надеюсь, было интересно и полезно.

• twitter
• , python
• , tweepy
• , бот

+39

29 августа 2011 в 11:13

143

thevar1able3,0

Похожие посты

26.07.2012

Twitter лёг

25.07.2012

Twitter позволит пользователю скачивать свой архив твитов

07.07.2012

Twitter улучшил свой поисковый движок

30.06.2012

Twitter собирается побороться с троллингом