(二)漫话中文分词：Trie、KMP、AC自动机

class Trie():  #定义一个Trie类型
    def __init__(self):  #为这个生成的实例定义一个名为_children的对象，用于存放词的Trie结构
        self._children = {}
    def _add_word(self, word):  # 定义一个添加词的实例方法
        child = self._children  # 首先会将_children的对象赋值给child
        for i,char in enumerate(word):  # 然后从头遍历添加词的每一个字符
            if char not in child:  # 查看当前字符是否存在Trie树上
                child[char] = {'__value': False} # 如果没有则新建一个对象，并设置特殊key__value为False，表明这不是一个结尾字符
            if i == (len(word) - 1):  # 判断是否为结尾字符
                child[char]['__value'] = True # 如果是则将特殊key：__value设为True，表明为结尾字符
            child = child[char]  # 如果还有字符，则将当前字符对象更新为child，那么下一次查找则是基于上一次对象下
        return True # 添加完成返回True
    def _get_word(self, word):  # 查找词
        child = self._children  # 同样设置一个child变量，用于控制当前的字符对象 
        for char in word:  
            child = child.get(char)
            if child is None :  # 只要其中一个没有查找到，那么说明匹配识别，则返回False
                return False 
        return child['__value']  # 如果没有匹配失败则返回特殊__value的值
    #回True表示词典中存在该词，返回False表示不存在或者传递进来的词不成词 

trie = Trie()
trie._add_word('分词')

sentence = '中文分词算法' 
start = 0 
maxWidth = 2 # 改动1：手动填写最大长度
cut_result = [] 

while (start <= len(sentence)): 
    end = start + maxWidth     
    word = sentence[start: end] 
    while ( word ) :  
        if ( trie._get_word(word) ) :  # 改动2：利用Trie的查询函数，该返回查询到为词则返回True，否则False
            cut_result.append(word)
            start = start + len(word) - 1  
            break 
        if (len(word[:-1]) == 0):
            cut_result.append(word) 
            break
        word = word[:-1]  
    start = start + 1  

print(cut_result)
#['中', '文', '分词', '算', '法'] 

位移值 = 成功匹配的数量 - 匹配失败位前一位在部分匹配表中的值 

前缀集合为：{h, ho, hom}
后缀集合为：{ome, me, e} 

A：前后缀都为空，则值为0
AB：前缀为{A},后缀为{B},没有相同的字符，部分匹配表中的值为0
ABA：前缀为{A, AB},后缀为{BA, A}，其中有字符A交集，其长度为1，部分匹配表中的值为1
ABAB：前缀为{A,AB,ABA},后缀为{BAB,AB,B}，有相同字符AB，长度为2，部分匹配表中的值为2
ABABC：前缀为{A,AB,ABA,ABAB},后缀为{BABC,ABC,BC,C}，没有相同字符，部分匹配表中的值为0 

class TrieNode(object):
    def __init__(self) -> None:
        self._children = {}
        self._fail = None
        self._exist = []
    def _add_child(self, char, value, overwrite = None):
        child = self._children.get(char)
        if child is None:
            child = TrieNode()
            self._children[char] = child
        if overwrite:
            child._exist.append(value)
        return child

class Trie(TrieNode):
    def __init__(self) -> None:
        super().__init__()
    def _find_text(self, text):
        state = self
        cut_word = []
        for i,t in enumerate(text):
            while state._children.get(t) is None and state._fail:
                state = state._fail
            if state._children.get(t) is None:
                continue
            state = state._children.get(t)
            if len(state._exist) != 0:
                for x in state._exist:
                    max_cut = text[i - x + 1:i + 1]
                    cut_word.append(max_cut)
        return cut_word
    def __setitem__(self, key, value):
        state = self
        for char in key:
            if char == key[-1] :
                state = state._add_child(char, len(value), True)
                break
            state = state._add_child(char, None, False)
    def _init_fail(self):
        q = queue.Queue()
        for i in self._children:
            state = self._children.get(i)
            state._fail = self
            q.put(state)
        while q.empty() == False:
            state = q.get()
            for i in state._children:
                v = state._children.get(i)
                fafail = state._fail
                while fafail is not None and fafail._children.get(i) is not None:
                    fafail = fafail._children.get(i)
                v._fail = fafail
                if v._fail:
                    if len(fafail._exist) != 0:
                        v._exist.extend(v._fail._exist)
                q.put(v)