hellog〜英語史ブログ / 2018-08-24

■ #3406. Levenshtein distance [cgi][web_service][spelling][shakespeare][levenshtein_distance]

　文字列の類似度や相違度を測る有名な指標の1つに，標題の "Levenshtein distance" というものがある，「#3397. 後期中英語期の through のワースト綴字」 ([2018-08-15-1])，「#3398. 中英語期の such のワースト綴字」 ([2018-08-16-1])，「#3399. 綴字の類似度計算機」 ([2018-08-17-1]) でも前提としてきた指標であり，「#1163. オンライン語彙データベース DICT.ORG」 ([2012-07-03-1]) でもこの指標を利用して類似綴字語を取り出すオプションがある．
　考え方は難しくない．もとの文字列から目標の文字列に変換するには，いくつの編集工程（挿入，削除，置換）が必要かを数えればよい．例えば，kitten から sitting へ変換するには，kitten →（k を s に置換）→ sitten →（e を i に置換）→ sittin →（g を挿入）→ sitting という3工程を踏む必要があるので，両綴字間の Levenshtein distance は3ということになる．通常は挿入，削除，置換の編集工程にそれぞれ1の値を割り当てるが，各々に異なる値を与える計算の仕方もある．
　以下に，通常の重みづけで Levenshtein distance を計測する CGI を置いておく．試しに「#1720. Shakespeare の綴り方」 ([2014-01-11-1]) より25種類の異綴字を取り出して，カンマ区切りなどで下欄に入力してみてください（要するに以下をコピペ）．Shakespeare, Schaksp, Shackespeare, Shackespere, Shackspeare, Shackspere, Shagspere, Shakespe, Shakespear, Shake-speare, Shakespere, Shakespheare, Shakp, Shakspe?, Shakspear, Shakspeare, Shak-speare, Shaksper, Shakspere, Shaxberd, Shaxpeare, Shaxper, Shaxpere, Shaxspere, Shexpere

　綴字間の類似度や相違度の計測は，曖昧検索やスペリングチェックなどの実用的な目的にも応用されている．標準的な綴字がなかった古い英語の研究にも，ときに役立つことがありそうだ．

[ 固定リンク | 印刷用ページ ]