算法笔记之trie树

一个保存了8个键的trie结构

图片来自维基百科

介绍

trie,又称前缀树/字典树/单词查找树,是一种有序树

Trie的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的

上图图示说明

图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机。键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trie的原理

读音

trie的发明者Edward Fredkin把它读作英语发音:"tree"。但是,其他作者把它读作英语发音:"try"。

基本特性

  • 根结点不包含字符,除根节点意外每个结点只包含一个字符
  • 从根结点到某个结点,经过的字符连接起来,为该结点对应的字符串
  • 每个节点的所有子节点包含的字符都不相同

基本操作

基本操作有:查找、插入和删除,当然删除操作比较少见

应用

典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串)

trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能

在我们做NLP中命名实体识别(NER),采用字典法时,可能会用到trie-tree作为快速搜索算法

可视化

C语言实现

#define MAX 26//字符集大小
typedef struct TrieNode
{
    int nCount;//记录该字符出现次数
    struct TrieNode* next[MAX];
}TrieNode;

TrieNode Memory[1000000];
int allocp=0;

/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
    *pRoot=NULL;
}

/*创建新结点*/
TrieNode* CreateTrieNode()
{
    int i;
    TrieNode *p;
    p=&Memory[allocp++];
    p->nCount=1;
    for(i=0;i<MAX;i++)
    {
        p->next[i]=NULL;
    }
    return p;
}

/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
    inti,k;
    TrieNode*p;
    if(!(p=*pRoot))
    {
        p=*pRoot=CreateTrieNode();
    }
    i=0;
    while(s[i])
    {
        k=s[i++]-'a';//确定branch
        if(!p->next[k])
            p->next[k]=CreateTrieNode();
                p->next[k]->nCount++;
        p=p->next[k];
    }
}

//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
    TrieNode *p;
    int i,k;
    if(!(p=*pRoot))
    {
        return0;
    }
    i=0;
    while(s[i])
    {
        k=s[i++]-'a';
        if(p->next[k]==NULL) return 0;
        p=p->next[k];
    }
    return p->nCount;
}

python描述

""" Tries in python
Methods -  insert_key(k, v)
           has_key(k)
           retrie_val(k)
           start_with_prefix(prefix)
"""


def _get_child_branches(trie):
    """
    Helper method for getting branches
    """
    return trie[1:]


def _get_child_branch(trie, c):
    """
    Get branch matching the character
    """
    for branch in _get_child_branches(trie):
        if branch[0] == c:
            return branch

    return None


def _retrive_branch(k, trie):
    """
    Get branch matching the key word
    """
    if not k:
        return None

    for c in k:
        child_branch = _get_child_branch(trie, c)
        if not child_branch:
            return None
        trie = child_branch

    return trie


def _is_trie_bucket(bucket):
    if len(bucket) != 2:
        return False

    return type(bucket[1]) is tuple


def _get_bucket_key(bucket):
    if not _is_trie_bucket(bucket):
        return None

    return bucket[1][0]


def has_key(k, trie):
    """
    Check if trie contain the key word
    """
    return _retrive_branch(k, trie) is not None


def retrie_val(k, trie):
    key_tuple = _retrive_branch(k, trie)
    if not key_tuple:
        return None

    return key_tuple[1]


def insert_key(key, v, trie):
    """
    Insert a (key, value) pair into trie
    """
    if not key or has_key(key, trie):
        return

    for char in key:
        branch = _get_child_branch(trie, char)
        if not branch:
            new_branch = [char]
            trie.append(new_branch)
            trie = new_branch
        else:
            trie = branch
    trie.append((key, v))


def start_with_prefix(prefix, trie):
    """
    Find words start with prefix
    """
    branch = _retrive_branch(prefix, trie)
    if not branch:
        return []

    prefix_list = []
    q = branch[1:]
    while q:
        curr_branch = q.pop(0)
        if _is_trie_bucket(curr_branch):
            prefix_list.append(_get_bucket_key(curr_branch))
        else:
            q.extend(curr_branch[1:])

    return prefix_list
使用
trie = [[]]
states = """
            Alabama
            Alaska
            Arizona
            Arkansas
            California
            Colorado
            Connecticu
            Hawaii
            Idaho
            Illinois
            Indiana
            Maine
            Maryland
            Massachusetts
            Michigan
            Minnesota
            Mississippi
            Missouri
            Montana
"""
states_list = [w.strip().lower() for w in states.splitlines() if w]
for state in states_list:
    insert_key(state, True, trie)
print start_with_prefix("new", trie)

参考




Fork me on GitHub