文字列の近似について調べ中。
文字列の比較と照合(PDFです)
『A.4 文字列の近似照合』のアルゴリズムを参考にテストしてみようと思ったんだけど、アルゴリズム中の関数の戻りがよく分からない。挿入／削除／置換について関数が定義されてるんだけど、内部操作は予想出来てもそこからの戻りが全く分からない。多分、整数値が返ってくる事を期待してると思うんだけど、何を整数で返せばいいんだ？
文字列の近似は、２つの文字列の『編集距離』で求めるらしい事は分かった。編集距離は、片方の文字列に編集操作を行いもう一方の文字列に近づけていき、２つの文字列が等価になるまでに要した操作回数。で、その編集操作が、挿入／削除／置換。
動的計画法ってのを理解しないとスタート地点にも立てないってことか？付録だけ読んでも駄目ってこと？それともどこか別のところに書いてあるのかな？
Cのライブラリとかで探した方が早いのかな。。。
