Python-сообщество

Есть такой алгоритм у Питера Норвига: http://norvig.com/spell-correct.html
Взял у него часть кода отвечающего за подборку вариаций:

def edits1(word):
    alphabet = u'йцукенгшзхъфвапролджэячсмитьбю'
    s = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    deletes    = [a + b[1:] for a, b in s if b]
    transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1]
    replaces   = [a + c + b[1:] for a, b in s for c in alphabet if b]
    inserts    = [a + c + b     for a, b in s for c in alphabet]
    return set(deletes + transposes + replaces + inserts)

def known(word): # похожие (отклонение на 1 букву)
        return set(e1 for e1 in edits1(word) if e1 in DICTIONARY)

алгоритм звиздец)
на слово ‘Ня’ выдает мне 150 вариантов. На ‘Ололо’ около 300. На слово ‘Алгоритм’ около 500….
А затем вы делаете ЭТО return set(e1 for e1 in edits1(word) if e1 in DICTIONARY)…

для каждого из скажем 1000 вариантов вы ищите (полным перебором) это слово в своем DICTIONARY, который как я предполагаю сам метра 2… Во вторых когда вы делаете set из всех слов все дубликаты выбрасываются. Я не знаю как там работает алгоритм, но не думаю, что он может работать быстро. В общем швах полный)

Отредактировано (Янв. 28, 2010 00:01:07)

Zubchick
алгоритм звиздец)
на слово ‘Ня’ выдает мне 150 вариантов. На ‘Ололо’ около 300. На слово ‘Алгоритм’ около 500….
А затем вы делаете ЭТО return set(e1 for e1 in edits1(word) if e1 in DICTIONARY)…

для каждого из скажем 1000 вариантов вы ищите (полным перебором) это слово в своем DICTIONARY, который как я предполагаю сам метра 2… В общем швах полный)

ну да, делать что-то со словарем и использовать другой поиск а не ‘e1 in DICTIONARY’, для начала. Затем можно выкинуть set из edits1 если эта процедура больше нигде не вызывается. Ну потом еще посмотрю насчет самой процедуры edits1, я в ней не особо разбирался +)

Zubchick
ну да, делать что-то со словарем и использовать другой поиск а не ‘e1 in DICTIONARY’, для начала

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

Я бы сделал хеш :)

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

Отредактировано (Янв. 28, 2010 09:40:28)

http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0

http://docs.python.org/library/difflib.html?highlight=difflib#difflib.get_close_matches

Отредактировано (Янв. 28, 2010 09:56:25)

k0sh
http://ru.wikipedia.org/wiki/%D0%A0%D0% … 0%BD%D0%B0

k0sh
http://docs.python.org/library/difflib. … se_matches

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

странно что бинарный поиск вешает компутир, чему там вешать то О_о'
Тогда скажи какие слова у тебя добавляются в DICTIONARY. Просто может ты постоянно туда что-то пишешь, а потом сортируешь, тогда, конечно будет тупить :)

Zubchick
странно что бинарный поиск вешает компутир, чему там вешать то О_о'
Тогда скажи какие слова у тебя добавляются в DICTIONARY. Просто может ты постоянно туда что-то пишешь, а потом сортируешь, тогда, конечно будет тупить

def known(word):
        slovar= cache.get('slovar') # получаю словарь списком слов с кеша
        t1 = time.clock() # засекаем начало для профайлинга
        alphabet = u'Iйцукенгшзхъфвапролджэячсмитьбю'
        s = [(word[:i], word[i:]) for i in range(len(word) + 1)]
        deletes    = [a + b[1:] for a, b in s if b]
        transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1]
        replaces   = [a + c + b[1:] for a, b in s for c in alphabet if b]
        inserts    = [a + c + b     for a, b in s for c in alphabet]
        edits = list(deletes + transposes + replaces + inserts)
        result = []
        for edit in edits:
            for d in slovar:
                if edit == d:
                    result.append(edit)
        t2 = time.clock()
        result.append(round(t2-t1, 4))
        return result

        i = 0
        j = len(slovar)
        m = int((i+j)/2)
        for edit in edits:
            x = hash(edit)
            while slovar[m]!=x or i<j:
                m=int((i+j)/2)
                if slovar[m] < x:
                    i = m+1
                elif slovar[m] > x:
                    j = m
                else:
                    resault.append(edit)

Отредактировано (Янв. 29, 2010 00:30:58)