implab/ImplabNet Commit - r167:96681e9d0cea

sync

cin -

r167:96681e9d0cea ref20160224

parent child

Context file:

r167:96681e9d0cea

Collapse all files

Implab/Automaton/DFATransitionTable.cs +6 -6

             using Implab;
             using System;
             using System.Collections.Generic;
             using System.Linq;
             namespace Implab.Automaton {
-                public class DFATransitionTable<TTag> : IDFATableBuilder {
+                public class DFATransitionTable : IDFATableBuilder {
                     DFAStateDescriptior[] m_dfaTable;
                     int m_stateCount;
                     int m_symbolCount;
                     int m_initialState;
-                    readonly Dictionary<int, TTag[]> m_finalStates = new Dictionary<int, TTag[]>();
+                    readonly HashSet<int> m_finalStates = new HashSet<int>();
                     readonly HashSet<AutomatonTransition> m_transitions = new HashSet<AutomatonTransition>();
                     #region IDFADefinition implementation
                     public DFAStateDescriptior[] GetTransitionTable() {
                         if (m_dfaTable == null) {
                             if (m_stateCount <= 0)
                                 throw new InvalidOperationException("Invalid automaton definition: states count = {0}", m_stateCount);
                             if (m_symbolCount <= 0)
                                 throw new InvalidOperationException("Invalid automaton definition: symbols count = {0}", m_symbolCount);
                             m_dfaTable = ConstructTransitionTable();
                         }
                         return m_dfaTable;
                     }
                     public bool IsFinalState(int s) {
                         Safe.ArgumentInRange(s, 0, m_stateCount, "s");
-                        return m_finalStates.ContainsKey(s);
+                        return m_dfaTable != null ? m_dfaTable[s].final :  m_finalStates.Contains(s);
                     }
-                    public IEnumerable<KeyValuePair<int,TTag[]>> FinalStates {
+                    public IEnumerable<int> FinalStates {
                         get {
                             return m_finalStates;
                         }
                     }
                     public int StateCount {
                         get { return m_stateCount; }
                     }
                     public int AlphabetSize {
                         get { return m_symbolCount; }
                     }
                     public int InitialState {
                         get { return m_initialState; }
                     }
                     #endregion
-                    protected virtual DFAStateDescriptior<TTag>[] ConstructTransitionTable() {
+                    protected virtual DFAStateDescriptior[] ConstructTransitionTable() {
-                        var dfaTable = new DFAStateDescriptior<TTag>[m_stateCount];
+                        var dfaTable = new DFAStateDescriptior[m_stateCount];
                         foreach (var pair in m_finalStates) {
                             var idx = pair.Key;
                             dfaTable[idx].final = true;
                             dfaTable[idx].tag = pair.Value;
                         }
                         foreach (var t in m_transitions) {
                             if (dfaTable[t.s1].transitions == null) {
                                 dfaTable[t.s1].transitions = new int[m_symbolCount];
                                 for (int i = 0; i < dfaTable[t.s1].transitions.Length; i++)
                                     dfaTable[t.s1].transitions[i] = DFAConst.UNREACHABLE_STATE;
                             }
                             dfaTable[t.s1].transitions[t.edge] = t.s2;
                         }
                     }
                     #region IDFADefinitionBuilder
                     public void DefineTransition(int s1, int s2, int symbol) {
                         if (m_dfaTable != null)
                             throw new InvalidOperationException("The transition table is already built");
                         Safe.ArgumentAssert(s1 > 0, "s1");
                         Safe.ArgumentAssert(s2 > 0, "s2");
                         Safe.ArgumentAssert(symbol >= 0, "symbol");
                         m_stateCount = Math.Max(Math.Max(m_stateCount, s1 + 1), s2 + 1);
                         m_symbolCount = Math.Max(m_symbolCount, symbol + 1);
                         m_transitions.Add(new AutomatonTransition(s1, s2, symbol));
                     }
                     public void MarkFinalState(int state, params TTag[] tags) {
                         if (m_dfaTable != null)
                             throw new InvalidOperationException("The transition table is already built");
                         m_finalStates[state] = tags;
                     }
                     public void SetInitialState(int s) {
                         Safe.ArgumentAssert(s >= 0, "s");
                         m_initialState = s;
                     }
                     #endregion
                     protected void Optimize<TInput, TState>(
                         IDFATableBuilder<TTag> optimalDFA,
                         IAlphabet<TInput> inputAlphabet,
                         IAlphabetBuilder<TInput> optimalInputAlphabet,
                         IAlphabet<TState> stateAlphabet,
                         IAlphabetBuilder<TState> optimalStateAlphabet
                     ) {
                         Safe.ArgumentNotNull(optimalDFA, "dfa");
                         Safe.ArgumentNotNull(optimalInputAlphabet, "optimalInputAlphabet");
                         Safe.ArgumentNotNull(optimalStateAlphabet, "optimalStateAlphabet");
                         Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
                         Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
                         if (inputAlphabet.Count != m_symbolCount)
                             throw new InvalidOperationException("The input symbols aphabet mismatch");
                         if (stateAlphabet.Count != m_stateCount)
                             throw new InvalidOperationException("The states alphabet mismatch");
                         var setComparer = new CustomEqualityComparer<HashSet<int>>(
                             (x, y) => x.SetEquals(y),
                             s => s.Sum(x => x.GetHashCode())
                         );
                         var arrayComparer = new CustomEqualityComparer<TTag[]>(
                             (x,y) => (new HashSet<int>(x)).SetEquals(new HashSet<int>(y)),
                             a => a.Sum(x => x.GetHashCode())
                         );
                         var optimalStates = new HashSet<HashSet<int>>(setComparer);
                         var queue = new HashSet<HashSet<int>>(setComparer);
                         // получаем конечные состояния, сгруппированные по маркерам
                         optimalStates.UnionWith(
                             m_finalStates
                             .GroupBy(pair => pair.Value, arrayComparer)
                             .Select(
                                 g => new HashSet<int>(
                                     g.Select( pair => pair.Key)
                                 )
                             )
                         );
                         var state = new HashSet<int>(
                             Enumerable
                             .Range(0, m_stateCount - 1)
                             .Where(i => !m_finalStates.ContainsKey(i))
                         );
                         optimalStates.Add(state);
                         queue.Add(state);
                         var rmap = m_transitions
                             .GroupBy(t => t.s2)
                             .ToLookup(
                                 g => g.Key, // s2
                                 g => g.ToLookup(t => t.edge, t => t.s1)
                             );
                         while (queue.Count > 0) {
                             var stateA = queue.First();
                             queue.Remove(stateA);
                             for (int c = 0; c < m_symbolCount; c++) {
                                 var stateX = new HashSet<int>();
                                 foreach(var a in stateA)
                                     stateX.UnionWith(rmap[a][c]); // all states from wich 'c' leads to 'a'
                                 foreach (var stateY in optimalStates.ToArray()) {
                                     if (stateX.Overlaps(stateY) && !stateY.IsSubsetOf(stateX)) {
                                         var stateR1 = new HashSet<int>(stateY);
                                         var stateR2 = new HashSet<int>(stateY);
                                         stateR1.IntersectWith(stateX);
                                         stateR2.ExceptWith(stateX);
                                         optimalStates.Remove(stateY);
                                         optimalStates.Add(stateR1);
                                         optimalStates.Add(stateR2);
                                         if (queue.Contains(stateY)) {
                                             queue.Remove(stateY);
                                             queue.Add(stateR1);
                                             queue.Add(stateR2);
                                         } else {
                                             queue.Add(stateR1.Count <= stateR2.Count ? stateR1 : stateR2);
                                         }
                                     }
                                 }
                             }
                         }
                         // карта получения оптимального состояния по соотвествующему ему простому состоянию
                         var statesMap = stateAlphabet.Reclassify(optimalStateAlphabet, optimalStates);
                         // получаем минимальный алфавит
                         // входные символы не различимы, если Move(s,a1) == Move(s,a2)
                         var optimalAlphabet = m_transitions
                             .GroupBy(t => Tuple.Create(statesMap[t.s1], statesMap[t.s2]), t => t.edge);
                         var alphabetMap = inputAlphabet.Reclassify(optimalInputAlphabet, optimalAlphabet);
                         var optimalTags = m_finalStates
                             .GroupBy(pair => statesMap[pair.Key])
                             .ToDictionary(
                                 g => g.Key,
                                 g => g.SelectMany(pair => pair.Value).ToArray()
                             );
                         // построение автомата
                         optimalDFA.SetInitialState(statesMap[m_initialState]);
                         foreach (var pair in optimalTags)
                             optimalDFA.MarkFinalState(pair.Key, pair.Value);
                         foreach (var t in m_transitions.Select(t => new AutomatonTransition(statesMap[t.s1],statesMap[t.s2],alphabetMap[t.edge])).Distinct())
                             optimalDFA.DefineTransition(t.s1, t.s2, t.edge);
                     }
                     protected void PrintDFA<TInput, TState>(IAlphabet<TInput> inputAlphabet, IAlphabet<TState> stateAlphabet) {
                         Safe.ArgumentNotNull(inputAlphabet, "inputAlphabet");
                         Safe.ArgumentNotNull(stateAlphabet, "stateAlphabet");
                         var inputMap = inputAlphabet.CreateReverseMap();
                         var stateMap = stateAlphabet.CreateReverseMap();
                         for (int i = 0; i < inputMap.Length; i++)
                             Console.WriteLine("C{0}: {1}", i, String.Join(",", inputMap[i]));
                         foreach(var t in m_transitions)
                             Console.WriteLine(
                                 "[{0}] -{{{1}}}-> [{2}]{3}",
                                 stateMap[t.s1],
                                 String.Join(",", inputMap[t.edge]),
                                 stateMap[t.s2],
                                 m_finalStates.ContainsKey(t.s2) ? "$" : ""
                             );
                     }
                 }
             }

Implab/Automaton/IDFATableBuilder.cs +2 -10

             using System;
+            using System.Collections.Generic;
             namespace Implab.Automaton {
-                public interface IDFATableBuilder : IDFATable {
+                public interface IDFATableBuilder : IDFATable, ICollection<AutomatonTransition> {
                     /// <summary>
                     /// Marks the state as final.
                     /// </summary>
                     /// <param name="state">State.</param>
                     void MarkFinalState(int state);
-                    /// <summary>
-                    /// Defines the transition from <paramref name="s1"/> to
-                    /// <paramref name="s2"/> with input <paramref name="symbol"/>.
-                    /// </summary>
-                    /// <param name="s1">S1.</param>
-                    /// <param name="s2">S2.</param>
-                    /// <param name="symbol">Symbol.</param>
-                    void DefineTransition(int s1, int s2, int symbol);
                     void SetInitialState(int s);
                 }
             }

Implab/Automaton/IndexedAlphabetBase.cs +5 0

             using Implab;
             using System;
             using System.Collections.Generic;
             using System.Diagnostics;
             using System.Linq;
             namespace Implab.Automaton {
                 /// <summary>
                 /// Indexed alphabet is the finite set of symbols where each symbol has a zero-based unique index.
                 /// </summary>
+                /// <remarks>
+                /// Indexed alphabets are usefull in bulting efficient translations from source alphabet
+                /// to the input alphabet of the automaton. It's assumed that the index to the symbol match
+                /// is well known and documented.
+                /// </remarks>
                 public abstract class IndexedAlphabetBase<T> : IAlphabetBuilder<T> {
                     int m_nextId = 1;
                     readonly int[] m_map;
                     public int Count {
                         get { return m_nextId; }
                     }
                     protected IndexedAlphabetBase(int mapSize) {
                         m_map = new int[mapSize];
                     }
                     protected IndexedAlphabetBase(int[] map) {
                         Debug.Assert(map != null);
                         m_map = map;
                         m_nextId = map.Max() + 1;
                     }
                     public int DefineSymbol(T symbol) {
                         var index = GetSymbolIndex(symbol);
                         if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
                             m_map[index] = m_nextId++;
                         return m_map[index];
                     }
                     public int DefineClass(IEnumerable<T> symbols) {
                         Safe.ArgumentNotNull(symbols, "symbols");
                         symbols = symbols.Distinct();
                         foreach (var symbol in symbols) {
                             var index = GetSymbolIndex(symbol);
                             if (m_map[index] == DFAConst.UNCLASSIFIED_INPUT)
                                 m_map[GetSymbolIndex(symbol)] = m_nextId;
                             else
                                 throw new InvalidOperationException(String.Format("Symbol '{0}' already in use", symbol));
                         }
                         return m_nextId++;
                     }
                     public List<T>[] CreateReverseMap() {
                         return
                             Enumerable.Range(0, Count)
                                 .Select(
                                     i => InputSymbols
                                     .Where(x => i != DFAConst.UNCLASSIFIED_INPUT && m_map[GetSymbolIndex(x)] == i)
                                         .ToList()
                                 )
                                 .ToArray();
                     }
                     public int[] Reclassify(IAlphabetBuilder<T> newAlphabet, IEnumerable<IEnumerable<int>> classes) {
                         Safe.ArgumentNotNull(newAlphabet, "newAlphabet");
                         Safe.ArgumentNotNull(classes, "classes");
                         var reverseMap = CreateReverseMap();
                         var translationMap = new int[Count];
                         foreach (var scl in classes) {
                             // skip if the supper class contains the unclassified element
                             if (scl.Contains(DFAConst.UNCLASSIFIED_INPUT))
                                 continue;
                             var range = new List<T>();
                             foreach (var cl in scl) {
                                 if (cl < 0 || cl >= reverseMap.Length)
                                     throw new ArgumentOutOfRangeException(String.Format("Class {0} is not valid for the current alphabet", cl));
                                 range.AddRange(reverseMap[cl]);
                             }
                             var newClass = newAlphabet.DefineClass(range);
                             foreach (var cl in scl)
                                 translationMap[cl] = newClass;
                         }
                         return translationMap;
                     }
                     public virtual int Translate(T symbol) {
                         return m_map[GetSymbolIndex(symbol)];
                     }
                     public abstract int GetSymbolIndex(T symbol);
                     public abstract IEnumerable<T> InputSymbols { get; }
                     /// <summary>
                     /// Gets the translation map from the index of the symbol to it's class this is usefull for the optimized input symbols transtaion.
                     /// </summary>
                     /// <returns>The translation map.</returns>
                     public int[] GetTranslationMap() {
                         return m_map;
                     }
                 }
             }

General Comments 0

Write
Preview

You need to be logged in to leave comments. Login now

No TODOs yet

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages