Skip to content

Instantly share code, notes, and snippets.

@uemuraj
Created June 10, 2012 09:58
Show Gist options
  • Save uemuraj/2904730 to your computer and use it in GitHub Desktop.
Save uemuraj/2904730 to your computer and use it in GitHub Desktop.
セマンティックWebプログラミングの第2章から第3章の内容を試す。
//
// セマンティックWebプログラミングの第2章から第3章の内容を試す。
//
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 ] の2次元配列である必要あり
//
// [ ['?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}" }
}
}
}
@uemuraj
Copy link
Author

uemuraj commented Jun 10, 2012

動かしてみるとこんな感じ:

SimpleGraph.groovy movies.csv "[ ['?actor', 'name', 'Harrison Ford'], ['?movie', 'starring', '?actor'], ['?movie', 'name', '?title'] ]"
?actor = /en/harrison_ford
?movie = /authority/imdb/title/tt0066601
?movie = /authority/imdb/title/tt0083866
?movie = /authority/imdb/title/tt0090329
?movie = /authority/imdb/title/tt0095174
?movie = /authority/imdb/title/tt0100404
?movie = /authority/imdb/title/tt0105112
?movie = /authority/imdb/title/tt0109444
?movie = /authority/imdb/title/tt0118571
?movie = /authority/imdb/title/tt0267626
?movie = /authority/imdb/title/tt0408345
?movie = /authority/netflix/movie/1152837
?movie = /authority/netflix/movie/528009
?movie = /authority/netflix/movie/60010820
?movie = /authority/netflix/movie/60010932
?movie = /authority/netflix/movie/60011114
?movie = /authority/netflix/movie/60011733
?movie = /authority/netflix/movie/70060424
?movie = /authority/netflix/movie/70077535
?movie = /authority/netflix/movie/70082398
?movie = /en/american_graffiti
?movie = /en/apocalypse_now
?movie = /en/blade_runner
?movie = /en/force_10_from_navarone
?movie = /en/hanover_street
?movie = /en/hollywood_homicide
?movie = /en/indiana_jones_4
?movie = /en/indiana_jones_and_the_last_crusade
?movie = /en/indiana_jones_and_the_temple_of_doom
?movie = /en/raiders_of_the_lost_ark
?movie = /en/random_hearts
?movie = /en/regarding_henry
?movie = /en/return_of_the_ewok
?movie = /en/scary_movie_3
?movie = /en/six_days_seven_nights
?movie = /en/the_conversation
?movie = /en/the_frisco_kid
?movie = /en/the_mosquito_coast
?movie = /en/the_star_wars_holiday_special
?movie = /en/what_lies_beneath
?movie = /en/working_girl
?movie = /guid/9202a8c04000641f800000000552fdf4
?movie = /guid/9202a8c04000641f80000000057a001d
?movie = /guid/9202a8c04000641f8000000005aa9682
?title = Air Force One
?title = American Graffiti
?title = Apocalypse Now
?title = Apocalypse Now Redux
?title = Blade Runner
?title = Clear and Present Danger
?title = Crossing Over
?title = E.T. the Extra-Terrestrial
?title = Firewall
?title = Force 10 from Navarone
?title = Frantic
?title = Getting Straight
?title = Hanover Street
?title = Hearts of Darkness: A Filmmakers's Apocalypse
?title = Heroes
?title = Hollywood Homicide
?title = Indiana Jones and the Kingdom of the Crystal Skull
?title = Indiana Jones and the Last Crusade
?title = Indiana Jones and the Temple of Doom
?title = K-19: The Widowmaker
?title = Patriot Games
?title = Presumed Innocent
?title = Raiders of the Lost Ark
?title = Random Hearts
?title = Regarding Henry
?title = Return of the Ewok
?title = Sabrina
?title = Scary Movie 3
?title = Six Days Seven Nights
?title = Star Wars Episode IV: A New Hope
?title = Star Wars Episode V: The Empire Strikes Back
?title = Star Wars Episode VI: Return of the Jedi
?title = The Conversation
?title = The Devil's Own
?title = The Frisco Kid
?title = The Fugitive
?title = The Mosquito Coast
?title = The Star Wars Holiday Special
?title = Up
?title = What Lies Beneath
?title = Witness
?title = Working Girl
?title = Zabriskie Point

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment