Mercurial > pub > ImplabNet

comparison Implab/Automaton/DFADefinition.cs @ 162:0526412bbb26 ref20160224

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }