レーベンシュタイン距離(Levenshtein Distance)

文字列同士の類似度にはいくつかあるが，今回はLsDを用い た類似度を使用する．LsDとは,一つの文字列をもう一つの文字列にす るための編集回数である.編集には,挿入編集(Insertion),削除編集(Deletion),置換編集(Substitution)の三つがあ る．一つの文字列を入力文，もう一つの文字列を日本語原文として編集内容を説 明する．挿入編集は入力文に存在せず，日本語原文に存在する必要な単語を挿入する編 集である．削除編集は入力文に存在し，日本語原文に存在しない不必要な単語に 対して行われる編集である．置換編集は，入力文の不必要な単語を，日本語原文 の必要な単語に置き換える，挿入編集と削除編集を同時に行う編集である． この編集回数の総和がレーベンシュタイン距離となる． 　レーベンシュタイン距離を求める手順を表4.1の入力文と日本語原文を用い て示す．

表 4.1: レーベンシュタイン例:データ

入力文	彼 は 車 で 海 に 行 く 。
日本語原文	今日 彼 は 山 に 行 く 。

手順1

入力文の単語と日本語原文の単語の対応を取得する．対応は動的計画 法より取得する．対応を取った結果を表4.2に示す．

表 4.2: レーベンシュタイン例:対応

入力文	彼 は 車 で 海 に 行 く 。
日本語原文	今日 彼 は 　　山 に 行 く 。

手順2

入力文を日本語原文にするための編集を行う．編集内容を図 4.1に示す．

図 4.1: レーベンシュタイン距離:編集

手順3

編集回数の総和を求め，それをレーベンシュタイン距離とする．今 回の例では挿入編集一回，削除編集二回，置換編集一回となり，入 力文と日本語原文のレーベンシュタイン距離は4となる．