Changeset 15714 for branches/2886_SymRegGrammarEnumeration

Timestamp:

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

Author:

lkammere

Message:

#2886: Add tree hashing for addition and multiplication.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj (modified) (1 diff)
• Test/GrammarEnumerationTest.cs (modified) (1 diff)
• Test/Test.csproj (modified) (2 diffs)
• Test/TreeHashingTest.cs (added)

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());
     }
   }

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

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
 using System.Collections.ObjectModel;
 using System.Diagnostics;
@@ -41 +42 @@
       DoubleValue averageTreeLength = new DoubleValue();
       Results.Add(new Result("Average Tree Length of Solutions", averageTreeLength));
-
 
       int maxStringLength = 4;

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

@@ -1 @@
-using System;
-using System.Collections.Generic;
+using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
 
   public abstract class Symbol {
-    private readonly string stringRepresentation;
+    public readonly string StringRepresentation;
 
     protected Symbol(string representation) {
-      stringRepresentation = representation;
+      StringRepresentation = representation;
     }
 
     public override string ToString() {
-      return stringRepresentation;
+      return StringRepresentation;
     }
   }
@@ -33 +33 @@
 
   public class VariableSymbol : NonterminalSymbol { // Convenience class
+    public IEnumerable<TerminalSymbol> VariableTerminalSymbols;
+
     public VariableSymbol(string representation, IEnumerable<string> variableNames) : base(representation) {
+      List<TerminalSymbol> createdSymbols = new List<TerminalSymbol>();
+      VariableTerminalSymbols = createdSymbols;
+
       foreach (string variableName in variableNames) {
-        AddProduction(new TerminalSymbol("[" + variableName + "]"));
+        TerminalSymbol s = new TerminalSymbol(variableName);
+        createdSymbols.Add(s);
+        AddProduction(s);
       }
     }

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj

@@ -98 +98 @@
     <Compile Include="GrammarEnumeration\Symbol.cs" />
   </ItemGroup>
+  <ItemGroup />
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <!-- To modify your build process, add your task inside one of the targets below and uncomment it. 

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -10 +10 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis.MctsSymbolicRegression {
-  [TestClass()]
+  //[TestClass()]
   public class MctsSymbolicRegressionTest {
     private const int Seed = 1234;

branches/2886_SymRegGrammarEnumeration/Test/Test.csproj

@@ -103 +103 @@
     <Otherwise>
       <ItemGroup>
-        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework" />
+        <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework">
+          <Private>False</Private>
+        </Reference>
       </ItemGroup>
     </Otherwise>
@@ -110 +112 @@
     <Compile Include="GrammarEnumerationTest.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
+    <Compile Include="TreeHashingTest.cs" />
   </ItemGroup>
   <ItemGroup>