Ищите похожие слова

Я пытаюсь написать модуль проверки орфографии.Ищите похожие слова

Загружает текст, создает словарь из 16-мегабайтного файла и затем проверяет, совпадает ли найденное слово со словом в словаре (аналогично = варьируется до двух символов), если это так, то оно меняет его на форму из словаря.

Сейчас я использую алгоритм Левенштейн и обработки 50 слов набора занимает 3 мин ...

Я уверен, что должно быть более быстрым решением. Профилировщик сказал мне, что мое приложение тратит более 80% своего времени на функцию расстояния Левенштейна.

Есть ли лучшие решения/алгоритмы?

Здесь внедренная версии алгоритма я использую:

def levenshteinDistance(s1, s2): 
    l_s1 = len(s1) 
    l_s2 = len(s2) 
    d = [[a for a in genM(x, l_s2 + 1)] for x in xrange(l_s1 + 1)] 
    for i in xrange(1, l_s1 + 1): 
     for j in xrange(1, l_s2 + 1): 
      d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + decide_of_equality(s1[i - 1],s2[j - 1])) 
    return d[l_s1][l_s2]

источник

2012-04-08 Michal

Звучит просто как «Autocorrect», чем проверка орфографии, поскольку орфографические проверки обычно создают параметры и позволяют пользователям выбирать из них. Autocorrect, очевидно, невозможно сделать хорошо, факт, который почти повсеместно признан даже в телевизионных рекламных роликах. :-) –

Если вы сделаете предположение, что первая буква слова всегда правильная, вы можете просто проверить словарь для слов, начинающихся с этой буквы. Это уменьшит ваше время более или менее фактором или 26 – Doboy

Я мало знаю о python, но ваша функция расстояния использует стандартное решение динамического программирования. Вот моя версия на C++: http://codereview.stackexchange.com/questions/10130/edit-distance-between-two-strings, может быть, вы можете заметить какую-то разницу. –

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

Однако, придя к вашей проблеме, вы написали динамический алгоритм редактирования редактирования программирования. Ваш алгоритм квалифицируется как параллельный алгоритм данных. В общей памяти, то есть на одной машине, если у вас есть несколько ядер, вы можете их использовать. Вы знаете что-то, называемое map-reduce? Пожалуйста, не думайте, что распределены и все прямо сейчас, просто рассмотрите один четырехъядерный процессор и общую память. В качестве шага 1 вы можете разбить свой словарь и выделить часть для каждого потока, который будет запускать расстояние редактирования на части словаря (аналогично шагу карты). Позже все ваши потоки вернут вам все слова на расстоянии редактирования 2 (аналогично шагу уменьшения). Таким образом, ваша программа получит многоядерную архитектуру.

Еще одна вещь, о которой я мог думать, заключается в том, что внутри вашего кода на питоне записывается интенсивный алгоритм расстояния cpu в C i.e путем написания расширения python.

источник

2012-04-08 20:15:40 Yavar

К сожалению, я не мог использовать несколько ядер, но решение Норвига сделало трюк. – Michal

Возможно, проблема на более высоком уровне. Когда профайлер говорит вам, что в функции тратится много времени, возможно, вы слишком часто вызываете ее. Возможно, вы сравниваете каждое слово в тексте с каждым словом в словаре? Попробуйте это наоборот: для слов в тексте, непосредственно генерируйте слова расстояния < = 2 и проверьте, находятся ли они в словаре.

источник

2012-04-08 21:06:40

Вы правы, что иногда проблема ложится на слишком много звонков, но это не мое дело. Я могу использовать только слова из словаря, поэтому мне не нужно генерировать новые слова, но вместо этого я могу использовать слова из словаря, которые имеют расстояние <= 2 от моего встреченного слова. Но вы отметили некоторые хорошие вещи для других случаев. – Michal

ответ

Смежные вопросы