レーベンシュタイン距離

某求職掲示板で見つけたパズル。あわよくば答えつけて応募してやろうと思ったのだが、かなりハードルが高い。

問題はレーベンシュタイン距離が1の単語のネットワークを計算するというもの。レーベンシュタイン距離自体を求める処理は以下のように書ける。

(define (levenshtein-distance word1 word2)
  (define (table-ref t i j)
    (vector-ref (vector-ref t i) j))
  (define (table-set! t i j v)
    (vector-set! (vector-ref t i) j v))

  (define (make-table word1 word2)
    (let1 table (make-vector (+ (string-length word1) 1) 0)
      (dotimes (i (+ (string-length word1) 1))
 (vector-set! table i (make-vector (+ (string-length word2) 1) 0)))
      (dotimes (i (string-length word1))
 (table-set! table (+ i 1) 0 (+ i 1)))
      (dotimes (i (string-length word2))
 (table-set! table 0 (+ i 1) (+ i 1)))
      table))

  (let ((d (make-table word1 word2))
 (word1-size (string-length word1))
 (word2-size (string-length word2)))
    (dotimes (i word1-size)
      (dotimes (j word2-size)
 (if (char=? (string-ref word1 i) (string-ref word2 j))
     (table-set! d (+ i 1) (+ j 1) (table-ref d i j))
     (table-set! d (+ i 1) (+ j 1)
   (min (+ (table-ref d i (+ j 1)) 1)
        (+ (table-ref d (+ i 1) j) 1)
        (+ (table-ref d i j) 1))))))
    (table-ref d word1-size word2-size)))

普通にWikipediaに載っていたものをSchemeで書き直しただけ。メモリのアロケーションを気にして2次元配列を1次元で表現したバージョンも作ったんだけど、Sagittariusでは普通に書いた方がわずかに速かったので却下した。なんでだろう？

レーベンシュタイン距離を求めるアルゴリズムはO(mn)で、距離が1の物を自前で見つけるよりは速いと思うんだけど、問題なのはネットワークを構成するのに使用される単語リストが26万くらいあること。とりあえず与えられた単語をリストから順番に見ていくようにしたのだが、世代が4を超えた辺りで計算オーダーがとんでもないことになるっぽく、ちょっと現実的な時間で帰って来ない。(10分とかでは無理)。

根本的にO(n^m)になるような気がするのだけど、(nが単語リストでmが与えられた単語)、これに更に世代が入ってくるとげんなりするよなぁ。第一世代のmは一個だけど、二世代目以降は複数になるわけだし。なんか、別な方法があるのだろうか？