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

Я могу получить довольно близко к тому, что вы хотите, сделав 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);
}

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

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

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

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

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

Редактировать:

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