source: stable/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs @ 17141

Last change on this file since 17141 was 17141, checked in by abeham, 17 months ago

#2950: merged r17076 to stable

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