レーベンシュタイン距離を求める
【内部主要記事】
【本文】
レーベンシュタイン距離を使って個体の適合度を求めます。
gaucheの配列に関する資料
http://www.shiro.dreamhost.com/scheme/gauche/man/gauche-refj_71.html
レーベンシュタイン距離に関する資料
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2
http://www-06.ibm.com/jp/developerworks/java/041217/j_j-jazzy.html#figure1
; 以下の2つのリストのレーベンシュタイン距離を求める (define str1 '(#\p #\z #\z #\e #\l)) (define str2 '(#\p #\u #\z #\z #\l #\e)) ; 解は 3 となる ; 補足：最終的な配列の状態 ; gosh> d ; #,(<array> (0 6 0 7) 0 1 2 3 4 5 6 ; 1 0 1 2 3 4 5 ; 2 1 1 1 2 3 4 ; 3 2 2 1 1 2 3 ; 4 3 3 2 2 2 2 ; 5 4 4 3 3 2 3)
【レーベンシュタイン距離を求めるコード】
ファイル loewenstein-distance.scm
; 配列を使えるようにする
(use gauche.array)
; テスト用リスト
; 文字のリスト文字列ではないが str1 str2 という表現で扱う
(define str1 '(#\p #\z #\z #\e #\l))
(define str2 '(#\p #\u #\z #\z #\l #\e))
(define loewenstein-distance
(lambda (str1 str2)
; length str1 + 1 行 length str2 + 1 列のテーブル d を用意する
(define d (make-array (shape 0 (+ (length str1) 1) 0 (+ (length str2) 1)) 0))
; #,(<array> (0 6 0 7) 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0)
; 配列dの初期化
; (do を使えば init1 と init2 に分ける必要はない。
; ループは再帰で行う方が望ましいと考え2つに分けたが
; こういう場合は下で定義してある calc-LD のように
; do でループしたほうがいいのだろうか？)
(define init1
(lambda (i1 len)
(cond ((> i1 len) d)
(else (array-set! d i1 0 i1) (init1 (+ i1 1) len)))))
(define init2
(lambda (i2 len)
(cond ((> i2 len) d)
(else (array-set! d 0 i2 i2) (init2 (+ i2 1) len)))))
;#,(<array> (0 6 0 7) 0 1 2 3 4 5 6
; 1 0 0 0 0 0 0
; 2 0 0 0 0 0 0
; 3 0 0 0 0 0 0
; 4 0 0 0 0 0 0
; 5 0 0 0 0 0 0)
; str1 と str2 のレーベンシュタイン距離を求める
(define calc-LD
(lambda ()
(let ((cost 0) (i1 1) (i2 2) (len1 (length str1)) (len2 (length str2)))
(do ((i1 1 (+ i1 1))) ((> i1 len1))
(do ((i2 1 (+ i2 1))) ((> i2 len2))
; array-refではないので -1 する必要がある
(if (eq? (list-ref str1 (- i1 1)) (list-ref str2 (- i2 1)))
(set! cost 0)
(set! cost 1))
(array-set! d i1 i2
(min (+ 1 (array-ref d (- i1 1) i2) )
(+ 1 (array-ref d i1 (- i2 1)) )
(+ cost (array-ref d (- i1 1) (- i2 1)) )))))
(array-ref d len1 len2))))
;#,(<array> (0 6 0 7) 0 1 2 3 4 5 6
; 1 0 1 2 3 4 5
; 2 1 1 1 2 3 4
; 3 2 2 1 1 2 3
; 4 3 3 2 2 2 2
; 5 4 4 3 3 2 3)
(init1 0 (length str1))
(init2 0 (length str2))
(calc-LD)))実行
gosh> (load "./loewenstein-distance.scm")
#t
gosh> (loewenstein-distance str1 str2)
3
次は、学習用とするアルファベット小文字のリストの集合(10〜20程度)の用意します(各リストはチャットなどでの1単位の発話とみなす)。ただ、自然言語は10〜20回程度の対話を見ると、その中に同じ単語が出てくるので、完全にランダムなアルファベット小文字のリストでは問題があるかとも考えました。しかし、アルファベット小文字の数の語しか登場しない特性は、ある特定のテーマのみを扱った対話のモデルとみなせるのではないかと考え、ランダムなアルファベット小文字のリストを学習用データとして採用する方向です。
