介绍
前缀树，也称为Trie树，是一种有序树结构，专门设计用于存储字符串数据以便进行高效检索。它的主要应用包括：
- 字符串匹配：通过构建前缀树，可以快速进行字符串匹配，特别是在需要查找以特定前缀开头的单词或字符串时，前缀树能够显著提高检索效率。
- 统计以特定前缀开头的单词数量：前缀树可以用于统计以特定前缀开头的单词数量，这对于语言处理、信息检索等领域非常有用。
- 替换单词：前缀树还可以用于实现替换单词的功能，这在自然语言处理和文本编辑中非常有用。
前缀树的构建基于字符的频率和顺序，通过将字符串按照其字符序列构建成树状结构，每个节点代表一个字符，从根节点到某一节点的一条路径就代表一个字符串。这种数据结构使得对于具有相同前缀的字符串查询变得非常高效，因为只需要沿着树的一条路径进行查找即可。此外，前缀树还可以用于解决诸如单词之和等问题，通过插入和查询操作，可以快速统计以特定前缀开头的单词数量，这对于需要处理大量字符串数据的场景非常有用
代码
// 前缀树字符，一个前缀树字符包含一个码元（或者若干个码点）
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}
说明
- 使用ts/js实现的前缀树效率不高，不如直接遍历；
- 内存消耗较大，数据量较大时可能导致进程崩溃；
- 本前缀树支持emoji表情、中文；
