山本隆の開発日誌

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

このプログラムはパターンが文字列に一致するかどうかをテストします。
パターンでは、「?」を先頭に付加した文字列を変数とします。
たとえば「?x」は変数です。

次のような動作を期待します。

文字の比較

matching("Hanako", "Hanako") #=> True
matching("Taro", "Hanako") #=> False

変数を含むパターンとの比較

matching("I am ?x", "I am Hanako") #=> True(?x : Hanako)

同じ変数を複数回使用できる。

matching("?x is ?x", "a is a") #=> True(?x : a)
matching("?x is ?x", "a is b") #=> False

複数の変数を使用できる

matching("?x is ?y", "a is b") #=> True(?x : a, ?y : b)

ソースコードの全体です。

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

import re

def matching(string1, string2):
    """
    実際にマッチングを行う関数
    @param string1: マッチングをする文字列
    @param string2: マッチングをする文字列
    @return: 成功ならTrue，失敗なら False
    """
    vars = {} #変数と値の辞書

    print string1
    print string2

    # 同じなら成功
    if string1 == string2: return True

    # 各々トークンに分ける
    r = re.compile('\s')
    sl1 = r.split(string1)
    sl2 = r.split(string2)

    # 数が異なったら失敗
    if len(sl1) != len(sl2): return False

    # 定数同士
    for s1, s2 in zip(sl1, sl2):
        if not token_matching(s1, s2, vars):
            return False

    # 最後まで O.K. なら成功
    print vars
    return True

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

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

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

if __name__ == "__main__":
    print matching("Hanako", "Hanako")
    print matching("Taro", "Hanako")
    print matching("I am ?x", "I am Hanako")
    print matching("?x is ?x", "a is a")
    print matching("?x is ?x", "a is b")
    print matching("?x is ?y", "a is b")