Good morning, I am using Python 2.7.1 on Windows XP Service Pack 3. Here is the program where the Python interpreter complains about NameError: global name 'levenshtein_automata' is not defined.
The python 2,7.1 error message is: Traceback (most recent call last): File "automata_test.py", line 174, in <module> length = len(list(testdfa.find_all_matches('food', 1, m))) File "automata_test.py", line 145, in find_all_matches lev = levenshtein_automata(word, k).to_dfa() NameError: global name 'levenshtein_automata' is not defined Here is the program. I have marked lines 174, 145 and 125. import bisect import random class NFA(object): EPSILON = object() ANY = object() def __init__(self, start_state): self.transitions = {} self.final_states = set() self._start_state = start_state @property def start_state(self): return frozenset(self._expand(set([self._start_state]))) def add_transition(self, src, input, dest): self.transitions.setdefault(src, {}).setdefault(input, set()).add(dest) def add_final_state(self, state): self.final_states.add(state) def is_final(self, states): return self.final_states.intersection(states) def _expand(self, states): frontier = set(states) while frontier: state = frontier.pop() new_states = self.transitions.get(state, {}).get(NFA.EPSILON, set()).difference(states) frontier.update(new_states) states.update(new_states) return states def next_state(self, states, input): dest_states = set() for state in states: state_transitions = self.transitions.get(state, {}) dest_states.update(state_transitions.get(input, [])) dest_states.update(state_transitions.get(NFA.ANY, [])) return frozenset(self._expand(dest_states)) def get_inputs(self, states): inputs = set() for state in states: inputs.update(self.transitions.get(state, {}).keys()) return inputs def to_dfa(self): dfa = DFA(self.start_state) frontier = [self.start_state] seen = set() while frontier: current = frontier.pop() inputs = self.get_inputs(current) for input in inputs: if input == NFA.EPSILON: continue new_state = self.next_state(current, input) if new_state not in seen: frontier.append(new_state) seen.add(new_state) if self.is_final(new_state): dfa.add_final_state(new_state) if input == NFA.ANY: dfa.set_default_transition(current, new_state) else: dfa.add_transition(current, input, new_state) return dfa class DFA(object): def __init__(self, start_state): self.start_state = start_state self.transitions = {} self.defaults = {} self.final_states = set() def add_transition(self, src, input, dest): self.transitions.setdefault(src, {})[input] = dest def set_default_transition(self, src, dest): self.defaults[src] = dest def add_final_state(self, state): self.final_states.add(state) def is_final(self, state): return state in self.final_states def next_state(self, src, input): state_transitions = self.transitions.get(src, {}) return state_transitions.get(input, self.defaults.get(src, None)) def next_valid_string(self, input): state = self.start_state stack = [] # Evaluate the DFA as far as possible print state for i, x in enumerate(input): print "%s" % input print 'e' stack.append((input[:i], state, x)) state = self.next_state(state, x) if not state: break else: stack.append((input[:i+1], state, None)) if self.is_final(state): # Input word is already valid return input # Perform a 'wall following' search for the lexicographically smallest # accepting state. while stack: path, state, x = stack.pop() x = self.find_next_edge(state, x) #print 'x' if x: path += x state = self.next_state(state, x) if self.is_final(state): print 'p' return path stack.append((path, state, None)) print 'v' return None def find_next_edge(self, s, x): if x is None: x = '\0' # u'\0' else: x = chr(ord(x) + 1) state_transitions = self.transitions.get(s, {}) if x in state_transitions or s in self.defaults: return x labels = sorted(state_transitions.keys()) pos = bisect.bisect_left(labels, x) if pos < len(labels): print 'n' return labels[pos] return None def levenshtein_automata(self, term, k): ##### line 125 ########' nfa = NFA((0, 0)) for i, c in enumerate(term): for e in range(k + 1): # Correct character nfa.add_transition((i, e), c, (i + 1, e)) if e < k: # Deletion nfa.add_transition((i, e), NFA.ANY, (i, e + 1)) # Insertion nfa.add_transition((i, e), NFA.EPSILON, (i + 1, e + 1)) # Substitution nfa.add_transition((i, e), NFA.ANY, (i + 1, e + 1)) for e in range(k + 1): if e < k: nfa.add_transition((len(term), e), NFA.ANY, (len(term), e + 1)) nfa.add_final_state((len(term), e)) return nfa def find_all_matches(self, word, k, lookup_func): lev = levenshtein_automata(word, k).to_dfa() ######### line 145 ########## match = lev.next_valid_string('\0') while match: next = lookup_func(match) if not next: return if match == next: yield match next1 = next1 + '\0' match = lev.next_valid_string(next1) class Matcher(object): def __init__(self, l): self.l = l self.probes = 0 def __call__(self, w): self.probes += 1 pos = bisect.bisect_left(self.l, w) if pos < len(self.l): return self.l[pos] else: return None words = [x.strip().lower() for x in open('F:/shedskin/database.txt')] words.sort() m = Matcher(words) testdfa = DFA(1) length = len(list(testdfa.find_all_matches('food', 1, m))) ######## line 174 ########## I cannot understand why the Python 2.7.1 interpreter complains about NameError: global name 'levenshtein_automata' is not defined. On line 125 , I try to define levenshtein_automata(self,term,k) as a method of the class DFA. I am new to Python 2.7.1. Could someone help me fix this NameError error message. Thank you.
_______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor