http://linguis.ru/art/spellздововский сайт, добавил в закладки :D
ZubchickСпасиб. Буду добавлять новые посты, по мере возможности.
здововский сайт, добавил в закладки
lightcasterОтличный сайт, также добавил в закладки, спасибо!
http://linguis.ru/art/spell
ZubchickМой вариант бинарного зависает, ума не приложу почему.
вы выберите что-то одно, либо бинарный поиск http://algolist.manual.ru/search/bin_search.php либо хеш-поиск http://goo.gl/Z4a4
ZubchickТ.е. даже если я ищу полным перебором через for in он будет работать быстре отсортированным?
Если слова в словарь добавляются редко, то отсортируйте его (создайте функцию добавления в словарь, которая будет добавлять слово в нужное место, так чтобы словарь оставался отсортированным) и ищите в нем (как написать сортировку смотрите по ссылке выше), работает быстро я гарантирую это
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
ZubchickСпасибо, это гораздо лучше.
try it
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