Changeset 14426

Timestamp:

11/28/16 17:51:37 (8 years ago)

Author:

bburlacu

Message:

#1772: QueryMatch: implement more elaborate node comparison (better accuracy when matching schemas).

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs (modified) (5 diffs)

branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/TreeMatching/QueryMatch.cs

@@ -29 +29 @@
   // by M. Götz, C. Koch and W. Martens in http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.182.5440
   public class QueryMatch {
-    public ISymbolicExpressionTreeNodeEqualityComparer Comparer { get; private set; }
+    public ISymbolicExpressionTreeNodeEqualityComparer EqualityComparer { get; private set; }
     private readonly NodeInfo Inf = new NodeInfo { Index = int.MaxValue };
     private readonly NodeInfo Nil = new NodeInfo { Index = -1 };
+    private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
+    private readonly ISymbolicExpressionTreeNodeComparer nodeComparer = new SymbolicExpressionTreeNodeComparer();
 
     private QueryMatch() { }
@@ -41 +43 @@
     public bool MatchParents { get; set; }
 
-    public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer comparer) {
-      Comparer = comparer;
+    public QueryMatch(ISymbolicExpressionTreeNodeEqualityComparer equalityComparer) {
+      EqualityComparer = equalityComparer;
     }
 
@@ -58 +60 @@
 
     public bool Match(ISymbolicExpressionTreeNode data, ISymbolicExpressionTreeNode query) {
-      if (!Comparer.Equals(data, query))
+      if (!EqualityComparer.Equals(data, query))
         return false;
 
@@ -72 +74 @@
     public IEnumerable<ISymbolicExpressionTree> GetMatchingTrees(IEnumerable<ISymbolicExpressionTree> data, ISymbolicExpressionTree query) {
       var qRoot = query.Root.GetSubtree(0).GetSubtree(0);
-      var filtered = data.Where(x => x.Length >= query.Length && Comparer.Equals(x.Root.GetSubtree(0).GetSubtree(0), qRoot));
+      var filtered = data.Where(x => x.Length >= query.Length && EqualityComparer.Equals(x.Root.GetSubtree(0).GetSubtree(0), qRoot));
       var qNodes = InitializePostOrder(query.Root.GetSubtree(0).GetSubtree(0));
       return from d in filtered let dNodes = InitializePostOrder(d.Root.GetSubtree(0).GetSubtree(0)) where Match(dNodes, qNodes) select d;
     }
 
-    private bool AreMatching(NodeInfo a, NodeInfo b) {
+    private bool AreMatching(NodeInfo d, NodeInfo q) {
       // force the nodes to be on the same level
-      if (a.Level != b.Level)
-        return false;
-
-      bool equals = Comparer.Equals(a.Node, b.Node);
-      if (equals && MatchParents) {
-        var pa = a.Parent;
-        var pb = b.Parent;
-        if (pa == null && pb == null)
-          return true;
-        if (pa == null || pb == null)
-          return false;
-        return pa.Level == pb.Level && Comparer.Equals(pa.Node, pb.Node);
-      }
-      return equals;
+      if (d.Level != q.Level)
+        return false;
+
+      // compare nodes
+      bool equals = EqualityComparer.Equals(d.Node, q.Node);
+
+      if (!equals)
+        return false;
+
+      // compare node parents
+      if (MatchParents && !EqualityComparer.Equals(d.Node.Parent, q.Node.Parent))
+        return false;
+
+      // compare children to make sure they are the same
+      if (d.Node.SubtreeCount > 0 && q.Node.SubtreeCount > 0) {
+        var dSubtrees = d.Node.Subtrees.ToList();
+
+        if (commutativeSymbols.Contains(d.Node.Symbol.Name)) {
+          var qSubtrees = q.Node.Subtrees.Where(x => !(x is AnyNode || x is AnySubtree)).ToList();
+
+          dSubtrees.Sort(nodeComparer);
+          qSubtrees.Sort(nodeComparer);
+
+          var nw = q.Node.SubtreeCount - qSubtrees.Count; // number of wildcards 
+          if (nw == 0)
+            return dSubtrees.SequenceEqual(qSubtrees, EqualityComparer);
+
+          for (int i = 0, j = 0; i < dSubtrees.Count && j < qSubtrees.Count;) {
+            if (EqualityComparer.Equals(dSubtrees[i], qSubtrees[j])) {
+              ++i;
+              ++j;
+            } else {
+              if (nw == 0)
+                return false;
+              ++i;
+              --nw;
+            }
+          }
+        } else {
+          var qSubtrees = q.Node.Subtrees;
+          return dSubtrees.SequenceEqual(qSubtrees, EqualityComparer);
+        }
+      }
+      return true;
     }
 
@@ -167 +199 @@
         if (n != nodes.Last()) n.Next = nodes[n.Index + 1];
         if (n != nodes.First()) n.Previous = nodes[n.Index - 1];
-        NodeInfo parentInfo;
-        map.TryGetValue(n.Node.Parent, out parentInfo);
+        NodeInfo parentInfo = null;
+        if (n.Node.Parent != null)
+          map.TryGetValue(n.Node.Parent, out parentInfo);
         n.Parent = parentInfo;
         if (n.Parent == null) {