【TS】用typescript实现前缀树(字典树)

介绍

前缀树,也称为Trie树,是一种有序树结构,专门设计用于存储字符串数据以便进行高效检索。它的主要应用包括:

  1. 字符串匹配:通过构建前缀树,可以快速进行字符串匹配,特别是在需要查找以特定前缀开头的单词或字符串时,前缀树能够显著提高检索效率。
  2. 统计以特定前缀开头的单词数量:前缀树可以用于统计以特定前缀开头的单词数量,这对于语言处理、信息检索等领域非常有用。
  3. 替换单词:前缀树还可以用于实现替换单词的功能,这在自然语言处理和文本编辑中非常有用。

前缀树的构建基于字符的频率和顺序,通过将字符串按照其字符序列构建成树状结构,每个节点代表一个字符,从根节点到某一节点的一条路径就代表一个字符串。这种数据结构使得对于具有相同前缀的字符串查询变得非常高效,因为只需要沿着树的一条路径进行查找即可。此外,前缀树还可以用于解决诸如单词之和等问题,通过插入和查询操作,可以快速统计以特定前缀开头的单词数量,这对于需要处理大量字符串数据的场景非常有用

代码

// 前缀树字符,一个前缀树字符包含一个码元(或者若干个码点)
type TrieChar = string;

/**
 * 前缀树节点
 */
class TrieNode {
    // 这个字符串出现的次数
    count: number = 0;
    // 子节点
    readonly children: Map<TrieChar, TrieNode> = new Map();
}

/**
 * 前缀树
 */
class TrieTree {
    // 根节点
    private readonly _root: TrieNode = new TrieNode();

    /**
     * 插入字符串
     * @param str
     */
    insert(str: string): boolean {
        if (str == null) {
            return false;
        }
        let node: TrieNode = this._root;
        // 这里需要用for of,不然可能会分割多长度的字符比如emoji表情
        for (const char of str) {
            if (node.children.has(char)) {
                node = node.children.get(char);
            } else {
                const newNode: TrieNode = new TrieNode();
                node.children.set(char, newNode);
                node = newNode;
            }
        }
        node.count++;
        return true;
    }

    /**
     * 是否存在这个字符串
     * @param str
     */
    has(str: string): boolean {
        if (str == null) {
            return false;
        }
        let node: TrieNode = this._root;
        for (const char of str) {
            node = node.children.get(char);
            if (node == null) {
                return false;
            }
        }
        return node.count > 0;
    }

    /**
     * 是否包含以这个字符串开头的字符串
     * @param str
     */
    startsWith(str: string): boolean {
        if (str == null) {
            return false;
        }
        let node: TrieNode = this._root;
        for (const char of str) {
            node = node.children.get(char);
            if (node == null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 筛选以此字符串开头的字符串
     * @param str
     */
    search(str: string): string[] {
        const results: string[] = [];
        if (str == null) {
            return results;
        }
        let node: TrieNode = this._root;
        let path: string = "";
        for (const char of str) {
            node = node.children.get(char);
            if (node == null) {
                return results;
            }
            path += char;
        }
        this._forEach(node, path, (str) => {
            results.push(str);
        });
        return results;
    }

    /**
     * 获取字符串出现的次数
     * @param str
     */
    count(str: string): number {
        if (str == null) {
            return 0;
        }
        let node: TrieNode = this._root;
        for (const char of str) {
            node = node.children.get(char);
            if (node == null) {
                return 0;
            }
        }
        return node.count;
    }

    /**
     * 移除字符串
     * @param str
     * @param count 移除次数,默认为1,如果为-1则移除所有
     */
    remove(str: string, count: number = 1): boolean {
        if (str == null) {
            return false;
        }
        let node: TrieNode = this._root;
        const path: { char: TrieChar; node: TrieNode }[] = [{ char: null, node }];
        for (const char of str) {
            node = node.children.get(char);
            if (node == null) {
                return false;
            }
            path.push({ char, node });
        }
        if (node.count <= 0) {
            return false;
        }
        if (count < 0) {
            // 移除所有
            node.count = 0;
        } else {
            node.count -= count;
        }
        if (node.count > 0 || node.children.size > 0) {
            return true;
        }
        node.count = 0;
        let next: { char: TrieChar; node: TrieNode } = path[path.length - 1];
        for (let i = path.length - 2; i >= 0; i--) {
            const pre: { char: TrieChar; node: TrieNode } = path[i];
            if (next.node.count === 0) {
                pre.node.children.delete(next.char);
            } else {
                break;
            }
            next = pre;
        }
        return true;
    }

    /**
     * 遍历所有存入的字符串,遍历顺序优先为从短到长、其次为插入顺序<br>
     * 遍历方式为广度优先遍历
     * @param cb 回调函数内容:存入的字符串、次数、TrieTree自身
     */
    forEach(cb: (str: string, count: number, source: this) => void): void {
        this._forEach(this._root, "", cb);
    }

    private _forEach(node: TrieNode, path: string, cb: (str: string, count: number, source: this) => void): void {
        const queue: { node: TrieNode; path: string }[] = [{ node, path }];
        while (queue.length > 0) {
            const { node, path } = queue.shift();
            if (node.count > 0) {
                cb(path, node.count, this);
            }
            for (const [char, childNode] of node.children) {
                queue.push({ node: childNode, path: path + char });
            }
        }
    }

    /**
     * 将TrieTree转换为JSON格式,key为存入的字符串,value为存入次数
     */
    toJson(): { [key: string]: number } {
        const json: { [key: string]: number } = {};
        this.forEach((str, count) => {
            json[str] = count;
        });
        return json;
    }

    /**
     * 将TrieTree转换为字符串
     */
    toString(): string {
        return JSON.stringify(this.toJson());
    }
}

测试

const tree: TrieTree = new TrieTree();
tree.insert("hello");
tree.insert("hello");
tree.insert("hello1");
tree.insert("😎😎😎");
tree.insert("😎114514");
tree.insert("abc");
tree.remove("abc");

console.log(tree.has("😎😎😎")); // true
console.log(tree.startsWith("😎")); // true
console.log(tree.search("h")); // [ 'hello', 'hello1' ]
console.log(tree.count("hello")); // 2
tree.forEach((str: string, count: number, source: TrieTree) => {
    console.log(str, count);
    // 😎😎😎 1
    // hello 2
    // hello1 1
    // 😎114514 1
});
console.log(tree.toString()); // {"😎😎😎":1,"hello":2,"hello1":1,"😎114514":1}

说明

  1. 使用ts/js实现的前缀树效率不高,不如直接遍历;
  2. 内存消耗较大,数据量较大时可能导致进程崩溃;
  3. 本前缀树支持emoji表情、中文;
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,772评论 6 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,458评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,610评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,640评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,657评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,590评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,962评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,631评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,870评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,611评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,704评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,386评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,969评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,944评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,179评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,742评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,440评论 2 342

推荐阅读更多精彩内容