Алгоритм Левенштейна:Как мне выполнить эти требования к редактированию текста?

Question

Я использую алгоритм Левенштейна для удовлетворения этих требований:

При нахождении слова из N символов в моей базе данных словаря в качестве исправления предлагаются следующие слова:

Каждое словарное слово из N символов, которое имеет 1 символ отличия от найденного слова.Пример:найденное слово:беарн, словарное слово:медведи

Каждое словарное слово из N + 1 символов, содержащее N символов, равных найденному слову.Пример:найденное слово:медведь, словарное слово:медведи

Каждое словарное слово из N-1 символов, содержащее N-1 символов, равных найденному слову.Пример:найденное слово:медведи, словарное слово:медведь

Я использую эту реализацию алгоритма Левенштейна в C ++, чтобы определить, когда слово имеет число Левенштейна, равное 1 (которое является числом Левенштейна для всех трех случаев), но тогда как мне выбрать слово для предложения?Я читал о Бойере-Муре-Хорспуле и Кнуте-Моррисе-Пратте, но я не уверен, чем кто-либо из них может быть полезен.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   string::size_type N1 = s1.length();
   string::size_type N2 = s2.length();
   string::size_type i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ ) {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}

Answer 1

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

Прошло много времени с тех пор, как я это читал, но я помню, что это было очень похоже на то, о чем вы пишете.

Answer 2

Как я уже говорил в другом месте, Бойер-Мур на самом деле не подходит для этого.Поскольку вы хотите выполнять поиск нескольких укусов одновременно, алгоритм Wu и Manber должен быть вам больше по душе.

Я опубликовал доказательство концептуального кода C ++ в ответ на еще один вопрос.Примите во внимание упомянутые там предостережения.

Answer 3

Зачем ограничивать предложение одним словом, почему бы не включить набор слов?Если вы ограничены одним словом, вы можете упорядочить свои результаты по некоторой заранее рассчитанной частоте использования или чему-то еще.Эта частота может быть обновлена в зависимости от того, что пользователи выбирают из предложенного.

Кроме того, в случае, когда в исходном слове нет орфографической ошибки, вы можете захотеть расставить приоритеты для N + 1 случаев, что было бы больше похоже на автозаполнение.В любом случае, я не думаю, что есть один правильный способ сделать это, возможно, если бы ваши требования были более конкретными, было бы легче сузить круг.

Кроме того, вам не нужно знать Python, чтобы понять алгоритмы, описанные в статье Норвиг.

Answer 4

Если я вас правильно понял, то правильного ответа на ваш вопрос не существует.Вы определяете до трех предложений для данного слова, используя Levenshtein - вам решать, какое из них использовать, а какие отфильтровать.Или, может быть, вам следует использовать их все?

Просто из интереса, вам может быть интересно расширение Damerau к Levenshtein, где два поменявшихся местами символа также считаются дающими оценку 1 вместо 2, что и возвращает vanilla Levenshtein.