- @ThothChildren
- 2017.9.7
- PV 110
単語をどれだけ変更するかの距離を選ぶ
ー 概要 ー
単語同士がどれだけ離れているかをどれだけ各文字を編集する必要であるかで表す距離があります。
この章を学ぶ前に必要な知識
条件
- 入力する文字列が二つあること
効果
- その文字列をどれほど編集するかの距離が得られる
解 説
文字列の距離を変更する距離の一つに何回文字を変更するかで距離を表す方法があります。 | 導入 |
ある文字と他の文字がどれだけ離れているかを表す距離なので、
二つの文字列が必要となるのは大前提です。
| 前提 |
1.ハミング距離 | |
まず一つ目の距離として「ハミング距離」があります。
これを使用するときは、
・入力する二つの文字列が同じ長さである必要があります。
そして距離は、同じ位置を比較したときにどれだけ文字が違うかを集計する単純な仕組みになっています。 | 外部リンク ハミング距離 |
例えば、"abcdefg"と"abeeefg"の距離は
cとdがeと一致していないため、2となります | 実態 例え 比較もと abcdefg 比較先 abeeefg |
2.レーベンシュタイン距離 | |
次に二つ目の距離として「レーベンシュタイン距離」があります。
この距離において文字数の制限はありません。
距離の計算方法としては、
文字の置換、削除、挿入の各操作を一回として数えて、最短何回で目的の単語に変化させられるかを距離と定義しています。
| 外部リンク レーベンシュタイン距離 |
・比較する文字数が同一でシンプルな距離なら
ハミング距離
・そうでないなら
レーベンシュタイン距離を選択すれば良い | 結論 |
この章を学んで新たに学べる
Comments