http://qiita.com/mpyw/items/a4495d476ea9ffe54e16
にてpython実装されている Damerau–Levenshtein アルゴリズム。
from weighted_levenshtein import dam_lev
にて読込んでいるdam_lev()。
それに対応するC実装は以下のものが使えそうだろうか。
http://stackoverflow.com/questions/10727174/damerau-levenshtein-distance-edit-distance-with-transposition-c-implementation
answered May 24 '12 at 16:35
Dmitri Chubarov
の
int dldist2(char *s, char* t, int n, int m) {
元記事のpython実装のdam_lev()のコール文と比べて引数の数が異なる。
上記のコードを試した。
http://ideone.com/HFEmDT
- M=16, N=16なら動く
- M=32, N=32以上はRuntime error
- ideoneのメモリ制約か、実行時間制約か?
- insert_costs, delete_costs, substitute_costs, transpose_costsの適用方法は不明
とりあえずここで保留とする。
Runtime errorの理由
cost = ((s[i-1]==t[j-1])?0:1);
にてエラーが出る。
s,tというのは以下での文字列"BANANA", "HANANA"のポインタである。iやjが(32-1)になるとs[i-1]などは文字列として定義していない部分を参照している。
dist = dldist2("BANANA", "HANANA", 32, 32);
こういう場合、msize, nsizeにどういう値を入れるべきか、ということを理解していない。
substitute_costs などのサイズ128x128とは別のサイズを使うのかもしれない。
https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
のDistance with adjacent transpositionsのPseudo codeを見ると、以下のようだ。
- nsize: 上記の例で"BANANA"のサイズ
- msize: 上記の例で"HANANA"のサイズ
各種costの処理追加方針
https://github.com/infoscout/weighted-levenshtein/blob/master/weighted_levenshtein/clev.pyx
に記載のc_damerau_levenshtein()をまねる。
- DTYPE_t[::1] insert_costs,
- DTYPE_t[::1] delete_costs,
- DTYPE_t[:,::1] substitute_costs,
- DTYPE_t[:,::1] transpose_costs) nogil: