Changeset 17141 for stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing

Timestamp:

07/17/19 22:02:08 (5 years ago)

Author:

abeham

Message:

#2950: merged r17076 to stable

Location:

stable

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic (modified) (1 prop)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs (modified) (6 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs (modified) (4 diffs)

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

@@ -25 +25 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   public static class SymbolicExpressionHashExtensions {
+    /// <summary>
+    /// Holds data that is necessary to handle tree nodes in hashing / simplification.
+    /// </summary>
+    /// <typeparam name="T">The tree node type</typeparam>
     public sealed class HashNode<T> : IComparable<HashNode<T>>, IEquatable<HashNode<T>> where T : class {
       public T Data;
@@ -38 +42 @@
       public SimplifyAction Simplify;
 
-      //public IComparer<T> Comparer;
-
       public bool IsLeaf => Arity == 0;
-
-      //public HashNode(IComparer<T> comparer) {
-      //  Comparer = comparer;
-      //}
-
-      //public HashNode() { }
 
       public int CompareTo(HashNode<T> other) {
@@ -170 +166 @@
 
     /// <summary>
-    /// Get a function node's child indicest
+    /// Get a function node's child indices
     /// </summary>
     /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
-    /// <param name="nodes">An array of hash nodes with up-to-date node sizes</param>
+    /// <param name="nodes">An array of hash nodes with up-to-date node sizes (see UpdateNodeSizes)</param>
     /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
     /// <returns>An array containing child indices</returns>
@@ -188 +184 @@
     }
 
+    /// <summary>
+    /// Determines size of each branch and sets the results for each node.
+    /// </summary>
+    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
+    /// <param name="nodes">An array of hash nodes in postfix order.</param>
+    /// <returns>The array with updated node sizes. The array is not copied.</returns>
     public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
       for (int i = 0; i < nodes.Length; ++i) {
@@ -196 +198 @@
         }
         node.Size = node.Arity;
-
+        // visit all children and sum up their size (assumes postfix order).
         for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
           node.Size += nodes[j].Size;
@@ -204 +206 @@
     }
 
+    // disables duplicate branches and removes the disabled nodes
     public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
       int count = 0;

stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

@@ -48 +48 @@
       ulong hashFunction(byte[] input) => HashUtil.DJBHash(input);
 
-      var hashNodes = simplify ? node.MakeNodes(strict).Simplify(hashFunction) : node.MakeNodes(strict).Sort(hashFunction);
+      var hashNodes = simplify ? node.MakeNodes(strict).Simplify(hashFunction) : node.MakeNodes(strict).Sort(hashFunction); // simplify sorts implicitly
       var hashes = new ulong[hashNodes.Length];
       for (int i = 0; i < hashes.Length; ++i) {
@@ -210 +210 @@
       var treeNodes = nodes.Select(x => x.Data.Symbol.CreateTreeNode()).ToArray();
 
+      // construct tree top down (assumes postfix order for nodes)
       for (int i = nodes.Length - 1; i >= 0; --i) {
         var node = nodes[i];
@@ -244 +245 @@
     // (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);
+      ulong hashFunction(byte[] bytes) => HashUtil.DJBHash(bytes);
+      var root = tree.ActualRoot();
       var nodes = root.MakeNodes();
       var simplified = nodes.Simplify(hashFunction);
@@ -369 +370 @@
         nodes[i].Enabled = false;
       } else if ((parentSymbol is Exponential && childSymbol is Logarithm) || (parentSymbol is Logarithm && childSymbol is Exponential)) {
+        // exp(log(x)) == x only for positive x. We consider this as equivalent for hashing anyway.
         child.Enabled = parent.Enabled = false;
       }