11

私はC++のレーベンシュタイン距離アルゴリズムを使用して2つの文字列を比較し、それらが互いにどれだけ近いかを測定しています。ただし、プレーンなレーベンシュタイン距離アルゴリズムは、スペースで区切られた単語の境界を区別しません。これにより、距離の計算が私が望むよりも小さくなります。タイトルを比較して、それらが互いにどれだけ近いかを確認しています。アルゴリズムが、複数の単語にまたがる場合に文字が一致しているとカウントしないようにしたいと思います。

たとえば、これら2つの文字列を比較すると+、一致を指定し、不一致を指定すると、次の結果が得られます-。

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

"Chertoff"4つの単語間で単語が一致すると、距離は20に"Church Department of finance"なりますが、複数の単語から文字が一致することを許可せず、単語との距離が25になるようにすることで、それらを互いにさらに離して検討する必要があります。"Chertoff"1つの単語に最も一致し、"Department"3つの文字が一致します。

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

これを達成するためにレーベンシュタイン距離をどのように適応させることができますか、またはこれにより適した別の距離アルゴリズムがありますか？おそらく、各単語のレーベンシュタイン距離を個別に使用して、単語の働きをし、距離が最も短い単語を選択しますか？ただし、1つの単語を文字列の奥深くまで一致させると、後続の単語の一致が文字列の最初の方で最も優れていたために、一致が不十分になった場合はどうなりますか？これは、レーベンシュタイン距離を単語レベルに適合させて、どういうわけか行うことができますか？

たとえば、次のより複雑な例のこのアイデアによる最短距離は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

レーベンシュタイン距離の現在の実装は次のとおりです。

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];
}
4

2 に答える 2

6

levenshtein_distanceシーケンスコンテナで一般的なアルゴリズムを作成し、2つの要素間の距離を計算するコスト関数を含めることで、必要なものにかなり近づけることができます。

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に、単語の境界間で編集できないように、2つの文の間の編集距離は、次のように定義できます。

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で動作するコードです。私はいくつかのケースをテストしましたが、それが正しいことを行うと確信していますが、結果が妥当であることを確認するために、さらに試してみる必要があります。

これは、編集距離測定のすべてのスペースを無視するため、正確には要求されていないことに注意してください。それを行わないように変更するのはそれほど難しいことではないと思いますが、完全には考えていません。いずれにせよ、これはあなたのニーズに応じて同じくらい良い（またはさらに良い）かもしれないので、あなたがそれを微調整したいかどうかをあなたに決めさせます。

ちょっとしたメモですが、元のコードは次の2行で少しバグがありました。

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

ベクトルの容量を予約しますが、実際にはそれらのサイズを変更しないため、その後の配列へのアクセスは未定義の動作でした。範囲内の要素にアクセスする場合は、実際にresizeはベクトルを使用する必要があります。reserve通常push_back、特定の数の要素を1つずつ（一度にではなく、サイズを大きくしていく）、特定の数の要素にアクセスしようとしている状況に使用します。また、複数の内部再割り当てのコストを回避する必要があります（内部容量は、容量を超えるたびに特定の係数だけ増加するため）。

編集：

このバージョンでは、編集距離の一部として単語間のスペースが考慮されますが、場合によっては複数のスペースを追加する必要があるため、結果は例とまったく同じではありません。

于 2013-03-14T22:01:42.150 に答える
-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));

個々の単語レベルで一致するように2つの入力文字列を変更した方法に注目してください。これを実行すると、19の距離が得られました。同様に、文字列を次のように変更すると、次のようになります。

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

私は24の距離を取得します。

于 2013-03-14T19:06:37.343 に答える