Changeset 15832 for branches/2886_SymRegGrammarEnumeration
- Timestamp:
- 03/08/18 10:54:04 (6 years ago)
- Location:
- branches/2886_SymRegGrammarEnumeration
- Files:
-
- 2 added
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Analysis/SearchGraphVisualizer.cs
r15821 r15832 50 50 var alg = (GrammarEnumerationAlgorithm)sender; 51 51 var phrase0 = new SymbolString(new[] { alg.Grammar.StartSymbol }); 52 var phrase0Hash = alg.Grammar. CalcHashCode(phrase0);52 var phrase0Hash = alg.Grammar.Hasher.CalcHashCode(phrase0); 53 53 54 54 dotFileTrace.WriteLine($"{phrase0Hash} [label=\"{phrase0}\", shape=doublecircle]; }}"); -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs
r15828 r15832 1 using System; 2 using System.Collections.Generic; 1 using System.Collections.Generic; 3 2 using System.Diagnostics; 4 3 using System.Linq; 5 4 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration; 6 using HeuristicLab.Common;7 5 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 8 6 using HeuristicLab.Problems.DataAnalysis.Symbolic; … … 12 10 13 11 public Symbol StartSymbol { get; } 12 13 public Hasher<int> Hasher { get; } 14 14 15 15 #region Symbols … … 146 146 infixExpressionFormatter = new InfixExpressionFormatter(); 147 147 #endregion 148 } 149 150 #region Hashing 151 public int CalcHashCode(SymbolString sentence) { 152 return CalcHashCode<int>(sentence, AggregateIntHashes); 153 } 154 155 private int CalcHashCode<THashType>(SymbolString sentence, Func<Symbol, THashType[], THashType> aggregateFunction) { 156 Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!"); 157 158 Stack<Symbol> parseStack = new Stack<Symbol>(sentence); 159 160 Symbol peek = parseStack.Peek(); 161 return aggregateFunction(peek, GetSubtreeHashes(parseStack, aggregateFunction)).GetHashCode(); 162 } 163 164 private THashType[] GetSubtreeHashes<THashType>(Stack<Symbol> parseStack, Func<Symbol, THashType[], THashType> aggregateHashes) { 165 Symbol currentSymbol = parseStack.Pop(); 166 167 // ADDITION 168 if (currentSymbol == Addition) { 169 var uniqueChildHashes = new HashSet<THashType>(); 170 171 // First subtree 172 if (parseStack.Peek() == Addition) { 173 uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack, aggregateHashes)); 174 } else { 175 var peek = parseStack.Peek(); 176 uniqueChildHashes.Add(aggregateHashes(peek, GetSubtreeHashes(parseStack, aggregateHashes))); 177 } 178 // Second subtree 179 if (parseStack.Peek() == Addition) { 180 uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack, aggregateHashes)); 181 } else { 182 var peek = parseStack.Peek(); 183 uniqueChildHashes.Add(aggregateHashes(peek, GetSubtreeHashes(parseStack, aggregateHashes))); 184 } 185 186 var result = uniqueChildHashes.ToArray(); 187 Array.Sort(result); 188 return result; 189 } 190 191 // MULTIPLICATION 192 if (currentSymbol == Multiplication) { 193 var childHashes = new List<THashType>(); 194 195 // First subtree 196 if (parseStack.Peek() == Multiplication) { 197 childHashes.AddRange(GetSubtreeHashes(parseStack, aggregateHashes)); 198 } else { 199 childHashes.Add(aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes))); 200 } 201 // Second subtree 202 if (parseStack.Peek() == Multiplication) { 203 childHashes.AddRange(GetSubtreeHashes(parseStack, aggregateHashes)); 204 } else { 205 childHashes.Add(aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes))); 206 } 207 208 // Sort due to commutativity 209 childHashes.Sort(); 210 211 // Cancel out inverse factors. 212 bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray(); 213 214 for (int i = 0; i < isFactorRemaining.Length; i++) { 215 if (!isFactorRemaining[i]) continue; 216 if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms. 217 218 var currFactor = childHashes[i]; 219 var invFactor = aggregateHashes(Inv, new[] { currFactor }); 220 221 int indexOfInv = childHashes.IndexOf(invFactor); 222 if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) { 223 isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false; 224 } 225 } 226 227 return childHashes 228 .Where((c, i) => isFactorRemaining[i]) 229 .ToArray(); 230 } 231 232 // LOG, EXP, SIN, INV 233 if (currentSymbol == Log || currentSymbol == Exp || 234 currentSymbol == Sin || currentSymbol == Cos || 235 currentSymbol == Inv) { 236 return new[] { aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)) }; 237 } 238 239 // var or nonterminal symbol 240 return new[] { aggregateHashes(currentSymbol, new THashType[0]) }; 241 } 242 243 private string AggregateStringHashes(Symbol operatorSym, string[] hashes) { 244 var hashesArray = hashes.ToArray(); 245 246 if ((operatorSym == Addition || operatorSym == Multiplication) && hashesArray.Length <= 1) { 247 return hashesArray[0]; 248 } 249 if (operatorSym is NonterminalSymbol || ((TerminalSymbol)operatorSym).IsVariable) { 250 return operatorSym.StringRepresentation; 251 } 252 253 return $"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray)}]"; 254 } 255 256 private int AggregateIntHashes(Symbol operatorSym, int[] hashes) { 257 int start; 258 if ((operatorSym == Addition || operatorSym == Multiplication) && hashes.Length <= 1) { 259 start = 0; 260 261 } else if (operatorSym is NonterminalSymbol || ((TerminalSymbol)operatorSym).IsVariable) { 262 return operatorSym.StringRepresentation.GetHashCode(); 263 264 } else { 265 start = operatorSym.StringRepresentation.GetHashCode(); 266 } 267 268 for (int i = 0; i < hashes.Length; i++) { 269 start = ((start << 5) + start) ^ hashes[i]; 270 } 271 return start; 272 } 273 #endregion 148 149 Hasher = new IntHasher(this); 150 } 274 151 275 152 #region Parse to SymbolicExpressionTree … … 323 200 parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); 324 201 325 } else if (currentSymbol == 202 } else if (currentSymbol == Cos) { 326 203 parsedSubTree = cosSy.CreateTreeNode(); 327 204 parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); … … 334 211 parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack)); 335 212 336 } else if (currentSymbol .IsVariable) {213 } else if (currentSymbol is VariableTerminalSymbol) { 337 214 VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode(); 338 215 varNode.Weight = 1.0; -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs
r15827 r15832 135 135 OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy 136 136 var phrase0 = new SymbolString(new[] { Grammar.StartSymbol }); 137 var phrase0Hash = Grammar. CalcHashCode(phrase0);137 var phrase0Hash = Grammar.Hasher.CalcHashCode(phrase0); 138 138 #endregion 139 139 … … 160 160 161 161 if (newPhrase.Count() <= MaxTreeSize) { 162 var phraseHash = Grammar. CalcHashCode(newPhrase);162 var phraseHash = Grammar.Hasher.CalcHashCode(newPhrase); 163 163 164 164 OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]); -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs
r15828 r15832 20 20 #region IEquatable 21 21 public static bool operator ==(Symbol s1, Symbol s2) { 22 return !ReferenceEquals(null, s1) && !ReferenceEquals(null, s2) && (ReferenceEquals(s1, s2) 23 || s1.Equals(s2)); 22 if (ReferenceEquals(s1, s2)) return true; 23 if (ReferenceEquals(s1, null) || ReferenceEquals(s2, null)) return false; 24 return s1.Equals(s2); 24 25 } 25 26 … … 29 30 30 31 public bool Equals(Symbol other) { 31 if (ReferenceEquals(null, other)) return false; 32 if (ReferenceEquals(this, other)) return true; 33 return string.Equals(StringRepresentation, other.StringRepresentation); 32 if (ReferenceEquals(other, null)) return false; 33 if (ReferenceEquals(other, this)) return true; 34 if (this.GetType() != other.GetType()) return false; // Otherwise, this needs to be reimplemented in derived classes. 35 return StringRepresentation == other.StringRepresentation; 34 36 } 35 37 36 38 public override bool Equals(object obj) { 37 if (ReferenceEquals( null, obj)) return false;38 if (ReferenceEquals( this, obj)) return true;39 if ( obj.GetType() != this.GetType()) return false;39 if (ReferenceEquals(obj, null)) return false; 40 if (ReferenceEquals(obj, this)) return true; 41 if (this.GetType() != obj.GetType()) return false; 40 42 return Equals((Symbol)obj); 41 43 } … … 48 50 49 51 public class TerminalSymbol : Symbol { 50 public readonly bool IsVariable;51 52 52 public TerminalSymbol(string representation, bool isVariable = false) : base(representation) { 53 IsVariable = isVariable; 54 } 53 public TerminalSymbol(string representation) : base(representation) { } 55 54 } 56 55 56 public class VariableTerminalSymbol : TerminalSymbol { 57 public VariableTerminalSymbol(string representation) : base(representation) { } 58 } 59 60 57 61 public class NonterminalSymbol : Symbol { 58 public List<Production> Alternatives { get; } 62 private readonly List<Production> alternatives; 63 64 public IReadOnlyList<Production> Alternatives { 65 get { return alternatives.AsReadOnly(); } 66 } 59 67 60 68 public NonterminalSymbol(string representation) : base(representation) { 61 Alternatives = new List<Production>();69 alternatives = new List<Production>(); 62 70 } 63 71 64 72 public void AddProduction(params Symbol[] production) { 65 Alternatives.Add(new Production(production));73 alternatives.Add(new Production(production)); 66 74 } 67 75 } 68 76 69 77 public class VariableSymbol : NonterminalSymbol { // Convenience class 70 public IEnumerable< TerminalSymbol> VariableTerminalSymbols { get; }78 public IEnumerable<VariableTerminalSymbol> VariableTerminalSymbols { get; } 71 79 72 80 public VariableSymbol(string representation, IEnumerable<string> variableNames) : base(representation) { 73 List< TerminalSymbol> createdSymbols = new List<TerminalSymbol>();81 List<VariableTerminalSymbol> createdSymbols = new List<VariableTerminalSymbol>(); 74 82 VariableTerminalSymbols = createdSymbols; 75 83 76 84 foreach (string variableName in variableNames) { 77 TerminalSymbol s = new TerminalSymbol(variableName, isVariable: true);85 VariableTerminalSymbol s = new VariableTerminalSymbol(variableName); 78 86 createdSymbols.Add(s); 79 87 AddProduction(s); -
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj
r15824 r15832 116 116 <Compile Include="GrammarEnumeration\Grammar.cs" /> 117 117 <Compile Include="GrammarEnumeration\GrammarEnumerationAlgorithm.cs" /> 118 <Compile Include="Hashing\Hasher.cs" /> 118 119 <Compile Include="GrammarEnumeration\SearchDataStructure.cs" /> 119 120 <Compile Include="GrammarEnumeration\Sentence.cs" /> -
branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs
r15821 r15832 72 72 }); 73 73 74 int targetSolutionHash = alg.Grammar. CalcHashCode(targetSolution);75 int actualSolutionHash = alg.Grammar. CalcHashCode(alg.BestTrainingSentence);74 int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution); 75 int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence); 76 76 77 77 Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!"); … … 127 127 }); 128 128 129 int targetSolutionHash = alg.Grammar. CalcHashCode(targetSolution);130 int actualSolutionHash = alg.Grammar. CalcHashCode(alg.BestTrainingSentence);129 int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution); 130 int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence); 131 131 132 132 Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!"); … … 156 156 }); 157 157 158 int targetSolutionHash = alg.Grammar. CalcHashCode(targetSolution);159 int actualSolutionHash = alg.Grammar. CalcHashCode(alg.BestTrainingSentence);158 int targetSolutionHash = alg.Grammar.Hasher.CalcHashCode(targetSolution); 159 int actualSolutionHash = alg.Grammar.Hasher.CalcHashCode(alg.BestTrainingSentence); 160 160 161 161 Assert.IsTrue(alg.DistinctSentencesLength.ContainsKey(targetSolutionHash), "Actual solution was not generated!"); -
branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs
r15824 r15832 28 28 SymbolString s2 = new SymbolString(new[] { varA, varB, grammar.Addition, varC, grammar.Addition }); 29 29 30 int hash1 = grammar. CalcHashCode(s1);31 int hash2 = grammar. CalcHashCode(s2);30 int hash1 = grammar.Hasher.CalcHashCode(s1); 31 int hash2 = grammar.Hasher.CalcHashCode(s2); 32 32 33 33 Assert.AreEqual(hash1, hash2); … … 40 40 SymbolString s2 = new SymbolString(new[] { varB, varB, grammar.Addition, varB, grammar.Addition }); 41 41 42 int hash1 = grammar. CalcHashCode(s1);43 int hash2 = grammar. CalcHashCode(s2);42 int hash1 = grammar.Hasher.CalcHashCode(s1); 43 int hash2 = grammar.Hasher.CalcHashCode(s2); 44 44 45 45 Assert.AreNotEqual(hash1, hash2); … … 52 52 SymbolString s2 = new SymbolString(new[] { varB, varA, grammar.Addition }); 53 53 54 int hash1 = grammar. CalcHashCode(s1);55 int hash2 = grammar. CalcHashCode(s2);54 int hash1 = grammar.Hasher.CalcHashCode(s1); 55 int hash2 = grammar.Hasher.CalcHashCode(s2); 56 56 57 57 Assert.AreEqual(hash1, hash2); … … 64 64 SymbolString s2 = new SymbolString(new[] { varA, varB, varA, grammar.Addition, grammar.Addition }); 65 65 66 int hash1 = grammar. CalcHashCode(s1);67 int hash2 = grammar. CalcHashCode(s2);66 int hash1 = grammar.Hasher.CalcHashCode(s1); 67 int hash2 = grammar.Hasher.CalcHashCode(s2); 68 68 69 69 Assert.AreEqual(hash1, hash2); … … 76 76 SymbolString s2 = new SymbolString(new[] { varA }); 77 77 78 int hash1 = grammar. CalcHashCode(s1);79 int hash2 = grammar. CalcHashCode(s2);78 int hash1 = grammar.Hasher.CalcHashCode(s1); 79 int hash2 = grammar.Hasher.CalcHashCode(s2); 80 80 81 81 Assert.AreEqual(hash1, hash2); … … 88 88 SymbolString s2 = new SymbolString(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition }); 89 89 90 int hash1 = grammar. CalcHashCode(s1);91 int hash2 = grammar. CalcHashCode(s2);90 int hash1 = grammar.Hasher.CalcHashCode(s1); 91 int hash2 = grammar.Hasher.CalcHashCode(s2); 92 92 93 93 Assert.AreNotEqual(hash1, hash2); … … 100 100 SymbolString s2 = new SymbolString(new Symbol[] { varA, grammar.Expr, grammar.Addition }); 101 101 102 int hash1 = grammar. CalcHashCode(s1);103 int hash2 = grammar. CalcHashCode(s2);102 int hash1 = grammar.Hasher.CalcHashCode(s1); 103 int hash2 = grammar.Hasher.CalcHashCode(s2); 104 104 105 105 Assert.AreEqual(hash1, hash2); … … 114 114 SymbolString s2 = new SymbolString(new Symbol[] { varA, varB, grammar.Multiplication }); 115 115 116 int hash1 = grammar. CalcHashCode(s1);117 int hash2 = grammar. CalcHashCode(s2);116 int hash1 = grammar.Hasher.CalcHashCode(s1); 117 int hash2 = grammar.Hasher.CalcHashCode(s2); 118 118 119 119 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 }); 127 127 128 int hash1 = grammar. CalcHashCode(s1);129 int hash2 = grammar. CalcHashCode(s2);128 int hash1 = grammar.Hasher.CalcHashCode(s1); 129 int hash2 = grammar.Hasher.CalcHashCode(s2); 130 130 131 131 Assert.AreEqual(hash1, hash2);
Note: See TracChangeset
for help on using the changeset viewer.