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

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

http://linguis.ru/art/spell

Что же касается “правильного” поиска слов - копайте в сторону автоматов и трансдьюсеров (finite state automata, transducer). Там же на сайте есть несколько примеров. Правда, на питоне наврятли это можно сделать оптимально. По крайней мере мои попытки с реализацией обходом по дереву были не оч. успешны.

вы выберите что-то одно, либо бинарный поиск http://algolist.manual.ru/search/bin_search.php либо хеш-поиск http://goo.gl/Z4a4

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

Если слова добавляются часто то лучше использовать хеш поиск. Описывал выше.

http://linguis.ru/art/spell

Отредактировано (Янв. 29, 2010 13:55:52)

Zubchick
здововский сайт, добавил в закладки

lightcaster
http://linguis.ru/art/spell

Zubchick
вы выберите что-то одно, либо бинарный поиск http://algolist.manual.ru/search/bin_search.php либо хеш-поиск http://goo.gl/Z4a4

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

Отредактировано (Янв. 29, 2010 16:12:45)

полный перебор не может работать быстрее чем полный перебор :D

киньте сюда свою функцию бинарного поиска)

Отредактировано (Янв. 29, 2010 17:07:15)

Zubchick
киньте сюда свою функцию бинарного поиска)

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

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 deletes + transposes + replaces + inserts

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


def search(word, lst):
    """ Eсть ли word в списке lst? """
    l = 0
    r = len(lst) - 1
    while 1:
        m = (l + r) // 2
        if word < lst[m]:
            r = m -1
        elif word > lst[m]:
            l = m + 1
        else:
            return True
        if l > r :
            return False

Отредактировано (Янв. 29, 2010 18:25:51)

Zubchick
try it

Отредактировано (Янв. 29, 2010 20:01:36)

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

Но вообще оставшиеся тормоза в любом случае связаны с edit1 и тем что нам потом надо будет поискать len(edit1(word)) раз в словаре. А с этим уже особо ничего не попишешь… разве что другой алгоритм :)

Отредактировано (Янв. 29, 2010 20:32:35)

Zubchick
всех быстрей он будет работать если он в памяти
если словарь всего 1н метр, так может имеет смысл считать его в память?

 
        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 = deletes + transposes + replaces + inserts

Отредактировано (Янв. 29, 2010 21:33:52)