Changeset 17503 for branches/2968_infix_string_formatter/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing

Timestamp:

04/10/20 13:10:26 (5 years ago)

Author:

chaider

Message:

#2968 merged trunk into branch

Location:

branches/2968_infix_string_formatter/HeuristicLab.Problems.DataAnalysis.Symbolic

Files:

• . (modified) (1 prop)
• 3.4/Hashing/HashExtensions.cs (modified) (8 diffs)
• 3.4/Hashing/HashUtil.cs (modified) (1 diff)
• 3.4/Hashing/SymbolicExpressionTreeHash.cs (modified) (10 diffs)

branches/2968_infix_string_formatter/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
+using System.Linq;
 
 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;
-      }
-
-      private HashNode() { }
-
       public int CompareTo(HashNode<T> other) {
-        var res = Comparer.Compare(Data, other.Data);
+        var res = HashValue.CompareTo(other.HashValue);
         return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
       }
@@ -103 +99 @@
 
     public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
-      var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
-
-      for (int i = 0; i < reduced.Length; ++i) {
-        var node = reduced[i];
-        if (node.IsLeaf) {
-          continue;
-        }
-        node.Simplify?.Invoke(ref reduced, i);
-      }
-      // detect if anything was simplified
-      var count = 0;
-      foreach (var node in reduced) {
-        if (!node.Enabled) { ++count; }
-      }
-      if (count == 0) {
-        return reduced;
-      }
-
-      var simplified = new HashNode<T>[reduced.Length - count];
-      int j = 0;
-      foreach (var node in reduced) {
-        if (node.Enabled) {
-          simplified[j++] = node;
-        }
-      }
-      return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
+      bool simplified = false;
+      nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
+      do {
+        if (simplified) {
+          simplified = false;
+          nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);
+        }
+
+        for (int i = 0; i < nodes.Length; ++i) {
+          var node = nodes[i];
+          if (node.IsLeaf) {
+            continue;
+          }
+          node.Simplify?.Invoke(ref nodes, i);
+          for (int j = i - node.Size; j <= i; ++j) {
+            // detect if anything was simplified
+            if (!nodes[j].Enabled) {
+              simplified = true;
+              break;
+            }
+          }
+        }
+      } while (simplified);
+      return nodes.UpdateNodeSizes().Sort(hashFunction);
     }
 
@@ -173 +167 @@
 
     /// <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>
@@ -191 +185 @@
     }
 
+    /// <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) {
@@ -199 +199 @@
         }
         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;
@@ -207 +207 @@
     }
 
-    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
+    // disables duplicate branches and removes the disabled nodes
+    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
       int count = 0;
       for (int i = 0; i < nodes.Length; ++i) {

branches/2968_infix_string_formatter/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashUtil.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.

branches/2968_infix_string_formatter/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
@@ -37 +38 @@
     private static readonly Constant constant = new Constant();
 
-    private static readonly ISymbolicExpressionTreeNodeComparer comparer = new SymbolicExpressionTreeNodeComparer();
-
-    public static ulong ComputeHash(this ISymbolicExpressionTree tree) {
-      return ComputeHash(tree.Root.GetSubtree(0).GetSubtree(0));
-    }
-
-    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;
+    private static ISymbolicExpressionTreeNode ActualRoot(this ISymbolicExpressionTree tree) => tree.Root.GetSubtree(0).GetSubtree(0);
+    public static ulong HashFunction(byte[] input) => HashUtil.DJBHash(input);
+
+    #region tree hashing
+    public static ulong[] Hash(this ISymbolicExpressionTree tree, bool simplify = false, bool strict = false) {
+      return tree.ActualRoot().Hash(simplify, strict);
+    }
+
+    public static ulong[] Hash(this ISymbolicExpressionTreeNode node, bool simplify = false, bool strict = false) {
+      var hashNodes = simplify ? node.MakeNodes(strict).Simplify(HashFunction) : node.MakeNodes(strict).Sort(HashFunction);
+      var hashes = new ulong[hashNodes.Length];
+      for (int i = 0; i < hashes.Length; ++i) {
+        hashes[i] = hashNodes[i].CalculatedHashValue;
+      }
+      return hashes;
+    }
+
+    public static ulong ComputeHash(this ISymbolicExpressionTree tree, bool simplify = false, bool strict = false) {
+      return ComputeHash(tree.ActualRoot(), simplify, strict);
+    }
+
+    public static ulong ComputeHash(this ISymbolicExpressionTreeNode treeNode, bool simplify = false, bool strict = false) {
+      return treeNode.Hash(simplify, strict).Last();
     }
 
@@ -143 +72 @@
       }
       var hash = (ulong)name.GetHashCode();
-      var hashNode = new HashNode<ISymbolicExpressionTreeNode>(comparer) {
+      var hashNode = new HashNode<ISymbolicExpressionTreeNode> {
         Data = node,
         Arity = node.SubtreeCount,
@@ -167 +96 @@
 
     public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTree tree, bool strict = false) {
-      return MakeNodes(tree.Root.GetSubtree(0).GetSubtree(0), strict);
+      return MakeNodes(tree.ActualRoot(), strict);
     }
 
@@ -173 +102 @@
       return node.IterateNodesPostfix().Select(x => x.ToHashNode(strict)).ToArray().UpdateNodeSizes();
     }
+    #endregion
+
+    #region tree similarity
+    public static double ComputeSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool simplify = false, bool strict = false) {
+      return ComputeSimilarity(t1.ActualRoot(), t2.ActualRoot(), simplify, strict);
+    }
+
+    public static double ComputeSimilarity(ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, bool simplify = false, bool strict = false) {
+      var lh = t1.Hash(simplify, strict);
+      var rh = t2.Hash(simplify, strict);
+
+      Array.Sort(lh);
+      Array.Sort(rh);
+
+      return ComputeSimilarity(lh, rh);
+    }
+
+    // requires lhs and rhs to be sorted
+    public static int IntersectCount(this ulong[] lh, ulong[] rh) {
+      int 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 count;
+    }
+
+    public static IEnumerable<ulong> Intersect(this ulong[] lh, ulong[] rh) {
+      for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
+        var h1 = lh[i];
+        var h2 = rh[j];
+        if (h1 == h2) {
+          yield return h1;
+          ++i;
+          ++j;
+        } else if (h1 < h2) {
+          ++i;
+        } else if (h1 > h2) {
+          ++j;
+        }
+      }
+    }
+
+    // this will only work if lh and rh are sorted
+    public static double ComputeSimilarity(ulong[] lh, ulong[] rh) {
+      return 2d * IntersectCount(lh, rh) / (lh.Length + rh.Length);
+    }
+
+    public static double ComputeAverageSimilarity(IList<ISymbolicExpressionTree> trees, bool simplify = false, bool strict = false) {
+      var total = trees.Count * (trees.Count - 1) / 2;
+      double avg = 0;
+      var hashes = new ulong[trees.Count][];
+      // build hash arrays
+      for (int i = 0; i < trees.Count; ++i) {
+        var nodes = trees[i].MakeNodes(strict);
+        hashes[i] = (simplify ? nodes.Simplify(HashFunction) : nodes.Sort(HashFunction)).Select(x => x.CalculatedHashValue).ToArray();
+        Array.Sort(hashes[i]);
+      }
+      // compute similarity matrix
+      for (int i = 0; i < trees.Count - 1; ++i) {
+        for (int j = i + 1; j < trees.Count; ++j) {
+          avg += ComputeSimilarity(hashes[i], hashes[j]);
+        }
+      }
+      return avg / total;
+    }
+
+    public static double[,] ComputeSimilarityMatrix(IList<ulong[]> hashes) {
+      // compute similarity matrix
+      var n = hashes.Count;
+      var sim = new double[n, n];
+      for (int i = 0; i < n - 1; ++i) {
+        for (int j = i + 1; j < n; ++j) {
+          sim[i, j] = sim[j, i] = ComputeSimilarity(hashes[i], hashes[j]);
+        }
+      }
+      return sim;
+    }
+
+    public static double[,] ComputeSimilarityMatrix(IList<ISymbolicExpressionTree> trees, bool simplify = false, bool strict = false) {
+      var hashes = new ulong[trees.Count][];
+      // build hash arrays
+      for (int i = 0; i < trees.Count; ++i) {
+        var nodes = trees[i].MakeNodes(strict);
+        hashes[i] = (simplify ? nodes.Simplify(HashFunction) : nodes.Sort(HashFunction)).Select(x => x.CalculatedHashValue).ToArray();
+        Array.Sort(hashes[i]);
+      }
+      return ComputeSimilarityMatrix(hashes);
+    }
+    #endregion
 
     #region parse a nodes array back into a tree
@@ -218 +246 @@
     #region tree simplification
     // these simplification methods rely on the assumption that child nodes of the current node have already been simplified
-    // (in other words simplification should be applied in a bottom-up fashion) 
+    // (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(hashFunction);
-      return simplified.ToTree();
+      return tree.MakeNodes().Simplify(HashFunction).ToTree();
     }
 
@@ -248 +272 @@
     }
 
-    // simplify multiplications by reducing constants and div terms  
+    // simplify multiplications by reducing constants and div terms
     public static void SimplifyMultiplication(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
       var node = nodes[i];
@@ -261 +285 @@
 
         var symbol = child.Data.Symbol;
-        if (symbol is Constant) {
+        if (child.Data is ConstantTreeNode firstConst) {
+          // fold sibling constant nodes into the first constant
           for (int k = j + 1; k < children.Length; ++k) {
-            var d = children[k];
-            if (nodes[d].Data.Symbol is Constant) {
-              nodes[d].Enabled = false;
+            var sibling = nodes[children[k]];
+            if (sibling.Data is ConstantTreeNode otherConst) {
+              sibling.Enabled = false;
               node.Arity--;
+              firstConst.Value *= otherConst.Value;
+            } else {
+              break;
+            }
+          }
+        } else if (child.Data is VariableTreeNode variable) {
+          // fold sibling constant nodes into the variable weight
+          for (int k = j + 1; k < children.Length; ++k) {
+            var sibling = nodes[children[k]];
+            if (sibling.Data is ConstantTreeNode constantNode) {
+              sibling.Enabled = false;
+              node.Arity--;
+              variable.Weight *= constantNode.Value;
             } else {
               break;
@@ -272 +310 @@
           }
         } else if (symbol is Division) {
-          var div = nodes[c];
-          var denominator =
-            div.Arity == 1 ?
-            nodes[c - 1] :                    // 1 / x is expressed as div(x) (with a single child)
-            nodes[c - nodes[c - 1].Size - 2]; // assume division always has arity 1 or 2
-
-          foreach (var d in children) {
-            if (nodes[d].Enabled && nodes[d] == denominator) {
-              nodes[c].Enabled = nodes[d].Enabled = denominator.Enabled = false;
+          // 1/x is expressed as div(x) (with a single child)
+          // we assume division always has arity 1 or 2
+          var d = child.Arity == 1 ? c - 1 : c - nodes[c - 1].Size - 2;
+          var denominator = nodes[d];
+
+          // iterate children of node i to see if any of them matches the denominator of div node c
+          for (int k = 0; k < children.Length; ++k) {
+            var sibling = nodes[children[k]];
+            if (sibling.Enabled && sibling == denominator) {
+              nodes.SetEnabled(children[j], false); // disable the div subtree
+              nodes.SetEnabled(children[k], false); // disable the sibling matching the denominator
+
               node.Arity -= 2; // matching child + division node
               break;