1

私は注文されたコレクションを持っています:

[Doc1, Doc2, Doc3, Doc4, Doc5]

Doc1 が上位にランク付けされてDoc2いる (この順序付けられたコレクションが検索の結果である検索クエリの状況を想像してください。

ここで、2 番目の順序付きコレクションがあるとします。

[Doc1, Doc2, Doc3, Doc5, Doc4]

この違いを数値スコアとして定量化する方法が必要です。また、重みも考慮に入れる必要があります。これにより[Doc1, Doc2, Doc3, Doc5, Doc4]、元のコレクションに[Doc2, Doc1, Doc3, Doc4, Doc5]近づきます。つまり、違いが上部に近づくためです。

レーベンシュタインの違いを考慮しましたが、順序を考慮する方法がわかりませんでした。

4

1 に答える 1

1

ウィキペディアによると、レーベンシュタイン距離は、次の擬似コードを使用して計算できます。

int LevenshteinDistance(string s, string t)
{
  int len_s = length(s), len_t = length(t), cost = 0;
  if (s[0] != t[0])
    cost = 1;
  if (len_s == 0)
    return len_t;
  else if (len_t == 0)
    return len_s;
  else
    return minimum(
        LevenshteinDistance(s[1..len_s], t) + 1,
        LevenshteinDistance(s, t[1..len_t]) + 1,
        LevenshteinDistance(s[1..len_s], t[1..len_t]) + cost);
}

私があなたの要件を正しく理解していれば、コレクションの最初の違いが最後の違いよりも重要であることを望んでいます。この要求を反映するように、この再帰関数を適応させましょう。

float LevenshteinDistance(string s, string t, float decay)
{
  int len_s = length(s), len_t = length(t), cost = 0;
  if (s[0] != t[0])
    cost = 1;
  if (len_s == 0)
    return len_t;
  else if (len_t == 0)
    return len_s;
  else
    return decay * minimum(
        LevenshteinDistance(s[1..len_s], t, decay) + 1,
        LevenshteinDistance(s, t[1..len_t], decay) + 1,
        LevenshteinDistance(s[1..len_s], t[1..len_t], decay) + cost);
}

パラメータが区間 (0,1) に属する場合decay、大きなインデックスの差は前のインデックスの差よりも重要ではなくなります。

の例を次に示しdecay=0.9ます。

s       t       dist
"1234"  "1234"  0.0000
"1234"  "1243"  1.3851
"1234"  "2134"  1.6290
于 2012-10-20T08:10:52.617 に答える