-1

LD = レーベンシュタイン距離

紙の上でいくつかの例を実行するだけで、これは機能しているように見えますが、これが常に正しいかどうかは誰にもわかりませんか?

3つの文字列があるとしましょう

ボット

ボブ

部品表

LD(ボット、ボブ) = 1

と

LD(BOB,BOM)=1

それから

LD(BOT,BOM)=max(LD(BOT,BOB),LD(BOB,DOM))=1

また

バアブ

BBAB

BCCD

LD(BBAB、BAAB) = 1

と

LD(BBAB,BCCD)=3

それから

LD(BAAB、BCCD)=max(LD(BBAB、BAAB)、LD(BBAB、BCCD))=3

これが常に当てはまるかどうか知りたいです。

あれは、

LD(B,C) = 最大 (LD(A,C),LD(A,B))

編集 -- 2009 年 10 月 22 日午後 7:08 PST に追加

これは同じ長さの単語にも当てはまると思い始めています。それ以外の場合は引き続き実行できますが、単語の長さの差の絶対値を追加する必要があります。

本質的に LD(B,C) = max(LD(A,C),LD(A,B)) + abs(長さ(B)-長さ(C))

4

5 に答える 5

2

うまくいきません。

LD("BOB", "BOT") == 1
LD("BOT", "BOB") == 1

LD("BOB", "BOB") == 0
max(LD("BOB", "BOT"), LD("BOT", "BOB")) == 1

0 != 1

おそらくもっと難しい例もあります...

于 2009-10-23T05:24:02.987 に答える
2

いいえ、しかしこれは：

lev(a, c) <= lev(a, b) + lev(b, c) (別名「三角不等式」)

...そして、VP-Trees と BK-Trees によるヒューリスティックとして頻繁に使用されます。

メトリックであるため、レーベンシュタイン距離は三角形の不等式に従います:
http://en.wikipedia.org/wiki/Triangle_inequality

于 2010-09-06T03:06:50.943 に答える
1

これは通常の動的計画法の問題です。ウィキペディアのエントリには、正確性の証明の部分があります。他に何かお探しですか？

于 2009-10-23T01:59:58.500 に答える