如何调整Levenshtein Distance算法以限制单个单词的匹配？

Question

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

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

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

我得到一个距离为20,在"Chertoff"四个单词中匹配单词,"Church Department of finance"而我真的希望它们被认为是彼此更远的,因为不允许字符与多个单词匹配并且与单词的距离为25 "Chertoff"大多数匹配一个单词"Department",三个字符匹配:

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距离的实施如下:

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上运行的代码.我已经测试了几个案例,我很确定它做对了,但你应该多尝试一下以确保结果是合理的.

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

只是一个小小的注释,你的原始代码略有错误,因为以下两行:

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

保留向量中的容量,但实际上并没有改变它们的大小,因此在此之后访问数组是未定义的行为.resize如果您要访问某个范围内的元素,您实际上应该是向量:reserve通常是针对您将要push_back逐个一定数量的元素的情况(这会增加您的大小,而不是一次性增加所有元素)并且您希望避免多次内部重新分配的成本(因为每次超出容量时内部容量仅增加一定的因子).

编辑:

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