This article mainly introduces examples of javascript trie word search trees. It introduces the concept and implementation of trie in detail. It has certain reference value. Interested friends can refer to it. I hope it can help everyone.
Introduction
Trie tree (from the word retrieval), also known as prefix word, word search tree, dictionary tree, is a tree structure, a kind of haha A variant of the Greek tree, a multi-tree structure used for fast retrieval.
Its advantage is: it minimizes unnecessary string comparisons and has higher query efficiency than hash tables.
The core idea of Trie is to exchange space for time. Use the common prefix of strings to reduce query time overhead to improve efficiency.
Trie tree also has its shortcomings. Assuming that we only process letters and numbers, then each node has at least 52+10 child nodes. To save memory, we can use linked lists or arrays. In JS, we use arrays directly, because JS arrays are dynamic and come with built-in optimization.
Basic properties
The root node does not contain characters, and each child node except the root node contains one character
From the root node to a certain node. The characters passing through the path are connected to form the string corresponding to the node
All sub-nodes of each node contain different characters
Program Implementation
// by 司徒正美
class Trie {
constructor() {
this.root = new TrieNode();
}
isValid(str) {
return /^[a-z1-9]+$/i.test(str);
}
insert(word) {
// addWord
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
var node = cur.son[c];
if (node == null) {
var node = (cur.son[c] = new TrieNode());
node.value = word.charAt(i);
node.numPass = 1; //有N个字符串经过它
} else {
node.numPass++;
}
cur = node;
}
cur.isEnd = true; //樯记有字符串到此节点已经结束
cur.numEnd++; //这个字符串重复次数
return true;
} else {
return false;
}
}
remove(word){
if (this.isValid(word)) {
var cur = this.root;
var array = [], n = word.length
for (var i = 0; i < n; i++) {
var c = word.charCodeAt(i);
c = this.getIndex(c)
var node = cur.son[c];
if(node){
array.push(node)
cur = node
}else{
return false
}
}
if(array.length === n){
array.forEach(function(){
el.numPass--
})
cur.numEnd --
if( cur.numEnd == 0){
cur.isEnd = false
}
}
}else{
return false
}
}
preTraversal(cb){//先序遍历
function preTraversalImpl(root, str, cb){
cb(root, str);
for(let i = 0,n = root.son.length; i < n; i ++){
let node = root.son[i];
if(node){
preTraversalImpl(node, str + node.value, cb);
}
}
}
preTraversalImpl(this.root, "", cb);
}
// 在字典树中查找是否存在某字符串为前缀开头的字符串(包括前缀字符串本身)
isContainPrefix(word) {
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return false;
}
}
return true;
} else {
return false;
}
}
isContainWord(str) {
// 在字典树中查找是否存在某字符串(不为前缀)
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return false;
}
}
return cur.isEnd;
} else {
return false;
}
}
countPrefix(word) {
// 统计以指定字符串为前缀的字符串数量
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return 0;
}
}
return cur.numPass;
} else {
return 0;
}
}
countWord(word) {
// 统计某字符串出现的次数方法
if (this.isValid(word)) {
var cur = this.root;
for (var i = 0; i < word.length; i++) {
var c = word.charCodeAt(i);
c -= 48; //减少”0“的charCode
if (cur.son[c]) {
cur = cur.son[c];
} else {
return 0;
}
}
return cur.numEnd;
} else {
return 0;
}
}
}
class TrieNode {
constructor() {
this.numPass = 0;//有多少个单词经过这节点
this.numEnd = 0; //有多少个单词就此结束
this.son = [];
this.value = ""; //value为单个字符
this.isEnd = false;
}
}Let’s focus on the insert method of TrieNode and Trie. Since the dictionary tree is mainly used for word frequency statistics, it has many node attributes, including numPass, numEnd but very important attributes.
The insert method is used to insert repeated words. Before starting, we must determine whether the word is legal and special characters and blanks cannot appear. When inserting, characters are broken up and placed into each node. numPass must be modified every time it passes a node.
Optimization
Now in each of our methods, there is an operation of c=-48. In fact, there are other characters between numbers, uppercase letters, and lowercase letters, so It will cause unnecessary waste of space
// by 司徒正美
getIndex(c){
if(c < 58){//48-57
return c - 48
}else if(c < 91){//65-90
return c - 65 + 11
}else {//> 97
return c - 97 + 26+ 11
}
}Then the relevant method is to change c-= 48 to c = this.getIndex(c)
Test
var trie = new Trie();
trie.insert("I");
trie.insert("Love");
trie.insert("China");
trie.insert("China");
trie.insert("China");
trie.insert("China");
trie.insert("China");
trie.insert("xiaoliang");
trie.insert("xiaoliang");
trie.insert("man");
trie.insert("handsome");
trie.insert("love");
trie.insert("Chinaha");
trie.insert("her");
trie.insert("know");
var map = {}
trie.preTraversal(function(node, str){
if(node.isEnd){
map[str] = node.numEnd
}
})
for(var i in map){
console.log(i+" 出现了"+ map[i]+" 次")
}
console.log("包含Chin（包括本身）前缀的单词及出现次数：");
//console.log("China")
var map = {}
trie.preTraversal(function(node, str){
if(str.indexOf("Chin") === 0 && node.isEnd){
map[str] = node.numEnd
}
})
for(var i in map){
console.log(i+" 出现了"+ map[i]+" 次")
}
Comparison of Trie trees and other data structures
Trie tree and binary search tree
The binary search tree should be the earliest tree structure we come into contact with. We know that when the data size is n, the binary search tree inserts, searches, and deletes operations. The time complexity is usually only O(log n). In the worst case, all nodes of the entire tree have only one child node, which degenerates into a linear table. At this time, the time complexity of insertion, search, and deletion operations is O( n).
Normally, the height n of the Trie tree is much greater than the length m of the search string, so the time complexity of the search operation is usually O(m), and the time complexity in the worst case is O (n). It is easy to see that the worst-case search in a Trie tree is faster than a binary search tree.
The Trie tree in this article uses strings as examples. In fact, it has strict requirements on the suitability of the key. If the key is a floating point number, the entire Trie tree may be extremely long and the nodes may be The readability is also very poor. In this case, it is not suitable to use Trie tree to save data; this problem does not exist with binary search tree.
Trie tree and Hash table
Consider the problem of Hash conflict. We usually say that the complexity of a Hash table is O(1). In fact, strictly speaking, this is the complexity of a Hash table that is close to perfect. In addition, we also need to consider that the hash function itself needs to traverse the search string, and the complexity is O(m ). When different keys are mapped to the "same position" (considering closed hashing, this "same position" can be replaced by an ordinary linked list), the complexity of the search depends on the number of nodes under the "same position" number, therefore, in the worst case, the Hash table can also become a one-way linked list.
Trie trees can be sorted according to the alphabetical order of keys more easily (the entire tree is traversed once in order), which is different from most Hash tables (Hash tables generally have different keys for different keys). is disordered).
Under ideal circumstances, the Hash table can quickly hit the target at O(1) speed. If the table is very large and needs to be placed on the disk, the search access of the Hash table will be faster under ideal circumstances. It only needs to be done once; but the number of disk accesses by the Trie tree needs to be equal to the node depth.
Many times a Trie tree requires more space than a Hash table. If we consider the situation where one node stores one character, there is no way to save it as a separate block when saving a string. . Node compression of the Trie tree can significantly alleviate this problem, which will be discussed later.
Improvement of Trie tree
Bitwise Trie tree (Bitwise Trie)
The principle is similar to the ordinary Trie tree, except that the ordinary Trie tree stores The smallest unit is a character, but Bitwise Trie stores only bits. The access of bit data is directly implemented once by the CPU instruction. For binary data, it is theoretically faster than the ordinary Trie tree.
Node compression.
Branch compression: For a stable Trie tree, basically search and read operations, some branches can be compressed. For example, the inn of the rightmost branch in the previous figure can be directly compressed into a node "inn" without existing as a regular subtree. The Radix tree is based on this principle to solve the problem of the Trie tree being too deep.
Node mapping table: This method is also used when the nodes of the Trie tree may have been almost completely determined. For each state of the node in the Trie tree, if the total number of states is repeated many times, through an element Represented as a multi-dimensional array of numbers (such as Triple Array Trie), the space overhead of storing the Trie tree itself will be smaller, although an additional mapping table is introduced.
Application of prefix tree
The prefix tree is still easy to understand, and its application is also very wide.
(1) Fast retrieval of strings
The query time complexity of the dictionary tree is O(logL), L is the length of the string. So the efficiency is still relatively high. Dictionary trees are more efficient than hash tables.
(2) String sorting
From the above figure we can easily see that the words are sorted, and the alphabetical order is traversed first. Reduce unnecessary common substrings.
(3) The longest common prefix
The longest common prefix of inn and int is in. When traversing the dictionary tree to letter n, the common prefix of these words is in.
(4) Automatically match prefixes and display suffixes
When we use a dictionary or search engine, enter appl, and a bunch of stuff with the prefix of appl will automatically be displayed. Then it may be achieved through a dictionary tree. As mentioned earlier, the dictionary tree can find the common prefix. We only need to traverse and display the remaining suffixes.
Related recommendations:
About uery EasyUI combined with ztrIee’s background page development tutorial
About dictionary tree Trie in php Example of implementation definition method
Word PHP implements Trie tree (dictionary tree)
The above is the detailed content of Detailed explanation of javascript trie prefix tree code. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
