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

Timestamp:

02/02/18 18:48:10 (7 years ago)

Author:

lkammere

Message:

#2886: Add tree hashing for addition and multiplication.

File:

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

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

@@ -1 @@
-namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
+using System.Collections;
+using System.Collections.Generic;
+using System.ComponentModel;
+using System.Diagnostics;
+using System.Linq;
+using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
+using HeuristicLab.Common;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
   public class Grammar {
 
     public Symbol StartSymbol;
 
+    #region Symbols
+    public VariableSymbol Var;
+
+    public NonterminalSymbol Expr;
+    public NonterminalSymbol Term;
+    public NonterminalSymbol Factor;
+
+    public TerminalSymbol Addition;
+    public TerminalSymbol Multiplication;
+    #endregion
+
+
     public Grammar(string[] variables) {
       #region Define Symbols
-      VariableSymbol var = new VariableSymbol("var", variables);
+      Var = new VariableSymbol("var", variables);
 
-      NonterminalSymbol expr = new NonterminalSymbol("Expr");
-      NonterminalSymbol term = new NonterminalSymbol("Expr");
-      NonterminalSymbol factor = new NonterminalSymbol("Expr");
+      Expr = new NonterminalSymbol("Expr");
+      Term = new NonterminalSymbol("Term");
+      Factor = new NonterminalSymbol("Factor");
 
-      TerminalSymbol addition = new TerminalSymbol("+");
-      TerminalSymbol multiplication = new TerminalSymbol("*");
+      Addition = new TerminalSymbol("+");
+      Multiplication = new TerminalSymbol("*");
       #endregion
 
 
       #region Production ruless
-      StartSymbol = expr;
+      StartSymbol = Expr;
 
-      expr.AddProduction(term, expr, addition);
-      expr.AddProduction(term);
+      Expr.AddProduction(Term, Expr, Addition);
+      Expr.AddProduction(Term);
 
-      term.AddProduction(factor, term, multiplication);
-      term.AddProduction(factor);
+      Term.AddProduction(Factor, Term, Multiplication);
+      Term.AddProduction(Factor);
 
-      factor.AddProduction(var);
+      Factor.AddProduction(Var);
       #endregion
+    }
+
+    public int CalcHashCode(SymbolString sentence) {
+      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
+      Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
+
+      Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
+
+      int[] subtreeHashes = GetSubtreeHashes(parseStack.Pop(), parseStack);
+      return AggregateHashes(subtreeHashes);
+    }
+
+    private int[] GetSubtreeHashes(TerminalSymbol currentSymbol, Stack<TerminalSymbol> parseStack) {
+      List<int> childHashes = null;
+
+      if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
+        childHashes = currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToList();
+
+      } else if (ReferenceEquals(currentSymbol, Multiplication)) { // MULTIPLICATION
+        childHashes = new List<int>();
+
+        // First subtree
+        TerminalSymbol firstSubtreeRoot = parseStack.Pop();
+        int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack);
+
+        if (ReferenceEquals(firstSubtreeRoot, Multiplication)) {
+          childHashes.AddRange(firstSubtreeHashes);
+        } else {
+          childHashes.Add(AggregateHashes(firstSubtreeHashes));
+        }
+
+        // Second subtree
+        TerminalSymbol secondSubtreeRoot = parseStack.Pop();
+        int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack);
+
+        if (ReferenceEquals(secondSubtreeRoot, Multiplication)) {
+          childHashes.AddRange(secondSubtreeHashes);
+        } else {
+          childHashes.Add(AggregateHashes(secondSubtreeHashes));
+        }
+
+        // Sort due to commutativity
+        childHashes.Sort();
+
+
+
+      } else if (ReferenceEquals(currentSymbol, Addition)) { // ADDITION
+        HashSet<int> uniqueChildHashes = new HashSet<int>();
+
+        TerminalSymbol firstSubtreeRoot = parseStack.Pop();
+        int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack);
+
+        // First subtree
+        if (ReferenceEquals(firstSubtreeRoot, Addition)) {
+          uniqueChildHashes.UnionWith(firstSubtreeHashes);
+        } else {
+          uniqueChildHashes.Add(AggregateHashes(firstSubtreeHashes));
+        }
+
+        // Second subtree
+        TerminalSymbol secondSubtreeRoot = parseStack.Pop();
+        int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack);
+
+        if (ReferenceEquals(secondSubtreeRoot, Addition)) {
+          uniqueChildHashes.UnionWith(secondSubtreeHashes);
+        } else {
+          uniqueChildHashes.Add(AggregateHashes(secondSubtreeHashes));
+        }
+
+        childHashes = uniqueChildHashes.ToList();
+        childHashes.Sort();
+      }
+
+      Debug.Assert(childHashes != null, "Sentence not hashable!");
+      return childHashes.ToArray();
+    }
+
+
+    private int AggregateHashes(IEnumerable<int> hashes) {
+      return hashes.Aggregate(0, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
     }
   }