1段階のDPマッチング

　「宮沢弘の科学エッセイ２」の「動的計画法」(Dynamic Programming) (http://book1.adouzi.eu.org/n6631cs/15/) で、アルゴリズムの説明はしていますので、ここでは省略します。

　DPマッチングそのものは古典的な方法です。ですが、少し形が変わったり、別の今どきのアルゴリズムの奥底で実は使われていたりということがあるので、興味がある人は知っていても損はないと思います。

　サンプルはこちら[1]から閲覧およびDLをお願いします。

　これは "A" から "Z" の26単語を設定し、その中から一単語を認識用サンプルとして選び、その上で、そのサンプルが "A" から "Z" のどの単語かを認識するというような感じのサンプルです。

　1段階のDPマッチングだと、こういう感じの、単語認識っぽいのが限界です。2段階のDPマッチングだと、複数の語彙の組み合わさったものも可能ですが。それは、またそのうちにやります。

　いろいろ細かいことはREADME.txtに書いてあったりするので、そちらを参照してください。それでもちょっとだけ書いておくとすると、こんなあたりかなぁ。

　これを実行すると、例えば次のような結果が表示されます

[10, 0.234375]

　これは語彙番号と、距離のリストです。

　さて、そうしたら、sample.txtを読んでみてください。このような内容だったとします。

8752471207656428645717825336263746554425773876627347273223278345

#word is K ( 10 )

#word string is 8852471217656328646718725325263846554425784876727247373223178345

#error pattern is [0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 1, 0, 0, 0, 0, -1, 0, 0, -1, 1, 0, 0, 0, 1, 1, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, -1, 0, 0, 1, 0, 0, -1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]

　この2行めを見てください。先の出力の語彙番号は10で、認識サンプルとして選ばれているのも、語彙番号 "10" の "K" だと確認できます。

　words.txtを数えると、あるいは "A" から "Z" の順番を数えると、"K" は 11番目です。それに対して、この例では語彙番号は "10" になっています。これは、pythonでは配列は "0" 番から数えるためです。

　1段階だし、26単語(?)なので、すぐ計算できます。2段階になると結構時間かかるんですけど。それに1段階だと、こんなに簡単なプログラムなんですけどね。

　あ、計算をミスっても、つまりsample.txtにあるのとは別の語だと認識されても、文句はなしということで。むしろ、そういうこともあるという例と思ってください。

　計算をミスるのとは別にバグがあったらご連絡ください。たぶん大丈夫だと思いますけど。