Changeset 15725

Timestamp:

02/06/18 16:21:16 (7 years ago)

Author:

lkammere

Message:

#2886: Refactor tree hash function.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (7 diffs)
• Test/TreeHashingTest.cs (modified) (1 diff)

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

@@ -1 @@
-using System.Collections;
+using System;
 using System.Collections.Generic;
-using System.ComponentModel;
 using System.Diagnostics;
 using System.Linq;
@@ -163 +162 @@
       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;
-
+      TerminalSymbol peek = parseStack.Peek();
+      int[] subtreeHashes = GetSubtreeHashes(parseStack);
+      return AggregateHashes(peek, subtreeHashes);
+    }
+
+    private int[] GetSubtreeHashes(Stack<TerminalSymbol> parseStack) {
+      TerminalSymbol currentSymbol = parseStack.Pop();
+
+      // VARIABLE
       if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
-        childHashes = currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToList();
-
-      } else if (ReferenceEquals(currentSymbol, Multiplication)) {
-        // MULTIPLICATION
-        childHashes = new List<int>();
+        return currentSymbol.StringRepresentation.GetHashCode().ToEnumerable().ToArray();
+      }
+
+      // MULTIPLICATION
+      if (ReferenceEquals(currentSymbol, Multiplication)) {
+        List<int> childHashes = new List<int>();
 
         // First subtree
-        TerminalSymbol firstSubtreeRoot = parseStack.Pop();
-        int[] firstSubtreeHashes = GetSubtreeHashes(firstSubtreeRoot, parseStack);
-
-        if (ReferenceEquals(firstSubtreeRoot, Multiplication)) {
-          childHashes.AddRange(firstSubtreeHashes);
+        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
+          childHashes.AddRange(GetSubtreeHashes(parseStack));
         } else {
-          childHashes.Add(AggregateHashes(firstSubtreeHashes));
+          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
         }
-
         // Second subtree
-        TerminalSymbol secondSubtreeRoot = parseStack.Pop();
-        int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack);
-
-        if (ReferenceEquals(secondSubtreeRoot, Multiplication)) {
-          childHashes.AddRange(secondSubtreeHashes);
+        if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
+          childHashes.AddRange(GetSubtreeHashes(parseStack));
         } else {
-          childHashes.Add(AggregateHashes(secondSubtreeHashes));
+          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
         }
 
         // Sort due to commutativity
         childHashes.Sort();
-
-
-
-      } else if (ReferenceEquals(currentSymbol, Addition)) {
-        // ADDITION
+        return childHashes.ToArray();
+      }
+
+      // ADDITION
+      if (ReferenceEquals(currentSymbol, 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);
+        if (ReferenceEquals(parseStack.Peek(), Addition)) {
+          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
         } else {
-          uniqueChildHashes.Add(AggregateHashes(firstSubtreeHashes));
+          var peek = parseStack.Peek();
+          uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
         }
-
         // Second subtree
-        TerminalSymbol secondSubtreeRoot = parseStack.Pop();
-        int[] secondSubtreeHashes = GetSubtreeHashes(secondSubtreeRoot, parseStack);
-
-        if (ReferenceEquals(secondSubtreeRoot, Addition)) {
-          uniqueChildHashes.UnionWith(secondSubtreeHashes);
+        if (ReferenceEquals(parseStack.Peek(), Addition)) {
+          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
         } else {
-          uniqueChildHashes.Add(AggregateHashes(secondSubtreeHashes));
+          var peek = parseStack.Peek();
+          uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
         }
 
-        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());
+        var result = uniqueChildHashes.ToList();
+        result.Sort();
+        return result.ToArray();
+      }
+      throw new ArgumentException("Trying to hash malformed sentence!");
+    }
+
+    private int AggregateHashes(TerminalSymbol rule, IEnumerable<int> hashes) {
+      // If multiple subtrees are "merged" (e.g. added, multiplied, etc.), consider the executed operation
+      var hashesArray = hashes.ToArray();
+      int start = hashesArray.Length > 1 ? rule.StringRepresentation.GetHashCode() : 0;
+      return hashesArray.Aggregate(start, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
     }
     #endregion
@@ -297 +289 @@
 
       if (ReferenceEquals(head, Addition) || ReferenceEquals(head, Multiplication)) {
-        result.AddRange(PostfixToInfixSubtreeParser(parseStack));
+        // right part
+        SymbolString rightPart = PostfixToInfixSubtreeParser(parseStack);
+        SymbolString leftPart = PostfixToInfixSubtreeParser(parseStack);
+
+        result.AddRange(leftPart);
         result.Add(head);
-        result.AddRange(PostfixToInfixSubtreeParser(parseStack));
+        result.AddRange(rightPart);
       } else {
         result.Add(head);

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

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Threading;
@@ -28 +29 @@
     private readonly string UseMemoizationParameterName = "Use Memoization?";
 
-
     #region properties
     protected IValueParameter<IntValue> MaxTreeSizeParameter {
@@ -89 +89 @@
       BestTrainingSentence = null;
 
-      List<SymbolString> allGenerated = new List<SymbolString>();
+      List<Tuple<SymbolString, int>> allGenerated = new List<Tuple<SymbolString, int>>();
       List<SymbolString> distinctGenerated = new List<SymbolString>();
-
-      int expansions = 0;
 
       HashSet<int> evaluatedHashes = new HashSet<int>();
@@ -107 +105 @@
 
         if (currSymbolString.IsSentence()) {
-          allGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
-
-          //if (evaluatedHashes.Add(grammar.CalcHashCode(currSymbolString))) {
-          EvaluateSentence(currSymbolString);
-          distinctGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
-          //}
-
-          UpdateView(allGenerated, distinctGenerated, expansions);
+          allGenerated.Add(new Tuple<SymbolString, int>(currSymbolString, Grammar.CalcHashCode(currSymbolString)));
+
+          if (evaluatedHashes.Add(Grammar.CalcHashCode(currSymbolString))) {
+            EvaluateSentence(currSymbolString);
+            distinctGenerated.Add(Grammar.PostfixToInfixParser(currSymbolString));
+          }
+
+          UpdateView(allGenerated, distinctGenerated);
 
         } else {
@@ -133 +131 @@
       }
 
-      UpdateView(allGenerated, distinctGenerated, expansions, force: true);
-
-      StringArray sentences = new StringArray(allGenerated.Select(r => r.ToString()).ToArray());
-      Results.Add(new Result("All generated sentences", sentences));
+      UpdateView(allGenerated, distinctGenerated, force: true);
+
+      string[,] sentences = new string[allGenerated.Count, 3];
+      for (int i = 0; i < allGenerated.Count; i++) {
+        sentences[i, 0] = allGenerated[i].Item1.ToString();
+        sentences[i, 1] = Grammar.PostfixToInfixParser(allGenerated[i].Item1).ToString();
+        sentences[i, 2] = allGenerated[i].Item2.ToString();
+      }
+      Results.Add(new Result("All generated sentences", new StringMatrix(sentences)));
+
       StringArray distinctSentences = new StringArray(distinctGenerated.Select(r => r.ToString()).ToArray());
       Results.Add(new Result("Distinct generated sentences", distinctSentences));
@@ -142 +146 @@
 
 
-    private void UpdateView(List<SymbolString> allGenerated, List<SymbolString> distinctGenerated, int expansions, bool force = false) {
+    private void UpdateView(List<Tuple<SymbolString, int>> allGenerated, List<SymbolString> distinctGenerated, bool force = false) {
       int generatedSolutions = allGenerated.Count;
       int distinctSolutions = distinctGenerated.Count;
@@ -150 +154 @@
         Results.AddOrUpdateResult("Distinct Solutions", new IntValue(distinctSolutions));
 
-        DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Count).Average());
+        DoubleValue averageTreeLength = new DoubleValue(allGenerated.Select(r => r.Item1.Count).Average());
         Results.AddOrUpdateResult("Average Tree Length of Solutions", averageTreeLength);
-
-        IntValue expansionsValue = new IntValue(expansions);
-        Results.AddOrUpdateResult("Expansions", expansionsValue);
       }
     }

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -81 +81 @@
       Assert.AreEqual(hash1, hash2);
     }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void ComplexInequality() {
+      SymbolString s1 = new SymbolString(new[] { varA, varA, varA, grammar.Multiplication, grammar.Multiplication });
+      SymbolString s2 = new SymbolString(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });
+
+      int hash1 = grammar.CalcHashCode(s1);
+      int hash2 = grammar.CalcHashCode(s2);
+
+      Assert.AreNotEqual(hash1, hash2);
+    }
+
+
+    #region parser
+
+    [TestMethod]
+    [TestCategory("Parser")]
+    public void InfixParserSimpleTest() {
+      SymbolString postfix = new SymbolString(new[] { varA, varB, varC, grammar.Addition, grammar.Addition });
+      SymbolString infix = new SymbolString(new[] { varA, grammar.Addition, varB, grammar.Addition, varC });
+
+      Assert.AreEqual(infix.ToString(), grammar.PostfixToInfixParser(postfix).ToString());
+    }
+
+    [TestMethod]
+    [TestCategory("Parser")]
+    public void InfixParserComplexTest() {
+      SymbolString postfix = new SymbolString(new[] { varB, varA, varB, varC, grammar.Multiplication, grammar.Addition, grammar.Addition});
+      SymbolString infix = new SymbolString(new[] { varB, grammar.Addition, varA, grammar.Addition, varB, grammar.Multiplication, varC });
+
+      Assert.AreEqual(infix.ToString(), grammar.PostfixToInfixParser(postfix).ToString());
+    }
+
+    #endregion
   }
 }