0

我正在创建一个有限状态自动机 ( FSA)，它基本上是一棵树。单词中的每个字母构成一个节点 ( State)。一串字母构成通过 的路径FSA，并且路径可以重叠。不过，我似乎遇到了节点next_states或子节点的问题。

输入文件vocab.small看起来像这样，\n每行末尾都有一个：

A 
A A A 
A A B E R G 
A A C H E N

现在，我构建了FSA非常类似于树的结构，但是我在其中创建State start_state并State end_state链接它们：

class State (object):
    __slots__ = "chars","next_states"
    def __init__(self,chars,next_states=[]):
        self.chars = chars
        self.next_states = next_states

class FSA (object):
    __slots__ = "vocab","start_state","end_state"
    def __init__(self,vocab):
        self.vocab = vocab
        self.start_state = State("0")
        self.end_state = State("1")
        self.end_state.next_states.append(self.start_state)
        self.start_state.next_states.append(self.end_state)

中的其他方法FSA是：

    def create_fsa(self):
        vocab_file = open(self.vocab, 'r')
        for word in vocab_file:
            self.add_word(word)
        vocab_file.close()

    def add_word(self,word,current_state=None):
        next_char = word[0:2]
        if current_state == None:
            current_state = self.start_state
        ## next_char found in current_state.next_states
        if next((x for x in current_state.next_states if x.chars == next_char), None):
            if len(word) > 3:
                print "next_char found"
                current_state = next((x for x in current_state.next_states if x.chars == next_char), None)
                self.add_word(word[2:],current_state)
            else:
                print "next_char found + add end"
                current_state = next((x for x in current_state.next_states if x.chars == next_char), None)
                current_state.next_states.append(self.end_state)
##                current_state.children[current_state.children.index(next_char)].append(self.end_state)
        ## next_char NOT found in current_state.next_states
        else:
            current_state.next_states.append(State(next_char))
            current_state = next((x for x in current_state.next_states if x.chars == next_char), None)
            if len(word) > 3:
                print "next_char added"
                self.add_word(word[2:],current_state)
            else:
                print "next_char added + end"
                current_state.next_states.append(self.end_state)
        print

问题似乎在于current_state.next_states[]，因为它继续累积对象，而不是在每个新的State. 问题是否current_state.next_states.append(State(next_char))与我如何创建新State对象有关？

谢谢您的帮助。

4

0 回答 0