Как я могу адаптировать алгоритм расстояния Левенштейна, чтобы ограничить совпадения одним словом?

Я могу получить довольно близко к тому, что вы хотите, сделав levenshtein_distance универсальный алгоритм для контейнера последовательности, включающий функцию стоимости, которая вычисляет расстояние между двумя элементами:

template<typename T, typename C>
size_t
seq_distance(const T& seq1, const T& seq2, const C& cost,
const typename T::value_type& empty = typename T::value_type()) {
const size_t size1 = seq1.size();
const size_t size2 = seq2.size();

std::vector<size_t> curr_col(size2 + 1);
std::vector<size_t> prev_col(size2 + 1);

// Prime the previous column for use in the following loop:
prev_col[0] = 0;
for (size_t idx2 = 0; idx2 < size2; ++idx2) {
prev_col[idx2 + 1] = prev_col[idx2] + cost(empty, seq2[idx2]);
}

for (size_t idx1 = 0; idx1 < size1; ++idx1) {
curr_col[0] = curr_col[0] + cost(seq1[idx1], empty);

for (size_t idx2 = 0; idx2 < size2; ++idx2) {
curr_col[idx2 + 1] = std::min(std::min(
curr_col[idx2] + cost(empty, seq2[idx2]),
prev_col[idx2 + 1] + cost(seq1[idx1], empty)),
prev_col[idx2] + cost(seq1[idx1], seq2[idx2]));
}

curr_col.swap(prev_col);
curr_col[0] = prev_col[0];
}

return prev_col[size2];
}

Учитывая вышеизложенное seq_distanceрасстояние редактирования между двумя предложениями, так что редактирование не может быть сделано между границами слова, может быть определено с помощью следующего:

size_t
letter_distance(char letter1, char letter2) {
return letter1 != letter2 ? 1 : 0;
}

size_t
word_distance(const std::string& word1, const std::string& word2) {
return seq_distance(word1, word2, &letter_distance);
}

size_t
sentence_distance(const std::string& sentence1, const std::string& sentence2) {
std::vector<std::string> words1;
std::vector<std::string> words2;
std::istringstream iss1(sentence1);
std::istringstream iss2(sentence2);
std::copy(std::istream_iterator<std::string>(iss1),
std::istream_iterator<std::string>(),
std::back_inserter(words1));
std::copy(std::istream_iterator<std::string>(iss2),
std::istream_iterator<std::string>(),
std::back_inserter(words2));
return seq_distance(words1, words2, &word_distance);
}

Вот код, работающий над ideone. Я проверил несколько случаев, и я почти уверен, что это правильно, но вы должны попробовать это больше, чтобы убедиться, что результаты разумны.

Обратите внимание, что это не совсем то, что вы просили, поскольку в нем не учитываются все пробелы в измерении расстояния редактирования: я думаю, что не должно быть слишком сложно изменить его, чтобы не делать этого, но я не продумал это полностью. В любом случае, это может быть так же хорошо (или даже лучше), в зависимости от ваших потребностей, поэтому я позволю вам решить, хотите ли вы попытаться настроить его.

Небольшое замечание, ваш исходный код был слегка ошибочным в следующих двух строках:

curr_col.reserve(length2 + 1);
prev_col.reserve(length2 + 1);

резервируйте емкость в векторах, но на самом деле не изменяйте их размеры, поэтому доступ к массиву после этого был неопределенным поведением. Вы должны на самом деле resize вектор, если вы собираетесь получить доступ к элементам в диапазоне: reserve обычно для ситуаций, когда вы собираетесь push_back определенное количество элементов по одному (что увеличивает размер по мере того, как вы идете, а не все сразу), и вы хотите избежать затрат на несколько внутренних перераспределений (поскольку внутренняя емкость увеличивается только на определенный коэффициент каждый раз, когда емкость превышен).

РЕДАКТИРОВАТЬ:

Эта версия учитывает пробелы между словами как часть расстояния редактирования, но результаты все равно не совпадают с вашими примерами из-за необходимости добавления нескольких пробелов в некоторых случаях.