我如何调整Levenshtein距离算法来限制匹配到单个单词

Question

我使用c++中的Levenshtein Distance算法来比较两个字符串以测量它们彼此之间的距离。然而，普通的Levenshtein Distance算法不区分由空格分隔的单词边界。这导致距离计算比我想要的要小。我正在比较标题，看看它们彼此之间有多接近，我希望算法不将字符计数为匹配，如果它们来自多个单词。

例如，如果我比较这两个字符串，我得到以下结果，+指定匹配，-指定不匹配:

Al Chertoff Et
Al Church Department of finance Et
+++++------+--++-----++-+------+++
Al Ch      e  rt     of f       Et

我得到了一个与四个字"Church Department of finance"匹配的单词"Chertoff"的距离为20，然而，我真的希望通过不允许字符从多个单词匹配并且与单词"Chertoff"最匹配的单词"Department"的距离为25来考虑它们彼此之间的距离，三个字符匹配:

Al Chertoff Et
Al Church Department of finance Et
+++--------+--++---------------+++
Al         e  rt                Et
         Ch     off

我如何调整Levenshtein距离来实现这一点，或者是否有另一种距离算法更适合于此?也许在每个单词上使用Levenshtein距离，然后选择距离最小的单词?但是，如果在字符串的深处匹配一个单词导致后续单词匹配不佳，因为它们的匹配在字符串的早期是最好的，那该怎么办?这是否可以通过Levenshtein距离调整到单词水平来实现?

例如，对于下面这个更复杂的例子，这个想法的最短距离是20:

Al Chertoff Deport Et
Al Church Department of finance Et
+++++----++++-++---------------+++
Al Ch     Dep rt                Et
     ertoff  o

而不是最大化"Chertoff"的匹配并获得更长的距离24:

Al Chertoff Deport Et
Al Church Department of finance Et
+++--------+--++-----+---------+++
Al         e  rt     o          Et
         Ch     off
                  Dep rt

我目前对Levenshtein Distance的实现如下:

size_t
levenshtein_distance(const std::string& a_compare1,
                     const std::string& a_compare2) {
  const size_t length1 = a_compare1.size();
  const size_t length2 = a_compare2.size();
  std::vector<size_t> curr_col(length2 + 1);
  std::vector<size_t> prev_col(length2 + 1);
  // Prime the previous column for use in the following loop:
  for (size_t idx2 = 0; idx2 < length2 + 1; ++idx2) {
    prev_col[idx2] = idx2;
  }
  for (size_t idx1 = 0; idx1 < length1; ++idx1) {
    curr_col[0] = idx1 + 1;
    for (size_t idx2 = 0; idx2 < length2; ++idx2) {
      const size_t compare = a_compare1[idx1] == a_compare2[idx2] ? 0 : 1;
      curr_col[idx2 + 1] = std::min(std::min(curr_col[idx2] + 1,
                                             prev_col[idx2 + 1] + 1),
                                    prev_col[idx2] + compare);
    }
    curr_col.swap(prev_col);
  }
  return prev_col[length2];
}

Answer 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上的代码。我已经测试了几个案例，我很确定它做了正确的事情，但你应该多尝试一下，以确保结果是合理的。

请注意，这并不是您所要求的，因为它忽略了编辑距离测量中的所有空格:我认为修改它不这样做应该不会太难，但我还没有完全考虑过。在任何情况下，这可能一样好(甚至更好)，这取决于您的需要，所以我将让您决定是否要尝试调整它。

需要注意的是，您的原始代码在以下两行中存在一些bug:

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

保留vector中的容量，但实际上不改变它们的大小，因此在此之后访问数组是未定义的行为。如果你要访问一个范围内的元素，你实际上应该resize向量:reserve通常用于你要一个接一个地push_back一定数量的元素的情况(这会随着你的移动而增加大小，而不是一次全部增加)，并且你想避免多次内部重新分配的成本(因为每次超出容量时，内部容量只增加一定的系数)。

编辑:

这个版本考虑了单词之间的空格作为编辑距离的一部分，但结果仍然与您的示例不完全相同，因为在某些情况下需要添加多个空格。

Answer 2

如果单个单词的长度不相同，则会跨越单词边界。如果你想保持索引在各自的单词中进行比较，那么你需要使单词具有相同的长度。例如，这里有一个Javascript(是的，我知道你问或c++，但这是为了说明-取自维基百科的代码)距离计算例程:

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