文字列間のレーベンシュタイン距離を求める(3)Haskell版ふたたび

去年の12月に2つの文字列のレーベンシュタイン距離を求めるっていうのを、JavaScriptHaskell でやった。もともとは Python での実装を参考に2次元配列を使ってやってみたもので、JavaScript版はともかく Haskell版は2次元配列の更新に苦労した。
それが、今日ふと1次元配列でやってみたらどうだろうを思いついた。
つまりこうだ。(m + 1)行×(n + 1)列(m、n は比較する文字列2つの長さ)の各行をつなげた1次元配列を考えて、2次元配列の時の座標を表すタプル (i, j) で初期化しておく。0 < i, 0 < j のとき、(i, j) の値はひとつ左(i-1, j)、ひとつ上(i, j-1)、左上(i-1, j-1)から決まるから、これを1次元配列のインデックスに直すと次のようになる:

  • ひとつ左: i * (n + 1) + j – 1
  • ひとつ上: (i – 1) * (n + 1) + j
  • 左上: (i – 1) * (n + 1) + j – 1

これをコードに落としこんでやるとこうなった:

結果はこうだ。

takatoh@apostrophe $ runhaskell ld2.hs apple play
4
takatoh@apostrophe $ runhaskell ld2.hs perl pearl
1

OK、うまくいった。

だけど、上のコードはまだ2次元配列の意識を引きずっている。もっと単純にできるはずだ。1次元配列のインデックスを x とすると:

  • ひとつ左: x – 1
  • ひとつ上: x – (n + 1)
  • 左上: x – (n + 1) – 1

となる。これで一般部については2次元配列を気にしなくて良くなった。ただし問題がある。いちばん上の行(第0行)といちばん左の列(第0列)だ。少し考えて、x を (n + 1) で割った商と余りを使えばいいと気がついた。コードにするとこう:

1行だけだけど長くなってしまった。だけど考え方はシンプルのように思う。実行してみよう。

takatoh@apostrophe $ runhaskell ld3.hs apple play
4
takatoh@apostrophe $ runhaskell ld3.hs perl pearl
1

OK。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です