Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs @ 17132

Last change on this file since 17132 was 17132, checked in by bburlacu, 5 years ago

#2950: Small refactor in HashExtensions.cs (better comparison, consistent use of the same hash function). Fix bug and improve robustness of SimplifyMultiplication in SymbolicExpressionHashExtensions.cs

File size: 8.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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.Linq;
24
25namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
26  public static class SymbolicExpressionHashExtensions {
27    /// <summary>
28    /// Holds data that is necessary to handle tree nodes in hashing / simplification.
29    /// </summary>
30    /// <typeparam name="T">The tree node type</typeparam>
31    public sealed class HashNode<T> : IComparable<HashNode<T>>, IEquatable<HashNode<T>> where T : class {
32      public T Data;
33      public int Arity;
34      public int Size;
35      public bool IsCommutative;
36
37      public bool Enabled;
38      public ulong HashValue;           // the initial (fixed) hash value for this individual node/data
39      public ulong CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
40
41      public delegate void SimplifyAction(ref HashNode<T>[] nodes, int i);
42      public SimplifyAction Simplify;
43
44      public bool IsLeaf => Arity == 0;
45
46      public int CompareTo(HashNode<T> other) {
47        var res = HashValue.CompareTo(other.HashValue);
48        return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
49      }
50
51      public override string ToString() {
52        return $"{Data} {Arity} {Size} {CalculatedHashValue} {Enabled}";
53      }
54
55      public bool Equals(HashNode<T> other) {
56        return CalculatedHashValue.Equals(other.CalculatedHashValue);
57      }
58
59      public override bool Equals(object obj) {
60        var other = obj as HashNode<T>;
61        if (other != null)
62          return Equals(other);
63        return base.Equals(obj);
64      }
65
66      public override int GetHashCode() {
67        return (int)CalculatedHashValue;
68      }
69
70      public static bool operator ==(HashNode<T> a, HashNode<T> b) {
71        return a.Equals(b);
72      }
73
74      public static bool operator !=(HashNode<T> a, HashNode<T> b) {
75        return !a.Equals(b);
76      }
77    }
78
79    public static ulong ComputeHash<T>(this HashNode<T>[] nodes, int i, Func<byte[], ulong> hashFunction) where T : class {
80      var node = nodes[i];
81      const int size = sizeof(ulong);
82      var hashes = new ulong[node.Arity + 1];
83      var bytes = new byte[(node.Arity + 1) * size];
84
85      for (int j = i - 1, k = 0; k < node.Arity; ++k, j -= 1 + nodes[j].Size) {
86        hashes[k] = nodes[j].CalculatedHashValue;
87      }
88      hashes[node.Arity] = node.HashValue;
89      Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length);
90      return hashFunction(bytes);
91    }
92
93    // set the enabled state for the whole subtree rooted at this node
94    public static void SetEnabled<T>(this HashNode<T>[] nodes, int i, bool enabled) where T : class {
95      nodes[i].Enabled = enabled;
96      for (int j = i - nodes[i].Size; j < i; ++j)
97        nodes[j].Enabled = enabled;
98    }
99
100    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
101      bool simplified = false;
102      nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
103      do {
104        if (simplified) {
105          simplified = false;
106          nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);
107        }
108
109        for (int i = 0; i < nodes.Length; ++i) {
110          var node = nodes[i];
111          if (node.IsLeaf) {
112            continue;
113          }
114          node.Simplify?.Invoke(ref nodes, i);
115          for (int j = i - node.Size; j <= i; ++j) {
116            // detect if anything was simplified
117            if (!nodes[j].Enabled) {
118              simplified = true;
119              break;
120            }
121          }
122        }
123      } while (simplified);
124      return nodes.UpdateNodeSizes().Sort(hashFunction);
125    }
126
127    public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
128      int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);
129
130      for (int i = 0; i < nodes.Length; ++i) {
131        var node = nodes[i];
132
133        if (node.IsLeaf) {
134          continue;
135        }
136
137        if (node.IsCommutative) { // only sort when the argument order does not matter
138          var arity = node.Arity;
139          var size = node.Size;
140
141          if (arity == size) { // all child nodes are terminals
142            Array.Sort(nodes, i - size, size);
143          } else { // i have some non-terminal children
144            var sorted = new HashNode<T>[size];
145            var indices = new int[node.Arity];
146            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
147              indices[k] = j;
148            }
149            Array.Sort(indices, sort);
150
151            int idx = 0;
152            foreach (var j in indices) {
153              var child = nodes[j];
154              if (!child.IsLeaf) { // must copy complete subtree
155                Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
156                idx += child.Size;
157              }
158              sorted[idx++] = nodes[j];
159            }
160            Array.Copy(sorted, 0, nodes, i - size, size);
161          }
162        }
163        node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction);
164      }
165      return nodes;
166    }
167
168    /// <summary>
169    /// Get a function node's child indices
170    /// </summary>
171    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
172    /// <param name="nodes">An array of hash nodes with up-to-date node sizes (see UpdateNodeSizes)</param>
173    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
174    /// <returns>An array containing child indices</returns>
175    public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {
176      var node = nodes[i];
177      var arity = node.Arity;
178      var children = new int[arity];
179      var idx = i - 1;
180      for (int j = 0; j < arity; ++j) {
181        children[j] = idx;
182        idx -= 1 + nodes[idx].Size;
183      }
184      return children;
185    }
186
187    /// <summary>
188    /// Determines size of each branch and sets the results for each node.
189    /// </summary>
190    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
191    /// <param name="nodes">An array of hash nodes in postfix order.</param>
192    /// <returns>The array with updated node sizes. The array is not copied.</returns>
193    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
194      for (int i = 0; i < nodes.Length; ++i) {
195        var node = nodes[i];
196        if (node.IsLeaf) {
197          node.Size = 0;
198          continue;
199        }
200        node.Size = node.Arity;
201        // visit all children and sum up their size (assumes postfix order).
202        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
203          node.Size += nodes[j].Size;
204        }
205      }
206      return nodes;
207    }
208
209    // disables duplicate branches and removes the disabled nodes
210    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
211      int count = 0;
212      for (int i = 0; i < nodes.Length; ++i) {
213        var node = nodes[i];
214        if (node.IsLeaf || !node.IsCommutative) {
215          continue;
216        }
217
218        var arity = node.Arity;
219        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
220          if (node.HashValue == nodes[j].HashValue) {
221            nodes[j].Enabled = false;
222            node.Arity += nodes[j].Arity - 1;
223            ++count;
224          }
225        }
226      }
227      if (count == 0)
228        return nodes;
229
230      var reduced = new HashNode<T>[nodes.Length - count];
231      var idx = 0;
232      foreach (var node in nodes) {
233        if (node.Enabled) { reduced[idx++] = node; }
234      }
235      return reduced.UpdateNodeSizes();
236    }
237  }
238}
Note: See TracBrowser for help on using the repository browser.