ノート:レーベンシュタイン距離

外部リンクの http://www15.big.or.jp/~t98907/ld/ にあるソフト「編集距離1.1」ですが、ここの説明と異なる結果を返します。 たとえば、kittenとsittingの編集距離は、擬似コードでは３になるが、ソフトでは５を返します。考え方が若干違うだけで本質は同じようではあるのですが、混乱を招く気がします。

--sna17

上のフリーソフトをダウンロードして生成された行列を確認してみましたが、このソフトはレーベンシュタイン距離の算出にあたって、文字列の置換コストを2と見なす計算を行っているようです。

ソフトの配布サイトから参考資料としてリンクが貼られている、グーグルブックス内のDaniel Jurafsky, James H.Martin のSpeech and Laguage Processing、Minimum Edit Distanceの節[1]に目を通して見たところ、74ページの中ほどに以下の記述がありました。

We can also assign a paticular cost or weight to each of these operations [insertion, deletion, and substitution]. The Levenshtein distance between two sequences is the simplest weighting factor in which each of the three operations has a cost of 1 (Levenshtein, 1966). Thus, the Levenshtein distance between intention and execution is 5. Levenshtein also proposed an altrernative version of his metric in which each insertion or deletion has a cost of 1 and substitutions are not allowed (equivalent to allowing substitution, but giving each substitution a cost of 2 since any substitution can be represented by one insertion and one deletion). Using this version, the Levenshtein distance between intention and execution is 8.

私は情報理論に関してはまったくの門外漢なので、どちらのレーベンシュタイン距離が主流として用いられているのかは分かりませんが、とりあえず応急処置として、置換を禁止する（＝置換のコストを2と見なす）バージョンのレーベンシュタイン距離について本記事に加筆してみました。--Kasuga 2009年8月25日 (火) 10:50 (UTC)

Vladimir Levenshteinの表記について

Vladimir Levenshteinの名前はウラジーミル・レーベンシュタインと表記されていました。後の編集でより原語の発音に近づけた表記にされましたが、以前のものの方が適切ではないでしょうか。Vladimirは慣習的にウラジーミルと表記されることが多いですし（例：ウラジーミル・アーノルド、ウラジミーーミル・ナボコフ）、Levenshteinの方も（書籍による表記は調べていませんが、検索結果（https://www.google.co.jp/search?q=Levenshtein+site:ac.jp）を見る限りではレーベンシュタイン表記が多いです。なので、彼の記事が立項されるときには原語音声（ IPA: [vlɐˈdʲimʲɪr lʲɪvʲɪnˈʂtʲejn]、ヴラディミール・リィヴィンシュテイン？）は記事中で触れられるでしょうが、記事名はウラジミーーミル・レーベンシュタインであるべきでしょう。したがってリンクラベルもそのようにするべきです。--ARAKI Satoru（会話） 2015年12月10日 (木) 13:27 (UTC)

ウラジーミルとウラジミールで混乱があるようです．「ウラジーミル・レーベンシュタイン」（あるいはウラジミール・レーベンシュタイン）が広く一般的であるというのならばその表記に反対はしません．新規作成 (利用者名) （会話） 2015年12月11日 (金) 05:31 (UTC)