Stanford大学の自然言語処理講座(1-7)最短編集距離 〜最短編集距離の定義〜


こんにちは。藤井です。

Stanfordの自然言語処理講座、Edit Distance(編集距離)の項に入っていまいりました。

Defining Minimum Edit Distance

最短編集距離とは、2つの文章がどれくらい似ているか、を調べるものです。
2つの文字列の類似度は、機械翻訳、情報抽出、音声認識などあらゆるところで重要になります。
最短編集距離とは挿入、削除、置換などの操作で、1つの文字列をもう一方の文字列に変換したときに必要になる操作の数を指します。

INTENTION と EXECUTION という、2つの文字列の対応で考えてみましょう。

INTENTION を EXECUTIONに変換するためには

d=delete(削除)

s=Substitution(置換)

i=insert(挿入)

となります。

各文字列操作を1とすれば、編集距離は5となります。

なお、置換の距離を2にしたものをレーベンシュタイン距離といいます。
削除と挿入は1で、置換は2。これで考えると、上の編集距離は8となります。

自然言語処理での、編集距離の応用例

・機械翻訳
プロが訳したものと、機械が翻訳したものを比較して、機械翻訳システムの性能を比較することにも応用できます。

・固有表現抽出
以下の赤字は同じものだ、ということがわかるようになります。
IBM Inc. announced today
IBM profits

Stanford President John Hennessy announced yesterday
for Stanford University President John heneesy

最短編集距離の定義

・長さnの文字列X、長さmの文字列Yがあるとします。

・編集距離は D(i,j)と定義します。
編集距離D(i,j)は、X[1.,i](1文字目からi文字目)とY[1.,j](1文字目からj文字目)の距離です。
それゆえ、X(n文字)とY(m文字)の最終編集距離は、D(n,m) となります。

今日はここまでです。次回に続きます。


This entry was posted in 自然言語処理(NLP) and tagged , , . Bookmark the permalink.