レーベンシュタイン距離と文字列の変化を求める

しょうもないアイデアがひらめいたのですが，それを実現するために，Rubyでレーベンシュタイン距離と，その距離であることが確認できる，文字列変化の系列を求めるコードを書いてみました．
参考にしたものは以下のとおり．

• Wikipedia:レーベンシュタイン距離
• 編集距離 (Levenshtein Distance) - naoyaのはてなダイアリー
• ruby でレーベンシュタイン距離（編集距離）の計算 - Λάδι Βιώσας
• RAA Search (Levenshtein)*1

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-

# levenshtein-distance.rb

class LevenshteinDistance
  def initialize(str1, str2)
    @before, @after = str1, str2
    analyze
  end
  attr_reader :before, :after
  
  def before_substr(len); @before[0, len].join; end
  def after_substr(len); @after[0, len].join; end

  def analyze
    @before = @before.split(//u) if String === @before
    @after = @after.split(//u) if String === @after

    col = @before.size + 1
    row = @after.size + 1
    @dist = row.times.inject([]) {|a, i| a << [0] * col}
    @seq = row.times.inject([]) {|a, i| a << [""] * col}
    @dir = row.times.inject([]) {|a, i| a << [9] * col}
    col.times {|i|
      @dist[0][i] = i;
      @seq[0][i] = (i == 0) ? [""] : @seq[0][i - 1] + [before_substr(i)]
    }
    row.times {|i|
      @dist[i][0] = i;
      @seq[i][0] = (i == 0) ? [""] : [after_substr(i)] + @seq[i - 1][0]
    }

    @before.size.times do |i|
      @after.size.times do |j|
        cost = (@before[i] == @after[j]) ? 0 : 1
        x = i + 1
        y = j + 1
        d1 = @dist[y][x - 1] + 1
        d2 = @dist[y - 1][x] + 1
        d3 = @dist[y - 1][x - 1] + cost
        @dist[y][x] = dmin = [d1, d2, d3].min

        case dmin
        when d1
          @seq[y][x] = @seq[y][x - 1] + [before_substr(i + 1)]
          @dir[y][x] = 1
        when d2
          @seq[y][x] = [after_substr(j + 1)] + @seq[y - 1][x]
          @dir[y][x] = 2
        else
          @seq[y][x] = @seq[y - 1][x - 1].map {|s| s + @before[i]}
          if cost == 1
            @seq[y][x].unshift(after_substr(j + 1))
          end
          @dir[y][x] = 3
        end
      end
    end
  end
  
  def distance
    @dist[-1][-1]
  end
  
  def sequence
    @seq[-1][-1].reverse
  end
  
  def debug_print
    require "pp"
    pp @dist
    @seq.each_with_index do |f, i|
      f.each_with_index do |g, j|
        puts "@seq[#{i}][#{j}]<#{@dir[i][j]}> = #{g.inspect}"
      end
    end
  end
end

if __FILE__ == $0
  [["abc", "abc"], 
   ["kitten", "sitting"], 
   ["aaaaa", "bbbbb"],
   ["たけのこ", "たけひこm"]].each do |str1, str2|
    lev = LevenshteinDistance.new(str1, str2)
    puts "distance(#{str1}, #{str2}) = #{lev.distance}"
    puts "sequence(#{str1}, #{str2}) = #{lev.sequence.inspect}"
    if $DEBUG
      lev.debug_print
    end
  end
end

考え方は単純で，距離を格納する2次元のリスト@distのほかに，文字列の変化を保持するリスト@seqをつくりました．
もう少し具体的に書くと，@dist[y][x] は，「1番目の文字列の先頭からx文字分」と「2番目の文字列の先頭からy文字分」のレーベンシュタイン距離となります．xやyが0のときは，空文字列です．
@seq[y][x]は，「2番目の文字列の先頭からy文字分」から「1番目の文字列の先頭からx文字分」*2への変化を表す文字列のリストで，その要素数は，@dist[y][x]+1になります（レーベンシュタイン距離が1なら，ゴール，スタートの2個の文字列です）．
xが1番目の文字列の長さ，yが2番目の文字列の長さに等しいときの，@dist[y][x]が求めたいレーベンシュタイン距離で，@seq[y][x]を反転させたものが，知りたい文字列変化となります．
これまで同様，Ruby1.8，1.9両対応を考慮して，文字列は1文字単位で分解した配列に変換して使用しています．@dirは動作確認用です．2次元の表の左の値を使用して，@dist[y][x]を求めたのなら，@dir[y][x]には1が入り，上なら2，左上なら3，初期設定（最上段，最左列）は9としています．
実行結果は以下のとおり．

$ ruby levenshtein-distance.rb
distance(abc, abc) = 0
sequence(abc, abc) = ["abc"]
distance(kitten, sitting) = 3
sequence(kitten, sitting) = ["kitten", "sitten", "sittin", "sitting"]
distance(aaaaa, bbbbb) = 5
sequence(aaaaa, bbbbb) = ["aaaaa", "baaaa", "bbaaa", "bbbaa", "bbbba", "bbbbb"]
distance(たけのこ, たけひこm) = 2
sequence(たけのこ, たけひこm) = ["たけのこ", "たけひこ", "たけひこm"]

「ruby -d levenshtein-distance.rb」を実行すると，@dist，@seq，@dirの中身を知ることができます．
「しょうもないアイデア」とは何かですが，「タケヒコ」でも「ワカヤマ」でも何でもいいので，カタカナ書きの文字列と，ポケモンの各名称とでレーベンシュタイン距離を求め，最小のポケモン名と，その文字列の変化を知りたくなったのでした．フシギダネからアルセウスまで書かれているポケモンずかんをWebで見つけてダウンロードし，もう一つRubyスクリプトを書いて実行したところ，「タケヒコ」「ワカヤマ」とも，ポケモン名の語群の中で最小のレーベンシュタイン距離は，3でした．

*1:見つかった2つのライブラリについて，ソースまで見ましたが，距離を求めるだけで，文字列の変化を求めていませんでした．

*2:方向が逆なのは，参考にしたコードに，この値を求める処理を付け加えたためで，少々の変更で，逆順にならないようにできそうです．