しょうもないアイデアがひらめいたのですが，それを実現するために，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でした．
