文字列の編集距離
ビルドアップ 1
文字列には、次の四つの作用がある:
- 挿入: 文字列に新しい文字を挿入する。
- 削除: 文字列から文字一つを取り除く。
- 置換: 文字列内の文字一つを他の文字に変える。
- 転置: 二つの文字の位置を交換する。
定義
編集距離は、文字列間の距離関数として、編集方法を許可または禁止することによって、次のようなタイプに分類される:
- (1) ハミング距離: ハミング距離は最もシンプルで、置換のみを許可する。つまり、同じ長さのベクトルが与えられた場合、異なる位置だけをカウントすることである。大したことはないが、説明で省略されることが多いので、名前そのものを覚えておくといい。例えば、次の二つのベクトルの距離は$3$だ。 $$ x = (1,1,0,1) \\ y = (0,1,1,0) $$
- (2) レーベンシュタイン距離: レーベンシュタイン距離は挿入、削除、置換のみを許可する。編集距離としては最もメジャーに使われ、情報検索理論や生命情報学などの分野でも出会うことがある。レーベンシュタイン距離を測定するアルゴリズムには、レーベンシュタインアルゴリズムがある。例えば、「cats」と「facts」は、次の二つの編集を行うため、レーベンシュタイン距離は$2$だ。
- （置換）cats → fats
- （挿入）fats → facts
- (3) ジャロ距離: レーベンシュタイン距離とは反対に、ジャロ距離は転置のみを許可する。
- (4) 最長共通部分列距離: LCS距離は、挿入と削除のみを許可する。