Mercurial > pub > ImplabNet
comparison Implab/Automaton/DFADefinition.cs @ 162:0526412bbb26 ref20160224
DFA refactoring
author | cin |
---|---|
date | Wed, 24 Feb 2016 08:39:53 +0300 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
161:2a8466f0cb8a | 162:0526412bbb26 |
---|---|
1 using Implab; | |
2 using System; | |
3 using System.Collections.Generic; | |
4 using System.Linq; | |
5 | |
6 namespace Implab.Automaton { | |
7 public class DFADefinition<TInput, TState, TTag> : IDFADefinitionBuilder<TTag>, IDFADefinition<TInput, TState, TTag> { | |
8 DFAStateDescriptior<TTag>[] m_dfaTable; | |
9 readonly IAlphabet<TInput> m_inputAlphabet; | |
10 readonly IAlphabet<TState> m_stateAlphabet; | |
11 | |
12 readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>(); | |
13 readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>(); | |
14 | |
15 public DFADefinition(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) { | |
16 Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet"); | |
17 Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet"); | |
18 | |
19 m_inputAlphabet = inputAlphabet; | |
20 m_stateAlphabet = stateAlphabet; | |
21 } | |
22 | |
23 public void DefineTransition(int s1, int s2, int symbol) { | |
24 Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count-1, "s1"); | |
25 Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count-1, "s2"); | |
26 Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count-1, "symbol"); | |
27 | |
28 m_transitions.Add(new AutomatonTransition(s1, s2, symbol)); | |
29 } | |
30 | |
31 | |
32 #region IDFADefinition implementation | |
33 | |
34 public DFAStateDescriptior<TTag>[] GetTransitionTable() { | |
35 if (m_dfaTable == null) { | |
36 m_dfaTable = new DFAStateDescriptior<TTag>[m_stateAlphabet.Count]; | |
37 | |
38 foreach (var pair in m_finalStates) { | |
39 var idx = pair.Key; | |
40 | |
41 m_dfaTable[idx].final = true; | |
42 m_dfaTable[idx].tag = m_dfaTable[idx].tag != null ? | |
43 m_dfaTable[idx].tag.Concat(pair.Value).Distinct().ToArray() : | |
44 pair.Value; | |
45 } | |
46 | |
47 foreach (var t in m_transitions) { | |
48 if (m_dfaTable[t.s1].transitions == null) { | |
49 m_dfaTable[t.s1].transitions = new int[m_inputAlphabet.Count]; | |
50 for (int i = 0; i < m_dfaTable[t.s1].transitions.Length; i++) | |
51 m_dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE; | |
52 } | |
53 | |
54 m_dfaTable[t.s1].transitions[t.edge] = t.s2; | |
55 } | |
56 } | |
57 return m_dfaTable; | |
58 } | |
59 | |
60 public IAlphabet<TInput> InputAlphabet { | |
61 get { | |
62 return m_inputAlphabet; | |
63 } | |
64 } | |
65 | |
66 public IAlphabet<TState> StateAlphabet { | |
67 get { | |
68 return m_stateAlphabet; | |
69 } | |
70 } | |
71 | |
72 #endregion | |
73 | |
74 #region IDFADefinitionBuilder | |
75 | |
76 public void DefineTransition(int s1, int s2, int symbol) { | |
77 Safe.ArgumentInRange(s1, 0, m_stateAlphabet.Count - 1, "s1"); | |
78 Safe.ArgumentInRange(s2, 0, m_stateAlphabet.Count - 1, "s2"); | |
79 Safe.ArgumentInRange(symbol, 0, m_inputAlphabet.Count - 1, "symbol"); | |
80 | |
81 m_transitions.Add(new AutomatonTransition(s1, s2, symbol)); | |
82 } | |
83 | |
84 public void MarkFinalState(int state, params TTag[] tags) { | |
85 m_finalStates[state] = tags; | |
86 } | |
87 | |
88 | |
89 #endregion | |
90 | |
91 protected void Optimize(IDFADefinitionBuilder<TTag> optimalDFA,IAlphabetBuilder<TInput> optimalInputAlphabet, IAlphabetBuilder<TState> optimalStateAlphabet) { | |
92 Safe.ArgumentNotNull(optimalDFA, "dfa"); | |
93 Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet"); | |
94 Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet"); | |
95 | |
96 var setComparer = new CustomEqualityComparer<HashSet<int>>( | |
97 (x, y) => x.SetEquals(y), | |
98 s => s.Sum(x => x.GetHashCode()) | |
99 ); | |
100 | |
101 var arrayComparer = new CustomEqualityComparer<TTag[]>( | |
102 (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)), | |
103 a => a.Sum(x => x.GetHashCode()) | |
104 ); | |
105 | |
106 var optimalStates = new HashSet<HashSet<int>>(setComparer); | |
107 var queue = new HashSet<HashSet<int>>(setComparer); | |
108 | |
109 // получаем конечные состояния, сгруппированные по маркерам | |
110 optimalStates.UnionWith( | |
111 m_finalStates | |
112 .GroupBy(pair => pair.Value, arrayComparer) | |
113 .Select( | |
114 g => new HashSet<int>( | |
115 g.Select( pair => pair.Key) | |
116 ) | |
117 ) | |
118 ); | |
119 | |
120 var state = new HashSet<int>( | |
121 Enumerable | |
122 .Range(0, m_stateAlphabet.Count - 1) | |
123 .Where(i => !m_finalStates.ContainsKey(i)) | |
124 ); | |
125 optimalStates.Add(state); | |
126 queue.Add(state); | |
127 | |
128 var rmap = m_transitions | |
129 .GroupBy(t => t.s2) | |
130 .ToLookup( | |
131 g => g.Key, // s2 | |
132 g => g.ToLookup(t => t.edge, t => t.s1) | |
133 ); | |
134 | |
135 while (queue.Count > 0) { | |
136 var stateA = queue.First(); | |
137 queue.Remove(stateA); | |
138 | |
139 for (int c = 0; c < m_inputAlphabet.Count; c++) { | |
140 var stateX = new HashSet<int>(); | |
141 foreach(var a in stateA) | |
142 stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a' | |
143 | |
144 foreach (var stateY in optimalStates.ToArray()) { | |
145 if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) { | |
146 var stateR1 = new HashSet<int>(stateY); | |
147 var stateR2 = new HashSet<int>(stateY); | |
148 | |
149 stateR1.IntersectWith(stateX); | |
150 stateR2.ExceptWith(stateX); | |
151 | |
152 optimalStates.Remove(stateY); | |
153 optimalStates.Add(stateR1); | |
154 optimalStates.Add(stateR2); | |
155 | |
156 if (queue.Contains(stateY)) { | |
157 queue.Remove(stateY); | |
158 queue.Add(stateR1); | |
159 queue.Add(stateR2); | |
160 } else { | |
161 queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2); | |
162 } | |
163 } | |
164 } | |
165 } | |
166 } | |
167 | |
168 // карта получения оптимального состояния по соотвествующему ему простому состоянию | |
169 var statesMap = m_stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates); | |
170 | |
171 // получаем минимальный алфавит | |
172 // входные символы не различимы, если Move(s,a1) == Move(s,a2) | |
173 var optimalAlphabet = m_transitions | |
174 .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge); | |
175 | |
176 var alphabetMap = m_inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet); | |
177 | |
178 var optimalTags = m_finalStates | |
179 .GroupBy(pair => statesMap[pair.Key]) | |
180 .ToDictionary( | |
181 g => g.Key, | |
182 g => g.SelectMany(pair => pair.Value).ToArray() | |
183 ); | |
184 | |
185 // построение автомата | |
186 foreach (var pair in optimalTags) | |
187 optimalDFA.MarkFinalState(pair.Key, pair.Value); | |
188 | |
189 foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct()) | |
190 optimalDFA.DefineTransition(t.s1, t.s2, t.edge); | |
191 } | |
192 | |
193 public void PrintDFA() { | |
194 | |
195 var inputMap = InputAlphabet.CreateReverseMap(); | |
196 var stateMap = StateAlphabet.CreateReverseMap(); | |
197 | |
198 for (int i = 0; i < inputMap.Length; i++) { | |
199 Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i])); | |
200 } | |
201 | |
202 foreach(var t in m_transitions) | |
203 Console.WriteLine( | |
204 "S{0} -{1}-> S{2}{3}", | |
205 stateMap[t.s1], | |
206 String.Join(",", inputMap[t.edge]), | |
207 stateMap[t.s2], | |
208 m_finalStates.ContainsKey(t.s2) ? "$" : "" | |
209 ); | |
210 | |
211 } | |
212 } | |
213 } |