"An O(NP) Sequence Comparison Algorithm" with Python の添削

algorithm python

元ネタ: "An O(NP) Sequence Comparison Algorithm" with Python - 考える人、コードを書く人

おとなり日記をたまたま見たところ、面白そうな内容でしたので添削してみました。

  • ドキュメンテーション文字列をクラスの中に入れました
  • クラス名を Python コードのスタイルガイド - forest bookに準拠しました
  • 座標の大小判定に lambda 式を使いました
  • 未使用の変数 reverse を削除しました
  • editdis を直接返すようにしました
  • リスト fp の初期化をリスト内包表記にしました
  • ループブレイク条件を while 文で判定するようにしました
$ diff -u orig_onp.py t2y_onp.py
--- orig_onp.py	2009-08-01 21:24:56.000000000 +0900
+++ t2y_onp.py	2009-08-02 01:13:46.000000000 +0900
@@ -1,25 +1,14 @@
 # -*- coding: utf-8 -*-
-"""
-The algorithm implemented here is based on "An O(NP) Sequence Comparison Algorithm"
-by described by Sun Wu, Udi Manber and Gene Myers
-"""
-
-class onp(object):
 
+class Onp(object):
+    """
+    The algorithm implemented here is based on 
+    'An O(NP) Sequence Comparison Algorithm'
+    by described by Sun Wu, Udi Manber and Gene Myers
+    """
     def __init__(self, a, b):
-        self.a = a
-        self.b = b
-        self.m = len(a)
-        self.n = len(b)
-        self.editdis = 0
-        reverse = False
-        if self.m >= self.n:
-            self.a, self.b = self.b, self.a
-            self.m, self.n = self.n, self.m
-            self.reverse = True
-
-    def getEditDistance(self):
-        return self.editdis
+        small_large = lambda x,y,lx,ly: ((lx<=ly) and [x,y,lx,ly]) or [y,x,ly,lx]
+        self.a, self.b, self.m, self.n = small_large(a, b, len(a), len(b))
 
     def snake(self, k, p, pp):
         y = max(p, pp)
@@ -33,11 +22,9 @@
         offset = self.m
         delta  = self.n - self.m
         size   = self.m + self.n + 3
-        fp = []
-        for i in range(size):
-            fp.append(-1)
+        fp = [ -1 for i in range(size) ]
         p = -1
-        while (True):
+        while fp[delta+offset] < self.n:
             p = p + 1
             for k in range(-p, delta, 1):
                 fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])
@@ -46,6 +33,6 @@
                 fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])
 
             fp[delta+offset] = self.snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset])
-            if fp[delta+offset] >= self.n:
-                break
-        self.editdis = delta + 2 * p
+        
+        return (delta + 2 * p)   # editdis
+

コードそのもののリファクタリングは、さらにスマートに出来そうな気もしますが、擬似コードからの写経とあるので、オリジナルの実装スタイルを変更しないように修正してみました。実行部を含めた最終的なコードは以下になります。

#/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

class Onp(object):
    """
    The algorithm implemented here is based on 
    'An O(NP) Sequence Comparison Algorithm'
    by described by Sun Wu, Udi Manber and Gene Myers
    """
    def __init__(self, a, b):
        small_large = lambda x,y,lx,ly: ((lx<=ly) and [x,y,lx,ly]) or [y,x,ly,lx]
        self.a, self.b, self.m, self.n = small_large(a, b, len(a), len(b))

    def snake(self, k, p, pp):
        y = max(p, pp)
        x = y - k
        while x < self.m and y < self.n and self.a[x] == self.b[y]:
            x = x + 1
            y = y + 1
        return y

    def compose(self):
        offset = self.m
        delta  = self.n - self.m
        size   = self.m + self.n + 3
        fp = [ -1 for i in range(size) ]
        p = -1
        while fp[delta+offset] < self.n:
            p = p + 1
            for k in range(-p, delta, 1):
                fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])

            for k in range(delta+p, delta, -1):
                fp[k+offset] = self.snake(k, fp[k-1+offset]+1, fp[k+1+offset])

            fp[delta+offset] = self.snake(delta, fp[delta-1+offset]+1, fp[delta+1+offset])
        
        return (delta + 2 * p)   # editdis

def main():
    diff = Onp(sys.argv[1], sys.argv[2])
    editdis = diff.compose()
    print editdis
    
if __name__ == '__main__':
    main()

実行結果。

$ python t2y_onp.py abdefabced dababcbcbaed
8
$ python t2y_onp.py dababcbcbaed abdefabced
8

コードは読めますが、何をするアルゴリズムなのか、さっぱり分かりませんでした。以下のリファレンスを何度も読み返して、3時間ぐらい考え込んで、やりたい事をようやく理解しました。図解がなかったら、私はさっぱり理解できなかったと思います(- -#

リファレンス:
•¶‘”äŠridiffjƒAƒ‹ƒSƒŠƒYƒ€
http://amoi.mib.jp/typo/articles/2007/12/11/diffalgorithm
http://www.slash-zero.jp/archives/program/466
http://www.slash-zero.jp/archives/program/468
http://www.slash-zero.jp/archives/program/476