Алгоритм сходства текста, проблемы оптимизации - PullRequest
Новая
       7

Алгоритм сходства текста, проблемы оптимизации

0 голосов
/ 20 августа 2011

У меня есть блог django, и я пишу для него простой подобный текстовый алгоритм. Код ниже - это код, который я протестировал с копией базы данных моего блога. (Примечание: код изначально был на турецком языке, для удобства я изменил имена переменных на английский. Поэтому все может выглядеть странно.) 

# -*- coding:utf-8 -*-
from django.utils.html import strip_tags
import os
import sys
import math
import re
PROJECT_FOLDER = os.path.abspath(os.path.dirname(__file__))
UPPER_FOLDER = os.path.abspath(PROJECT_FOLDER + "/../")
sys.path.append(UPPER_FOLDER)
os.environ["DJANGO_SETTINGS_MODULE"] = "similarity.settings"
from blog.models import Post

def getWords(post_object):
    all = post_object.title + " " + post_object.abstract + " " + post_object.post
    all = strip_tags(all.lower())

    regex = re.compile("\W+",flags=re.UNICODE)
    return re.split(regex,all)

def count_things(what_to_count,the_set):
    num = 0
    for the_thing in the_set:
        if what_to_count in the_thing[1]:
            num += 1
    return num

a = Post.objects.all()
b = []
for post in a:
    b.append((post.title,getWords(post)))
del(a)

def adjustWeight(the_list,the_word):
    numOccr = the_list.count(the_word)
    if numOccr == 0:
        return 0
    else:
        return math.log(numOccr,1.6)


results = []
uniques = []
for i in range(0,len(b)):
    for a_word in b[i][1]:
        if a_word not in uniques:
            uniques.append(a_word)

for i in range(1,len(b)):

    for j in range(0,i):

        upper_part = 0
        sum1 = 0
        sum2 = 0

        for a_word in uniques:

            adjusted1 = adjustWeight(b[i][1],a_word)
            adjusted2 = adjustWeight(b[j][1],a_word)

            upper_part +=  adjusted1 * adjusted2 * math.log(len(b)/count_things(a_word,b))
            sum1 += adjusted1
            sum2 += adjusted2


        lower_part = math.sqrt(sum1 * sum2)

        results.append((b[i][0], b[j][0], upper_part/lower_part))

results = sorted(results, key = lambda x: x[2])
results.reverse()
print("\n".join(["%s and %s => %f" % (x,c,v) for x,c,v in results]).encode("utf-8"))

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

У меня будет задание cron для файла python, в котором он сравнивает вновь добавленные или измененные тексты со всеми другими текстами и сохраняет оценки сходства в базе данных для использования.

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

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

1 Ответ

0 голосов
/ 21 августа 2011

Если вы хотите выполнить поиск на основе сходства текста, вам лучше воспользоваться поисковым сервером, таким как Sphinx: http://sphinxsearch.com/

...