読者です 読者をやめる 読者になる 読者になる

あのねノート

せんせいあのね、パソコンで字が書けるようになったよ

編集距離を求めようとしてみた

情報系なのでパターン認識の授業を受けているのですが、編集距離の求め方がよくわからなかったので調べて書いてみることにしました。

そもそも編集距離とは

2つの文字列を用意したとき、一方の文字列に対して1文字削除、1文字挿入、1文字置換の作業を最低何回行えばもう一方の文字列になるかを計算したもので、2つの文字列がどれぐらい似ているかを数値化することができる。レーベンシュタイン距離とも言う。

ウィキペディア(レーベンシュタイン距離 - Wikipedia)に編集距離を求める擬似コードが載っていて、それをRacketに書きかえるうちに何が分からなかったのかよく分からなくなってしまったのでとりあえずコードを貼っておきます。

実装した

#lang racket
(define (l-distance s1 s2)
  (define (cost c1 c2) ;;置換によるコストを1とする
    (if (eq? c1 c2) 0 1))
  (let* ((l1 (string-length s1))
         (l2 (string-length s2)))
    (cond
      ((= l1 0) l2) ;;長さ0の文字列と長さlの文字列の距離はl
      ((= l2 0) l1)
      (else
       (let*
           ((s1sub (substring s1 0 (- l1 1)))
            (s2sub (substring s2 0 (- l2 1)))
            (c1 (string-ref s1 (- l1 1)))
            (c2 (string-ref s2 (- l2 1)))
            (l-cost (cost c1 c2))
            (a (+ (l-distance s1sub s2) 1)) ;;挿入コスト
            (b (+ (l-distance s1 s2sub) 1)) ;;削除コスト
            (c (+ (l-distance s1sub s2sub) l-cost)) ;;置換コスト
            )
         (min a b c)
         )
       ))))

元の擬似コードでは配列を使っていたのですがRacketにそれらしきものがなかった気がしたのでどうしようと思っていたのですが、string-refとかsubstringとかで同じことができるっぽいことがわかってよかったです(ほんとかな)。
実行するとこんな感じになります。

> (l-distance "kitten" "sitting")
3

間違ってたらごめんなさい。