字典树

一.核心思想

Trie tree，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。字典树的查询时间复杂度是O (L)，L是待查字符串的长度。如果是普通的线性表结构，那么查询效率为O（NL），N为待查数据集的大小。

假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词,那我们创建字典树如下：

二.应用

目的：利用汉语拼音缩写还原中文汉字

准备：数据集（包含中文汉字以及对应汉语缩写）

思想：1.基于汉语拼音缩写检索出数据集中对应的所有中文汉字 2.基于中文汉字出现频次排序，将top1作为汉语拼音的还原结果

代码

import  pandas as pd
import pickle
import os
import joblib

class TrieNode(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = {}###字母字符
        self.data1={}###中文
        self.is_word = False###标识是否汉字


class Trie(object):

    def __init__(self):
        self.root = TrieNode()

    def insert(self, word,word1):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        node = self.root
        for letter in word:
            child = node.data.get(letter)
            if not child:
                node.data[letter] = TrieNode()
            node = node.data[letter]
        node.is_word = True
        if word1 not in node.data1:
            node.data1[word1]=1
        else:
            node.data1[word1]+=1

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        node = self.root
        for letter in word:
            node = node.data.get(letter)
            if not node:
                return False
        return node.is_word

    def starts_with(self, prefix):
        """
        Returns if there is any word in the trie
        that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        node = self.root
        for letter in prefix:
            node = node.data.get(letter)
            if not node:
                return False
        return True

    def get_start(self, prefix):
        """
        Returns words started with prefix
        :param prefix:
        :return: words (list)
        """
        def _get_key(pre, pre_node):
            words_list = []
            if pre_node.is_word:
                words_list.append([pre,pre_node.data1])
            for x in pre_node.data.keys():
                words_list.extend(_get_key(pre + str(x), pre_node.data.get(x)))
            return words_list

        words = []
        if not self.starts_with(prefix):
            return words
        # if self.search(prefix):
        #     words.append(prefix)
        #     return words
        node = self.root
        for letter in prefix:
            node = node.data.get(letter)
        return _get_key(prefix, node)


    def find_result(self,string):
        result =self.get_start(string)
        result = sort_by_value(result[0][1])
        result.reverse()
        return result[0]
    
    
def sort_by_value(d):
    return sorted(d.items(), key=lambda k: k[1])  # k[1] 取到字典的值。



def build_tree(data,save_path):

    trie = Trie()
    for element in data.values:
        trie.insert(element[0], element[1])
    joblib.dump(trie, save_path)
    return

def load_tree(path):
    trie = joblib.load(path)
    return trie

if __name__ == '__main__':

    ###
    build_tree(data,save_path)
    ###
    tree=load_tree(save_path)
    print(tree.find_result("XXXXXXXX"))

参考

https://zhuanlan.zhihu.com/p/28891541