Changeset 15832 for branches/2886_SymRegGrammarEnumeration

Timestamp:

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

Author:

lkammere

Message:

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

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/SearchGraphVisualizer.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (5 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs (modified) (3 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing (added)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/Hasher.cs (added)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj (modified) (1 diff)
• Test/GrammarEnumerationTest.cs (modified) (3 diffs)
• Test/TreeHashingTest.cs (modified) (9 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/SearchGraphVisualizer.cs

@@ -50 +50 @@
         var alg = (GrammarEnumerationAlgorithm)sender;
         var phrase0 = new SymbolString(new[] { alg.Grammar.StartSymbol });
-        var phrase0Hash = alg.Grammar.CalcHashCode(phrase0);
+        var phrase0Hash = alg.Grammar.Hasher.CalcHashCode(phrase0);
 
         dotFileTrace.WriteLine($"{phrase0Hash} [label=\"{phrase0}\", shape=doublecircle]; }}");

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;

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

@@ -135 +135 @@
       OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
       var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
-      var phrase0Hash = Grammar.CalcHashCode(phrase0);
+      var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0);
       #endregion
 
@@ -160 +160 @@
 
           if (newPhrase.Count() <= MaxTreeSize) {
-            var phraseHash = Grammar.CalcHashCode(newPhrase);
+            var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase);
 
             OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);

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

@@ -20 +20 @@
     #region IEquatable
     public static bool operator ==(Symbol s1, Symbol s2) {
-      return !ReferenceEquals(null, s1) && !ReferenceEquals(null, s2) && (ReferenceEquals(s1, s2)
-        || s1.Equals(s2));
+      if (ReferenceEquals(s1, s2)) return true;
+      if (ReferenceEquals(s1, null) || ReferenceEquals(s2, null)) return false;
+      return s1.Equals(s2);
     }
 
@@ -29 +30 @@
 
     public bool Equals(Symbol other) {
-      if (ReferenceEquals(null, other)) return false;
-      if (ReferenceEquals(this, other)) return true;
-      return string.Equals(StringRepresentation, other.StringRepresentation);
+      if (ReferenceEquals(other, null)) return false;
+      if (ReferenceEquals(other, this)) return true;
+      if (this.GetType() != other.GetType()) return false; // Otherwise, this needs to be reimplemented in derived classes.
+      return StringRepresentation == other.StringRepresentation;
     }
 
     public override bool Equals(object obj) {
-      if (ReferenceEquals(null, obj)) return false;
-      if (ReferenceEquals(this, obj)) return true;
-      if (obj.GetType() != this.GetType()) return false;
+      if (ReferenceEquals(obj, null)) return false;
+      if (ReferenceEquals(obj, this)) return true;
+      if (this.GetType() != obj.GetType()) return false;
       return Equals((Symbol)obj);
     }
@@ -48 +50 @@
 
   public class TerminalSymbol : Symbol {
-    public readonly bool IsVariable;
 
-    public TerminalSymbol(string representation, bool isVariable = false) : base(representation) {
-      IsVariable = isVariable;
-    }
+    public TerminalSymbol(string representation) : base(representation) { }
   }
 
+  public class VariableTerminalSymbol : TerminalSymbol {
+    public VariableTerminalSymbol(string representation) : base(representation) { }
+  }
+
+
   public class NonterminalSymbol : Symbol {
-    public List<Production> Alternatives { get; }
+    private readonly List<Production> alternatives;
+
+    public IReadOnlyList<Production> Alternatives {
+      get { return alternatives.AsReadOnly(); }
+    }
 
     public NonterminalSymbol(string representation) : base(representation) {
-      Alternatives = new List<Production>();
+      alternatives = new List<Production>();
     }
 
     public void AddProduction(params Symbol[] production) {
-      Alternatives.Add(new Production(production));
+      alternatives.Add(new Production(production));
     }
   }
 
   public class VariableSymbol : NonterminalSymbol { // Convenience class
-    public IEnumerable<TerminalSymbol> VariableTerminalSymbols { get; }
+    public IEnumerable<VariableTerminalSymbol> VariableTerminalSymbols { get; }
 
     public VariableSymbol(string representation, IEnumerable<string> variableNames) : base(representation) {
-      List<TerminalSymbol> createdSymbols = new List<TerminalSymbol>();
+      List<VariableTerminalSymbol> createdSymbols = new List<VariableTerminalSymbol>();
       VariableTerminalSymbols = createdSymbols;
 
       foreach (string variableName in variableNames) {
-        TerminalSymbol s = new TerminalSymbol(variableName, isVariable: true);
+        VariableTerminalSymbol s = new VariableTerminalSymbol(variableName);
         createdSymbols.Add(s);
         AddProduction(s);

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

@@ -116 +116 @@
     <Compile Include="GrammarEnumeration\Grammar.cs" />
     <Compile Include="GrammarEnumeration\GrammarEnumerationAlgorithm.cs" />
+    <Compile Include="Hashing\Hasher.cs" />
     <Compile Include="GrammarEnumeration\SearchDataStructure.cs" />
     <Compile Include="GrammarEnumeration\Sentence.cs" />

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -72 +72 @@
       });
 
-      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
-      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
       Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
@@ -127 +127 @@
       });
 
-      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
-      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
       Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");
@@ -156 +156 @@
       });
 
-      int targetSolutionHash = alg.Grammar.CalcHashCode(targetSolution);
-      int actualSolutionHash = alg.Grammar.CalcHashCode(alg.BestTrainingSentence);
+      int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution);
+      int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence);
 
       Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!");

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -28 +28 @@
       SymbolString s2 = new SymbolString(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -40 +40 @@
       SymbolString s2 = new SymbolString(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreNotEqual(hash1, hash2);
@@ -52 +52 @@
       SymbolString s2 = new SymbolString(new[] { varB, varA, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -64 +64 @@
       SymbolString s2 = new SymbolString(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -76 +76 @@
       SymbolString s2 = new SymbolString(new[] { varA });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -88 +88 @@
       SymbolString s2 = new SymbolString(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreNotEqual(hash1, hash2);
@@ -100 +100 @@
       SymbolString s2 = new SymbolString(new Symbol[] { varA, grammar.Expr, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -114 +114 @@
       SymbolString s2 = new SymbolString(new Symbol[] { varA, varB, grammar.Multiplication });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -126 +126 @@
       SymbolString s2 = new SymbolString(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });
 
-      int hash1 = grammar.CalcHashCode(s1);
-      int hash2 = grammar.CalcHashCode(s2);
+      int hash1 = grammar.Hasher.CalcHashCode(s1);
+      int hash2 = grammar.Hasher.CalcHashCode(s2);
 
       Assert.AreEqual(hash1, hash2);