|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 距離 ： [きょり] 【名詞】1. distance 2. range
レーベンシュタイン距離（レーベンシュタインきょり、）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。名称は、1965年にこれを考案したロシアの学者 () にちなむ。 レーベンシュタイン距離は、同じ文字数の単語に対する置換編集に使われているハミング距離の一般化であると見なすことが可能である。レーベンシュタイン距離の更なる一般化として、例えば一回の操作で二文字を変換する等の方法が考えられる。 == 例 == 実際的な距離の求め方を例示すれば、「 kitten」を「sitting」に変形する場合には、以下に示すように最低でも 3 回の手順が必要とされるので、2単語間のレーベンシュタイン距離は 3 となる。#「 kitten」#「 sitten」（「k」を「s」に置換）#「 sittin」（「e」を「i」に置換）#「 sitting」（「g」を挿入して終了）上の変形では挿入・削除・置換のそれぞれのコストを1に設定したが、これらのコストには別々の値を割り振る事も可能である。例を挙げれば、挿入・削除のみを許可し、置換を禁止するタイプのレーベンシュタイン距離は、挿入・削除にコスト1、置換にコスト2が割り振られるレーベンシュタイン距離と等価である。この場合、「 kitten」と「sitting」の間のレーベンシュタイン距離は5となる〔Daniel Jurafsky and James H.Martin: ''Speech and Laguage Processing'', pp.74, Prentice Hall, 2009, ISBN 0-13-187321-0〕。抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「レーベンシュタイン距離」の詳細全文を読む スポンサード リンク
|