パターンマッチングを使った簡単なデータベース検索

Question

前提・実現したいこと

パターンマッチングを使って簡単なデータベース検索がしたい

発生している問題・エラーメッセージ

条件を満たすすべての解の組み合わせを表示したいが、変数束縛によって解の組が１つしか表示できない
方針またはやり方を教えてほしい

該当のソースコード

メインクラス

問題があるのは引数で２つパターンを入力した場合です。

public static void main(String[] args) {
		
		if(args.length == 1){
			
			System.out.println("検索するデータセットを選択 \n"
					+ "0 :サンプルデータセット \n"
					+ "1 :自作のデータセット \n"
					+ ":");
			
			Scanner scan = new Scanner(System.in);
			int key = scan.nextInt();
			
			String filename = ("src/dataset_example.txt");
			
			switch(key) {
			
			case 0 : filename = ("src/dataset_example.txt");
			
			}
			
			try{
				  File file = new File(filename);
				  BufferedReader br = new BufferedReader(new FileReader(file));

				  String str;
				  while((str = br.readLine()) != null){
					
				    
				    if(new Matcher().matching(args[0],str)) {
				    	
				    	System.out.println(str);
				    	
				    }
				  }			 

				  br.close();
				}catch(FileNotFoundException e){
				  System.out.println(e);
				}catch(IOException e){
				  System.out.println(e);
				}
			
	// ****************ここまでパターンが１つの場合***********************
			
		}else if (args.length == 2){
			//System.out.println((new Matcher()).matching(args[0],args[1]));
			
			
			System.out.println("検索するデータセットを選択 \n"
					+ "0 :サンプルデータセット \n"
					+ "1 :自作のデータセット \n"
					+ ":");
			
			Scanner scan = new Scanner(System.in);
			int key = scan.nextInt();
			
			String filename = ("src/dataset_example.txt");
			
			switch(key) {
			
			case 0 : filename = ("src/dataset_example.txt");
			
			}
			
			try{
				  File file = new File(filename);
				  BufferedReader br = new BufferedReader(new FileReader(file));

				  String str;
				  
				  Unifier uni = new Unifier();
				  
				  uni.unify(args[0],args[1]);
				  
				  while((str = br.readLine()) != null){
					
					  uni.unify(args[0],str);
					  uni.unify(args[1],str);			
				    
				   // if(uni.unify(args[0],str)) {}
				   // if(uni.unify(args[1],str)) {}
				    
				  }
				  
				  uni.vars.toString();

				  br.close();
				}catch(FileNotFoundException e){
				  System.out.println(e);
				}catch(IOException e){
				  System.out.println(e);
				}
				
			
		
			
	// ****************ここまでパターンが２つの場合************************
		}else {System.out.println("引数は１または２です");
			}
	    }
		
		
		
	}

Unifierクラス

class Unifier {
    StringTokenizer st1;
    String buffer1[];    
    StringTokenizer st2;
    String buffer2[];
    HashMap<String,String> vars;
    
    Unifier(){
        vars = new HashMap<String,String>();
    }

    public boolean unify(String string1,String string2,HashMap<String,String> bindings){
        this.vars = bindings;
        return unify(string1,string2);
    }

    public boolean unify(String string1,String string2){
        System.out.println(string1);
        System.out.println(string2);
    
        // 同じなら成功
        if(string1.equals(string2)) return true;
    
        // 各々トークンに分ける
        st1 = new StringTokenizer(string1);
        st2 = new StringTokenizer(string2);
    
        // 数が異なったら失敗
        if(st1.countTokens() != st2.countTokens()) return false;
    
        // 定数同士
        int length = st1.countTokens();
        buffer1 = new String[length];
        buffer2 = new String[length];
        for(int i = 0 ; i < length; i++){
            buffer1[i] = st1.nextToken();
            buffer2[i] = st2.nextToken();
        }
        for(int i = 0 ; i < length ; i++){
            if(!tokenMatching(buffer1[i],buffer2[i])){
                return false;
            }
        }
    
    
        // 最後まで O.K. なら成功
        System.out.println(vars.toString());
        System.out.println("TRUE")
        return true;
    }

    boolean tokenMatching(String token1,String token2){
        if(token1.equals(token2)) return true;
        if( var(token1) && !var(token2)) return varMatching(token1,token2);
        if(!var(token1) &&  var(token2)) return varMatching(token2,token1);
        if( var(token1) &&  var(token2)) return varMatching(token1,token2);
        return false;
    }

    boolean varMatching(String vartoken,String token){
        if(vars.containsKey(vartoken)){
            if(token.equals(vars.get(vartoken))){
                return true;
            } else {
                return false;
            }
        } else {
            replaceBuffer(vartoken,token);
            if(vars.containsValue(vartoken)){
                replaceBindings(vartoken,token);
            }
            vars.put(vartoken,token);
        }
        return true;
    }

    void replaceBuffer(String preString,String postString){
        for(int i = 0 ; i < buffer1.length ; i++){
            if(preString.equals(buffer1[i])){
                buffer1[i] = postString;
            }
            if(preString.equals(buffer2[i])){
                buffer2[i] = postString;
            }
        }
    }
    
    void replaceBindings(String preString,String postString){
    Iterator<String> keys;
    for(keys = vars.keySet().iterator(); keys.hasNext();){
        String key = (String)keys.next();
        if(preString.equals(vars.get(key))){
        vars.put(key,postString);
        }
    }
    }
    
    
    boolean var(String str1){
    // 先頭が ? なら変数
    return str1.startsWith("?");
    }

}

試したこと

ファイルを順次読み込んでマッチングしていきました、パターン１つの場合は毎回新しくマッチングして検査すればよかったのですが
２つの場合、それまでの変数が束縛されている状態を保持しないともう1つのパターンがマッチした時に困ります
しかし、それでは最後まで変数が束縛されてしまい、解が１つしか出ません

補足情報（FW/ツールのバージョンなど）

データベースは

Taro is a student
Taro studies philosophy
Taro loves hanako

hanako is a student
・・・

というようなものに対して"?x is a student"などのパターンを与えます

"?x is a student" "?studies ?y"としたときに

x と y の組として<taro,philosophy> <hanako, informatics>などのようにすべての解を表示したいです。

Answer 1

条件を満たすすべての解の組み合わせを表示したいが、変数束縛によって解の組が１つしか表示できない
方針またはやり方を教えてほしい

例えばxの解が[x1, x2]の2つ、yの解が[y1, y2, y3]の3つだとして、考えられる(x, y)が(x1, y1), (x1, y2), (x1, y3)...(x2, y2), (x2, y3)のように組み合わせを列挙したいということですね。方針、やり方として候補になりうるものをひとつ挙げるとすれば、「再帰」です。

以下はxの解が2つ、yの解が3つ、おまけでzの解が4つある場合の(x, y, z)全ての組み合わせを列挙するサンプルです。

public class Main {
    public static void main(String[] args) {
        Main obj = new Main();
        obj.run();
    }

    String[][] resultSet = null;
    private void run() {
        // x, y, zの解のセットを生成
        resultSet = new String[3][];
        resultSet[0] = new String[] {"x1", "x2"};
        resultSet[1] = new String[] {"y1", "y2", "y3"};
        resultSet[2] = new String[] {"z1", "z2", "z3", "z4"};
        String[] result = new String[resultSet.length];
        solve(result, 0);
    }

    private void solve(String[] result, int ind) {
        if (resultSet.length <= ind) {
            String s = String.join(", ", result);
            System.out.println(s);
            return;
        }

        for (int i = 0; i < resultSet[ind].length; i++) {
            result[ind] = resultSet[ind][i];
            solve(result, ind + 1);
        }
    }
}

Windows10上での実行結果です。2 * 3 * 4の24個の組み合わせが出力されていることが分かります。

C>javac Main.java

C>java Main
x1, y1, z1
x1, y1, z2
x1, y1, z3
x1, y1, z4
x1, y2, z1
x1, y2, z2
x1, y2, z3
x1, y2, z4
x1, y3, z1
x1, y3, z2
x1, y3, z3
x1, y3, z4
x2, y1, z1
x2, y1, z2
x2, y1, z3
x2, y1, z4
x2, y2, z1
x2, y2, z2
x2, y2, z3
x2, y2, z4
x2, y3, z1
x2, y3, z2
x2, y3, z3
x2, y3, z4

再帰を使う場合、再帰呼び出しの深さに注意しなければなりませんが、前もってその深さが見積れる場合には充分使える方法だと思います。

Comments

[dodox86]

この回答をどう応用するのか？というと、要はxの条件に合うものを配列なりリストなりで列挙、yの条件に合うものも列挙した後、(x, y)の組み合わせで出力すれば良いのでは、ということです。あらかじめ決められた(x, y)の2個の条件で組み合わせ列挙ならば再帰を使わずとも2重ループ固定でできますが、再帰はN個、任意の個数で組み合わせが得られるメリットがあります。

[izonecf]

ありがとうございます！どちらかというと、解の列挙ができないです
"?x is a student" "?x studies ?y" というパターンを入力するとまず ?x = hanako が代入されます その場合 ?y = philosophy が解として出ますが　
?x = hanako は固定されてしまうので例えばデータリストのhanakoより下にある ?x = Taro の場合の解が出力できない問題があります。何かいい方法はないでしょうか

[dodox86]

とりあえずご提示のコードのコンパイルが通らないので試してみようにもこれ以上は何とも。importを追加しても、main()メソッド中の
if(new Matcher().matching(args[0],str)) {
が謎です。Matcherクラスにmatchingと言うメソッドが見当たらないのですが、Javaは何のバージョンをお使いなのでしょうか。

[izonecf]

すいません、Matcherクラスはパターンとデータを比較して同じときtrueを返す関数で、コメントアウトで //ここまでがパターン１つの場合　と書いてある箇所は問題外なのです、一応 Matcherクラスも載せます

////

/***
Matching Program written

変数:前に？をつける．

Examle:
% Matching "Takayuki" "Takayuki"
true

% Matching "Takayuki" "Takoyuki"
false

% Matching "?x am Takayuki" "I am Takayuki"
?x = I .

% Matching "?x is ?x" "a is b"
false

% Matching "?x is ?x" "a is a"
?x = a .

Mating は，パターン表現と通常表現とを比較して，通常表現が
パターン表現の例であるかどうかを調べる．
Unify は，ユニフィケーション照合アルゴリズムを実現し，
パターン表現を比較して矛盾のない代入によって同一と判断
できるかどうかを調べる．

***/

import java.lang.*;
import java.util.*;

/**
* マッチングのプログラム
*
*/
class Matching {
public static void main(String arg[]){
if(arg.length != 2){
System.out.println("Usgae : % Matching [string1] [string2]");
}
System.out.println((new Matcher()).matching(arg[0],arg[1]));
}
}

/**
* 実際にマッチングを行うクラス
*
*/
class Matcher {
StringTokenizer st1;
StringTokenizer st2;
HashMap<String,String> vars;

Matcher(){
vars = new HashMap<String,String>();
}

public boolean matching(String string1,String string2,HashMap<String,String> bindings){
this.vars = bindings;
if(matching(string1,string2)){
return true;
} else {
return false;
}
}

public boolean matching(String string1,String string2){
//System.out.println(string1);
//System.out.println(string2);

// 同じなら成功
if(string1.equals(string2)) return true;

// 各々トークンに分ける
st1 = new StringTokenizer(string1);
st2 = new StringTokenizer(string2);

// 数が異なったら失敗
if(st1.countTokens() != st2.countTokens()) return false;

// 定数同士
for(int i = 0 ; i < st1.countTokens();){
if(!tokenMatching(st1.nextToken(),st2.nextToken())){
// トークンが一つでもマッチングに失敗したら失敗
return false;
}
}

// 最後まで O.K. なら成功
return true;
}

boolean tokenMatching(String token1,String token2){
//System.out.println(token1+"<->"+token2);
if(token1.equals(token2)) return true;
if( var(token1) && !var(token2)) return varMatching(token1,token2);
if(!var(token1) && var(token2)) return varMatching(token2,token1);
return false;
}

boolean varMatching(String vartoken,String token){
if(vars.containsKey(vartoken)){
if(token.equals(vars.get(vartoken))){
return true;
} else {
return false;
}
} else {
vars.put(vartoken,token);
}
return true;
}

boolean var(String str1){
// 先頭が ? なら変数
return str1.startsWith("?");
}

}

////

[xebme]

関係演算の結合と同じことをやればよい。<?x>の集合と、<?x,?y>の集合を別別に作る。最後に二つの集合の共通部分をとる。どちらにも同じ?xがある。

[xebme]

ちょっと単純すぎました。質問が2つあるので全体は、f(g(x), h(x,y))の形式。高階関数とするのがよさそうですが、...。

[dodox86]

＞@質問者izonecfさん

ご提示のコードでエラーが出る部分は
> if(new Matcher().matching(args[0],str)) {
の、Matcherクラスのmatchingメソッドです。対して[2021/02/24 21:58]の本コメント欄で追加でご提示いただいたコードはMatchingクラスで、クラス名が一致しません。別のソースファイルではないでしょうか。すみませんが、当方で実行、検証することを断念しました。

[izonecf]

@dodox86さん
すいません、Matchingクラスは検証用にmainメソッドが入っているものでした、mainメソッド以外の/**
* 実際にマッチングを行うクラス
*/　と書かれた以下の部分がMatcher クラスです、申し訳ありません

@xebmeさん
ありがとうございます、変数はインスタンス毎にHashMapで管理しているので、何とかそこから上手く取り出して集合を作る方向で頑張ってみようと思います！