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

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

Он загружает текст, создает словарь из 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]
Источник

2 ответа

Решение

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

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

Еще одна вещь, о которой я могу подумать, - это написать внутри вашего кода на Python алгоритм интенсивного расстояния редактирования процессора на C, то есть, написав расширение на Python.

Источник

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

Источник
Другие вопросы по тегам