Найти - Пользователи
Полная версия: Алгоримт поиска похожих слов Норвига
Начало » Python для экспертов » Алгоримт поиска похожих слов Норвига
1 2 3
magasoft
Есть такой алгоритм у Питера Норвига: 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)
Возникает две проблемы, на продакшене стоит питон 2.4 и выдает варианты только из списка deletes (то бишь не складирует все списки). Хотя возможно он где-то обрывает вычисления, кто-нибудь в курсе разницы 2.4 и 2.5 в этом отношении?
Вторая и основная проблема это дикие ресурсы которые потребляет система чтобы подобрать варианты. Причем даже для отклонения в одну букву требуется в десять раз больше времени чем в обычной работе функции. Есть ли какие-либо идеи по оптимизации этого кода? Какие методики еще можете порекомендовать для поиска похожих слов с несколькими отклонениями? Из того что попалось по поиску этот метод показался наиболее простым среди них.
Zubchick
алгоритм звиздец)
на слово ‘Ня’ выдает мне 150 вариантов. На ‘Ололо’ около 300. На слово ‘Алгоритм’ около 500….
А затем вы делаете ЭТО return set(e1 for e1 in edits1(word) if e1 in DICTIONARY)…

для каждого из скажем 1000 вариантов вы ищите (полным перебором) это слово в своем DICTIONARY, который как я предполагаю сам метра 2… Во вторых когда вы делаете set из всех слов все дубликаты выбрасываются. Я не знаю как там работает алгоритм, но не думаю, что он может работать быстро. В общем швах полный)
magasoft
Zubchick
алгоритм звиздец)
на слово ‘Ня’ выдает мне 150 вариантов. На ‘Ололо’ около 300. На слово ‘Алгоритм’ около 500….
А затем вы делаете ЭТО return set(e1 for e1 in edits1(word) if e1 in DICTIONARY)…

для каждого из скажем 1000 вариантов вы ищите (полным перебором) это слово в своем DICTIONARY, который как я предполагаю сам метра 2… В общем швах полный)
Не два метра, но в словаре 13 тысяч слов, возможен рост до 100.
В том-то и дело что радости мало. Есть что-то более эффективное?
Zubchick
ну да, делать что-то со словарем и использовать другой поиск а не ‘e1 in DICTIONARY’, для начала. Затем можно выкинуть set из edits1 если эта процедура больше нигде не вызывается. Ну потом еще посмотрю насчет самой процедуры edits1, я в ней не особо разбирался +)
magasoft
Zubchick
ну да, делать что-то со словарем и использовать другой поиск а не ‘e1 in DICTIONARY’, для начала
Словарь можно взять отсортированным по алфавиту.
Насчет другого поиска честно говоря ничего на ум не приходит, кроме как перебирать по буквам (первым последним), но я боюсь это будет тяжелее в итоге.
Zubchick
другой поиск всмысле принципиально другой :D
Например хеш поиск, но тогда словарь переделывать придется. Ну или бинарный поиск по отсортированному словарю. Но тогда придется сортировать словарь каждый раз как добавляешь новое слово, причем тут алгоритм сортировки тоже надо подумать какой будет оптимальный.

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

UPD Кстати вот как надо сделать. При запуске проги считывать весь словарь в память и преобразовывать в таблицу для хеш поиска. С добавлением новых слов тут тоже проблем не будет. Пишешь в конец файла новое слово, а в памяти добавляешь туда куда нужно.
magasoft
k0sh
http://ru.wikipedia.org/wiki/%D0%A0%D0% … 0%BD%D0%B0
Слышал про Левинштейна, по-моему Норвиг тоже варианты подбирает по одному из таких алгоритмов, хотя надо посмотреть внимательней.
k0sh
http://docs.python.org/library/difflib. … se_matches
Работает в разы медленней, хотя и точней и ищет больший разброс отклонений.
Zubchick
UPD Кстати вот как надо сделать. При запуске проги считывать весь словарь в память и преобразовывать в таблицу для хеш поиска. С добавлением новых слов тут тоже проблем не будет. Пишешь в конец файла новое слово, а в памяти добавляешь туда куда нужно.
Попробовал просто бинарный поиск со сравнением строк (не хеш) - убивает компьютер со скрипом.
Про хеш вот думаю, придется каждый раз найденные варианты также хешировать, эти накладные расходы не будут превышать преимущество перед поиском по хеш-таблице словаря?
Zubchick
странно что бинарный поиск вешает компутир, чему там вешать то О_о'
Тогда скажи какие слова у тебя добавляются в DICTIONARY. Просто может ты постоянно туда что-то пишешь, а потом сортируешь, тогда, конечно будет тупить :)
magasoft
Zubchick
странно что бинарный поиск вешает компутир, чему там вешать то О_о'
Тогда скажи какие слова у тебя добавляются в DICTIONARY. Просто может ты постоянно туда что-то пишешь, а потом сортируешь, тогда, конечно будет тупить
Проект вообще - онлайн словарь одного из не самых распространенных языков, с кириллическм алфавитом (но с парой добавочных лат букв, и без некоторых кирил.) Основная проблема - ищущие часто не знают как пишется слово и делают много ошибок, поэтому надо им предлагать замены, желательно с ошибкой в две буквы, но как показал опыт на среднем VPS (где он щас стоит) трудно добиться быстродействия и для одной ошибки (над чем я сейчас и бьюсь).
Обновляться слова если и будут то крайней редко, поэтому для скармливания в скрипт поиска мы можем их готовить как угодно в отдельной функции вызываемой по крону или администратором раз в неделю/месяц. Хоть хешировать, хоть как.
Вот то что пока работает:
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)
Предварительно найдя хеш-суммы слов словаря функцией hash, осортировав его и т.д.
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB