Changeset 11972 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common

Timestamp:

02/09/15 09:48:30 (10 years ago)

Author:

gkronber

Message:

#2283 new experiments

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs (modified) (10 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

@@ -49 +49 @@
     }
 
-    // an expression is a list of terms 
+    // an expression is a sorted set of terms 
     // a term is an (ordered) list of factors
-    // a factor is a symbol or an inverted expression
+    // a factor is either a single symbol or an inverted expression
     // CanonicalExpression reads multiple terms (expressions) and must merge the terms in the expression (ordering and duplicates)
     // CanonicalTerm reads multiple factors and must expand factors whenever it reads a combined factor (expression) it produces an expression
@@ -83 +83 @@
     // canonical term returns either a single term (product of factors) or a set of terms 
     private Expr CanonicalTerm() {
-      var factors = new List<Expr>();
-      var invFactors = new List<Expr>();
+      var factors = new List<Factor>();
       var f = CanonicalFact();
       if (f != null) factors.Add(f);
@@ -97 +96 @@
           f = CanonicalFact();
           f.Invert();
-          if (f != null) invFactors.Add(f);
+          if (f != null) factors.Add(f);
         }
         curSy = CurSy();
       }
-
-      // cancellation
-      foreach (var invF in invFactors.ToArray()) {
-        invF.Invert();
-        if (factors.Contains(invF)) {
-          invFactors.Remove(invF);
-          factors.Remove(invF);
-          if (factors.Count == 0) factors.Add(new Expr(new Term('1')));
-        } else invF.Invert();
-      }
-
-      return ExpandFactors(factors, invFactors);
-    }
-
-    private Expr ExpandFactors(List<Expr> factors, List<Expr> invFactors) {
+      return ExpandFactors(factors);
+    }
+
+    /*
+    private List<Factor> CancelFactors(Term t) {
+      var nonInvF = t.Factors.Where(f => !f.IsInverse).ToArray();
+      var invF = t.Factors.Where(f => f.IsInverse).ToArray();
+
+      var result = new List<Factor>();
+      foreach (var f in nonInvF) {
+        if (!invF.Contains(f)) {
+          result.Add(f);
+        }
+      }
+      if (result.Count == 0) result.Add(new Factor('1'));
+      return result;
+    }
+    */
+    // canonical fact returns a factor (either a singe variable, or a set of terms)
+    private Factor CanonicalFact() {
+      var curSy = CurSy();
+      if (curSy == '!') {
+        throw new NotSupportedException();
+      } else if (curSy == '(') {
+        NewSy();
+        Expr r = CanonicalExpr(); // this is already simplified
+        if (CurSy() != ')') throw new ArgumentException();
+        NewSy();
+        return new Factor(r);
+      } else if (curSy >= 'a' && curSy <= 'z') {
+        NewSy();
+        return new Factor(curSy);
+        //       } else if (curSy >= '0' && curSy <= '9') {
+      } else if (curSy >= 'A' && curSy <= 'Z') {
+        // treat nonterminals in the same way as variables
+        NewSy();
+        return new Factor(curSy);
+
+      } else throw new ArgumentException("found symbol " + curSy);
+    }
+
+    // a list of factors (symbols, or expressions, and possibly inverses are read
+    // a lis to factors symbols or expressions and possibly inverses are produced
+    // all non-inverse expression factors are expanded
+    private Expr ExpandFactors(IEnumerable<Factor> factors) {
       // if (invFactors.Count > 0) throw new NotImplementedException();
-      Expr currentFact = factors.First(); // new Expr(simpleFactor));
-      Debug.Assert(!currentFact.Inverse); // the first factor is never an inverted factor
+      Debug.Assert(!factors.First().IsInverse); // the first factor is never an inverted factor
+
+      // each factor could be a list of terms (expression)
+
+      Expr currentFact = null;
+      var firstFactor = factors.First();
+      if (firstFactor.IsSimpleFactor) currentFact = new Expr(new Term(firstFactor));
+      else currentFact = firstFactor.Expr;
+
       foreach (var fact in factors.Skip(1)) {
-        currentFact = AllProducts(currentFact, fact);
-      }
-      foreach (var invF in invFactors) {
-        currentFact = AllInvProducts(currentFact, invF);
+        Expr curExpr = null;
+        if (fact.IsSimpleFactor || fact.IsInverse) curExpr = new Expr(new Term(fact));
+        else curExpr = fact.Expr;
+        currentFact = AllProducts(currentFact, curExpr);
       }
       return currentFact;
@@ -133 +169 @@
       var combs = from aT in aTerms
                   from bT in bTerms
-                  select new Term(aT.Symbols.Concat(bT.Symbols), aT.InvExpressions.Concat(bT.InvExpressions));
+                  let factors = CancelFactors(aT.Factors.Concat(bT.Factors))
+                  select new Term(factors);
       return new Expr(combs);
     }
 
-    private Expr AllInvProducts(Expr a, Expr b) {
-      var aTerms = a.Terms.ToArray();
-      var combs = from aT in aTerms
-                  select new Term(aT.Symbols, aT.InvExpressions.Concat(new Expr[] { b }));
-      return new Expr(combs);
-    }
-
-    // canonical fact returns a factor (either a singe variable, or a set of terms)
-    private Expr CanonicalFact() {
-      var curSy = CurSy();
-      if (curSy == '!') {
-        throw new NotSupportedException();
-      } else if (curSy == '(') {
-        NewSy();
-        Expr r = CanonicalExpr();
-        if (CurSy() != ')') throw new ArgumentException();
-        NewSy();
-        return r;
-      } else if (curSy >= 'a' && curSy <= 'z') {
-        NewSy();
-        return new Expr(new Term(curSy));
-        //       } else if (curSy >= '0' && curSy <= '9') {
-      } else if (curSy >= 'A' && curSy <= 'Z') {
-        // treat nonterminals in the same way as variables
-        NewSy();
-        return new Expr(new Term(curSy));
-
-      } else throw new ArgumentException("found symbol " + curSy);
+    private IEnumerable<Factor> CancelFactors(IEnumerable<Factor> factors) {
+      var factorsArr = factors.ToArray();
+      var results = new List<Factor>(factors);
+      foreach (var f in factorsArr) {
+        if (f.ToString() == "1") results.Remove(f);
+        if (f.IsInverse) {
+          // find matching
+          Factor match;
+          if (f.IsSimpleFactor) match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Symbol.Equals(other.Symbol));
+          else match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Expr.Equals(other.Expr));
+          if (match != null) {
+            results.Remove(match);
+            results.Remove(f);
+          }
+        }
+      }
+      if (results.Count == 0) results.Add(new Factor('1'));
+      return results;
     }
 
@@ -170 +197 @@
     // term can be merged (essentially an ordered list of factors)
     internal class Term : IComparable<Term> {
-      private readonly SortedList<char, int> factorSymbs; // factor symbol and the number of occurrences
-      private readonly SortedList<Expr, int> invExpressions;
-
-      public IEnumerable<char> Symbols {
+      private readonly SortedList<Factor, int> factors; // factor symbol and the number of occurrences
+
+      public IEnumerable<Factor> Factors {
         get {
-          return factorSymbs.SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
-        }
-      }
-
-      public IEnumerable<Expr> InvExpressions {
-        get {
-          if (invExpressions == null) return Enumerable.Empty<Expr>();
-          return invExpressions.Where(p => p.Value > 0).SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
-        }
-      }
-
-      public Term(char f) {
-        factorSymbs = new SortedList<char, int>(new FactorComparer());
-        factorSymbs.Add(f, 1);
-      }
-      public Term(IEnumerable<char> factors, IEnumerable<Expr> invFactors) {
-        factorSymbs = new SortedList<char, int>(new FactorComparer());
-        invExpressions = new SortedList<Expr, int>();
+          return factors.SelectMany(p => Enumerable.Repeat(p.Key, p.Value));
+        }
+      }
+
+      public Term(Factor f) {
+        factors = new SortedList<Factor, int>();
+        factors.Add(f, 1);
+      }
+      public Term(IEnumerable<Factor> factors) {
+        this.factors = new SortedList<Factor, int>();
         foreach (var f in factors) {
-          if (factorSymbs.ContainsKey(f)) factorSymbs[f] += 1;
-          else factorSymbs.Add(f, 1);
-        }
-
-        foreach (var invF in invFactors) {
-          if (invF.Terms.Count == 1) {
-            var t = invF.Terms.First();
-            foreach (var f in factors.Concat(new char[] { '1' })) {
-              if (t.factorSymbs.ContainsKey(f)) {
-                t.factorSymbs[f] -= 1;
-                if (t.factorSymbs[f] == 0) t.factorSymbs.Remove(f);
-              }
-            }
-          }
-          if (invExpressions.ContainsKey(invF)) invExpressions[invF] += 1;
-          else invExpressions.Add(invF, 1);
+          if (this.factors.ContainsKey(f)) this.factors[f] += 1;
+          else this.factors.Add(f, 1);
         }
       }
 
       public int CompareTo(Term other) {
-        if (ContainsNonTerminal(Symbols) && !ContainsNonTerminal(other.Symbols)) {
+        if (ContainsNonTerminal(Factors) && !ContainsNonTerminal(other.Factors)) {
           return 1;
-        } else if (!ContainsNonTerminal(Symbols) && ContainsNonTerminal(other.Symbols)) {
+        } else if (!ContainsNonTerminal(Factors) && ContainsNonTerminal(other.Factors)) {
           return -1;
         } else {
-          var countComp = Symbols.Count().CompareTo(other.Symbols.Count());
+          var countComp = Factors.Count().CompareTo(other.Factors.Count());
           if (countComp != 0) return countComp;
-          return string.Join("", Symbols).CompareTo(string.Join("", other.Symbols));
+          return string.Join("", Factors).CompareTo(string.Join("", other.Factors));
         }
       }
 
       public override string ToString() {
-        if (InvExpressions.Any())
-          return string.Join("*", Symbols) + "%" + string.Join("%", InvExpressions);
-        else {
-          return string.Join("*", Symbols);
-        }
+
+        return string.Join("*", Factors);
       }
       public override bool Equals(object obj) {
         var other = obj as Term;
         if (other == null) return false;
-        if (this.Symbols.Count() != other.Symbols.Count()) return false;
-        if (this.InvExpressions.Count() != other.InvExpressions.Count()) return false;
-        if (this.Symbols.Zip(other.Symbols, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
-        if (this.InvExpressions.Zip(other.InvExpressions, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
+        if (this.Factors.Count() != other.Factors.Count()) return false;
+        if (this.Factors.Zip(other.Factors, Tuple.Create).Any(t => t.Item1 != t.Item2)) return false;
         return true;
       }
       public override int GetHashCode() {
         var h = 31415;
-        foreach (var v in Symbols) {
+        foreach (var v in Factors) {
           h ^= v.GetHashCode();
         }
-        foreach (var v in InvExpressions) {
-          h ^= v.GetHashCode();
-        }
+        return h;
+      }
+    }
+    #endregion
+
+    #region factor
+    // factors is either a single symbol or an inverted expression
+    internal class Factor : IComparable<Factor> {
+      public bool IsSimpleFactor { get { return Expr == null; } }
+      public char Symbol { get { return symbol; } }
+      public Expr Expr { get { return expr; } }
+      public bool IsInverse { get { return inv; } }
+      private readonly char symbol = '\0';
+      private readonly Expr expr;
+      private bool inv;
+
+      public Factor(char f) {
+        this.symbol = f;
+      }
+      public Factor(Expr expr) {
+        this.expr = expr;
+      }
+
+      public void Invert() {
+        this.inv = !inv;
+      }
+
+      public int CompareTo(Factor other) {
+        // 1) single symbol factors first
+        // 2) expression factors by expression compare
+        var crit1 = ContainsNonTerminal(this).CompareTo(ContainsNonTerminal(other));
+        if (crit1 != 0) return crit1;
+
+        var crit2 = this.IsInverse.CompareTo(other.IsInverse);
+        if (crit2 != 0) return crit2;
+
+        var crit3 = this.IsSimpleFactor.CompareTo(other.IsSimpleFactor);
+        if (crit3 != 0) return crit3;
+
+        // both are simple or expressions
+        if (IsSimpleFactor) return this.symbol.CompareTo(other.symbol);
+        else return this.Expr.CompareTo(other.Expr);
+      }
+
+      public override string ToString() {
+        var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
+        if (IsInverse) {
+          return "1/" + s;
+        } else return s;
+      }
+      public override bool Equals(object obj) {
+        var other = obj as Factor;
+        if (other == null) return false;
+        if (IsInverse != other.IsInverse) return false;
+        if (this.symbol != other.symbol) return false;
+        if (this.Expr != other.Expr) return false;
+        return true;
+      }
+      public override int GetHashCode() {
+        var h = 31415;
+        h ^= symbol.GetHashCode();
+        if (Expr != null) h ^= Expr.GetHashCode();
         return h;
       }
@@ -258 +316 @@
     internal class Expr : IComparable<Expr> {
       public readonly SortedSet<Term> Terms; // only set for Kind == Expr 
-      public bool Inverse;
+      //public bool Inverse;
       public Expr(Term t) {
         Terms = new SortedSet<Term>();
@@ -286 +344 @@
 
       public override string ToString() {
-        if (Inverse && Terms.Count > 1)
-          return "(" + string.Join("+", Terms) + ")";
-        else if (Inverse && Terms.Count == 1) {
-          return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
-        } else
-          return string.Join("+", Terms);
+        // if (Inverse && Terms.Count > 1)
+        //   return "(" + string.Join("+", Terms) + ")";
+        // else if (Inverse && Terms.Count == 1) {
+        //   return Terms.First().ToString().Replace("%", "#").Replace("*", "%").Replace("#", "*");
+        // } else
+        return string.Join("+", Terms);
       }
       public override bool Equals(object obj) {
         var other = obj as Expr;
         if (other == null) return false;
-        if (this.Inverse != other.Inverse) return false;
+        //if (this.Inverse != other.Inverse) return false;
         if (this.Terms.Count() != other.Terms.Count()) return false;
         return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
@@ -308 +366 @@
         return h;
       }
-
-      public void Invert() {
-        this.Inverse = !Inverse;
-      }
     }
     #endregion
@@ -317 +371 @@
       return symb >= 'A' && symb <= 'Z';
     }
-    internal static bool ContainsNonTerminal(IEnumerable<char> symbs) {
-      return symbs.Any(IsNonTerminal);
-    }
+    internal static bool ContainsNonTerminal(IEnumerable<Factor> factors) {
+      return factors.Any(ContainsNonTerminal);
+    }
+    internal static bool ContainsNonTerminal(Factor f) {
+      if (f.Expr == null) return IsNonTerminal(f.Symbol);
+      else return ContainsNonTerminal(f.Expr);
+    }
+
+    private static bool ContainsNonTerminal(Expr expr) {
+      return expr.Terms.Any(ContainsNonTerminal);
+    }
+
+    private static bool ContainsNonTerminal(Term term) {
+      return ContainsNonTerminal(term.Factors);
+    }
+
+
+    /*
 
     internal class FactorComparer : IComparer<char> {
@@ -333 +402 @@
         }
       }
-    }
+    }*/
   }
 }