From a7acc5b68cd4850b1bce020421087788a57b4eab Mon Sep 17 00:00:00 2001 From: Huibo SHI Date: Wed, 26 Mar 2014 17:17:11 +0100 Subject: [PATCH] 1) ecrire la fonction hash et equal 2) creer un module QTree dans le fichier table.ml 3) definir notre propre hashtbl---->QTreeHash 4) ajouter la fonction minimize_qtree pour minimizer le query_tree 5) ameliorer la fonction eval_qtree en utilisant un QTreeHash pour partager maximalement les informations. 6) mise a jour l'interface query_tree.mli 7) mise a jour le main --- src/query_tree.ml | 62 ++++++++++++++++++++++++++++++++++++++++++++- src/query_tree.mli | 4 +++ src/table.ml | 37 +++++++++++++++++++++++++-- src/table_driver.ml | 15 ++++++----- 4 files changed, 109 insertions(+), 9 deletions(-) diff --git a/src/query_tree.ml b/src/query_tree.ml index 9297d3a..6d9e6bd 100644 --- a/src/query_tree.ml +++ b/src/query_tree.ml @@ -1,6 +1,8 @@ open Table let compteur = ref 0 +let table_query_tree = Hashtbl.create 97 +let table_qtree = QTreeHash.create 97 let all_nodes tree = let root = Naive_tree.root tree in eval_axis tree [root] (Descendant true) @@ -131,7 +133,7 @@ let debug tree q l = Format.pp_print_flush Format.std_formatter (); end -let table_query_tree = Hashtbl.create 97 + let rec compare_query_tree q1 q2 = @@ -184,3 +186,61 @@ let rec eval_query_tree tree start q = in debug tree q resultat; resultat + +let mini_id = ref 0 +let mini_table = QTreeHash.create 17 + +let rec minimize_qtree q = + if q.id != -1 then q + else + try + QTreeHash.find mini_table q + with Not_found -> + let mdesc = + match q.desc with + (Start | Dom | Tag _) as d -> d + | Binop(op,q1,q2) -> let mq1 = minimize_qtree q1 in + let mq2 = minimize_qtree q2 in + Binop(op,mq1,mq2) + | Axis(a,q1) -> let mq1 = minimize_qtree q1 in + Axis(a,mq1) + in + q.desc <- mdesc; + q.hash <- QTree.hash q; + q.id <- !mini_id; + incr mini_id; + QTreeHash.add mini_table q q; + q + + + +let rec eval_qtree tree start q = + let resultat = + begin + try + QTreeHash.find table_qtree q + with Not_found -> + let res = + match q.desc with + | Start -> start + | Dom -> all_nodes tree + | Tag (t,k) -> element_by_tag tree t k + | Axis (a,q1) -> let ls = eval_qtree tree start q1 in + eval_axis tree ls a + | Binop (op,q1,q2)-> begin + let ls1 = eval_qtree tree start q1 in + let ls2 = eval_qtree tree start q2 in + match op with + | Union -> union_list tree ls1 ls2 + | Inter -> inter_list tree ls1 ls2 + | Diff -> diff_list tree ls1 ls2 + end + in + let res = List.sort (Table.compare_node tree) res in + QTreeHash.add table_qtree q res; + compteur := !compteur + (List.length res); + res + end + in + debug tree q resultat; + resultat diff --git a/src/query_tree.mli b/src/query_tree.mli index ea520c4..f34cc3b 100644 --- a/src/query_tree.mli +++ b/src/query_tree.mli @@ -34,3 +34,7 @@ val eval_query_tree : Naive_tree.t -> Naive_tree.node list ->Table.query_tree -> [start] the set of nodes departing. [q] query_tree *) + +val minimize_qtree : Table.query_tree -> Table.query_tree + +val eval_qtree : Naive_tree.t -> Naive_tree.node list ->Table.query_tree -> Naive_tree.node list diff --git a/src/table.ml b/src/table.ml index 3d372ec..f0e24ee 100644 --- a/src/table.ml +++ b/src/table.ml @@ -20,8 +20,41 @@ and query_tree = { } - - +module QTree = struct + type t = query_tree + let rec equal q1 q2 = + q1 == q2 || + (q1.id == q2.id && q1.id != -1) || + match q1.desc, q2.desc with + | Binop(op1,qt1,qt2),Binop(op2,qt3,qt4)-> op1==op2&& (equal qt1 qt3 && equal qt2 qt4) + + | Axis(a1,qt1),Axis(a2,qt2) -> compare_axis a1 a2 && equal qt1 qt2 + | Tag(t1,k1),Tag(t2,k2) -> t1==t2&& k1==k2 + | Dom,Dom | Start,Start -> true + | _,_ ->false + and compare_axis a1 a2 = + match a1,a2 with + Self ,Self | Attribute, Attribute | Child , Child | Parent , Parent + | FollowingSibling , FollowingSibling + | PrecedingSibling , PrecedingSibling + | Preceding , Preceding | Following , Following -> true + | Descendant b1, Descendant b2 -> b1==b2 + | Ancestor b1, Ancestor b2 -> b1==b2 + | _,_ -> false + + let rec hash q = + if q.hash != -1 then q.hash + else match q.desc with + Dom -> 1 + | Start -> 3 + | Tag(s,_) -> 5 + 17*QNameSet.hash s + | Axis(a,q) -> 7 + 17 * Hashtbl.hash a + 23* hash q + | Binop(op,q1,q2) -> 11 + 17* Hashtbl.hash op + 23* hash q1 + 27* hash q2 + +end + + +module QTreeHash = Hashtbl.Make(QTree) diff --git a/src/table_driver.ml b/src/table_driver.ml index 64d1a1d..767cfdc 100644 --- a/src/table_driver.ml +++ b/src/table_driver.ml @@ -27,12 +27,15 @@ let main () = let query_tree_list = List.map (fun query -> compile_xpath query) queries in - List.iter ( fun q -> - let res = eval_query_tree doc [ (Naive_tree.root doc) ] q in - print_string "\n"; - print_node_list doc res; - print_string "\n" - ) query_tree_list ; + let mini_qtree_list = + List.map (fun qtree -> Query_tree.minimize_qtree qtree) query_tree_list + in + List.iter ( fun q -> + let res = eval_qtree doc [ (Naive_tree.root doc) ] q in + print_string "\n"; + print_node_list doc res; + print_string "\n"; + ) mini_qtree_list ; let _ = if !Table_options.count then Format.fprintf Format.std_formatter "there are %i nodes\n" !Query_tree.compteur; -- 2.17.1