Trie树 – 代码补全和搜索提示实现

Trie

前缀树是一个N叉树

字符串间相同前缀是同一路径

用于预测字符串、字符串存取、拼写检查和词频统计等

类实现

数组节点

class Trie
{
    private:
        Trie *child[26];
        int num;
 
    public:
        Trie(){ num = 0; memset(child, 0, sizeof(child)); };
        int get(string s);
        void put(string s);
};

迭代存储统计前缀数目

void Trie::put(string s)
{
    Trie *p = this;
    for (int i = 0; s[i]; i++)
    {
        int ch = s[i] - 'a';
        if (p->child[ch] == nullptr)
            p->child[ch] = new Trie();
        p->num++;
        p = p->child[c];
    }
}

迭代匹配前缀数

int Trie::get(string s)
{
    Trie *p = this;
    for (int i = 0; s[i]; i++)
    {
        int ch = s[i] - 'a';
        if (p->child[ch] == nullptr)
            return 0;
        p = p->child[ch];
    }
    return p->num;
}

map节点

struct Node
{
    unordered_map<char, Node *> map;
    int num;
};
 
class Trie
{
    private:
        Node *root;
        void put(Node *n, string s, int i);
        int get(Node *n, string s, int i);
 
    public:
        Trie() { root = new Node(); }
        void put(string s);
        int get(string s);
};

递归存储统计

void Trie::put(string s) { put(root, s, 0); };

void Trie::put(Node *n, string s, int i)
{
    n->num++;
    if (!s[i]) return;
    if (n->map.count(s[i]) <= 0)
        n->map[s[i]] = new Node();
    n = n->map[s[i]];
    put(n, s, ++i);
}

递归取出统计

int Trie::get(string s) { return get(root, s, 0); };

int Trie::get(Node *n, string s, int i)
{
    if (!s[i] && i != 0) return n->num;
    if (n->map.count(s[i]) <= 0) return 0;
    n = n->map[s[i]];
    return get(n, s, ++i);
}

数组实现

除0行每个元素表示对应单字符前缀的父节点外，数组每行均代表一个子节点，每新增一个子节点就存在数组下一行中，父节点通过子节点行索引链接子节点，相比类实现更省内存

子链接ID可唯一标识父节点表示的前缀，父前缀统计数目存储在 $$\textbf{\scriptsize num[子链接ID]}$$若以父节点所在行数作为标识，则0行无法区分各单字符前缀数目

const int MAX_NUM = 10000;
const int CHAR_NUM = 26;
int Trie[MAX_NUM][CHAR_NUM];
int num[MAX_NUM];
int rowNum = 0;

迭代存储统计前缀数目

void put(string s)
{
    int childRowNum = 0;
    for (int i = 0; s[i]; i++)
    {
        int ch = s[i] - 'a';
        if (Trie[childRowNum][ch] == 0)
            Trie[childRowNum][ch] = ++rowNum;
        childRowNum = Trie[childRowNum][ch];
        num[childRowNum]++;
    }
}

迭代匹配前缀数

int get(string s)
{
    int childRowNum = 0;
    for (int i = 0; s[i]; i++)
    {
        int ch = s[i] - 'a';
        childRowNum = Trie[childRowNum][ch];
        if (childRowNum == 0) return 0;
    }
    return num[childRowNum];
}

朴素字典序代码补全实现

原理实际是匹配前缀的所有字符串，先序遍历Trie树可实现字典序

(待续

朴素词频序搜索提示实现

(待续