##// END OF EJS Templates
implab » ImplabNet
RSS
sync
cin -
r167:96681e9d0cea ref20160224
parent child
Show More
Show file before | Show file after | Hide comments
@@ -1,251 +1,251
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Linq;
5 5
6 6 namespace Implab.Automaton {
7 public class DFATransitionTable<TTag> : IDFATableBuilder {
7 public class DFATransitionTable : IDFATableBuilder {
8 8 DFAStateDescriptior[] m_dfaTable;
9 9
10 10 int m_stateCount;
11 11 int m_symbolCount;
12 12 int m_initialState;
13 13
14 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
14 readonly HashSet<int> m_finalStates = new HashSet<int>();
15 15 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
16 16
17 17
18 18 #region IDFADefinition implementation
19 19
20 20 public DFAStateDescriptior[] GetTransitionTable() {
21 21 if (m_dfaTable == null) {
22 22 if (m_stateCount <= 0)
23 23 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
24 24 if (m_symbolCount <= 0)
25 25 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
26 26
27 27 m_dfaTable = ConstructTransitionTable();
28 28 }
29 29 return m_dfaTable;
30 30 }
31 31
32 32 public bool IsFinalState(int s) {
33 33 Safe.ArgumentInRange(s, 0, m_stateCount, "s");
34 34
35 return m_finalStates.ContainsKey(s);
35 return m_dfaTable != null ? m_dfaTable[s].final : m_finalStates.Contains(s);
36 36 }
37 37
38 public IEnumerable<KeyValuePair<int,TTag[]>> FinalStates {
38 public IEnumerable<int> FinalStates {
39 39 get {
40 40 return m_finalStates;
41 41 }
42 42 }
43 43
44 44 public int StateCount {
45 45 get { return m_stateCount; }
46 46 }
47 47
48 48 public int AlphabetSize {
49 49 get { return m_symbolCount; }
50 50 }
51 51
52 52 public int InitialState {
53 53 get { return m_initialState; }
54 54 }
55 55
56 56 #endregion
57 57
58 protected virtual DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
59 var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount];
58 protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
59 var dfaTable = new DFAStateDescriptior[m_stateCount];
60 60
61 61 foreach (var pair in m_finalStates) {
62 62 var idx = pair.Key;
63 63
64 64 dfaTable[idx].final = true;
65 65 dfaTable[idx].tag = pair.Value;
66 66 }
67 67
68 68 foreach (var t in m_transitions) {
69 69 if (dfaTable[t.s1].transitions == null) {
70 70 dfaTable[t.s1].transitions = new int[m_symbolCount];
71 71 for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++)
72 72 dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
73 73 }
74 74
75 75 dfaTable[t.s1].transitions[t.edge] = t.s2;
76 76 }
77 77 }
78 78
79 79 #region IDFADefinitionBuilder
80 80
81 81 public void DefineTransition(int s1, int s2, int symbol) {
82 82 if (m_dfaTable != null)
83 83 throw new InvalidOperationException("The transition table is already built");
84 84
85 85 Safe.ArgumentAssert(s1 > 0, "s1");
86 86 Safe.ArgumentAssert(s2 > 0, "s2");
87 87 Safe.ArgumentAssert(symbol >= 0, "symbol");
88 88
89 89 m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1);
90 90 m_symbolCount = Math.Max(m_symbolCount, symbol + 1);
91 91
92 92 m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
93 93 }
94 94
95 95 public void MarkFinalState(int state, params TTag[] tags) {
96 96 if (m_dfaTable != null)
97 97 throw new InvalidOperationException("The transition table is already built");
98 98
99 99 m_finalStates[state] = tags;
100 100 }
101 101
102 102 public void SetInitialState(int s) {
103 103 Safe.ArgumentAssert(s >= 0, "s");
104 104 m_initialState = s;
105 105 }
106 106
107 107
108 108 #endregion
109 109
110 110 protected void Optimize<TInput, TState>(
111 111 IDFATableBuilder<TTag> optimalDFA,
112 112 IAlphabet<TInput> inputAlphabet,
113 113 IAlphabetBuilder<TInput> optimalInputAlphabet,
114 114 IAlphabet<TState> stateAlphabet,
115 115 IAlphabetBuilder<TState> optimalStateAlphabet
116 116 ) {
117 117 Safe.ArgumentNotNull(optimalDFA, "dfa");
118 118 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
119 119 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
120 120 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
121 121 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
122 122
123 123 if (inputAlphabet.Count != m_symbolCount)
124 124 throw new InvalidOperationException("The input symbols aphabet mismatch");
125 125 if (stateAlphabet.Count != m_stateCount)
126 126 throw new InvalidOperationException("The states alphabet mismatch");
127 127
128 128 var setComparer = new CustomEqualityComparer<HashSet<int>>(
129 129 (x, y) => x.SetEquals(y),
130 130 s => s.Sum(x => x.GetHashCode())
131 131 );
132 132
133 133 var arrayComparer = new CustomEqualityComparer<TTag[]>(
134 134 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
135 135 a => a.Sum(x => x.GetHashCode())
136 136 );
137 137
138 138 var optimalStates = new HashSet<HashSet<int>>(setComparer);
139 139 var queue = new HashSet<HashSet<int>>(setComparer);
140 140
141 141 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΊΠΎΠ½Π΅Ρ‡Π½Ρ‹Π΅ состояния, сгруппированныС ΠΏΠΎ ΠΌΠ°Ρ€ΠΊΠ΅Ρ€Π°ΠΌ
142 142 optimalStates.UnionWith(
143 143 m_finalStates
144 144 .GroupBy(pair => pair.Value, arrayComparer)
145 145 .Select(
146 146 g => new HashSet<int>(
147 147 g.Select( pair => pair.Key)
148 148 )
149 149 )
150 150 );
151 151
152 152 var state = new HashSet<int>(
153 153 Enumerable
154 154 .Range(0, m_stateCount - 1)
155 155 .Where(i => !m_finalStates.ContainsKey(i))
156 156 );
157 157 optimalStates.Add(state);
158 158 queue.Add(state);
159 159
160 160 var rmap = m_transitions
161 161 .GroupBy(t => t.s2)
162 162 .ToLookup(
163 163 g => g.Key, // s2
164 164 g => g.ToLookup(t => t.edge, t => t.s1)
165 165 );
166 166
167 167 while (queue.Count > 0) {
168 168 var stateA = queue.First();
169 169 queue.Remove(stateA);
170 170
171 171 for (int c = 0; c < m_symbolCount; c++) {
172 172 var stateX = new HashSet<int>();
173 173 foreach(var a in stateA)
174 174 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
175 175
176 176 foreach (var stateY in optimalStates.ToArray()) {
177 177 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
178 178 var stateR1 = new HashSet<int>(stateY);
179 179 var stateR2 = new HashSet<int>(stateY);
180 180
181 181 stateR1.IntersectWith(stateX);
182 182 stateR2.ExceptWith(stateX);
183 183
184 184 optimalStates.Remove(stateY);
185 185 optimalStates.Add(stateR1);
186 186 optimalStates.Add(stateR2);
187 187
188 188 if (queue.Contains(stateY)) {
189 189 queue.Remove(stateY);
190 190 queue.Add(stateR1);
191 191 queue.Add(stateR2);
192 192 } else {
193 193 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
194 194 }
195 195 }
196 196 }
197 197 }
198 198 }
199 199
200 200 // ΠΊΠ°Ρ€Ρ‚Π° получСния ΠΎΠΏΡ‚ΠΈΠΌΠ°Π»ΡŒΠ½ΠΎΠ³ΠΎ состояния ΠΏΠΎ ΡΠΎΠΎΡ‚Π²Π΅ΡΡ‚Π²ΡƒΡŽΡ‰Π΅ΠΌΡƒ Π΅ΠΌΡƒ простому ΡΠΎΡΡ‚ΠΎΡΠ½ΠΈΡŽ
201 201 var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
202 202
203 203 // ΠΏΠΎΠ»ΡƒΡ‡Π°Π΅ΠΌ ΠΌΠΈΠ½ΠΈΠΌΠ°Π»ΡŒΠ½Ρ‹ΠΉ Π°Π»Ρ„Π°Π²ΠΈΡ‚
204 204 // Π²Ρ…ΠΎΠ΄Π½Ρ‹Π΅ символы Π½Π΅ Ρ€Π°Π·Π»ΠΈΡ‡ΠΈΠΌΡ‹, Ссли Move(s,a1) == Move(s,a2)
205 205 var optimalAlphabet = m_transitions
206 206 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
207 207
208 208 var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
209 209
210 210 var optimalTags = m_finalStates
211 211 .GroupBy(pair => statesMap[pair.Key])
212 212 .ToDictionary(
213 213 g => g.Key,
214 214 g => g.SelectMany(pair => pair.Value).ToArray()
215 215 );
216 216
217 217 // построСниС Π°Π²Ρ‚ΠΎΠΌΠ°Ρ‚Π°
218 218 optimalDFA.SetInitialState(statesMap[m_initialState]);
219 219
220 220 foreach (var pair in optimalTags)
221 221 optimalDFA.MarkFinalState(pair.Key, pair.Value);
222 222
223 223 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
224 224 optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
225 225
226 226 }
227 227
228 228 protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
229 229 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
230 230 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
231 231
232 232 var inputMap = inputAlphabet.CreateReverseMap();
233 233 var stateMap = stateAlphabet.CreateReverseMap();
234 234
235 235 for (int i = 0; i < inputMap.Length; i++)
236 236 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
237 237
238 238
239 239 foreach(var t in m_transitions)
240 240 Console.WriteLine(
241 241 "[{0}] -{{{1}}}-> [{2}]{3}",
242 242 stateMap[t.s1],
243 243 String.Join(",", inputMap[t.edge]),
244 244 stateMap[t.s2],
245 245 m_finalStates.ContainsKey(t.s2) ? "$" : ""
246 246 );
247 247
248 248 }
249 249
250 250 }
251 251 }
Show file before | Show file after | Hide comments
@@ -1,24 +1,16
1 1 using System;
2 using System.Collections.Generic;
2 3
3 4 namespace Implab.Automaton {
4 public interface IDFATableBuilder : IDFATable {
5 public interface IDFATableBuilder : IDFATable, ICollection<AutomatonTransition> {
5 6 /// <summary>
6 7 /// Marks the state as final.
7 8 /// </summary>
8 9 /// <param name="state">State.</param>
9 10 void MarkFinalState(int state);
10 11
11 /// <summary>
12 /// Defines the transition from <paramref name="s1"/> to
13 /// <paramref name="s2"/> with input <paramref name="symbol"/>.
14 /// </summary>
15 /// <param name="s1">S1.</param>
16 /// <param name="s2">S2.</param>
17 /// <param name="symbol">Symbol.</param>
18 void DefineTransition(int s1, int s2, int symbol);
19
20 12 void SetInitialState(int s);
21 13
22 14 }
23 15 }
24 16
Show file before | Show file after | Hide comments
@@ -1,103 +1,108
1 1 using Implab;
2 2 using System;
3 3 using System.Collections.Generic;
4 4 using System.Diagnostics;
5 5 using System.Linq;
6 6
7 7 namespace Implab.Automaton {
8 8 /// <summary>
9 9 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
10 10 /// </summary>
11 /// <remarks>
12 /// Indexed alphabets are usefull in bulting efficient translations from source alphabet
13 /// to the input alphabet of the automaton. It's assumed that the index to the symbol match
14 /// is well known and documented.
15 /// </remarks>
11 16 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
12 17 int m_nextId = 1;
13 18 readonly int[] m_map;
14 19
15 20 public int Count {
16 21 get { return m_nextId; }
17 22 }
18 23
19 24 protected IndexedAlphabetBase(int mapSize) {
20 25 m_map = new int[mapSize];
21 26 }
22 27
23 28 protected IndexedAlphabetBase(int[] map) {
24 29 Debug.Assert(map != null);
25 30
26 31 m_map = map;
27 32 m_nextId = map.Max() + 1;
28 33 }
29 34
30 35 public int DefineSymbol(T symbol) {
31 36 var index = GetSymbolIndex(symbol);
32 37 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
33 38 m_map[index] = m_nextId++;
34 39 return m_map[index];
35 40 }
36 41
37 42 public int DefineClass(IEnumerable<T> symbols) {
38 43 Safe.ArgumentNotNull(symbols, "symbols");
39 44 symbols = symbols.Distinct();
40 45
41 46 foreach (var symbol in symbols) {
42 47 var index = GetSymbolIndex(symbol);
43 48 if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
44 49 m_map[GetSymbolIndex(symbol)] = m_nextId;
45 50 else
46 51 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
47 52 }
48 53 return m_nextId++;
49 54 }
50 55
51 56 public List<T>[] CreateReverseMap() {
52 57 return
53 58 Enumerable.Range(0, Count)
54 59 .Select(
55 60 i => InputSymbols
56 61 .Where(x => i != DFAConst.UNCLASSIFIED_INPUT && m_map[GetSymbolIndex(x)] == i)
57 62 .ToList()
58 63 )
59 64 .ToArray();
60 65 }
61 66
62 67 public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
63 68 Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
64 69 Safe.ArgumentNotNull(classes, "classes");
65 70 var reverseMap = CreateReverseMap();
66 71
67 72 var translationMap = new int[Count];
68 73
69 74 foreach (var scl in classes) {
70 75 // skip if the supper class contains the unclassified element
71 76 if (scl.Contains(DFAConst.UNCLASSIFIED_INPUT))
72 77 continue;
73 78 var range = new List<T>();
74 79 foreach (var cl in scl) {
75 80 if (cl < 0 || cl >= reverseMap.Length)
76 81 throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
77 82 range.AddRange(reverseMap[cl]);
78 83 }
79 84 var newClass = newAlphabet.DefineClass(range);
80 85 foreach (var cl in scl)
81 86 translationMap[cl] = newClass;
82 87 }
83 88
84 89 return translationMap;
85 90 }
86 91
87 92 public virtual int Translate(T symbol) {
88 93 return m_map[GetSymbolIndex(symbol)];
89 94 }
90 95
91 96 public abstract int GetSymbolIndex(T symbol);
92 97
93 98 public abstract IEnumerable<T> InputSymbols { get; }
94 99
95 100 /// <summary>
96 101 /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion.
97 102 /// </summary>
98 103 /// <returns>The translation map.</returns>
99 104 public int[] GetTranslationMap() {
100 105 return m_map;
101 106 }
102 107 }
103 108 }
General Comments 0
You need to be logged in to leave comments. Login now