精华内容
下载资源
问答
  • Trie树是一种很常用的树结构,它被广泛用于各个方面,比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等,而且在输入法中也能看到Trie树的身影。 什么是Trie树 Trie树通常又称为字典树、单词查找树或...
  • Python Trie树实现最长前缀字符串提取

    千次阅读 2018-11-16 17:32:45
    在文本解析项目中,经常会碰到提取品牌、商家名等需求。如给定一个手机型号字符串,要求从中提取出品牌。Trie可以很好满足此类需求。...Python中无指针,使用Dict实现结构。 # -*- coding: ...

    在文本解析项目中,经常会碰到提取品牌、商家名等需求。如给定一个手机型号字符串,要求从中提取出品牌。Trie可以很好满足此类需求。

    Tire,也叫前缀树字典树,是一种数据结构,可以用来快速检索字符串是否存在以及在字符串开始处抽取预定义的子字符串。搜索时间复杂度为O(M)  M为字符串长度。

    Tire

    代码实现

    Python中无指针,使用Dict实现树结构。

    # -*- coding: utf-8 -*-
    """
    Trie for prefix search, a data structure that quickly matches and extracts predefined substrings
    at the beginning of a given text (if they can be found).
    
    We can also skip certain characters and still succeed in a match.
    """
    
    default_ignored_chars = u' _-/'
    
    
    class Trie(object):
        def __init__(self, items, ignored_chars=default_ignored_chars):
            """ Stores all given items into this trie. """
            self.ignored_chars = ignored_chars
    
            self.trie = {}
            for item in items:
                assert item, 'Empty/none item passed in'
                item = item.strip()
                assert item, 'Empty item given'
                curr_dict = self.trie
                for c in item.upper():
                    if c not in self.ignored_chars:
                        curr_dict = curr_dict.setdefault(c, {})
                curr_dict['end'] = item
    
        def is_item(self, text):
            """ Return True if text is a valid item stored in this trie. """
            if not text:
                return False
            curr_dict = self.trie
            for c in text.upper():
                if c not in self.ignored_chars:
                    if c not in curr_dict:
                        return False
                    curr_dict = curr_dict[c]
            return 'end' in curr_dict
    
        def extract_longest_item(self, text):
            """ Return longest item-name found at beginning of the text. Also returns the
                offset where the item ends in case the caller wants to chop the string. """
            curr_dict, longest, offset = self.trie, None, 0
    
            if not text:
                return longest, offset
    
            for i, c in enumerate(text.upper()):
                if c not in self.ignored_chars:
                    if c not in curr_dict:
                        return longest, offset
                    curr_dict = curr_dict[c]
                    if 'end' in curr_dict:
                        longest, offset = curr_dict['end'], i + 1
    
            return longest, offset
    
    
    # tester
    if __name__ == '__main__':
    
        brands = ['Huawei', 'OPPO', 'VIVO', 'Xiaomi', 'Xiao', 'HTC', 'Oneplus']
        model_name = 'xiaomi mix3'
        brand_lookup = Trie(brands)
    
        brand, offset = brand_lookup.extract_longest_item(model_name)
        print(brand, offset)
    

    通过自己写代码理解Trie之后,也可以使用Google的开源实现  https://github.com/google/pygtrie

    展开全文
  • #coding=utf-8 #字典嵌套牛逼,别人写的,这样每一层非常多的东西,搜索就快了,高26.所以整体搜索一个不关多大的单词表 #还是O(1). ''' Python 字典 setdefault() 函数和get() 方法类似, 如果键不存在于字典中,将...
    #coding=utf-8  #字典嵌套牛逼,别人写的,这样每一层非常多的东西,搜索就快了,树高26.所以整体搜索一个不关多大的单词表
    #还是O(1).
    '''
    Python 字典 setdefault() 函数和get() 方法类似, 如果键不存在于字典中,将会添加键并将值设为默认值。
    说清楚就是:如果这个键存在字典中,那么这句话就不起作用,否则就添加字典里面这个key的取值为后面的默认值.
    简化了字典计数的代码.并且这个函数的返回值是做完这些事情之后这个key的value值.
    dict.setdefault(key, default=None)
    Python 字典 get() 函数返回指定键的值,如果值不在字典中返回默认值。
    dict.get(key, default=None)
    '''
    class Trie:  
        root = {}  
        END = '/'  #加入这个是为了区分单词和前缀,如果这一层node里面没有/他就是前缀.不是我们要找的单词.
        def add(self, word):  
            #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志  
            node = self.root  
            for c in word:  
                node=node.setdefault(c,{})  #利用嵌套来做,一个trie树的子树也是一个trie树.
                                            #利用setdefault的返回值是value的特性,如果找到了key就进入value
                                            #没找到,就建立一个空字典然后
            node[self.END] = None          #当word都跑完了,就已经没有字了.那么当前节点也就是最后一个字母的节点
                                            #加一个属性标签end.这个end里面随意放一个value即可.因为我们判定只是
                                            #判定end这个key是否在字典里面.
                                            #考虑add 同一个单词2次的情况,第二次add 这个单词的时候,因为用setdefault
                                            #add里面的话都不对原字典进行修改.正好是我们需要的效果.
                                            
                                            #这个self.END很重要,可以作为信息来存储.比如里面可以输入这个单词的
                                            #起源,发音,拼写,词组等作为信息存进去.找这个单词然后读出单词的信息.
      
        def find(self, word):  
            node = self.root  
            for c in word:  
                if c not in node:  
                    return False  
                node = node[c]  
            return self.END in node  
        def associate_find(self, pre):  #搜索引擎里面的功能是你输入东西,不关是不是单词,他都输出以这个东西为前缀
                                           #的单词.
            node = self.root  
            for c in pre:  
                if c not in node:  
                    return []  #因为字典里面没有pre这个前缀
                node = node[c]  #有这个前缀就继续走,这里有个问题就是需要记录走过的路径才行.
            #运行到这里node就是最后一个字母所表示的字典.
    #举一个栗子:图形就是{a,b,c}里面a的value是{b,c,d} d的value是{/,e,f} 那么/代表的单词就是ad,看这个形象多了
            #首先看这个字母所在的字典有没有END,返回a这个list
    
            
    
            #然后下面就是把前缀是pre的单词都加到a里面.
            #应该用广度遍历,深度遍历重复计算太多了.好像深度也很方便,并且空间开销很小.
            #广度不行,每一次存入node,没用的信息存入太多了.需要的信息只是这些key是什么,而不需要存入node.
            #但是深度遍历,又需要一个flag记录每个字母.字典的key又实现不了.
            #用函数递归来遍历:只能先用这个效率最慢的先写了
            #因为你遍历一直到底,到底一定是'/'和None.所以一定bianli出来的是单词不是中间结果.
            def bianli(node):#返回node节点和他子节点拼出的所有单词
                if node==None:
                    return ['']
                a=[]#现在node是/ef
                
                for i in node:
                    tmp=node[i]
                    tmp2=bianli(tmp)
                    for j in tmp2:
    
                      a.append(i+j)
                return a
            output=bianli(node)
            for i in range(len(output)):
                output[i]=(pre+output[i])[:-1]
            return output
    
    
    
    
    
    
    
    
    
    
    
        def delete(self, word):#字典中删除word
            node = self.root  
            for c in word:  
                if c not in node:  
                    print('字典中没有不用删')
                    return False  
                node = node[c]  
            #如果找到了就把'/'给他删了就行了
            del node['/']  
            #后面还需要检索一遍,找一下是否有前缀的后面没有单词的.把前缀的最后一个字母也去掉.因为没单词了,前缀也没意义存在了.
            #也就是说最后一个字母这个节点,只有'/',删完如果是空的就把这个节点也删了.
            while node=={}:
                if word=='':
                    return 
                tmp=word[-1]
                word=word[:-1]
                node = self.root  
                for c in word:  
                  node = node[c]
                del node[tmp]
    
    
    a=Trie()
    
    (Trie.END)#python这个也是吊,类方法和类属性:自动也是对象的方法或者属性!
    a.add('apple')
    a.add('appl')
    a.delete('apple')
    
    print(a.find('apple'))
    print(a.root)#发现完美的解决了删除功能.删除apple因为没有其他单词了就把整个字典删了
    #下面我打算加一个功能就是词汇联想功能,输入a,输出a,ab,abc.就是把a后面的字典里面的所有的单词就输出出来.
    
    
    #两个字典的key相同,id就相同.真坑.用id区分不了2个取值相同的不同元素.
    #my={'a':{}}
    #print(type(my))
    #my['a']={'a':{'/'}}
    #for i in my:
    #   print(id(i))
    #   a=my[i]
    #   for j in a:
    #       print(id(j))
    View Code

    把问题写下来:

    对于插入删除还是挺满意的,就是前缀这个功能效率貌似太低了.因为是函数迭代所以会产生大量的重复计算.但是字典里面又不能随机访问.id对于重复字母会冲突.flag也不好弄.

    想到的唯一方法就是建立一个class node.把数据放到node里面.然后node里面再装入一个字典.就是把字典封装一下,带一个flag功能(或者直接手动给一个id计数).来记录所有记录过的值,建立一个memo字典来避免重复计算.

    继续想法还有:智能联想,根据单词出现的频率来输出数据.  任意片段联想,写单词中间的一个片段来联想所有能匹配的.还没想到太好的方法.这个任意片段,如果bianli所有字典就感觉太慢了.但是不这么做又会感觉结果不全.先做这么多,后面还有  

    双数组Trie树(DoubleArrayTrie)  需要实现.

    听9章算数直通bat课程的老师说腾讯考过双数组trie树.

    https://www.cnblogs.com/studyhs/p/5443767.html

    太牛逼的东西完全没看懂.

    只看懂,他本质是一个4*n的数组,通过里面的整数进行下表索引.就能很快找到单词.类似字典查询.

    只需要把单个中文字进行编码.然后通过编码和这个数组进行查询就能找到任意词汇所在的位置.然后可以再建立一个数组存信息即刻.

     

    #coding=utf-8  #字典嵌套牛逼,别人写的,这样每一层非常多的东西,搜索就快了,树高26.所以整体搜索一个不关多大的单词表
    #还是O(1).
    '''
    Python 字典 setdefault() 函数和get() 方法类似, 如果键不存在于字典中,将会添加键并将值设为默认值。
    说清楚就是:如果这个键存在字典中,那么这句话就不起作用,否则就添加字典里面这个key的取值为后面的默认值.
    简化了字典计数的代码.并且这个函数的返回值是做完这些事情之后这个key的value值.
    dict.setdefault(key, default=None)
    Python 字典 get() 函数返回指定键的值,如果值不在字典中返回默认值。
    dict.get(key, default=None)
    '''
    class Trie:  
        root = {}  
        END = '/'  #加入这个是为了区分单词和前缀,如果这一层node里面没有/他就是前缀.不是我们要找的单词.
        def add(self, word):  
            #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志  
            node = self.root  
            for c in word:  
                node=node.setdefault(c,{})  #利用嵌套来做,一个trie树的子树也是一个trie树.
                                            #利用setdefault的返回值是value的特性,如果找到了key就进入value
                                            #没找到,就建立一个空字典然后
            node[self.END] = None          #当word都跑完了,就已经没有字了.那么当前节点也就是最后一个字母的节点
                                            #加一个属性标签end.这个end里面随意放一个value即可.因为我们判定只是
                                            #判定end这个key是否在字典里面.
                                            #考虑add 同一个单词2次的情况,第二次add 这个单词的时候,因为用setdefault
                                            #add里面的话都不对原字典进行修改.正好是我们需要的效果.
                                            
                                            #这个self.END很重要,可以作为信息来存储.比如里面可以输入这个单词的
                                            #起源,发音,拼写,词组等作为信息存进去.找这个单词然后读出单词的信息.
      
        def find(self, word):  
            node = self.root  
            for c in word:  
                if c not in node:  
                    return False  
                node = node[c]  
            return self.END in node  
        def associate_find(self, pre):  #搜索引擎里面的功能是你输入东西,不关是不是单词,他都输出以这个东西为前缀
                                           #的单词.
            node = self.root  
            for c in pre:  
                if c not in node:  
                    return []  #因为字典里面没有pre这个前缀
                node = node[c]  #有这个前缀就继续走,这里有个问题就是需要记录走过的路径才行.
            #运行到这里node就是最后一个字母所表示的字典.
    #举一个栗子:图形就是{a,b,c}里面a的value是{b,c,d} d的value是{/,e,f} 那么/代表的单词就是ad,看这个形象多了
            #首先看这个字母所在的字典有没有END,返回a这个list
    
            
    
            #然后下面就是把前缀是pre的单词都加到a里面.
            #应该用广度遍历,深度遍历重复计算太多了.好像深度也很方便,并且空间开销很小.
            #广度不行,每一次存入node,没用的信息存入太多了.需要的信息只是这些key是什么,而不需要存入node.
            #但是深度遍历,又需要一个flag记录每个字母.字典的key又实现不了.
            #用函数递归来遍历:只能先用这个效率最慢的先写了
            #因为你遍历一直到底,到底一定是'/'和None.所以一定bianli出来的是单词不是中间结果.
            def bianli(node):#返回node节点和他子节点拼出的所有单词
                if node==None:
                    return ['']
                a=[]#现在node是/ef
                
                for i in node:
                    tmp=node[i]
                    tmp2=bianli(tmp)
                    for j in tmp2:
    
                      a.append(i+j)
                return a
            output=bianli(node)
            for i in range(len(output)):
                output[i]=(pre+output[i])[:-1]
            return output
    
    
    
    
    
    
    
    
    
    
    
        def delete(self, word):#字典中删除word
            node = self.root  
            for c in word:  
                if c not in node:  
                    print('字典中没有不用删')
                    return False  
                node = node[c]  
            #如果找到了就把'/'给他删了就行了
            del node['/']  
            #后面还需要检索一遍,找一下是否有前缀的后面没有单词的.把前缀的最后一个字母也去掉.因为没单词了,前缀也没意义存在了.
            #也就是说最后一个字母这个节点,只有'/',删完如果是空的就把这个节点也删了.
            while node=={}:
                if word=='':
                    return 
                tmp=word[-1]
                word=word[:-1]
                node = self.root  
                for c in word:  
                  node = node[c]
                del node[tmp]
    
    
    a=Trie()
    
    (Trie.END)#python这个也是吊,类方法和类属性:自动也是对象的方法或者属性!
    a.add('我是')
    a.add('我是草拟吗')
    
    
    print(a.find('我是'))
    print(a.root)#发现完美的解决了删除功能.删除apple因为没有其他单词了就把整个字典删了
    #下面我打算加一个功能就是词汇联想功能,输入a,输出a,ab,abc.就是把a后面的字典里面的所有的单词就输出出来.
    
    
    #两个字典的key相同,id就相同.真坑.用id区分不了2个取值相同的不同元素.
    #my={'a':{}}
    #print(type(my))
    #my['a']={'a':{'/'}}
    #for i in my:
    #   print(id(i))
    #   a=my[i]
    #   for j in a:
    #       print(id(j))
    
    #下面分析为什么中文要用双数组trie树,英文用trie树,英文里面每一个小dic至多27个数据.也就是26个字母加上'/'
    '''
    这样如果假设每一个字母组合都是单词的话,空间是26**len(word).假设word长度常用为8.但是事实上也就是
    12**8 差不多了.结果4亿个字母.换算空间的话.就400M空间而已.
    
    下面分析中文:常用字2千个,每个字组词匹配算15个基本够了,词组长度基本不超过4个.才一亿个汉字,常用的转码是一个
    汉字2个字节.所以才2亿个字节.也就200M空间.但是为什么说trie树存汉字词组空间不够?
    
    
    https://segmentfault.com/a/1190000008877595
    这个链接完美解决了上面问题
    '''
    View Code

    原来是hash的效率对于大数据还是不够快.比O(1)实际上要慢很多.空间也消耗大.

    不说废话了:总之:一定要弄好双数组树.他真正使用的方法是查询.这个绝对是O(1)了.简直快的不行!实际应用都是把数据直接学习完毕,不会插入和删除太多.所以

    双数组trie树是最好的选择:他在分词和机器学习里面对字符处理超重要.

     

     

    '''
    https://segmentfault.com/a/1190000008877595#articleHeader7
    5.4.2 Base Array 的构造
    看这里面写的还真不难,之前一直没看懂,是因为他数据没有显示写入.
    其实还有一个数组用来写入数据.比如
    这里面第一步之后的data数组变成了
    data[2]=''
    data[3]=''
    data[7]=''
    这样通过他的步骤,做到最后就是3个数组,data,base,check3个数组来
    表示这个2array trie.就能方便找到每一个词组了.
    '''
    View Code

     呕心沥血之作 DAT 双数组trie树

    '''
    
    ps:#a=[i*i for i in range(5) if i<3 ]  #python for if 的一行写法.
    https://segmentfault.com/a/1190000008877595#articleHeader7
    5.4.2 Base Array 的构造
    看这里面写的还真不难,之前一直没看懂,是因为他数据没有显示写入.
    其实还有一个数组用来写入数据.比如
    这里面第一步之后的data数组变成了
    data[2]=''
    data[3]=''
    data[7]=''
    这样通过他的步骤,做到最后就是3个数组,data,base,check3个数组来
    表示这个2array trie.就能方便找到每一个词组了.
    但是写起来简直吐血.
    
    首先看最终得到的结果如何使用它来找到所有的词组:
    
    字典:''清华”、“清华大学”、“清新”、“中华”、“华人”
    编码:清-1,华-2,大-3,学-4,新-5,中-6,人-7
    
    数组下表:0    1   2   3   4   5   6   7   8   9   10
    base数组:13   2   2   3   6   2   3   2    6
    
    1.使用:找清华:首先从base[0]出发.清在的位置是base[0]+code(清)=下表为2的地方
               清的base数组不是负数,说明有继续拓展的本事.所以找下一个词华可以找.
               华=他上一个节点的base值+code(华)=3+2=5.所以就找到了清华在我们字典里面存在
           找清华大学:上面华找到了,继续找大=base(华)+code(大)=5(注意是清华的华,所以是上面找到的3)+3=6
                      继续找学=base[6]+code(学)=10.所以清华大学找到了.
      继续细化:叶子节点的处理:将词的最后一个节点的转移基数统一改为某个负数
               所以 数组下表:0    1   2   3   4   5    6    7    8    9   10
                    base数组:13   2   -2   -3   6   2   -3   -2    -6
              这样做的代价就是需要将状态转移函数base[s]+code(字符)改为|base[s]|+code(字符)
              重新跑一次清华:上来还是清=1+1=2   华=3+2=5  然后看base[5]=-3 ,所以可以到此结束来组成一个词汇.
              但是我们还可以继续跑
              来找清华大学:从华找大:大=|-3|+code(大)=6,base[6]不是负数,不能输出.
                          继续找学:学=6+4=10,他的base是-6.所以可以输出.
      加入check数组来解决bug:比如找'清中':找清我们到了3,找中我们到了9.base[9]=-2.所以我们输出'清中'是一个词汇.
                            这显然是错误的!所以我们要加入check数组来避免这种匹配.这种bug的原因是中这个词前面
                            不能是清这个字.用check数组来记录这个位置前面一个字符所在的index.
              所以 数组下表:0    1   2   3   4   5    6    7    8    9   10
                   base数组:13   2   -2   -3   6   2   -3   -2    -6
                   check  :-3   -1   0   0   7   2     5   0   2    3     6
                   这样找清中:清是到了index2.判断check是不是清的上一个节点.是0(0表示根)没问题.
                             找中找到index9.然后需要判断check[9]是不是他过来的节点的index.发现一个是2,一个是3
                             所以不对.输出清中不存在.
    2.搭建:
    https://blog.csdn.net/kissmile/article/details/47417277
    这个写的也是不错.但是他搭建的顺序有一点错误,按照层搭建,第五部分应该是搭建第一层的b后面的c节点.
    逻辑基本就是这样,能讲清楚就不错了.基本达到智商110以上了.能代码实现感觉智商上150了.
    因为比较复杂,还是先写伪代码.再实现.
                              
    
    题目:建立字典:字典:''清华”、“清华大学”、“清新”、“中华”、“华人”
    伪代码过程:
    ●a=[''清华”、“清华大学”、“清新”、“中华”、“华人”],b=sum([len(i) for i in a])
    ●对set(a)进行编码:清-1,华-2,大-3,学-4,新-5,中-6,人-7
    ●建立首字集合c:清,中,华
    ●为了数组足够长,建立base=[0]*b  check=[0]*b
    ●把c插入双数组,对base[0]赋予初值1.(其实赋予2也一样,貌似更好,因为初值1基本都会发生冲突,会降低建立速度)
     对新建立的base里面也放入1.
     把c插入后:
     数组下表:0    1   2   3   4   5   6   7   8   9   10
     base数组:1    0   1   1   0   0   0   1    0   0    0
     check  :0    0   0   0   0   0   0   0    0   0    0
    
    ●下面就是插入第二个字:华,新,华,人(第一个华,表示清后面的华,虽然他有2个但是前面都是清,所以只插入一个,这就是为什么
     Trie树节省空间的原因).
     下面插入清后面的字:有华和新(对于同一个字的后面的字要一起考虑,因为可能要修改这同一个的base数组)
     从2开始跑,华=base[2]+code(华)=3.冲突了因为3里面已经有了.
     所以base[2]+=1.这时再算华=4了.不冲突了.
     插入新又冲突了.所以清要继续加1.插入后的新元素base还是置1.(但是网上写的是置清现在的base值.我感觉没必要啊!!!!)
     也就是下图5,8我都置1,但是网上置的是3.(下面通过我的计算,我置1最后还是为了解决冲突而加到3了.
     难道置3能减少冲突的发生?问题是会不会空间浪费太多?)(利用树来看就是树的第n层的偏移量一定比第n-1层的至少一样或者多)
     (为什么?)(我认为是从概率上来讲,每一个字符边上的字符数量都一样,所以你上个字母需要偏移3个才能不冲突,
     你也至少需要偏移3个.减少代码运行时间.要知道处理冲突非常非常慢!!!!!)
     同时把check也更新了,也就是把清的index 2放进去.
     得到:
     
     数组下表:0    1   2   3   4   5   6   7   8   9   10
     base数组:1    0   3   1   0   1   0   1    1   0    0
     check  : 0    0   0   0   0   2   0   0    2   0    0
     
     
     (!!!!!!这里面就是遇到一个问题非常重要.搭建时候一定要多行一起搭建,也就是按照root的一层来搭建.把一层都弄好
     再弄下一层,原因就是我们最后需要得到的树是一个公共前缀只保存一次的树!也是问题的根本,不保持的话这个trie树
     完全没意义了,所以公共前缀保持同时处理,所以只能这样按照root的层来搭建才可以.)
     同理插入中后面的字:7的base+=1.得到:
     数组下表:0    1   2   3   4   5   6   7   8   9   10
     base数组:1    0   3   1   1   1   0   2    1   0    0
     check  : 0    0   0   0   7   2   0   0    2   0    0
    
     同理华人:得到:
     数组下表:0    1   2   3   4   5   6   7   8   9   10
     base数组:1    0   3   2   1   1   0   2    1   1    0
     check  : 0    0   0   0   7   2   0   0    2   3    0
    
    
     第三层.
     得到:
     数组下表:0    1   2   3   4   5   6   7   8   9   10
     base数组:1    0   3   2   1   3   1   2    1   1    0
     check  : 0    0   0   0   7   2   5   0    2   3    0
    
      第四层.
     得到:
     数组下表:0    1   2   3   4   5   6   7   8   9   10
     base数组:1    0   3   2   1   3   6   2    1   1    1
     check  : 0    0   0   0   7   2   5   0    2   3    6
    
    
    
     总结:难度不比红黑树简单.
    '''
    class DAT():
        def __init__(self,data):#通过这个函数返回self.base和self.check 2个数组
            #对data预处理:
            firststep=[]
            max_ceng=0#数据有多少层
            for i in data:
                a=0
                for j in i:
                    firststep.append(j)
                    a+=1
                if a>max_ceng:
                    max_ceng=a
            all_len=len(firststep)
            mono_len=len(set(firststep))
    
            #用字典进行编码.用数组太慢了,因为数组里面搜索是O(N)
            bianma={}
            ma=1
            tmp=[]
            for i in firststep:#这里面去重,为了测试先这么写保顺序,写好后再改用set来加速
                if i not in tmp:
                    tmp.append(i)
            for i in tmp:
                if i not in bianma:
                   bianma[i]=ma
                   ma+=1
            #我为了方便把''作为root,给他bianma 是0,然后base[0]=1
            bianma['']=0#只是为了递归写起来代码更简洁而已.自我感觉很简约.
            #初始化base 和check
            base=['#']*all_len  #虽然相同也不要用等号给check赋值base,因为list赋值是浅拷贝,传的是地址
            base[0]=1
            check=['#']*all_len
            #打印一下编码看看,因为字典是乱序的,每一次生成都不同,所以打印一下来验算自己做的对不对.
            print(bianma)
            self.bianma=bianma
            #开始建立:
            #建立是按照第一列,...,最后一列这个顺序进行递归的.
            #提取当前列的set后元素.
            #第一列可以看做''空字符开始的后面一个元素.
            #提取第一列:然后再递归修改成提取第i列
            
    
            before=''
            col_now=[i[len(before)] for i in data if before in i]#提取有before前缀的字符的下一个小字符.#第一层就是清,华,中
            tmp=[]
            for i in col_now:
                if i not in tmp:
                    tmp.append(i)
            col_now=tmp
            print('第一列')
            print(col_now)
            #开始计算col_now里面的字符的base
            before_index=bianma[before]#其他层不是这么算的.
            now_layer_save_for_data=[]#为了下一层的递推而记录的文字信息
            now_layer_save_for_base=[]#为了下一层的递推而记录的index信息
            for i in col_now:
                
                while 1:
                 index=base[before_index]+bianma[i]
                 if base[index]=='#':#说明没有人占用
                     base[index]=base[before_index]
                     check[index]=before_index
                     now_layer_save_for_data.append(i)
                     now_layer_save_for_base.append(index)
                     break
                 else:
                     base[before_index]+=1
            last_layer=1
            print('第一层')
            print(base)#测试后第一层建立成功.
            print(check)
            print(max_ceng)
            print(now_layer_save_for_data)
            print(now_layer_save_for_base)
            #还是先写递推的写法,递归的写法想不清楚.
            #建立layer信息
            layer1={}
            for i in range(len(data)):
              for jj in range(len(now_layer_save_for_data)):
                j=now_layer_save_for_data[jj]
                j2=now_layer_save_for_base[jj]#光用汉字来做key会发生无法区分清华,中华这种bug.
                if data[i][0]==j:
                    layer1.setdefault((j,j2),[])
                    layer1[(j,j2)].append(i)
            #用layer1,data里面的信息,对base里面信息进行加工,也就是如果单字就取反
            for i in layer1:
                if i[0] in data:
                    base[i[1]]=-base[i[1]]
    
    
    
    
            #搭建第二层:先找到将要被搭建的字
            #利用last_layer和now_layer_save_for_data和now_layer_save_for_base来找.
            now_layer=last_layer+1
            
            #for i in range(len(now_layer_save_for_data)):
            #    tmp=now_layer_save_for_data[i]#tmp就是清
            #    id=now_layer_save_for_base[i]#id 就是清的base数组里面的值
                #找到清后面的字,也就是data里面第一个字为清的字.如果每建立一个节点就遍历一遍会是至少O(N方),并且
                #基本严格大于这个数字,太大了.我想法是一层的东西同时处理,这样一层只遍历一次.降到线性搜索.
                #对于同时一堆if,显然效率不行,所以还是字典来替代多if并列.还是慢,想到用类似线段树的手段来记录.
                #里面的每一层用一个字典来表示,一个value是一个list
            #根据layer1建立layer2
            layer=layer1
            print(layer)
            #下面就可以建立layer2了#从这里就能分析出为什么要把上一层有同一个前缀的都建立完再弄下一个.
            #下面整合起来是从一个layer得到这个层的全base数组和check数组.可以封装起来for循环.
            for iii in range(1,max_ceng):
                now_layer=iii+1
                layer4={}
                print(layer)  #layer1:{('', 2): [0, 1, 2], ('', 7): [3], ('', 3): [4]}
                
                for i in layer:
                    lastword=i[0]
                    lastindex=i[1]
                    beixuan=layer[i]
                    #找到应该插入哪个
                    charu=[]
                    #把beixuan里面长度不够的剔除,他长度不够其实就表示已经在上一步是词组了.
                    beixuan2=[]
                    for i in beixuan :
                        if len(data[i])>=now_layer:
                            beixuan2.append(i)
                    beixuan=beixuan2
    
                    for i in beixuan:
                        newword=data[i][now_layer-1]
                        if newword not in charu:
                            charu.append(newword)
                    #把charu里面的东西进入base,check算法中
    
                    now_layer_save_for_data=[]#为了下一层的递推而记录的文字信息
                    now_layer_save_for_base=[]#为了下一层的递推而记录的index信息
                    col_now=charu #插入华,新
                    before_index=abs(lastindex)
                    for i in col_now:
                
                        while 1:
                         index=abs(base[before_index])+bianma[i]
                         if base[index]=='#':#说明没有人占用
    
                             break
                         else:
                             if base[before_index]>0:
                              base[before_index]+=1
                             else:
                                 base[before_index]-=1
                             print(base)
                    #对于已经构成词汇的词语base里面的数要取相反数.
                    beixuanciku=[data[i][now_layer-1:] for i in beixuan]
                #调试状态vs2017把鼠标放变量上就能看到他的取值,很放方便.任意位置都能看
                    for i in col_now:
                        if i in beixuanciku:
                            index=abs(base[before_index])+bianma[i]
                            base[index]=-abs(base[before_index])#注意这地方不能写-要写-abs
                            check[index]=before_index
                            now_layer_save_for_data.append(i)
                            now_layer_save_for_base.append(index)
                        else:
                            index=abs(base[before_index])+bianma[i]
                            base[index]=base[before_index]
                            check[index]=before_index
                            now_layer_save_for_data.append(i)
                            now_layer_save_for_base.append(index)
                
    
                    #更新layer
    
                    for i in beixuan:
                     for jj in range(len(now_layer_save_for_data)):
                        j=now_layer_save_for_data[jj]
                        j2=now_layer_save_for_base[jj]#光用汉字来做key会发生无法区分清华,中华这种bug.
                        if data[i][now_layer-1]==j:
                            layer4.setdefault((j,j2),[])
                            layer4[(j,j2)].append(i)
    
    
            #已经得到了新的layer4,替换回去,为了递推.
                layer=layer4
                 
                
    
    
    
    
    
    
    
    
    
    
    
                
            #打印上个layer
            print(layer)     #{('', 2): [0, 1, 2], ('', 7): [3], ('', 3): [4]} 上个layeer信息
            #下面需要更新layer
            layernew={}
            for i in layer:#逐个计算里面的对儿即可.比如先计算('', 2): [0, 1, 2]应该改成什么
              pass
    
    
              #for jj in range(len(now_layer_save_for_data)):
              #  j=now_layer_save_for_data[jj]
              #  j2=now_layer_save_for_base[jj]#光用汉字来做key会发生无法区分清华,中华这种bug.
              #  if data[i][0]==j:
              #      layer1.setdefault((j,j2),[])
              #      layer1[(j,j2)].append(i)
    
    
    
    
    
    
    
            print(now_layer_save_for_data)
            print(now_layer_save_for_base)
    
    
    
            print('测试')#第二列也zhengque 
            #经过我2天超过20个小时的学习和写代码,写出了这个例子的base数组和check数组.修改些小bug就可以了.
            #绝逼不比红黑树简单.网上也几乎没有代码实现.因为我主题layer是从第一层建立后针对2到n层开始建立的
            #所以第一层如果是单字,直接返回这种情况,我还没写,但是相对盖起来简单.
            print(base)
            print(check)
            #最后的最后,用self把结果传出去
            self.base=base
            self.check=check
                         
            
    
    
    
    
    
                     
    
    
            
    
    
        def search(self,a):#通过这个函数a在data是否存在,这个函数随便玩了
            
            tmp=0
            #self写起来太麻烦,
            bianma=self.bianma
            base=self.base
            check=self.check
            i=a[0]
            if len(a)==1:
                tmp=1+bianma[i]
                return base[tmp]<0
            else:
                first=1+bianma[a[0]]
                for i in range(len(a)-1):
                    tmp=abs(base[first])+bianma[a[i+1]]
                    if check[tmp]!=first:
                        return False
                    first=tmp
                return base[tmp]<0
            
    '''
    base:[1, '#', -3, 2, -2, -3, -6, 2, -3, -2, -6, '#', '#']
    check:['#', '#', 0, 0, 7, 2, 5, 0, 2, 3, 6, '#', '#']
    '''
    
    
    
    
    
    #测试:
    a=DAT(['清华','清华大学','清新','中华','华人',''])
    #进行search测试
    print(a.search('清华大学'))
    #经过测试,稍微大一点的数据也是能跑出来的.
    View Code
    对上面代码加入给前缀找全部符合前缀的单词也很容易.其实就是layer层的东西.直接提取layer这个字典选一下即可.

     自信可改变未来,问谁又能做到,简单不过的道理,又是最难做到的道理

    转载于:https://www.cnblogs.com/zhangbo2008/p/9082012.html

    展开全文
  • Python实现Trie树

    2018-06-13 11:00:23
    Python实现Trie树的应用,并可以对英汉词典进行导入和检索、添加和删除,最终可以将导入的英汉词典保存到本地磁盘。内附两个.py文件,分别是tree.py和d_gui.py,tree.py是类和方法,d_gui.py是图形界面;一个.txt...
  • 这段代码的目的是实现TRIE字典结构,是来自<a href="https://blog.csdn.net/leitingvre/article/details/106782449">https://blog.csdn.net/leitingvre/article/details/106782449</a>的代码,先行...
  • 今天学习到了Trie树 字典树的详细定义可以看Trie树Stackoverflow上的简洁实践在trie树中查找单词单词的压缩编码(leetcode) Stackoverflow上的简洁实践 How to create a trie in Python class Trie: def __init__...

    今天学习到了Trie树
    字典树的详细定义可以看

    Stackoverflow上的简洁实践

    How to create a trie in Python

    class Trie:
        def __init__(self):
           self._end = '_end_'
    
        def make_trie(self,*words):
            root = dict()
            for word in words:
                current_dict = root
                for letter in word:
                    current_dict = current_dict.setdefault(letter,{})
                current_dict[self._end] = self._end
            return root
    
    if __name__ == '__main__':
        trie = Trie()
        print(trie.make_trie('foo', 'bar', 'baz', 'barz'))
    

    控制台输出

    {'f': {'o': {'o': {'_end_': '_end_'}}}, 
    'b': {'a': {'r': {'_end_': '_end_', 'z': {'_end_': '_end_'}}, 'z': {'_end_': '_end_'}}}}
    

    在trie树中查找单词

    class Trie:
        def __init__(self):
           self._end = '_end_'
    
        def make_trie(self,*words):
            root = dict()
            for word in words:
                current_dict = root
                for letter in word:
                    current_dict = current_dict.setdefault(letter,{})
                current_dict[self._end] = self._end
            return root
    
        def in_trie(self,trie,word):
            current_dict = trie
            for letter in word:
                if letter not in current_dict:
                    return False
                current_dict = current_dict[letter]
            return self._end in current_dict
    
    if __name__ == '__main__':
        trie = Trie()
        print(trie.make_trie('foo', 'bar', 'baz', 'barz'))
        print(trie.in_trie(trie.make_trie('foo', 'bar', 'baz', 'barz'),'bar'))
        # output: True
    

    单词的压缩编码(leetcode)

    给定一个单词列表,我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。

    例如,如果这个列表是 [“time”, “me”, “bell”],我们就可以将其表示为 S = “time#bell#” 和
    indexes = [0, 2, 5]。

    对于每一个索引,我们可以通过从字符串 S 中索引的位置开始读取字符串,直到 “#” 结束,来恢复我们之前的单词列表。

    那么成功对给定单词列表进行编码的最小字符串长度是多少呢?

    示例:

    输入: words = [“time”, “me”, “bell”] 输出: 10 说明: S = “time#bell#” ,
    indexes = [0, 2, 5] 。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/short-encoding-of-words
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    我觉得leetcode的官方实现才是最6的,pythonic极致

    class Solution:
        def minimumLengthEncoding(self, words: List[str]) -> int:
            words = list(set(words)) #去重
            # Trie是带有已创建节点的嵌套字典
            # 当其中缺少节点时会创建节点
            Trie = lambda: collections.defaultdict(Trie)
            trie = Trie()
    
            #reduce(..., S, trie) is trie[S[0]][S[1]][S[2]][...][S[S.length - 1]],将单词反序插入
            nodes = [reduce(dict.__getitem__, word[::-1], trie)
                     for word in words]
    
            #如果节点没有邻居节点,则添加该单词
            return sum(len(word) + 1
                       for i, word in enumerate(words)
                       if len(nodes[i]) == 0)
    
    作者:LeetCode-Solution
    链接:https://leetcode-cn.com/problems/short-encoding-of-words/solution/dan-ci-de-ya-suo-bian-ma-by-leetcode-solution/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    奇怪的知识又增加了哈哈哈~
    今早还学习到了

    set.discard(ele)# 可以移除集合中不存在的元素
    
    展开全文
  • 字典常用做高效的文本词语保存,适用于敏感词过滤、关键词提取等场景。... 实现1:通过python自带的字典结构 具有如下基本功能: (1)根据一组words进行TrieTree的构建 (2)添加某个word (3)查询某个word

    字典树常用做高效的文本词语保存,适用于敏感词过滤、关键词提取等场景。在字典树中相同前缀的词之间共享相同的树节点和路径。

    字典树结构一般包括如下功能和属性:(1)构建;(2)添加;(3)删除;(4)前缀统计;(5)搜索

    • 实现一:通过字典的嵌套来实现
    class Trie(object):
        """
        实现1:通过python自带的字典结构
        具有如下基本功能:
        (1)根据一组words进行TrieTree的构建
        (2)添加某个word
        (3)查询某个word
        (4)删除某个word
        """
        def __init__(self):
            self.trie = {}
            self.count = 0
    
        def __repr__(self):
            return str(self.trie)
    
        def buildTree(self, wordList):
            for word in wordList:
                t = self.trie             # 指向各节点的指针,初始化为root节点
                for w in word:
                    if w not in t:
                        t[w] = {'count': 0}
                    t[w]['count'] += 1
                    t = t[w]
    
                self.count += 1
                t['end'] = 1
    
        def add(self, word):
            t = self.trie
            for w in word:
                if w not in t:
                    t[w] = {'count': 0}
                t[w]['count'] += 1
                t = t[w]
    
            self.count += 1
            t['end'] = 1
    
        def delete(self, word):
            # 仅仅改变end和count属性,字符串仍存在于存储中
            # 先确定是否存在,若存在沿着的每条路径的count都需要-1
            if not self.search(word):
                return False
    
            t = self.trie
            for w in word:
                t = t[w]
                t['count'] -= 1
    
            self.count -= 1
            t['end'] = 0
    
    
        def search(self, word):
            t = self.trie
            for w in word:
                if w not in t:
                    return False
                t = t[w]
            if t.get('end') == 1:
                return True
            return False
    
        def prefix_count(self, prefix):
            t = self.trie
            for w in prefix:
                if w not in t:
                    return -1
                t = t[w]
            return t['count']
    
    • 实现二:通过递归的节点类实现
    class Trie(object):
        """
        另一种实现
        Trie可视作一种递归结构
        """
        def __init__(self, depth=0):
            self.children = {}             # {key: Trie()},   key为每个层级对应的字符
            self.depth = depth           # 在整个字典树中的层级,root为0,因此可以视为word的长度
            self.end = False             # word终止标志
            self.count = 0               # 以当前节点前序子串为前缀的word数量
            self.words = []
    
        def __repr__(self):
            return str(self.words)
    
        def insert(self, word: str) -> None:
            cur = self
            cur.count += 1
            for w in word:
                if w not in cur.children:
                    cur.children[w] = Trie(cur.depth+1)
                cur = cur.children[w]
                cur.count += 1
                cur.words.append(word)
    
            cur.end = True
    
        def buildTree(self, words: list) -> None:
            for word in words:
                self.insert(word)
    
        def prefix(self, pref):
            cur = self
            for p in pref:
                if p not in cur.children:
                    return None
                cur = cur.children[p]
            return cur.words
    
        def search(self, word):
            cur = self
            for w in word:
                if w not in cur.children:
                    return False
                cur = cur.children[w]
            if cur.end:
                return True
            else:
                return False
    
        def remove(self, word):
            if not self.search(word):
                return False
            cur = self
            cur.count -= 1
            for w in word:
                cur = cur.children[w]
                cur.count -= 1
            cur.end = False
    
    
    展开全文
  • Python笔记:Trie树结构简介 Python笔记:Trie树结构简介 1. Trie树是什么 2. Trie树原理 3. Trie树代码实现 4. Leetcode例题分析 1. Leetcode 208. Implement Trie (Prefix Tree) 2. Leetcode 211. Design Add ...
  • datrie, 快速高效的python 存储Trie树 使用 libdatrie datrie 超快速。高效的python ( 2.x 和 3. x ) 存储 Trie 。 使用 libdatrie 。安装pip install datrie用法创建一个新的trie,可以存储小写
  • python3 Trie树及其应用

    2020-03-22 17:12:50
    关于前缀基础知识就不介绍了,通俗总结就是从根节点出发,每个节点都有两个属性,一个是这个节点的所有子节点(python3用一个字典记录这个节点所有后续节点即可)和一个标志,标志是否是一个字符串的结束。...
  • Trie树的介绍网上已经有很多了,不懂的同学自行去学习昂! 下面实现Trie树: class Trie: def __init__(self): self.root = {} # 这里用一个字典存储 self.end_of_word = '#' # 用#标志一个单词的结束 ...
  • 双端trie树python实现 版本翻译于 将其改写成python3.5版本 最主要的贡献是 —— 1:实现了其模糊查询的功能;2:自定义编码值,解决双端trie树需要预定义字母表的问题 另外,有实现了字典Trie树,字典Trie树构建...
  • 飘逸的python - 实现trie树

    万次阅读 2014-11-24 15:56:21
    Trie树中每个单词都是通过character by character方法进行存储,相同前缀单词共享前缀节点. 可以看到,每条路径组成一个单词.上面这颗树存了to/tea/ted/ten/inn这些词. 性质 (1)根节点不包含字符,...
  • 原题 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 示例 1: 输入: [“flower”,“flow”,“flight”] ...利用Trie树实现 class TrieNode(object): # 利用Python定义...
  • Trie树 python代码实现

    2019-11-08 15:35:29
    重要的是了解什么是Trie树,前缀树,这个数的应用还是挺多的,将字符串组成的路径记录下来,以此来快速 查找具有同一前缀的字符串! 首先Trie树的每个节点本身不存储字符,是整个树的路径信息存储字符,每个...
  • 有字符串go, golang, php, python, perl,它这棵Trie树可如下图所示构造: 我们来分析下上面这张图。除了根节点外,每个子节点只存储一个字符。go和golang共享go前缀,php、perl和python只共用p前缀。为了实现...
  • 使用python实现了一个简单的trie树结构,可增加/查找/删除关键词,用于中文的关键词匹配
  • Trie树

    2019-03-07 23:09:28
    Trie树 别称:字典树 树形结构,专门处理字符串匹配的数据结构,解决在一组字符串集合中快速查找某个字符串的问题。 样例: 搜索引擎的提示功能,当搜索东西时,并不用把所有内容都输入进去,一定程度上节省了搜索...
  • Trie树学习及python实现

    2021-04-07 06:08:22
    字典(Trie),又称单词查找或键,是一种形结构,是一种哈希的变种。 应用:统计和排序大量的字符串(但不仅限于字符串),经常被搜索引擎系统用于文本词频统计、前缀匹配用来搜索提示,也常用于计算左右信息...
  • Trie树python实现

    2016-03-21 18:34:50
    class TrieNode: def __init__(self): self.children = {} self.flag = None class Trie: def __init__(self): self.root = TrieNode() def add(self,s): curNode = se
  • 一.trie树应用: 常用于搜索提示,如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。 例如三个单词app, apple, add,我们按照以下规则创建了一颗Trie树.对于从树...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,228
精华内容 1,291
关键字:

pythontrie树

python 订阅