特里算法 ||使用 Javascript 自动完成功能

IT行业相对于一般传统行业，发展更新速度更快，一旦停止了学习，很快就会被行业所淘汰。所以我们需要踏踏实实的不断学习，精进自己的技术，尤其是初学者。今天golang学习网给大家整理了《特里算法 ||使用 Javascript 自动完成功能》，聊聊，我们一起来看看吧！

介绍

trie，也称为前缀树，是一种专门的基于树的数据结构，用于高效的信息检索。

它对于涉及字符串内搜索和前缀匹配的用例特别有用。

1. 如果我告诉你 trie 算法，你可能会对这个算法感兴趣，也可能不感兴趣

2. 但是如果我告诉你你可以使用它创建一个自动完成算法。你会更兴奋地学习这个。

该算法的用例

1.自动完成：

a。搜索引擎或文本编辑器中经常使用尝试来实现自动完成功能。
b.当您开始输入时，应用程序会根据您输入的前缀建议可能的补全。

2.拼写检查器：

a。尝试可用于实现拼写检查器。如果某个单词不存在于 trie 中，则它可能是拼写错误的。
b.特里树还可以通过查找相似的单词来建议更正。

3. ip路由：

a。尝试在路由器中用于存储路由表。
b.路由器使用 trie 来匹配最长前缀，这决定了数据包的下一跳。

4.高效存储和搜索字符串：

a。如果您有一个包含大量共享前缀的字符串数据集，则 trie 可以使用比单独存储它们更少的空间来存储这些字符串。
b. 搜索操作也很高效，时间复杂度与您要搜索的字符串的长度成正比。

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

class Trie {
    constructor() {
        this.root = new Node ();
    }

    insert(word) {
        let head = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!head.children[word[i]]) {
                head.children[word[i]] = new Node();
            }
            head = head.children[word[i]];
        }
        head.end = true;
    }

    search(word){
        let current = this.root;

        for (let i = 0; i < word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]]
        }

        return true;
    }

    autoComplete(word) {
        let current = this.root;

        for (let i = 0; i< word.length; i++) {
            if (!current.children[word[i]]) {
                return false;
            }
            current = current.children[word[i]];
        }
        if (Object.keys(current.children).length === 1) {
            console.log('Please Type More...');
            return;
        }
        console.log('children =---> ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word+key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

如果您有任何疑虑/疑问，请随时与我联系。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~