Как я могу адаптировать алгоритм Levenshtein Distance для ограничения совпадений одним словом?

Ответ 1

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

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

EDIT:

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

Ответ 2

Границы слов будут пересекаться, если отдельные слова не имеют одинаковой длины. Если вы хотите, чтобы индексы сравнивались в соответствующих словах, вам нужно будет сделать слова одинаковой длины. Например, здесь Javascript (да, я знаю, что вы спросили или С++, но это для иллюстрации - код, взятый из Википедии). Процедура вычисления расстояния:

var memo = {};

function d(str1, i, len1, str2, j, len2){
    var key = [i,len1,j,len2].join(',');
    if(memo[key] != undefined) return memo[key];

    if(len1 == 0) return len2;
    if(len2 == 0) return len1;
    var cost = 0;
    if(str1[i] != str2[j]) cost = 1;

    var dist = Math.min(
        d(str1, i+1,len1-1, str2,j,len2)+1, 
        d(str1,i,len1,str2,j+1,len2-1)+1,
        d(str1,i+1,len1-1,str2,j+1,len2-1)+cost);
    memo[key] = dist;
    return dist;
}

var str1 = "Al Chertoff Deport$$$$ $$ $$$$$$$ Et";
var str2 = "Al Church$$ Department of finance Et";

console.log(d(str1, 0, str1.length, str2, 0, str2.length));

Обратите внимание, как я изменил две строки ввода, чтобы они соответствовали отдельному уровню слов. Запустив это, я получил расстояние 19. Аналогично, если я изменил строки на:

var str1 = "Al Chertoff $$$$$$$$$$ $$ $$$$$$$ Et";
var str2 = "Al Church$$ Department of finance Et";

Я получаю расстояние 24.