Levenshtein距離
挿入
、
置換
、
削除
をそれぞれ1と数える
編集距離
例
距離0 = 完全一致
距離1
置換: scr
a
pbox→scr
i
pbox
挿入:kidaam→kidaa
a
m
削除: dai
i
z→daiz
距離2
隣接交換: d
on
e→d
no
e
よくあるタイプミス
Damerau-Levenshtein距離
だと隣接交換も1にカウント
距離3
sc
pra
boxとsc
rap
box
レーベンシュタイン距離 - Wikipedia