特里算法 ||使用 Javascript 自动完成功能-js教程-PHP中文网

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

PHPz

发布： 2024-08-23 13:57:05

转载

999人浏览过

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

介绍

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

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

如果我告诉你 trie 算法，你可能会对这个算法感兴趣，也可能不感兴趣
但是如果我告诉你你可以使用它创建一个自动完成算法。你会更兴奋地学习这个。

立即学习“Java免费学习笔记（深入）”；

该算法的用例

ReportPlus数据报表中心小程序

ReportPlust意在打造一套精美的数据报表模板，里面高度封装日历组件、表格组件、排行榜组件、条形进度条组件、文本块组件以及ucharts的多个图表组件，用户只需要按照虚拟数据的格式，传特定数据即可方便、快捷地打造出属于自己的报表页面。该小程序主要使用了ucharts和wyb-table两插件实现的数据报表功能。特点使用的是uni-app中最受欢迎的图表uCharts插件完成图表展示，该插件

查看详情

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
*/

登录后复制

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

以上就是特里算法 ||使用 Javascript 自动完成功能的详细内容，更多请关注php中文网其它相关文章！