Changeset 16304 for branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

Timestamp:

11/19/18 14:34:25 (5 years ago)

Author:

lkammere

Message:

#2915: Merge changes in the trunk to current HEAD into the branch.

Location:

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic

Files:

• . (modified) (1 prop)
• 3.4/Hashing/SymbolicExpressionTreeHash.cs (modified) (6 diffs)

branches/2915-AbsoluteSymbol/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

@@ -1 @@
-using System.Collections.Generic;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
 using System.Linq;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -18 +39 @@
     private static readonly ISymbolicExpressionTreeNodeComparer comparer = new SymbolicExpressionTreeNodeComparer();
 
-    public static int ComputeHash(this ISymbolicExpressionTree tree) {
+    public static ulong ComputeHash(this ISymbolicExpressionTree tree) {
       return ComputeHash(tree.Root.GetSubtree(0).GetSubtree(0));
     }
 
-    public static Dictionary<ISymbolicExpressionTreeNode, int> ComputeNodeHashes(this ISymbolicExpressionTree tree) {
-      var root = tree.Root.GetSubtree(0).GetSubtree(0);
-      var nodes = root.MakeNodes();
-      nodes.UpdateNodeSizes();
-
-      for (int i = 0; i < nodes.Length; ++i) {
-        if (nodes[i].IsChild)
-          continue;
-        nodes[i].CalculatedHashValue = nodes.ComputeHash(i);
-      }
-      return nodes.ToDictionary(x => x.Data, x => x.CalculatedHashValue);
-    }
-
-    public static int ComputeHash(this ISymbolicExpressionTreeNode treeNode) {
-      var hashNodes = treeNode.MakeNodes();
-      var simplified = hashNodes.Simplify();
-      return ComputeHash(simplified);
-    }
-
-    public static int ComputeHash(this HashNode<ISymbolicExpressionTreeNode>[] nodes) {
-      int hash = 1315423911;
-      foreach (var node in nodes)
-        hash ^= (hash << 5) + node.CalculatedHashValue + (hash >> 2);
-      return hash;
-    }
-
-    public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node) {
+    public static double ComputeSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool simplify = false) {
+      return ComputeSimilarity(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0), simplify);
+    }
+
+    public static double ComputeSimilarity(ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, bool simplify = false) {
+      HashNode<ISymbolicExpressionTreeNode>[] lhs;
+      HashNode<ISymbolicExpressionTreeNode>[] rhs;
+
+      ulong hashFunction(byte[] input) => HashUtil.DJBHash(input);
+
+      if (simplify) {
+        lhs = t1.MakeNodes().Simplify(hashFunction);
+        rhs = t2.MakeNodes().Simplify(hashFunction);
+      } else {
+        lhs = t1.MakeNodes().Sort(hashFunction); // sort calculates hash values
+        rhs = t2.MakeNodes().Sort(hashFunction);
+      }
+
+      var lh = lhs.Select(x => x.CalculatedHashValue).ToArray();
+      var rh = rhs.Select(x => x.CalculatedHashValue).ToArray();
+
+      Array.Sort(lh);
+      Array.Sort(rh);
+
+      return ComputeSimilarity(lh, rh);
+    }
+
+    // this will only work if lh and rh are sorted 
+    private static double ComputeSimilarity(ulong[] lh, ulong[] rh) {
+      double count = 0;
+      for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
+        var h1 = lh[i];
+        var h2 = rh[j];
+        if (h1 == h2) {
+          ++count;
+          ++i;
+          ++j;
+        } else if (h1 < h2) {
+          ++i;
+        } else if (h1 > h2) {
+          ++j;
+        }
+      }
+
+      return 2d * count / (lh.Length + rh.Length);
+    }
+
+    public static double ComputeAverageSimilarity(ISymbolicExpressionTree[] trees, bool simplify = false, bool strict = false) {
+      var total = (double)trees.Length * (trees.Length - 1) / 2;
+      double avg = 0;
+      var hashes = new ulong[trees.Length][];
+      // build hash arrays
+      for (int i = 0; i < trees.Length; ++i) {
+        var nodes = trees[i].MakeNodes(strict);
+        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
+        Array.Sort(hashes[i]);
+      }
+      // compute similarity matrix
+      for (int i = 0; i < trees.Length - 1; ++i) {
+        for (int j = i + 1; j < trees.Length; ++j) {
+          avg += ComputeSimilarity(hashes[i], hashes[j]);
+        }
+      }
+      return avg / total;
+    }
+
+    public static double[,] ComputeSimilarityMatrix(ISymbolicExpressionTree[] trees, bool simplify = false, bool strict = false) {
+      var sim = new double[trees.Length, trees.Length];
+      var hashes = new ulong[trees.Length][];
+      // build hash arrays
+      for (int i = 0; i < trees.Length; ++i) {
+        var nodes = trees[i].MakeNodes(strict);
+        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
+        Array.Sort(hashes[i]);
+      }
+      // compute similarity matrix
+      for (int i = 0; i < trees.Length - 1; ++i) {
+        for (int j = i + 1; j < trees.Length; ++j) {
+          sim[i, j] = sim[j, i] = ComputeSimilarity(hashes[i], hashes[j]);
+        }
+      }
+      return sim;
+    }
+
+    public static ulong ComputeHash(this ISymbolicExpressionTreeNode treeNode, bool strict = false) {
+      ulong hashFunction(byte[] input) => HashUtil.JSHash(input);
+      var hashNodes = treeNode.MakeNodes(strict);
+      var simplified = hashNodes.Simplify(hashFunction);
+      return simplified.Last().CalculatedHashValue;
+    }
+
+    public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node, bool strict = false) {
       var symbol = node.Symbol;
       var name = symbol.Name;
-      if (symbol is Variable) {
-        var variableTreeNode = (VariableTreeNode)node;
-        name = variableTreeNode.VariableName;
-      }
-      var hash = name.GetHashCode();
+      if (node is ConstantTreeNode constantNode) {
+        name = strict ? constantNode.Value.ToString() : symbol.Name;
+      } else if (node is VariableTreeNode variableNode) {
+        name = strict ? variableNode.Weight.ToString() + variableNode.VariableName : variableNode.VariableName;
+      }
+      var hash = (ulong)name.GetHashCode();
       var hashNode = new HashNode<ISymbolicExpressionTreeNode>(comparer) {
         Data = node,
@@ -79 +166 @@
     }
 
-    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node) {
-      return node.IterateNodesPostfix().Select(ToHashNode).ToArray();
+    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTree tree, bool strict = false) {
+      return MakeNodes(tree.Root.GetSubtree(0).GetSubtree(0), strict);
+    }
+
+    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node, bool strict = false) {
+      return node.IterateNodesPostfix().Select(x => x.ToHashNode(strict)).ToArray().UpdateNodeSizes();
     }
 
@@ -98 +189 @@
         var node = nodes[i];
 
-        if (node.IsChild) {
+        if (node.IsLeaf) {
           if (node.Data is VariableTreeNode variable) {
             var variableTreeNode = (VariableTreeNode)treeNodes[i];
             variableTreeNode.VariableName = variable.VariableName;
-            variableTreeNode.Weight = 1;
+            variableTreeNode.Weight = variable.Weight;
           } else if (node.Data is ConstantTreeNode @const) {
             var constantTreeNode = (ConstantTreeNode)treeNodes[i];
@@ -129 +220 @@
     // (in other words simplification should be applied in a bottom-up fashion) 
     public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree tree) {
+      ulong hashFunction(byte[] bytes) => HashUtil.JSHash(bytes);
       var root = tree.Root.GetSubtree(0).GetSubtree(0);
       var nodes = root.MakeNodes();
-      var simplified = nodes.Simplify();
+      var simplified = nodes.Simplify(hashFunction);
       return simplified.ToTree();
     }
@@ -174 +266 @@
             var d = children[k];
             if (nodes[d].Data.Symbol is Constant) {
-              ((ConstantTreeNode)child.Data).Value *= ((ConstantTreeNode)nodes[d].Data).Value;
               nodes[d].Enabled = false;
               node.Arity--;