Changeset 15794

Timestamp:

02/20/18 15:54:21 (6 years ago)

Author:

lkammere

Message:

#2886: Add "full" inverse production, cancellation of factors by their inverse and resolution of compound division.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (9 diffs)
• Test/GrammarEnumerationTest.cs (modified) (1 diff)

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

@@ -24 +24 @@
     public NonterminalSymbol SinFactor;
 
-    public NonterminalSymbol InvExpr;
-    public NonterminalSymbol InvTerm;
-    public NonterminalSymbol InvFactor;
-
     public NonterminalSymbol SimpleExpr;
     public NonterminalSymbol SimpleTerm;
@@ -75 +71 @@
       SinFactor = new NonterminalSymbol("SinFactor");
 
-      InvExpr = new NonterminalSymbol("InvExpr");
-      InvTerm = new NonterminalSymbol("InvTerm");
-      InvFactor = new NonterminalSymbol("InvFactor");
-
       SimpleExpr = new NonterminalSymbol("SimpleExpr");
       SimpleTerm = new NonterminalSymbol("SimpleTerm");
@@ -95 +87 @@
 
       #region Production rules
-      // order of production is important, since they are accessed via index
-      // in memoization.
       StartSymbol = Expr;
 
@@ -103 +93 @@
 
       Term.AddProduction(Factor, Term, Multiplication);
+      Term.AddProduction(Expr, Inv, Term, Multiplication);
       Term.AddProduction(Factor);
-      Term.AddProduction(InvExpr, Inv);
 
       Factor.AddProduction(Var);
@@ -120 +110 @@
       SimpleTerm.AddProduction(Var, SimpleTerm, Multiplication);
       SimpleTerm.AddProduction(Var);
-  
-      InvExpr.AddProduction(InvTerm, InvExpr, Addition);
-      InvExpr.AddProduction(InvTerm);
-
-      InvTerm.AddProduction(InvFactor, InvTerm, Multiplication);
-      InvTerm.AddProduction(InvFactor);
-
-      InvFactor.AddProduction(Var);
-      InvFactor.AddProduction(LogFactor);
-      InvFactor.AddProduction(SinFactor);
       #endregion
 
@@ -157 +137 @@
 
       Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
+      CancelOutCompoundInverse(parseStack);
 
       Symbol peek = parseStack.Peek();
@@ -164 +145 @@
 
     private string[] GetSubtreeHashes(Stack<Symbol> parseStack) {
+      CancelOutCompoundInverse(parseStack);
       Symbol currentSymbol = parseStack.Pop();
 
@@ -211 +193 @@
 
         // Cancel out inverse factors.
-        var inversChildHashes = childHashes
-          .Select(ch => AggregateHashes(Inv, ch.ToEnumerable()))
-          .ToList();
-
-        return childHashes // If this factor cancels out another one, then remove BOTH. Otherwise, keep the factor.
-          .Where(ch => !inversChildHashes.Remove(ch))
+        bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray();
+
+        for (int i = 0; i < isFactorRemaining.Length; i++) {
+          if (!isFactorRemaining[i]) continue;
+          if (isFactorRemaining.Count(b => b) <= 2) break; // Until we have constants, we can't cancel out all terms.
+
+          var currFactor = childHashes[i];
+          var invFactor = AggregateHashes(Inv, currFactor.ToEnumerable());
+
+          int indexOfInv = childHashes.IndexOf(invFactor);
+          if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) {
+            isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false;
+          }
+        }
+        return Enumerable
+          .Range(0, isFactorRemaining.Length)
+          .Where(i => isFactorRemaining[i])
+          .Select(i => childHashes[i])
           .ToArray();
       }
@@ -241 +235 @@
 
       return "[" + hashesArray.Aggregate(operatorSym.StringRepresentation, (result, ti) => result + " ° " + ti) + "]";
+    }
+
+    private void CancelOutCompoundInverse(Stack<Symbol> parseStack) {
+      // Resolve compound divisions
+      int compoundFractionsCount = 0;
+
+      while (ReferenceEquals(parseStack.Peek(), Inv)) {
+        compoundFractionsCount++;
+        parseStack.Pop();
+      }
+
+      if (compoundFractionsCount % 2 != 0) {
+        // Compound division are reduced to a single division.
+        parseStack.Push(Inv);
+      } // else: compound divisions fully cancel out each other.
     }
     #endregion

branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

@@ -179 +179 @@
     [TestProperty("Goal", "structure search")]
     public void NoConstants_Inverse() {
-      // sin(x) / (log(x)*x + x)
+      // x / (log(x)*x + x)
       alg.MaxTreeSize = 12;