MENU

字典树

May 20, 2018 • 文章

一:背景

字典树,又称前缀树(英文名:Trie Tree),为Edward Fredkin发明。

举个例子,给出一些单词,(and,as,at,cn,com),则其字典树如下:

从上图可以发现,它有3个基本性质:

  1. 根结点不包含字符,除根结点外每一个结点都只包含一个字符。
  2. 从根结点到某一结点,路径上经过的字符连接起来,为该结点对应的字符串。
  3. 每个结点的所有子结点包含的字符都不相同。

字典树是一个很重要的数据结构,其主要应用为:

  1. 词频统计:例如,给定一个由10万个单词组成的库,现要你判断一个单词是否有在库中出现,若出现,求出共出现多少次。
  2. 前缀匹配:以上图为例,如果想获取所有以"a"开头的字符串,那么从图中可以很明显的看到是:(and,as,at)。因此利用这个特性,可以巧妙地实现搜索提示功能,如输入一个网址,可以自动列出可能的选择。当没有完全匹配的搜索结果,可以列出前缀最相似的可能。

二:算法过程分析

共实现三个对外接口:

  1. void add(char * s);:将字符串s添加至字典树;
  2. int query(char * s);:查询字符串s是否存在。若存在,返回其存在的次数;若不存在,返回0;
  3. bool remove(char * s);:删除字符串s。字符串s若存在,则直接删除,返回真;若不存在,则返回假。

结点结构如下:

#define TREE_WIDTH 26

struct Node
{
    int path;
    int end;
    char ch;
    Node * next[TREE_WIDTH];
    Node(char ch = ' ')
    {
        this->ch = ch;
        this->path = this->end = 0;
        for (int i = 0; i < TREE_WIDTH; i++)
            this->next[i] = nullptr;
    }
};

本文只讨论小写26个英文字母的字典集合,故TREE_WIDTH设为26。

变量end的作用,标记该结点是否是单词结尾。变量path则用来记录结点被路径覆盖的次数。

请注意,下述代码针对的是动态数据集,即一系列添加,查询,删除三种混合操作。因此对于已无路径覆盖的结点,我们并不会释放其内存,这也是引入path的原因(当path = 0,表示该结点已无路径覆盖)。

两个变量的具体使用如下图:

三:完整代码

#include <iostream>

#define TREE_WIDTH 26

using namespace std;

struct Node
{
    int path;
    int end;
    char ch;
    Node * next[TREE_WIDTH];
    Node(char ch = ' ')
    {
        this->ch = ch;
        this->path = this->end = 0;
        for (int i = 0; i < TREE_WIDTH; i++)
            this->next[i] = nullptr;
    }
};

class TrieTree
{
private:
    Node * root;
public:
    TrieTree();
    ~TrieTree();
    void destroy(Node * t);
    void add(char * s);
    int query(char * s);
    bool remove(char * s);
};

TrieTree::TrieTree()
{
    root = new Node;
}

TrieTree::~TrieTree()
{
    destroy(root);
    root = nullptr;
}

void TrieTree::destroy(Node * t)
{
    for (int i = 0; i < TREE_WIDTH; i++)
        if (t->next[i])
            destroy(t->next[i]);
    delete t;
}

void TrieTree::add(char * s)
{
    Node * t = root;
    while (*s)
    {
        if (t->next[*s - 'a'] == nullptr)
            t->next[*s - 'a'] = new Node(*s);
        t->next[*s - 'a']->path++;
        t = t->next[*s - 'a'];
        s++;
    }
    t->end++;
}

int TrieTree::query(char * s)
{
    Node * t = root;
    while (*s)
    {
        if (t->next[*s - 'a'] == nullptr || t->next[*s - 'a']->path == 0)
            return 0;
        t = t->next[*s - 'a'];
        s++;
    }
    return t->end;
}

bool TrieTree::remove(char * s)
{
    if (query(s))
    {
        Node * t = root;
        while (*s)
        {
            t->next[*s - 'a']->path--;
            t = t->next[*s - 'a'];
            s++;
        }
        t->end--;
        return true;
    }

    return false;
}

int main()
{
    TrieTree tree;

    tree.add("strawberry");
    tree.add("grandfather");
    tree.add("policeman");
    tree.add("breakfast");
    tree.add("mutton");
    tree.add("bus");
    tree.add("bus");
    tree.add("bustop");
    tree.add("computer");

    // test "query"
    cout << tree.query("bud") << endl; // 0
    cout << tree.query("bus") << endl; // 2

    // test "remove"
    tree.remove("bustop");
    cout << tree.query("bustop") << endl; // 0
    tree.remove("bus");
    cout << tree.query("bus") << endl;    // 1
    tree.remove("bus");
    cout << tree.query("bus") << endl;    // 0

    return 0;
}

四:不足之处

字典树中的每个结点,其内部都有一个指针数组,若取数组长度为128,则在树完全展开后需要的内存是非常恐怖的,这也就是字典树在实际工程中需谨慎使用的原因。

Archives QR Code Tip
QR Code for this page
Tipping QR Code