Changeset 11730 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs

Timestamp:

01/02/15 16:08:21 (9 years ago)

Author:

gkronber

Message:

#2283: several major extensions for grammatical optimization

File:

• branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs (modified) (8 diffs)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs

@@ -19 +19 @@
   public class Grammar : IGrammar {
 
-    private readonly Dictionary<char, List<string>> rules;
+    private readonly Dictionary<char, List<Sequence>> rules;
     private readonly HashSet<char> terminalSymbols;
     private readonly char sentenceSymbol;
     private readonly HashSet<char> nonTerminalSymbols;
-    private readonly Dictionary<string, int> maxPhraseLength = new Dictionary<string, int>();
-    private readonly Dictionary<string, int> minPhraseLength = new Dictionary<string, int>();
+    private readonly Dictionary<Sequence, int> maxPhraseLength = new Dictionary<Sequence, int>();
+    private readonly Dictionary<Sequence, int> minPhraseLength = new Dictionary<Sequence, int>();
 
     public char SentenceSymbol { get { return sentenceSymbol; } }
@@ -33 +33 @@
     // cloning ctor
     public Grammar(Grammar orig) {
-      this.rules = new Dictionary<char, List<string>>(orig.rules);
+      this.rules = new Dictionary<char, List<Sequence>>();
+      foreach (var r in orig.rules)
+        this.rules.Add(r.Key, new List<Sequence>(r.Value.Select(v => new Sequence(v)))); // clone sequences
       this.terminalSymbols = new HashSet<char>(orig.terminalSymbols);
       this.sentenceSymbol = orig.sentenceSymbol;
       this.nonTerminalSymbols = new HashSet<char>(orig.nonTerminalSymbols);
-      this.maxPhraseLength = new Dictionary<string, int>(orig.maxPhraseLength);
-      this.minPhraseLength = new Dictionary<string, int>(orig.minPhraseLength);
+      this.maxPhraseLength = new Dictionary<Sequence, int>();
+      foreach (var p in orig.maxPhraseLength) this.maxPhraseLength.Add(new Sequence(p.Key), p.Value);
+      this.minPhraseLength = new Dictionary<Sequence, int>();
+      foreach (var p in orig.minPhraseLength) this.minPhraseLength.Add(new Sequence(p.Key), p.Value);
     }
 
@@ -47 +51 @@
       this.terminalSymbols = new HashSet<char>(terminalSymbols);
       this.nonTerminalSymbols = new HashSet<char>(nonTerminalSymbols);
-      this.rules = new Dictionary<char, List<string>>();
+      this.rules = new Dictionary<char, List<Sequence>>();
       foreach (var r in rules) {
-        if (!this.rules.ContainsKey(r.Item1)) this.rules.Add(r.Item1, new List<string>());
-        this.rules[r.Item1].Add(r.Item2); // here we store an array of symbols for a phase
+        if (!this.rules.ContainsKey(r.Item1)) this.rules.Add(r.Item1, new List<Sequence>());
+        this.rules[r.Item1].Add(new Sequence(r.Item2)); // here we store an array of symbols for a phase
       }
 
@@ -86 +90 @@
           max = Math.Max(max, maxPhraseLength[alt]);
         }
-        minPhraseLength[nt.ToString()] = min;
-        maxPhraseLength[nt.ToString()] = max;
-      }
-    }
-
-
-    public IEnumerable<string> GetAlternatives(char nt) {
+        minPhraseLength[new Sequence(nt)] = min;
+        maxPhraseLength[new Sequence(nt)] = max;
+      }
+    }
+
+
+    public IEnumerable<Sequence> GetAlternatives(char nt) {
       return rules[nt];
     }
 
-    public IEnumerable<string> GetTerminalAlternatives(char nt) {
+    public IEnumerable<Sequence> GetTerminalAlternatives(char nt) {
       return GetAlternatives(nt).Where(alt => alt.All(IsTerminal));
     }
 
-    public IEnumerable<string> GetNonTerminalAlternatives(char nt) {
+    public IEnumerable<Sequence> GetNonTerminalAlternatives(char nt) {
       return GetAlternatives(nt).Where(alt => alt.Any(IsNonTerminal));
     }
 
     // caches for this are build in construction of object
-    public int MinPhraseLength(string phrase) {
+    public int MinPhraseLength(Sequence phrase) {
       int l;
       if (minPhraseLength.TryGetValue(phrase, out l)) return l;
@@ -125 +129 @@
 
     // caches for this are build in construction of object
-    public int MaxPhraseLength(string phrase) {
+    public int MaxPhraseLength(Sequence phrase) {
       int l;
       if (maxPhraseLength.TryGetValue(phrase, out l)) return l;
@@ -152 +156 @@
     }
 
-    public string CompleteSentenceRandomly(Random random, string phrase, int maxLen) {
+    public Sequence CompleteSentenceRandomly(Random random, Sequence phrase, int maxLen) {
       if (phrase.Length > maxLen) throw new ArgumentException();
       if (MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
-      bool done = phrase.All(IsTerminal); // terminal phrase means we are done
+      bool done = phrase.IsTerminal; // terminal phrase means we are done
       while (!done) {
-        int ntIdx; char nt;
-        FindFirstNonTerminal(this, phrase, out nt, out ntIdx);
+        char nt = phrase.FirstNonTerminal;
 
         int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
@@ -168 +171 @@
         // replace nt with random alternative
         var selectedAlt = alts.SelectRandom(random);
-        phrase = phrase.Remove(ntIdx, 1);
-        phrase = phrase.Insert(ntIdx, selectedAlt);
+        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
 
         done = phrase.All(IsTerminal); // terminal phrase means we are done
       }
       return phrase;
-    }
-
-    public static void FindFirstNonTerminal(IGrammar g, string phrase, out char nt, out int ntIdx) {
-      ntIdx = 0;
-      while (ntIdx < phrase.Length && g.IsTerminal(phrase[ntIdx])) ntIdx++;
-      if (ntIdx >= phrase.Length) {
-        ntIdx = -1;
-        nt = '\0';
-      } else {
-        nt = phrase[ntIdx];
-      }
     }
 
@@ -262 +253 @@
       foreach (var r in rules) {
         foreach (var alt in r.Value) {
-          var phrase = string.Join(" ", alt);
-          sb.AppendFormat("  {0} -> {1} (min: {2}, max {3})", r.Key, phrase, MinPhraseLength(phrase), MaxPhraseLength(phrase))
+          sb.AppendFormat("  {0} -> {1} (min: {2}, max {3})", r.Key, alt, MinPhraseLength(alt), MaxPhraseLength(alt))
             .AppendLine();
         }