JavaScript -- 搜索引擎的关键字提示功能（字典树）

布满荆棘的人生 2022-02-20 18:13 198阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70][]

如上图，类似Google，百度这样的搜索引擎的关键字提示功能，你知道是怎么实现的吗？

虽然它们可能实现的比较复杂，考虑到情况比较多，但是归根结底就是一种数据结构Trie树，又称字典树。

首先我们先大体认识一下，知道它是一棵树。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70 1][]

现在当然看不出什么东西，最直观的感觉就是一棵多叉树而已，那么上面那棵树是如何形成的了？

这是输入hello hi her how see so这些单词构成的一棵字典树。我们发现从第二层的根节点出发，到每一个叶子节点的路径上面的字母的和就是一个单词！！！（顶层根节点不考虑）

如下是详细过程，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70 2][]

是不是非常简单，没错，字典树就是这么简单，当我们加入某个单词的时候，我们从第一个字母从字典树的根节点出发，查询下一层是否存在这个字母，如果存在那么就沿着这个节点往下走，并且处理下个字母，如果不存在，那么我们就添加一个新的节点（value为当前字母）并且沿着新节点继续处理下一个字母。

那么字典树有什么作用了？字典树对于查询前缀相同的字符串十分高效。

譬如我们查询前缀为h的字符串时，从h到每个叶子节点就是一个单词。这正好应用到搜索引擎的提示功能。

光说不练假把式。我们把问题简化，假设我们输入的都是小写英文字母，那么每一个节点就会储存俩个东西。

1：当前节点的value(保存字母）

2：一个数组（26位），因为每个节点最多会有26个子节点（a-z),那么我们正好可以用下标0来储存a字树，25来储存z子树。

class Node {
        constructor (value) {
            this.childNode = new Array(25).fill(null); //初始化 假设我们只输入小写字母
            this.value = value;
        }
    }

trie树主要是俩个操作1：添加2：查询相同前缀的字符串。

class TrieTree {
        constructor () {
            this.root = new Node("/"); //假设以/开头的Trie树
        }
        getPos (ch) {
            return ch.charCodeAt() - "a".charCodeAt();
        }
        add (str) { //新被加的字符串
            let curNode = this.root; //获取node;
            while (curNode !== null) {
                let firstChar = str[0] || "";
                if (!firstChar || str === "") break; //证明已经插入完成了
                else {
                    str = str.slice(1); //因为当前的curNode已经要被插入字典树了
                    const pos = this.getPos(firstChar); // 获取存放的位置
                   // console.log(pos);
                    const newNode = new Node(firstChar); //生成新的节点
                    if (!curNode.childNode[pos]){
                        curNode.childNode[pos] = newNode; //如果当前节点不存在，将新节点挂上
                        curNode = newNode;
                    } else { //如果当前节点有，那么就需要将curNode = curNode.childNode[pos];
                        curNode = curNode.childNode[pos];
                    }
                     
                }
            }
        }
        findPrefix (prefixStr) { //查询有多少字符串以perfixStr为前缀
            let curNode = this.root;
            let firstChar = prefixStr[0];
            if (prefixStr === "") return []; //为空处理
            while(true) {
                if (curNode === null) return [];//证明匹配失败了
                curNode = curNode.childNode[this.getPos(firstChar)]; //获取下一位
                prefixStr = prefixStr.slice(1);
                if (prefixStr === "" ) break; //prefixStr已经全部匹配完了
                firstChar = prefixStr[0];
            }
            //证明匹配成功了，而且curNode.value就是perfixStr的最后一个字符，因此curNode.childNode里面的字符就是我们要找的
            return curNode?this.deepFind(curNode):[]; 
        }
    
        deepFind (node, curStr = "", ans = []) { //深度优先搜索去查找所有的字符串
            let flag = false;
            for (const next of node.childNode) {
                if (next !== null) {
                    flag = true; //表示的确还有字符
                    this.deepFind(next, curStr+next.value, ans);
                }
            }
            if (!flag) { //那么表示此为叶子节点
                ans.push(curStr);
            }
            return ans;
        }
    }

接下来，我们就来试试（虽然小弟以后方向是前端工程师，但样式，展示等不是重点，这些从简）。

import TrieTree from "./trieTree";
    import React from 'react';
    import ReactDOM from 'react-dom';
    
    
    class Input extends React.Component{
      constructor (props) {
        super(props);
        this.__trieTree = new TrieTree(); //内部维护一棵字典树
        this.state = {
          value: "",
          point: []
        }
    
        this.handleChange = this.handleChange.bind(this);
        this.handleClick = this.handleClick.bind(this);
      }
    
      handleChange (ev) {
        this.setState({
          value: ev.target.value
        }, () => {
          this.setState({
            point: this.__trieTree.findPrefix(this.state.value) //将查询的结果保存下来
          })
        })
    
      }
      handleClick () {
        this.__trieTree.add(this.state.value); //将查询值保存
      }
      render () {
        return (
          <div>
            <label htmlFor="input">输入查询内容</label>
            <input id="input" 
               placeholder="输入关键字"
               value = { this.state.value }
               onChange = { (ev) => { this.handleChange(ev)}}
            />
            <input type="submit" 
               onClick = { this.handleClick }
            />
            <ul>
              {
                this.state.point.map( (item, index) => { //显示的值
                  return (<li key={index}>{ this.state.value + item }</li>)
                })
              }
            </ul>
          </div>
        )
      }
    }
    
    
    ReactDOM.render(<Input />, document.getElementById("root"));

结果如图，我们先输入hello,然后点击submit

![20190414153845761.png][]

当我们在输入h时：![20190414153917949.png][]

当我们输入hi时，点击submit: ![20190414153956922.png][]

然后输入h时：![20190414154035565.png][]

怎么样，你觉得如何，是不是很简单。玩玩呗！

字典树虽然很好，但是它内存消耗非常大，不难发现，每个节点利用的childNode并不是很多，所有浪费了很多空间，你也可以牺牲一定时间复杂度来换空间（childNode换成一个空数组，然后添加时候维护内部有序，查找时可以用二分查找）。PS：我们当前只考虑了小写字母，你可以算算如果考虑所有字母，并且处理中文的话!!!!)空间浪费很大吧。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70]: /images/20220220/2971685075994bd8ae396eddfac38296.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70 1]: /images/20220220/0d2d96c1a74c45b18b387f3f65c65604.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d1c3RfY3ls_size_16_color_FFFFFF_t_70 2]: /images/20220220/901ec2b671134891a3de577f63c2e367.png
[20190414153845761.png]: /images/20220220/1c4c222a39564fdf9daa9d9e123925a6.png
[20190414153917949.png]: /images/20220220/de20a3b48b3d41e39417f4521219fa03.png
[20190414153956922.png]: /images/20220220/586718ab2e7048ac9121b1a66ead4e1b.png
[20190414154035565.png]: /images/20220220/932d3ce1081f4f9bb3bdc0440d21dda5.png