Blame view

fsabuilder/fsa/state.py 1.7 KB
Michał Lenart authored
1
2
3
4
5
6
7
8
9
10
11
12
13
'''
Created on Oct 8, 2013

@author: mlenart
'''

class State(object):
    '''
    A state in an automaton
    '''

    def __init__(self):
        self.transitionsMap = {}
Michał Lenart authored
14
        self.freq = 0
Michał Lenart authored
15
16
17
        self.encodedData = None
        self.reverseOffset = None
        self.offset = None
Michał Lenart authored
18
19
        self.label2Freq = {}
        self.serializeAsArray = False
Michał Lenart authored
20
Michał Lenart authored
21
22
23
24
    @property
    def transitionsNum(self):
        return len(self.transitionsMap)
Michał Lenart authored
25
26
27
28
29
30
    def setTransition(self, byte, nextState):
        self.transitionsMap[byte] = nextState

    def hasNext(self, byte):
        return byte in self.transitionsMap
Michał Lenart authored
31
32
33
    def getNext(self, byte, addFreq=False):
        if addFreq:
            self.freq += 1
Michał Lenart authored
34
            self.label2Freq[byte] = self.label2Freq.get(byte, 0) + 1
Michał Lenart authored
35
36
37
38
39
40
41
42
        return self.transitionsMap.get(byte, None)

    def getRegisterKey(self):
        return ( frozenset(self.transitionsMap.iteritems()), tuple(self.encodedData) if self.encodedData else None )

    def isAccepting(self):
        return self.encodedData is not None
Michał Lenart authored
43
    def tryToRecognize(self, word, addFreq=False):
Michał Lenart authored
44
        if word:
Michał Lenart authored
45
            nextState = self.getNext(word[0], addFreq)
Michał Lenart authored
46
            if nextState:
Michał Lenart authored
47
                return nextState.tryToRecognize(word[1:], addFreq)
Michał Lenart authored
48
49
50
51
52
            else:
                return False
        else:
            return self.encodedData
Michał Lenart authored
53
    def dfs(self, alreadyVisited=set(), sortKey=lambda (_, state): -state.freq):
Michał Lenart authored
54
        if not self in alreadyVisited:
Michał Lenart authored
55
            for _, state in sorted(self.transitionsMap.iteritems(), key=sortKey):
Michał Lenart authored
56
57
58
59
                for state1 in state.dfs(alreadyVisited):
                    yield state1
            alreadyVisited.add(self)
            yield self