前回(パターン照合(1))の続き。

『Javaによる知能プログラミング入門』の「2.探索とパターン照合」にあるパターン照合プログラムのソースコードをPythonで実装してみました。

前回のパターン照合プログラムは文字列とパターンが一致するかをテストしました。
今回のプログラムでは、2つのパターンが矛盾のない変数代入によって同一と判断できるかをテストします。

次のパターンをテストします。

print Unify().unify("Takayuki", "Takayuki")
print Unify().unify("Takayuki", "Takoyuki")
print Unify().unify("?x am Takayuki", "I am Takayuki")
print Unify().unify("?x is ?x", "a is b")
print Unify().unify("?x is ?x", "a is a")
print Unify().unify("?x is a", "b is ?y")
print Unify().unify("?x is a", "?y is ?x")

ユニフィケーション照合アルゴリズムというらしい。

関数をまたかってやりとりする変数(vars,buffer1,buffer2)があるので、クラスにしました。
読みやすくなったかどうかは、微妙なところです。

#! /usr/bin/python
# -*- coding: Shift_JIS -*-
import re

class Unify(object):
    def __init__(self):
        self.vars = {} #変数と値の辞書

    def unify(self, str1, str2):
        print str1
        print str2

        # 同じなら成功
        if str1 == str2: return True

        # 各々トークンに分ける
        r = re.compile('\s')
        self.buffer1 = r.split(str1)
        self.buffer2 = r.split(str2)

        # 数が異なったら失敗
        if len(self.buffer1) != len(self.buffer2): return False

        for i in range(len(self.buffer1)):
            if not self.token_matching(self.buffer1[i], self.buffer2[i]):
                return False

        print self.vars
        return True

    def token_matching(self, token1, token2):
        if token1 == token2: return True
        if var(token1) and not var(token2): return self.var_matching(token1, token2)
        if not var(token1) and var(token2): return self.var_matching(token2, token1)
        if var(token1) and var(token2): return self.var_matching(token1, token2)
        return False

    def var_matching(self, vartoken, token):
        if self.vars.has_key(vartoken):
            if token == self.vars[vartoken]:
                return True
            else:
                return False
        else:
            self.replace_buffer(vartoken, token);
            if self.vars.has_key(vartoken):
                self.replace_bindings(vartoken,token)
            self.vars[vartoken] = token
        return True

    def replace_buffer(self, pre_string, post_string):
        def replace_pre(x):
            if pre_string == x:
                return post_string
            else:
                return x
        self.buffer1 = map(replace_pre, self.buffer1)
        self.buffer2 = map(replace_pre, self.buffer2)

    def replace_bindings(self, pre_string, post_string):
        for key in self.vars.keys():
            if pre_string == self.vars[key]:
                self.vars[key] = post_string

def var(str):
    """ strは変数か。先頭が ? なら変数。 """
    return str.startswith("?")

if __name__ == "__main__":
    print Unify().unify("Takayuki", "Takayuki")
    print Unify().unify("Takayuki", "Takoyuki")
    print Unify().unify("?x am Takayuki", "I am Takayuki")
    print Unify().unify("?x is ?x", "a is b")
    print Unify().unify("?x is ?x", "a is a")
    print Unify().unify("?x is a", "b is ?y")
    print Unify().unify("?x is a", "?y is ?x")