source: branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs @ 11730

Last change on this file since 11730 was 11730, checked in by gkronber, 5 years ago

#2283: several major extensions for grammatical optimization

File size: 11.0 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Data;
4using System.Diagnostics;
5using System.IO;
6using System.Linq;
7using System.Text;
8using System.Text.RegularExpressions;
9using System.Xml.Linq;
10using HeuristicLab.Common;
11
12namespace HeuristicLab.Problems.GrammaticalOptimization {
13
14  // phrases and symbols are both strings
15  // spaces are used to separate symbols in phases
16  // terminal and non-terminal symbols must not contain white-space
17  // white-spaces are not counted when determining the length of a sentence, only the number of terminal symbols is relevant
18
19  public class Grammar : IGrammar {
20
21    private readonly Dictionary<char, List<Sequence>> rules;
22    private readonly HashSet<char> terminalSymbols;
23    private readonly char sentenceSymbol;
24    private readonly HashSet<char> nonTerminalSymbols;
25    private readonly Dictionary<Sequence, int> maxPhraseLength = new Dictionary<Sequence, int>();
26    private readonly Dictionary<Sequence, int> minPhraseLength = new Dictionary<Sequence, int>();
27
28    public char SentenceSymbol { get { return sentenceSymbol; } }
29    public IEnumerable<char> NonTerminalSymbols { get { return nonTerminalSymbols; } }
30    public IEnumerable<char> TerminalSymbols { get { return terminalSymbols; } }
31    public IEnumerable<char> Symbols { get { return nonTerminalSymbols.Concat(terminalSymbols); } } // ctor guarantees that intersection is empty
32
33    // cloning ctor
34    public Grammar(Grammar orig) {
35      this.rules = new Dictionary<char, List<Sequence>>();
36      foreach (var r in orig.rules)
37        this.rules.Add(r.Key, new List<Sequence>(r.Value.Select(v => new Sequence(v)))); // clone sequences
38      this.terminalSymbols = new HashSet<char>(orig.terminalSymbols);
39      this.sentenceSymbol = orig.sentenceSymbol;
40      this.nonTerminalSymbols = new HashSet<char>(orig.nonTerminalSymbols);
41      this.maxPhraseLength = new Dictionary<Sequence, int>();
42      foreach (var p in orig.maxPhraseLength) this.maxPhraseLength.Add(new Sequence(p.Key), p.Value);
43      this.minPhraseLength = new Dictionary<Sequence, int>();
44      foreach (var p in orig.minPhraseLength) this.minPhraseLength.Add(new Sequence(p.Key), p.Value);
45    }
46
47    public Grammar(string grammar) : this((Grammar)FromString(grammar)) { }
48
49    public Grammar(char sentenceSymbol, IEnumerable<char> terminalSymbols, IEnumerable<char> nonTerminalSymbols, IEnumerable<Tuple<char, string>> rules) {
50      this.sentenceSymbol = sentenceSymbol;
51      this.terminalSymbols = new HashSet<char>(terminalSymbols);
52      this.nonTerminalSymbols = new HashSet<char>(nonTerminalSymbols);
53      this.rules = new Dictionary<char, List<Sequence>>();
54      foreach (var r in rules) {
55        if (!this.rules.ContainsKey(r.Item1)) this.rules.Add(r.Item1, new List<Sequence>());
56        this.rules[r.Item1].Add(new Sequence(r.Item2)); // here we store an array of symbols for a phase
57      }
58
59      CheckValidity();
60      CalculatePhaseLengthBounds();
61    }
62
63    private void CheckValidity() {
64      // check validity of parameters
65      if (!nonTerminalSymbols.Contains(sentenceSymbol) || // sentence symbol must be a non-terminal
66          nonTerminalSymbols.Any(c => c < 'A' || c > 'Z') || // nonterminal symbols \in 'A' .. 'Z'
67          terminalSymbols.Intersect(nonTerminalSymbols).Any() || // no overlap between non-terminals and terminal
68          rules.Keys.Intersect(nonTerminalSymbols).Count() < nonTerminalSymbols.Count ||
69          nonTerminalSymbols.Any(nt => !rules.ContainsKey(nt)) || // each nt must have at least one rule
70          rules.Values.Any(alternatives => !alternatives.Any()) || // no eps alternatives
71          rules.Any(rule => rule.Value.Any(alternative => alternative.Length == 1 && alternative[0] == rule.Key))
72        // no infinite direct recursions
73        ) {
74        throw new ArgumentException();
75      }
76    }
77
78    private void CalculatePhaseLengthBounds() {
79      minPhraseLength.Clear();
80      maxPhraseLength.Clear();
81      // cache phrase lengths
82      foreach (var nt in nonTerminalSymbols) {
83        var min = int.MaxValue;
84        var max = int.MinValue;
85        foreach (var alt in rules[nt].OrderBy(alt => alt.Length)) {
86          minPhraseLength[alt] = MinPhraseLength(alt);
87          maxPhraseLength[alt] = MaxPhraseLength(alt);
88
89          min = Math.Min(min, minPhraseLength[alt]);
90          max = Math.Max(max, maxPhraseLength[alt]);
91        }
92        minPhraseLength[new Sequence(nt)] = min;
93        maxPhraseLength[new Sequence(nt)] = max;
94      }
95    }
96
97
98    public IEnumerable<Sequence> GetAlternatives(char nt) {
99      return rules[nt];
100    }
101
102    public IEnumerable<Sequence> GetTerminalAlternatives(char nt) {
103      return GetAlternatives(nt).Where(alt => alt.All(IsTerminal));
104    }
105
106    public IEnumerable<Sequence> GetNonTerminalAlternatives(char nt) {
107      return GetAlternatives(nt).Where(alt => alt.Any(IsNonTerminal));
108    }
109
110    // caches for this are build in construction of object
111    public int MinPhraseLength(Sequence phrase) {
112      int l;
113      if (minPhraseLength.TryGetValue(phrase, out l)) return l;
114      l = 0;
115      minPhraseLength[phrase] = short.MaxValue; // mark
116
117      foreach (var symb in phrase) {
118        if (IsNonTerminal(symb)) {
119          l += MinSymbolLength(symb);
120        } else {
121          l++;
122        }
123      }
124
125      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
126      minPhraseLength[phrase] = l; // update
127      return l;
128    }
129
130    // caches for this are build in construction of object
131    public int MaxPhraseLength(Sequence phrase) {
132      int l;
133      if (maxPhraseLength.TryGetValue(phrase, out l)) return l;
134      l = 0;
135      maxPhraseLength[phrase] = short.MaxValue; // mark
136
137      foreach (var symb in phrase) {
138        if (IsNonTerminal(symb)) {
139          l += MaxSymbolLength(symb);
140        } else {
141          l++;
142        }
143      }
144      l = Math.Min(short.MaxValue, l); // maximal allowed value is short.MaxValue
145      maxPhraseLength[phrase] = l; // update
146      return l;
147    }
148
149    private int MinSymbolLength(char nt) {
150      if (IsTerminal(nt)) return 1;
151      else return Math.Min(short.MaxValue, rules[nt].Min(alt => MinPhraseLength(alt))); // maximal allowed value is short.MaxValue
152    }
153    private int MaxSymbolLength(char nt) {
154      if (IsTerminal(nt)) return 1;
155      else return Math.Min(short.MaxValue, rules[nt].Max(alt => MaxPhraseLength(alt))); // maximal allowed value is short.MaxValue
156    }
157
158    public Sequence CompleteSentenceRandomly(Random random, Sequence phrase, int maxLen) {
159      if (phrase.Length > maxLen) throw new ArgumentException();
160      if (MinPhraseLength(phrase) > maxLen) throw new ArgumentException();
161      bool done = phrase.IsTerminal; // terminal phrase means we are done
162      while (!done) {
163        char nt = phrase.FirstNonTerminal;
164
165        int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2
166        Debug.Assert(maxLenOfReplacement > 0);
167
168        var alts = GetAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
169        Debug.Assert(alts.Any());
170
171        // replace nt with random alternative
172        var selectedAlt = alts.SelectRandom(random);
173        phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt);
174
175        done = phrase.All(IsTerminal); // terminal phrase means we are done
176      }
177      return phrase;
178    }
179
180    public bool IsTerminal(char symbol) {
181      return terminalSymbols.Contains(symbol);
182    }
183
184    public bool IsNonTerminal(char symbol) {
185      return nonTerminalSymbols.Contains(symbol);
186    }
187
188    private static readonly string symbRegex = @"(?<symb>[^\s\|\.])";
189    private static readonly string altRegex = @"(?<alt>[^\s\|\.]+)";
190    private static readonly string altListRegex = altRegex + @"(\s*\|\s*" + altRegex + @")*";
191    // private static readonly string terminalClassRegex = @"[^\s\|\.]\s*\.\.\s*[^\s\|\.]";
192    private static readonly string terminalClassRegex = symbRegex + @"\s*\.\.\s*" + symbRegex + @"\s*";
193
194    private static readonly Regex sentenceSymbRegex = new Regex(@"\s*G\(" + symbRegex + @"\):\s*$", RegexOptions.ExplicitCapture);
195    private static readonly Regex ruleRegex = new Regex(@"\s*" + symbRegex + @"\s*->\s*(" + altListRegex + "|" + terminalClassRegex + @")\s*$", RegexOptions.ExplicitCapture);
196
197
198    // supports only meta-symbol for alternatives (syntax of formal grammars)
199    // epsilon-alternatives are not supported
200    public static IGrammar FromString(string grammar) {
201      char sentenceSymbol;
202      var nonTerminals = new List<char>();
203      var terminals = new List<char>();
204      var rules = new List<Tuple<char, string>>();
205
206      using (var reader = new StringReader(grammar)) {
207        var line = reader.ReadLine();
208        while (string.IsNullOrWhiteSpace(line)) line = reader.ReadLine();
209        // first line contains "G(...):"
210        var match = sentenceSymbRegex.Match(line);
211        if (!match.Success) throw new ArgumentException();
212        sentenceSymbol = match.Groups["symb"].Value[0]; // only a single symbol is in the capture group
213
214        line = reader.ReadLine();
215        while (!string.IsNullOrWhiteSpace(line)) {
216          match = ruleRegex.Match(line);
217          if (match.Length != line.Length) throw new ArgumentException();
218          var nt = match.Groups["symb"].Captures[0].Value[0];
219          if (!nonTerminals.Contains(nt)) nonTerminals.Add(nt);
220
221          // contains alternatives?
222          if (match.Groups["alt"].Captures.Count > 0) {
223            foreach (var m in match.Groups["alt"].Captures) {
224              rules.Add(Tuple.Create(nt, m.ToString()));
225            }
226          } else if (match.Groups["symb"].Captures.Count == 3) {
227            // contains terminal range
228            var fromSymb = match.Groups["symb"].Captures[1].Value[0];
229            var toSymb = match.Groups["symb"].Captures[2].Value[0];
230            if (fromSymb > toSymb) throw new ArgumentException("left symbol is larger than right symbol in range");
231
232            for (byte b = Convert.ToByte(fromSymb); b <= Convert.ToByte(toSymb); b++) {
233              rules.Add(Tuple.Create(nt, Convert.ToChar(b).ToString()));
234            }
235          }
236
237          line = reader.ReadLine();
238        }
239      }
240
241      foreach (var r in rules) {
242        foreach (var s in r.Item2) {
243          if (!nonTerminals.Contains(s) && !terminals.Contains(s)) terminals.Add(s);
244        }
245      }
246      return new Grammar(sentenceSymbol, terminals, nonTerminals, rules);
247    }
248
249    public override string ToString() {
250      // for debugging
251      var sb = new StringBuilder();
252      sb.AppendFormat("G({0}):", sentenceSymbol).AppendLine();
253      foreach (var r in rules) {
254        foreach (var alt in r.Value) {
255          sb.AppendFormat("  {0} -> {1} (min: {2}, max {3})", r.Key, alt, MinPhraseLength(alt), MaxPhraseLength(alt))
256            .AppendLine();
257        }
258      }
259      return sb.ToString();
260    }
261  }
262}
Note: See TracBrowser for help on using the repository browser.