source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs @ 16382

Last change on this file since 16382 was 16382, checked in by bburlacu, 7 months ago

#2950: Change signature of ComputeSimilarity methods to accent a generic list of trees. This enables us to directly pass HL ItemAray or ItemList without overhead.

File size: 14.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
26using static HeuristicLab.Problems.DataAnalysis.Symbolic.SymbolicExpressionHashExtensions;
27
28namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
29  public static class SymbolicExpressionTreeHash {
30    private static readonly Addition add = new Addition();
31    private static readonly Subtraction sub = new Subtraction();
32    private static readonly Multiplication mul = new Multiplication();
33    private static readonly Division div = new Division();
34    private static readonly Logarithm log = new Logarithm();
35    private static readonly Exponential exp = new Exponential();
36    private static readonly Sine sin = new Sine();
37    private static readonly Cosine cos = new Cosine();
38    private static readonly Constant constant = new Constant();
39
40    private static readonly ISymbolicExpressionTreeNodeComparer comparer = new SymbolicExpressionTreeNodeComparer();
41
42    public static ulong ComputeHash(this ISymbolicExpressionTree tree) {
43      return ComputeHash(tree.Root.GetSubtree(0).GetSubtree(0));
44    }
45
46    public static double ComputeSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2, bool simplify = false) {
47      return ComputeSimilarity(t1.Root.GetSubtree(0).GetSubtree(0), t2.Root.GetSubtree(0).GetSubtree(0), simplify);
48    }
49
50    public static double ComputeSimilarity(ISymbolicExpressionTreeNode t1, ISymbolicExpressionTreeNode t2, bool simplify = false) {
51      HashNode<ISymbolicExpressionTreeNode>[] lhs;
52      HashNode<ISymbolicExpressionTreeNode>[] rhs;
53
54      ulong hashFunction(byte[] input) => HashUtil.DJBHash(input);
55
56      if (simplify) {
57        lhs = t1.MakeNodes().Simplify(hashFunction);
58        rhs = t2.MakeNodes().Simplify(hashFunction);
59      } else {
60        lhs = t1.MakeNodes().Sort(hashFunction); // sort calculates hash values
61        rhs = t2.MakeNodes().Sort(hashFunction);
62      }
63
64      var lh = lhs.Select(x => x.CalculatedHashValue).ToArray();
65      var rh = rhs.Select(x => x.CalculatedHashValue).ToArray();
66
67      Array.Sort(lh);
68      Array.Sort(rh);
69
70      return ComputeSimilarity(lh, rh);
71    }
72
73    // this will only work if lh and rh are sorted
74    private static double ComputeSimilarity(ulong[] lh, ulong[] rh) {
75      double count = 0;
76      for (int i = 0, j = 0; i < lh.Length && j < rh.Length;) {
77        var h1 = lh[i];
78        var h2 = rh[j];
79        if (h1 == h2) {
80          ++count;
81          ++i;
82          ++j;
83        } else if (h1 < h2) {
84          ++i;
85        } else if (h1 > h2) {
86          ++j;
87        }
88      }
89
90      return 2d * count / (lh.Length + rh.Length);
91    }
92
93    public static double ComputeAverageSimilarity(IList<ISymbolicExpressionTree> trees, bool simplify = false, bool strict = false) {
94      var total = (double)trees.Count * (trees.Count - 1) / 2;
95      double avg = 0;
96      var hashes = new ulong[trees.Count][];
97      // build hash arrays
98      for (int i = 0; i < trees.Count; ++i) {
99        var nodes = trees[i].MakeNodes(strict);
100        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
101        Array.Sort(hashes[i]);
102      }
103      // compute similarity matrix
104      for (int i = 0; i < trees.Count - 1; ++i) {
105        for (int j = i + 1; j < trees.Count; ++j) {
106          avg += ComputeSimilarity(hashes[i], hashes[j]);
107        }
108      }
109      return avg / total;
110    }
111
112    public static double[,] ComputeSimilarityMatrix(IList<ISymbolicExpressionTree> trees, bool simplify = false, bool strict = false) {
113      var sim = new double[trees.Count, trees.Count];
114      var hashes = new ulong[trees.Count][];
115      // build hash arrays
116      for (int i = 0; i < trees.Count; ++i) {
117        var nodes = trees[i].MakeNodes(strict);
118        hashes[i] = (simplify ? nodes.Simplify(HashUtil.DJBHash) : nodes.Sort(HashUtil.DJBHash)).Select(x => x.CalculatedHashValue).ToArray();
119        Array.Sort(hashes[i]);
120      }
121      // compute similarity matrix
122      for (int i = 0; i < trees.Count - 1; ++i) {
123        for (int j = i + 1; j < trees.Count; ++j) {
124          sim[i, j] = sim[j, i] = ComputeSimilarity(hashes[i], hashes[j]);
125        }
126      }
127      return sim;
128    }
129
130    public static ulong ComputeHash(this ISymbolicExpressionTreeNode treeNode, bool strict = false) {
131      ulong hashFunction(byte[] input) => HashUtil.JSHash(input);
132      var hashNodes = treeNode.MakeNodes(strict);
133      var simplified = hashNodes.Simplify(hashFunction);
134      return simplified.Last().CalculatedHashValue;
135    }
136
137    public static HashNode<ISymbolicExpressionTreeNode> ToHashNode(this ISymbolicExpressionTreeNode node, bool strict = false) {
138      var symbol = node.Symbol;
139      var name = symbol.Name;
140      if (node is ConstantTreeNode constantNode) {
141        name = strict ? constantNode.Value.ToString() : symbol.Name;
142      } else if (node is VariableTreeNode variableNode) {
143        name = strict ? variableNode.Weight.ToString() + variableNode.VariableName : variableNode.VariableName;
144      }
145      var hash = (ulong)name.GetHashCode();
146      var hashNode = new HashNode<ISymbolicExpressionTreeNode>(comparer) {
147        Data = node,
148        Arity = node.SubtreeCount,
149        Size = node.SubtreeCount,
150        IsCommutative = node.Symbol is Addition || node.Symbol is Multiplication,
151        Enabled = true,
152        HashValue = hash,
153        CalculatedHashValue = hash
154      };
155      if (symbol is Addition) {
156        hashNode.Simplify = SimplifyAddition;
157      } else if (symbol is Multiplication) {
158        hashNode.Simplify = SimplifyMultiplication;
159      } else if (symbol is Division) {
160        hashNode.Simplify = SimplifyDivision;
161      } else if (symbol is Logarithm || symbol is Exponential || symbol is Sine || symbol is Cosine) {
162        hashNode.Simplify = SimplifyUnaryNode;
163      } else if (symbol is Subtraction) {
164        hashNode.Simplify = SimplifyBinaryNode;
165      }
166      return hashNode;
167    }
168
169    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTree tree, bool strict = false) {
170      return MakeNodes(tree.Root.GetSubtree(0).GetSubtree(0), strict);
171    }
172
173    public static HashNode<ISymbolicExpressionTreeNode>[] MakeNodes(this ISymbolicExpressionTreeNode node, bool strict = false) {
174      return node.IterateNodesPostfix().Select(x => x.ToHashNode(strict)).ToArray().UpdateNodeSizes();
175    }
176
177    #region parse a nodes array back into a tree
178    public static ISymbolicExpressionTree ToTree(this HashNode<ISymbolicExpressionTreeNode>[] nodes) {
179      var root = new ProgramRootSymbol().CreateTreeNode();
180      var start = new StartSymbol().CreateTreeNode();
181      root.AddSubtree(start);
182      start.AddSubtree(nodes.ToSubtree());
183      return new SymbolicExpressionTree(root);
184    }
185
186    public static ISymbolicExpressionTreeNode ToSubtree(this HashNode<ISymbolicExpressionTreeNode>[] nodes) {
187      var treeNodes = nodes.Select(x => x.Data.Symbol.CreateTreeNode()).ToArray();
188
189      for (int i = nodes.Length - 1; i >= 0; --i) {
190        var node = nodes[i];
191
192        if (node.IsLeaf) {
193          if (node.Data is VariableTreeNode variable) {
194            var variableTreeNode = (VariableTreeNode)treeNodes[i];
195            variableTreeNode.VariableName = variable.VariableName;
196            variableTreeNode.Weight = variable.Weight;
197          } else if (node.Data is ConstantTreeNode @const) {
198            var constantTreeNode = (ConstantTreeNode)treeNodes[i];
199            constantTreeNode.Value = @const.Value;
200          }
201          continue;
202        }
203
204        var treeNode = treeNodes[i];
205
206        foreach (var j in nodes.IterateChildren(i)) {
207          treeNode.AddSubtree(treeNodes[j]);
208        }
209      }
210
211      return treeNodes.Last();
212    }
213
214    private static T CreateTreeNode<T>(this ISymbol symbol) where T : class, ISymbolicExpressionTreeNode {
215      return (T)symbol.CreateTreeNode();
216    }
217    #endregion
218
219    #region tree simplification
220    // these simplification methods rely on the assumption that child nodes of the current node have already been simplified
221    // (in other words simplification should be applied in a bottom-up fashion)
222    public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree tree) {
223      ulong hashFunction(byte[] bytes) => HashUtil.JSHash(bytes);
224      var root = tree.Root.GetSubtree(0).GetSubtree(0);
225      var nodes = root.MakeNodes();
226      var simplified = nodes.Simplify(hashFunction);
227      return simplified.ToTree();
228    }
229
230    public static void SimplifyAddition(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
231      // simplify additions of terms by eliminating terms with the same symbol and hash
232      var children = nodes.IterateChildren(i);
233
234      // we always assume the child nodes are sorted
235      var curr = children[0];
236      var node = nodes[i];
237
238      foreach (var j in children.Skip(1)) {
239        if (nodes[j] == nodes[curr]) {
240          nodes.SetEnabled(j, false);
241          node.Arity--;
242        } else {
243          curr = j;
244        }
245      }
246      if (node.Arity == 1) { // if the arity is 1 we don't need the addition node at all
247        node.Enabled = false;
248      }
249    }
250
251    // simplify multiplications by reducing constants and div terms
252    public static void SimplifyMultiplication(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
253      var node = nodes[i];
254      var children = nodes.IterateChildren(i);
255
256      for (int j = 0; j < children.Length; ++j) {
257        var c = children[j];
258        var child = nodes[c];
259
260        if (!child.Enabled)
261          continue;
262
263        var symbol = child.Data.Symbol;
264        if (symbol is Constant) {
265          for (int k = j + 1; k < children.Length; ++k) {
266            var d = children[k];
267            if (nodes[d].Data.Symbol is Constant) {
268              nodes[d].Enabled = false;
269              node.Arity--;
270            } else {
271              break;
272            }
273          }
274        } else if (symbol is Division) {
275          var div = nodes[c];
276          var denominator =
277            div.Arity == 1 ?
278            nodes[c - 1] :                    // 1 / x is expressed as div(x) (with a single child)
279            nodes[c - nodes[c - 1].Size - 2]; // assume division always has arity 1 or 2
280
281          foreach (var d in children) {
282            if (nodes[d].Enabled && nodes[d] == denominator) {
283              nodes[c].Enabled = nodes[d].Enabled = denominator.Enabled = false;
284              node.Arity -= 2; // matching child + division node
285              break;
286            }
287          }
288        }
289
290        if (node.Arity == 0) { // if everything is simplified this node becomes constant
291          var constantTreeNode = constant.CreateTreeNode<ConstantTreeNode>();
292          constantTreeNode.Value = 1;
293          nodes[i] = constantTreeNode.ToHashNode();
294        } else if (node.Arity == 1) { // when i have only 1 arg left i can skip this node
295          node.Enabled = false;
296        }
297      }
298    }
299
300    public static void SimplifyDivision(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
301      var node = nodes[i];
302      var children = nodes.IterateChildren(i);
303
304      var tmp = nodes;
305
306      if (children.All(x => tmp[x].Data.Symbol is Constant)) {
307        var v = ((ConstantTreeNode)nodes[children.First()].Data).Value;
308        if (node.Arity == 1) {
309          v = 1 / v;
310        } else if (node.Arity > 1) {
311          foreach (var j in children.Skip(1)) {
312            v /= ((ConstantTreeNode)nodes[j].Data).Value;
313          }
314        }
315        var constantTreeNode = constant.CreateTreeNode<ConstantTreeNode>();
316        constantTreeNode.Value = v;
317        nodes[i] = constantTreeNode.ToHashNode();
318        return;
319      }
320
321      var nominator = nodes[children[0]];
322      foreach (var j in children.Skip(1)) {
323        var denominator = nodes[j];
324        if (nominator == denominator) {
325          // disable all the children of the division node (nominator and children + denominator and children)
326          nominator.Enabled = denominator.Enabled = false;
327          node.Arity -= 2; // nominator + denominator
328        }
329        if (node.Arity == 0) {
330          var constantTreeNode = constant.CreateTreeNode<ConstantTreeNode>();
331          constantTreeNode.Value = 1; // x / x = 1
332          nodes[i] = constantTreeNode.ToHashNode();
333        }
334      }
335    }
336
337    public static void SimplifyUnaryNode(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
338      // check if the child of the unary node is a constant, then the whole node can be simplified
339      var parent = nodes[i];
340      var child = nodes[i - 1];
341
342      var parentSymbol = parent.Data.Symbol;
343      var childSymbol = child.Data.Symbol;
344
345      if (childSymbol is Constant) {
346        nodes[i].Enabled = false;
347      } else if ((parentSymbol is Exponential && childSymbol is Logarithm) || (parentSymbol is Logarithm && childSymbol is Exponential)) {
348        child.Enabled = parent.Enabled = false;
349      }
350    }
351
352    public static void SimplifyBinaryNode(ref HashNode<ISymbolicExpressionTreeNode>[] nodes, int i) {
353      var children = nodes.IterateChildren(i);
354      var tmp = nodes;
355      if (children.All(x => tmp[x].Data.Symbol is Constant)) {
356        foreach (var j in children) {
357          nodes[j].Enabled = false;
358        }
359        nodes[i] = constant.CreateTreeNode().ToHashNode();
360      }
361    }
362    #endregion
363  }
364}
Note: See TracBrowser for help on using the repository browser.