質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

1回答

1710閲覧

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

izonecf

総合スコア10

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

1クリップ

投稿2021/02/21 15:37

前提・実現したいこと

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

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

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

該当のソースコード

メインクラス

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

Java

1public static void main(String[] args) { 2 3 if(args.length == 1){ 4 5 System.out.println("検索するデータセットを選択 \n" 6 + "0 :サンプルデータセット \n" 7 + "1 :自作のデータセット \n" 8 + ":"); 9 10 Scanner scan = new Scanner(System.in); 11 int key = scan.nextInt(); 12 13 String filename = ("src/dataset_example.txt"); 14 15 switch(key) { 16 17 case 0 : filename = ("src/dataset_example.txt"); 18 19 } 20 21 try{ 22 File file = new File(filename); 23 BufferedReader br = new BufferedReader(new FileReader(file)); 24 25 String str; 26 while((str = br.readLine()) != null){ 27 28 29 if(new Matcher().matching(args[0],str)) { 30 31 System.out.println(str); 32 33 } 34 } 35 36 br.close(); 37 }catch(FileNotFoundException e){ 38 System.out.println(e); 39 }catch(IOException e){ 40 System.out.println(e); 41 } 42 43 // ****************ここまでパターンが1つの場合*********************** 44 45 }else if (args.length == 2){ 46 //System.out.println((new Matcher()).matching(args[0],args[1])); 47 48 49 System.out.println("検索するデータセットを選択 \n" 50 + "0 :サンプルデータセット \n" 51 + "1 :自作のデータセット \n" 52 + ":"); 53 54 Scanner scan = new Scanner(System.in); 55 int key = scan.nextInt(); 56 57 String filename = ("src/dataset_example.txt"); 58 59 switch(key) { 60 61 case 0 : filename = ("src/dataset_example.txt"); 62 63 } 64 65 try{ 66 File file = new File(filename); 67 BufferedReader br = new BufferedReader(new FileReader(file)); 68 69 String str; 70 71 Unifier uni = new Unifier(); 72 73 uni.unify(args[0],args[1]); 74 75 while((str = br.readLine()) != null){ 76 77 uni.unify(args[0],str); 78 uni.unify(args[1],str); 79 80 // if(uni.unify(args[0],str)) {} 81 // if(uni.unify(args[1],str)) {} 82 83 } 84 85 uni.vars.toString(); 86 87 br.close(); 88 }catch(FileNotFoundException e){ 89 System.out.println(e); 90 }catch(IOException e){ 91 System.out.println(e); 92 } 93 94 95 96 97 // ****************ここまでパターンが2つの場合************************ 98 }else {System.out.println("引数は1または2です"); 99 } 100 } 101 102 103 104 } 105 106

Unifierクラス

Java

1class Unifier { 2 StringTokenizer st1; 3 String buffer1[]; 4 StringTokenizer st2; 5 String buffer2[]; 6 HashMap<String,String> vars; 7 8 Unifier(){ 9 vars = new HashMap<String,String>(); 10 } 11 12 public boolean unify(String string1,String string2,HashMap<String,String> bindings){ 13 this.vars = bindings; 14 return unify(string1,string2); 15 } 16 17 public boolean unify(String string1,String string2){ 18 System.out.println(string1); 19 System.out.println(string2); 20 21 // 同じなら成功 22 if(string1.equals(string2)) return true; 23 24 // 各々トークンに分ける 25 st1 = new StringTokenizer(string1); 26 st2 = new StringTokenizer(string2); 27 28 // 数が異なったら失敗 29 if(st1.countTokens() != st2.countTokens()) return false; 30 31 // 定数同士 32 int length = st1.countTokens(); 33 buffer1 = new String[length]; 34 buffer2 = new String[length]; 35 for(int i = 0 ; i < length; i++){ 36 buffer1[i] = st1.nextToken(); 37 buffer2[i] = st2.nextToken(); 38 } 39 for(int i = 0 ; i < length ; i++){ 40 if(!tokenMatching(buffer1[i],buffer2[i])){ 41 return false; 42 } 43 } 44 45 46 // 最後まで O.K. なら成功 47 System.out.println(vars.toString()); 48 System.out.println("TRUE") 49 return true; 50 } 51 52 boolean tokenMatching(String token1,String token2){ 53 if(token1.equals(token2)) return true; 54 if( var(token1) && !var(token2)) return varMatching(token1,token2); 55 if(!var(token1) && var(token2)) return varMatching(token2,token1); 56 if( var(token1) && var(token2)) return varMatching(token1,token2); 57 return false; 58 } 59 60 boolean varMatching(String vartoken,String token){ 61 if(vars.containsKey(vartoken)){ 62 if(token.equals(vars.get(vartoken))){ 63 return true; 64 } else { 65 return false; 66 } 67 } else { 68 replaceBuffer(vartoken,token); 69 if(vars.containsValue(vartoken)){ 70 replaceBindings(vartoken,token); 71 } 72 vars.put(vartoken,token); 73 } 74 return true; 75 } 76 77 void replaceBuffer(String preString,String postString){ 78 for(int i = 0 ; i < buffer1.length ; i++){ 79 if(preString.equals(buffer1[i])){ 80 buffer1[i] = postString; 81 } 82 if(preString.equals(buffer2[i])){ 83 buffer2[i] = postString; 84 } 85 } 86 } 87 88 void replaceBindings(String preString,String postString){ 89 Iterator<String> keys; 90 for(keys = vars.keySet().iterator(); keys.hasNext();){ 91 String key = (String)keys.next(); 92 if(preString.equals(vars.get(key))){ 93 vars.put(key,postString); 94 } 95 } 96 } 97 98 99 boolean var(String str1){ 100 // 先頭が ? なら変数 101 return str1.startsWith("?"); 102 } 103 104} 105

試したこと

ファイルを順次読み込んでマッチングしていきました、パターン1つの場合は毎回新しくマッチングして検査すればよかったのですが
2つの場合、それまでの変数が束縛されている状態を保持しないともう1つのパターンがマッチした時に困ります
しかし、それでは最後まで変数が束縛されてしまい、解が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>などのようにすべての解を表示したいです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

条件を満たすすべての解の組み合わせを表示したいが、変数束縛によって解の組が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)全ての組み合わせを列挙するサンプルです。

Java

1public class Main { 2 public static void main(String[] args) { 3 Main obj = new Main(); 4 obj.run(); 5 } 6 7 String[][] resultSet = null; 8 private void run() { 9 // x, y, zの解のセットを生成 10 resultSet = new String[3][]; 11 resultSet[0] = new String[] {"x1", "x2"}; 12 resultSet[1] = new String[] {"y1", "y2", "y3"}; 13 resultSet[2] = new String[] {"z1", "z2", "z3", "z4"}; 14 String[] result = new String[resultSet.length]; 15 solve(result, 0); 16 } 17 18 private void solve(String[] result, int ind) { 19 if (resultSet.length <= ind) { 20 String s = String.join(", ", result); 21 System.out.println(s); 22 return; 23 } 24 25 for (int i = 0; i < resultSet[ind].length; i++) { 26 result[ind] = resultSet[ind][i]; 27 solve(result, ind + 1); 28 } 29 } 30}

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

CMD

1C>javac Main.java 2 3C>java Main 4x1, y1, z1 5x1, y1, z2 6x1, y1, z3 7x1, y1, z4 8x1, y2, z1 9x1, y2, z2 10x1, y2, z3 11x1, y2, z4 12x1, y3, z1 13x1, y3, z2 14x1, y3, z3 15x1, y3, z4 16x2, y1, z1 17x2, y1, z2 18x2, y1, z3 19x2, y1, z4 20x2, y2, z1 21x2, y2, z2 22x2, y2, z3 23x2, y2, z4 24x2, y3, z1 25x2, y3, z2 26x2, y3, z3 27x2, y3, z4

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

投稿2021/02/22 02:49

編集2021/02/22 03:02
dodox86

総合スコア9183

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

dodox86

2021/02/22 03:39

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

2021/02/22 23:30

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

2021/02/23 07:28

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

2021/02/24 12:58

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

2021/02/25 08:53

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

2021/02/25 09:35

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

2021/02/26 03:30

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

2021/02/26 09:18

@dodox86さん すいません、Matchingクラスは検証用にmainメソッドが入っているものでした、mainメソッド以外の/** * 実際にマッチングを行うクラス */ と書かれた以下の部分がMatcher クラスです、申し訳ありません @xebmeさん ありがとうございます、変数はインスタンス毎にHashMapで管理しているので、何とかそこから上手く取り出して集合を作る方向で頑張ってみようと思います!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問