Created
June 10, 2012 09:58
-
-
Save uemuraj/2904730 to your computer and use it in GitHub Desktop.
セマンティックWebプログラミングの第２章から第３章の内容を試す。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // セマンティックWebプログラミングの第２章から第３章の内容を試す。 | |
| // | |
| class SimpleGraph { | |
| // 各インデックスとも [ a : [ b : [ c, .. ] ] ] の様な格納方法 | |
| def spo = [:] | |
| def pos = [:] | |
| def osp = [:] | |
| SimpleGraph(File csv) { | |
| csv.eachLine { | |
| // 恐ろしく適当にCSV形式を解釈する | |
| def (s, p, o) = it.split(',', 3) | |
| add(s, p, o) | |
| } | |
| } | |
| void add(String s, String p, String o) { | |
| add(spo, s, p, o) | |
| add(pos, p, o, s) | |
| add(osp, o, s, p) | |
| } | |
| void add(def index, String a, String b, String c) { | |
| def map = index.get(a) | |
| if (map == null) { | |
| index.put(a, [(b):[c]]) // !!! "b" がリテラルでないことを丸カッコで示す | |
| return; | |
| } | |
| def set = map.get(b) | |
| if (set == null) { | |
| map.put(b, [c]) | |
| return; | |
| } | |
| set.add(c) | |
| } | |
| def query(String qs, String qp, String qo) { | |
| // インデックスからそのまま結果を返すと順番が異なるため、結果を並べ替えるクロージャも渡す | |
| if (qs != null) { | |
| return query(spo, qs, qp, qo) { s, p, o -> [s, p, o] } | |
| } | |
| if (qp != null) { | |
| return query(pos, qp, qo, qs) { p, o, s -> [s, p, o] } | |
| } | |
| if (qo != null) { | |
| return query(osp, qo, qs, qp) { o, s, p -> [s, p, o] } | |
| } | |
| } | |
| def query(def index, String qa, String qb, String qc, Closure closure) { | |
| // qb と qc のどちらか、またはどちらも null の場合を処理する必要あり（ qa == null は何もしない） | |
| // 問い合わせ文字列が null であれば、その部分は存在するもの（複数あり）をあてる | |
| // 問い合わせの結果は、どの場合もフラットなリストへ展開して返す | |
| def map = index.get(qa) | |
| if (map == null) { | |
| return [] | |
| } | |
| def set = map.get(qb) | |
| if (set == null) { | |
| def results = [] | |
| if (qb == null) { | |
| if (qc == null) { | |
| map.each { b, values -> values.collect(results) { c -> closure.call(qa, b, c) } } | |
| } else { | |
| map.each { b, values -> if (values.contains(qc)) results.add(closure.call(qa, b, qc)) } | |
| } | |
| } | |
| return results | |
| } | |
| if (qc == null) { | |
| return set.collect { c -> closure.call(qa, qb, c) } | |
| } | |
| if (set.contains(qc)) { | |
| return [ closure.call(qa, qb, qc) ] | |
| } | |
| return [] | |
| } | |
| def query(def clauses) { | |
| Bindings bindings = new Bindings() | |
| // 検索条件として [ s, p, o ] 配列を複数受け取る | |
| clauses.each { clause -> | |
| def (clause_s, clause_p, clause_o) = clause | |
| // ここでは s, p, o それぞれの内容が変数名かリテラルを区別しない | |
| // bind() が実際の検索に使う問い合わせ文字列を返すので、全部の組み合わせを試す | |
| def query_s = bindings.bind(clause_s) | |
| def query_p = bindings.bind(clause_p) | |
| def query_o = bindings.bind(clause_o) | |
| query_s.each { qs -> | |
| query_p.each { qp -> | |
| query_o.each { qo -> | |
| def results = query(qs, qp, qo) | |
| // 元の検索文字列、検索結果、結果の何番目に対応するかを返すクロージャを渡す | |
| if (results.size() > 0) { | |
| bindings.bind(clause_s, results) { it[0] } | |
| bindings.bind(clause_p, results) { it[1] } | |
| bindings.bind(clause_o, results) { it[2] } | |
| } | |
| } | |
| } | |
| } | |
| bindings.flush() | |
| } | |
| return bindings | |
| } | |
| class Bindings extends LinkedHashMap<String, List<String>> { | |
| def buffer = [:] | |
| def groups = [] | |
| def bind(String qc) { | |
| // 変数名ではないリテラルならそのまま | |
| // まだ値が登録されていない変数なら null | |
| // 既に値が登録されている変数ならその値を返す | |
| // （値は複数登録されるので、ここでは返すのはどの場合もリストにしておく） | |
| if (!qc.startsWith('?')) { | |
| return [qc]; | |
| } | |
| if (!containsKey(qc)) { | |
| return [null] | |
| } | |
| return get(qc).clone() // !!! ConcurrentModificationException を避ける | |
| } | |
| def bind(String qc, def results, Closure closure) { | |
| // 変数名ではないリテラルなら何もしない | |
| // まだ値が登録されていない変数なら新規リストを登録 | |
| // 既に値が登録されている変数なら既存リストへ追加 | |
| if (!qc.startsWith('?')) { | |
| return null | |
| } | |
| if (!buffer.containsKey(qc)) { | |
| return buffer.put(qc, results.collect { closure.call(it) }) | |
| } | |
| def values = buffer.get(qc) | |
| results.each { values.add(closure.call(it)) } | |
| return values | |
| } | |
| void flush() { | |
| groups.add(buffer) | |
| buffer = [:] | |
| // 検索条件間は AND のため、これまでの検索結果の間で保持していない変数の値を相互に削除する | |
| for (;;) { | |
| int count = 0 | |
| for (def source in groups) { | |
| for (def target in groups) { | |
| if (!target.is(source)) { | |
| count += purge(target, source) | |
| } | |
| } | |
| } | |
| if (count == 0) { | |
| break | |
| } | |
| } | |
| // 本体へ結果を反映する | |
| for (def group in groups) { | |
| group.each { qc, results -> | |
| if (containsKey(qc)) { | |
| get(qc).retainAll(results) | |
| } else { | |
| put(qc, new TreeSet(results)) | |
| } | |
| } | |
| } | |
| } | |
| int purge(def target, def source) { | |
| // ターゲット、ソースどちらも [ 変数名 : [値, ...] ] となったマップ | |
| // ターゲットにソースと同じ変数があれば、ソースにある値に従ってターゲットの中の値を削除する | |
| int count = 0 | |
| source.each { qc, results -> | |
| if (target.containsKey(qc)) { | |
| count += purge(target, qc, results) | |
| } | |
| } | |
| return count | |
| } | |
| int purge(def map, String qc, def results) { | |
| // 削除のため、渡された値の中に同じ値がないもののインデックスを調べる | |
| BitSet flags = new BitSet() | |
| map.get(qc).eachWithIndex { value, index -> | |
| if (!results.contains(value)) { | |
| flags.set(index) | |
| } | |
| } | |
| // 名前にかかわらず、すべての変数の同じ位置の値を（後ろから）削除する | |
| // 同じ位置の値は検索結果として同じ組のもの | |
| int count = 0 | |
| if (flags.length() > 0) { | |
| map.each { name, values -> | |
| for (int index = flags.length() - 1; index >= 0; index--) { | |
| if (flags.get(index)) { | |
| values.remove(index) | |
| count++ | |
| } | |
| } | |
| } | |
| } | |
| return count; | |
| } | |
| } | |
| static void main(String[] args) { | |
| // 読み込むCSVファイルの名前と検索条件を受け取る | |
| System.err.println(args) | |
| // 検索条件はGroovyの文法で解釈される | |
| // 以下の様な [ s, p, o ] の２次元配列である必要あり | |
| // | |
| // [ ['?actor', 'name', 'Harrison Ford'], ['?movie', 'starring', '?actor'], ['?movie', 'name', '?title'] ] | |
| // コマンドラインからは以下の様に指定する | |
| // | |
| // $ ./SimpleGraph.groovy movies.csv ?actor,name,Harrison%20Ford ?movie,starring,?actor ?movie,name?title | |
| StringBuilder query = new StringBuilder('[') | |
| for (int i = 1; i < args.size(); i++) { | |
| String pattern = URLDecoder.decode(args[i], 'UTF8') | |
| def (s, p, o) = pattern.split(',', 3) | |
| query.append("['${s}', '${p}', '${o}'],") | |
| } | |
| query.append(']') | |
| def graph = new SimpleGraph(new File(args[0])) | |
| def clauses = Eval.me(query.toString()) | |
| graph.query(clauses).each { | |
| key, values -> values.each { println "${key} = ${it}" } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
動かしてみるとこんな感じ：