|
1
2
3
4
5
6
|
'''
Created on 24 sty 2014
@author: mlenart
'''
|
|
7
|
from morfeuszbuilder.segrules.rulesFSA import RulesFSA, RulesState
|
|
8
9
10
|
class RulesNFAState(object):
|
|
11
12
13
|
statesCounter = 0
def __init__(self, initial=False, final=False, weak=False):
|
|
14
|
self.transitionsMap = {}
|
|
15
|
# self.transitionsDataMap = {}
|
|
16
17
|
self.initial = initial
self.final = final
|
|
18
19
20
21
22
|
self.weak = weak
self.idx = RulesNFAState.statesCounter
RulesNFAState.statesCounter += 1
def addTransition(self, label, targetState):
|
|
23
|
assert label is None or len(label) == 2
|
|
24
25
26
27
28
29
30
31
32
33
34
35
36
|
self.transitionsMap.setdefault(label, set())
self.transitionsMap[label].add(targetState)
def getClosure(self, visited):
if self in visited:
return set()
else:
visited.add(self)
res = set()
res.add(self)
for nextState in self.transitionsMap.get(None, []):
res |= nextState.getClosure(visited)
return res
|
|
37
|
|
|
38
39
40
41
42
43
|
def dfs(self, visitedStates=set()):
if not self in visitedStates:
visitedStates.add(self)
yield self
for _, nextStates in self.transitionsMap.iteritems():
for state in nextStates:
|
|
44
|
for state1 in state.dfs(visitedStates):
|
|
45
46
47
48
49
50
51
|
yield state1
def debug(self):
print '----------------'
print 'STATE:', self.idx
for label, nextStates in self.transitionsMap.iteritems():
print label, '-->', [s.idx for s in sorted(nextStates, key=lambda s: s.idx)]
|
|
52
53
54
|
class RulesNFA(object):
|
|
55
|
def __init__(self):
|
|
56
57
|
self.initialState = RulesNFAState(initial=True)
|
|
58
59
60
61
62
|
def _groupOutputByLabels(self, nfaStates):
res = {}
for nfaState in nfaStates:
for label, nextStates in nfaState.transitionsMap.iteritems():
if label is not None:
|
|
63
64
65
|
# transitionData = nfaState.transitionsDataMap[label]
segnum, shiftOrth = label
res.setdefault((segnum, shiftOrth), set())
|
|
66
|
for nextNFAState in nextStates:
|
|
67
|
res[(segnum, shiftOrth)] |= nextNFAState.getClosure(set())
|
|
68
69
70
|
return res
def _doConvertState(self, dfaState, nfaStates, nfaSubset2DFAState):
|
|
71
72
73
|
assert all(map(lambda state: state.weak, filter(lambda state: state.final, nfaStates))) \
or not any(map(lambda state: state.weak, filter(lambda state: state.final, nfaStates)))
weak = any(map(lambda state: state.weak and state.final, nfaStates))
|
|
74
|
final = any(map(lambda state: state.final, nfaStates))
|
|
75
|
# assert not weak or not final
|
|
76
77
78
|
if final:
# dfaState should be final
# and contain info about weakness
|
|
79
80
81
|
dfaState.setAsAccepting(weak=weak)
# dfaState.encodedData = bytearray([1 if weak else 0])
for (segnum, shiftOrth), nextNFAStates in self._groupOutputByLabels(nfaStates).iteritems():
|
|
82
83
84
85
|
key = frozenset(nextNFAStates)
if key in nfaSubset2DFAState:
nextDFAState = nfaSubset2DFAState[key]
else:
|
|
86
|
nextDFAState = RulesState()
|
|
87
88
|
nfaSubset2DFAState[key] = nextDFAState
self._doConvertState(nextDFAState, nextNFAStates, nfaSubset2DFAState)
|
|
89
90
|
dfaState.setTransition((segnum, shiftOrth), nextDFAState)
# dfaState.setTransitionData(label, transitionData)
|
|
91
92
|
def convertToDFA(self):
|
|
93
|
dfa = RulesFSA()
|
|
94
|
startStates = self.initialState.getClosure(set())
|
|
95
|
assert not any(filter(lambda s: s.final, startStates))
|
|
96
|
dfa.initialState = RulesState()
|
|
97
98
99
100
101
102
|
self._doConvertState(dfa.initialState, startStates, {frozenset(startStates): dfa.initialState})
return dfa
def debug(self):
for state in self.initialState.dfs():
state.debug()
|
|
103
|
|