Mercurial > hg > Members > shinya > pyrect

annotate pyrect/regexp/nfa.py @ 98:4d498b002de5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactor for data-structure (dict -> Transition).
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Sun, 12 Dec 2010 23:04:31 +0900
parents 19a88707bd29
children 2632b963e441
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #!/usr/bin/env python
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 import curses.ascii as ascii
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 import copy
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
5 import collections
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
6 from pyrect.regexp.fa import FA, Transition
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 class NFAFragment(object):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 def __init__(self):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 self.start = None # integer
47
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
11 self.accepts = set() # frozenset
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
12 self.transition = Transition() # transition, char or special -> frozenset([states])
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 def connect(self, from_, char, to):
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
15 if self.transition[from_, char]:
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
16 slot = self.transition[from_, char]
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
17 else:
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
18 slot = set()
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
19 self.transition[from_, char] = slot
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 slot.add(to)
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
47
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
22 def accept_to(self, from_, char):
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
23 self.accepts.add((from_, char))
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
24
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
25 def set_accept(self, to):
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
26 for from_, char in self.accepts:
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
27 self.connect(from_, char, to)
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
28 self.accepts = set()
701beabd7d97 add input-rules, Range, CharacterClass, Anchor and MultiByte-Char(but not work)\nand more simplify NFA (is global improvement).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 45
diff changeset
29
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 def new_skelton(self):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 # copy fragment (self), and it return
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 newFrag = NFAFragment();
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
33 newFrag.transition = copy.deepcopy(self.transition)
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 return newFrag
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 def __or__(self, frag):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 newFrag = self.new_skelton()
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
38 for k, v in frag.transition.iterstates():
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
39 newFrag.transition[k] = copy.deepcopy(v)
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 return newFrag
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 def __str__(self):
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 return ("NFA: delta -> %s, start -> %s, accepts -> %s" %
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
44 (self.transition, self.start, self.accepts))
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 def build(self):
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
47 states = set()
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
48 for s in self.transition.iterkeys():
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
49 states.add(s)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
50
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 return NFA(
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
52 self.transition,
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 self.start,
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 self.accepts,
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
55 sorted(states)
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 )
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 class NFA(FA):
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
59 def epsilon_expand(self, states):
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
60 if not isinstance(states, set) and \
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
61 not isinstance(states, list):
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
62 states = set([states])
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
63 states = copy.deepcopy(states)
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 done = set()
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
65 while states:
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
66 stat = states.pop()
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 done.add(stat)
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
68 if self.transition[stat, ""] != None:
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
69 for n in self.transition[stat, ""]:
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
70 if not n in done: states.add(n)
43
83c69d42faa8 replace converting-flow, module dfareg with module regexp. it's is substantial changing in implimentation.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 return frozenset(done)
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
72
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
73 class SuffixNFA(NFA):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
74 def __init__(self, nfa):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
75 self.start = nfa.start
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
76 self.accepts = copy.deepcopy(nfa.accepts)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
77 self.states = copy.deepcopy(nfa.states)
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
78 self.transition = self.nfa_trans(nfa)
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
79 start = set(self.states)-set([self.start])
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
80 if self.map.has_key((self.start, '')):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
81 self.map[(self.start, '')].add(start)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
82 else:
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
83 self.map[(self.start, '')] = start
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
84
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
85 def nfa_trans(self, fa):
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
86 if type(fa) == NFA:
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
87 return copy.deepcopy(fa.transition)
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
88 ntrans = dict()
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
89 for k, v in fa.map.itertrans():
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
90 ntrans[k] = set([v])
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
91 return ntrans
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
92
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
93 class SuffixTrieNFA(NFA):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
94 def __init__(self, dfa):
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
95 self.start = dfa.start
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
96 self.pdfa = dfa
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
97 self.states = copy.deepcopy(dfa.states)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
98 self.acceptable = collections.defaultdict(set)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
99 self.accepts = copy.deepcopy(set(dfa.accepts))
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
100 states = [self.start] + list(set(self.states)-set((self.start,)))
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
101 self.make_trie_trans(states)
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
102
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
103 def make_trie_trans(self, states):
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
104 add_states = set()
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
105 offset = [x * len(states) for x in range(len(states))]
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
106 for s, ind in zip(states, offset):
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
107 for (s_, i), n in self.pdfa.trans.itertrans():
89
933d422f21f0 add class trie. this can accept suffix-language.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
108 sind = s_ + ind
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
109 nind = n + ind
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
110 add_states.add((sind, nind))
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
111 if n in self.pdfa.accepts:
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
112 self.accepts.add(nind)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
113 self.acceptable[nind].add(s)
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
114 self.map[(sind, i)] = set((nind,))
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
115
89
933d422f21f0 add class trie. this can accept suffix-language.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
116 starts = set()
933d422f21f0 add class trie. this can accept suffix-language.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
117 for i in range(1, len(states)):
933d422f21f0 add class trie. this can accept suffix-language.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
118 starts.add(self.start + i + offset[i])
933d422f21f0 add class trie. this can accept suffix-language.
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
119
87
d23f12ce0369 add suffix-dfa, it's used to be parallel-matching-algorithm (not implement, yet).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 47
diff changeset
120 self.states = list(add_states)
98
4d498b002de5 refactor for data-structure (dict -> Transition).
Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
parents: 91
diff changeset
121 self.trans[(self.start, '')] = starts