Я использую алгоритм Левенштейна для удовлетворения этих требований:
При нахождении слова из N символов в моей словарной базе данных есть следующие слова для исправления:
Каждое словарное слово из N символов, которое имеет 1 символ разницы с найденным словом.
Пример:
найденное слово: bearn, словарное слово: bears
Каждое словарное слово из N + 1 символов, которое имеет N символов, равных найденному слову.
Пример:
найдено слово: медведь, словарь слово: медведи
Каждое словарное слово из N-1 символов, которое имеет N-1 символов, равных найденному слову.
Пример:
найденное слово: bears, словарное слово: bear
Я использую эту реализацию алгоритма Левенштейна в 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];
}