Changeset 15832 for branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

Timestamp:

03/08/18 10:54:04 (6 years ago)

Author:

lkammere

Message:

#2886: Fix Equals methods in Symbols.
Move semantical hashing of phrases to separate class.

File:

• branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (5 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

@@ -1 @@
-using System;
-using System.Collections.Generic;
+using System.Collections.Generic;
 using System.Diagnostics;
 using System.Linq;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
-using HeuristicLab.Common;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Problems.DataAnalysis.Symbolic;
@@ -12 +10 @@
 
     public Symbol StartSymbol { get; }
+
+    public Hasher<int> Hasher { get; }
 
     #region Symbols
@@ -146 +146 @@
       infixExpressionFormatter = new InfixExpressionFormatter();
       #endregion
-    }
-
-    #region Hashing
-    public int CalcHashCode(SymbolString sentence) {
-      return CalcHashCode<int>(sentence, AggregateIntHashes);
-    }
-
-    private int CalcHashCode<THashType>(SymbolString sentence, Func<Symbol, THashType[], THashType> aggregateFunction) {
-      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
-
-      Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
-
-      Symbol peek = parseStack.Peek();
-      return aggregateFunction(peek, GetSubtreeHashes(parseStack, aggregateFunction)).GetHashCode();
-    }
-
-    private THashType[] GetSubtreeHashes<THashType>(Stack<Symbol> parseStack, Func<Symbol, THashType[], THashType> aggregateHashes) {
-      Symbol currentSymbol = parseStack.Pop();
-
-      // ADDITION
-      if (currentSymbol == Addition) {
-        var uniqueChildHashes = new HashSet<THashType>();
-
-        // First subtree
-        if (parseStack.Peek() == Addition) {
-          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack, aggregateHashes));
-        } else {
-          var peek = parseStack.Peek();
-          uniqueChildHashes.Add(aggregateHashes(peek, GetSubtreeHashes(parseStack, aggregateHashes)));
-        }
-        // Second subtree
-        if (parseStack.Peek() == Addition) {
-          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack, aggregateHashes));
-        } else {
-          var peek = parseStack.Peek();
-          uniqueChildHashes.Add(aggregateHashes(peek, GetSubtreeHashes(parseStack, aggregateHashes)));
-        }
-
-        var result = uniqueChildHashes.ToArray();
-        Array.Sort(result);
-        return result;
-      }
-
-      // MULTIPLICATION
-      if (currentSymbol == Multiplication) {
-        var childHashes = new List<THashType>();
-
-        // First subtree
-        if (parseStack.Peek() == Multiplication) {
-          childHashes.AddRange(GetSubtreeHashes(parseStack, aggregateHashes));
-        } else {
-          childHashes.Add(aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)));
-        }
-        // Second subtree
-        if (parseStack.Peek() == Multiplication) {
-          childHashes.AddRange(GetSubtreeHashes(parseStack, aggregateHashes));
-        } else {
-          childHashes.Add(aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)));
-        }
-
-        // Sort due to commutativity
-        childHashes.Sort();
-
-        // Cancel out inverse factors.
-        bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray();
-
-        for (int i = 0; i < isFactorRemaining.Length; i++) {
-          if (!isFactorRemaining[i]) continue;
-          if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.
-
-          var currFactor = childHashes[i];
-          var invFactor = aggregateHashes(Inv, new[] { currFactor });
-
-          int indexOfInv = childHashes.IndexOf(invFactor);
-          if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) {
-            isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false;
-          }
-        }
-
-        return childHashes
-          .Where((c, i) => isFactorRemaining[i])
-          .ToArray();
-      }
-
-      // LOG, EXP, SIN, INV
-      if (currentSymbol == Log || currentSymbol == Exp ||
-          currentSymbol == Sin || currentSymbol == Cos ||
-          currentSymbol == Inv) {
-        return new[] { aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)) };
-      }
-
-      // var or nonterminal symbol
-      return new[] { aggregateHashes(currentSymbol, new THashType[0]) };
-    }
-
-    private string AggregateStringHashes(Symbol operatorSym, string[] hashes) {
-      var hashesArray = hashes.ToArray();
-
-      if ((operatorSym == Addition || operatorSym == Multiplication) && hashesArray.Length <= 1) {
-        return hashesArray[0];
-      }
-      if (operatorSym is NonterminalSymbol || ((TerminalSymbol)operatorSym).IsVariable) {
-        return operatorSym.StringRepresentation;
-      }
-
-      return $"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray)}]";
-    }
-
-    private int AggregateIntHashes(Symbol operatorSym, int[] hashes) {
-      int start;
-      if ((operatorSym == Addition || operatorSym == Multiplication) && hashes.Length <= 1) {
-        start = 0;
-
-      } else if (operatorSym is NonterminalSymbol || ((TerminalSymbol)operatorSym).IsVariable) {
-        return operatorSym.StringRepresentation.GetHashCode();
-
-      } else {
-        start = operatorSym.StringRepresentation.GetHashCode();
-      }
-
-      for (int i = 0; i < hashes.Length; i++) {
-        start = ((start << 5) + start) ^ hashes[i];
-      }
-      return start;
-    }
-    #endregion
+
+      Hasher = new IntHasher(this);
+    }
 
     #region Parse to SymbolicExpressionTree
@@ -323 +200 @@
         parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
 
-      } else if (currentSymbol ==  Cos) {
+      } else if (currentSymbol == Cos) {
         parsedSubTree = cosSy.CreateTreeNode();
         parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
@@ -334 +211 @@
         parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
 
-      } else if (currentSymbol.IsVariable) {
+      } else if (currentSymbol is VariableTerminalSymbol) {
         VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode();
         varNode.Weight = 1.0;