联想词搜索（suggest）

1 .应用场景

现在很多应用都有搜索联想功能，baidu，google，各种电商都有这种搜索智能提示功能，可以帮助用户尽快找到自己想要的，用户是比较懒的，所有这种还是比较常见的。如下图所示用户输入 “数据结构”，联想出下面的结果以及结果数量

2.实现原理

这种联想功能有两种实现方式

2.1 倒排索引

比如说lucene的 suggest模块)，这种方式可以实现，但是有点大材小用，而且性能也是问题， 主要是通过编辑距离大于某个阈值就认为联想出来的词和下面的相关，分词也是必须采用NGRAM才行，要不然用户搜索的时候会发现结果会消失。索引大和查询性能都会有影响，所以不推荐这种方式，solr&es关于suggest模块没有做什么优化，es里面目spellcheck里面默认是2-Gram方法，关于编辑距离优化的方法 推荐看 N-Gram

2.2 字典树（trie）

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

3. trie原理

这里举个例子吧，比如我现在有 int, at, age, and 这几个词，我现在建树

线上主要场景是用户通过拼音和汉字都能搜索到相同的结果，这里就可以把拼音通过map映射成汉字就行

插入过程

对于一个单词，从root开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为绿色，表示该单词已插入trie树，代码里面会标记节点为叶子

查询过程

树的深度遍历，太简单了，这里就不说了

Node.java

package com.suggest.search.trie
import java.io.Serializable;
import java.util.HashMap;
public class Node implements Serializable {
    /**
     *
     */
    private static final long serialVersionUID = 1L;
    private HashMap<Character, Node> childMap;
    private boolean isLeaf;

    public Node() {
        setLeaf(false);
        setChildMap(new HashMap<>());
    }

    public boolean isLeaf() {
        return isLeaf;
    }

    public void setLeaf(boolean isLeaf) {
        this.isLeaf = isLeaf;
    }

    public HashMap<Character, Node> getChildMap() {
        return childMap;
    }

    public void setChildMap(HashMap<Character, Node> childMap) {
        this.childMap = childMap;
    }
}

TrieTree.java

package com.suggest.search.trie;

import java.util.HashSet;
import java.util.Map;

/**
 * Created by wangds on 16/9/25.
 */
public class TrieTree {
    private static final int maxStr = 200;
    private Node root;

    public TrieTree() {
        root = new Node();
    }

    public void insert(String words) {
        insert(this.root, words);
    }

    private void insert(Node root, String words) {
        if (null == words || "".equals(words)) return;
        char[] chars = words.toLowerCase().toCharArray();
        for (int i = 0, length = chars.length; i < length; i++) {
            if (!root.getChildMap().containsKey(chars[i]))
                root.getChildMap().put(chars[i], new Node());
            if (i == length - 1) {
                root.getChildMap().get(chars[i]).setLeaf(true);
            }
            root = root.getChildMap().get(chars[i]);
        }
    }

    private HashSet<String> preTraversal(Node root, String preStr) {
        HashSet<String> set = new HashSet<>();
        if (root != null) {
            if (root.isLeaf()) {
                set.add(preStr);
            }
            for (Map.Entry<Character, Node> chr : root.getChildMap().entrySet()) {
                String tempStr = preStr + chr.getKey();
                if (set.size() > maxStr) return set;
                set.addAll(preTraversal(chr.getValue(), tempStr));
            }
        }
        return set;
    }

    public HashSet<String> getWordsForPrefix(String word) {
        return getWordsForTrie(this.root, word);
    }

    private HashSet<String> getWordsForTrie(Node root, String word) {
        char[] chars = word.toLowerCase().toCharArray();
        for (int i = 0, length = chars.length; i < length; i++) {
            if (!root.getChildMap().containsKey(chars[i])) {
                break;
            }
            root = root.getChildMap().get(chars[i]);
        }
        return preTraversal(root, word);
    }
}

Trie问题以及应用

字典树这种方式也是有问题的，当你的词很多的时候，这时候占用内存就比较多，核心思想就是用空间换时间，上面介绍的是前缀树，还有后缀树。

应用比较多了，面试的时候也会问很多，这里就汇总下吧。

1.字符串查询，数量统计，热搜

事先将已知的一些字符串（字典）的有关信息保存到trie树里，查找另外一些未知字符串是否出现过或者出现频率。
举例：
1）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。
返回频数最高的100个词。
2）给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
3）给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
4）1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串
5）寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

2.字符串最长公共前缀

Trie树利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵trie树上时，我们可以快速得到某些字符串的公共前缀。举例：
1) 给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少. 解决方案：
首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线 （Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。
而最近公共祖先问题同样是一个经典问题，可以用下面几种方法：
1. 利用并查集（Disjoint Set），可以采用采用经典的Tarjan 算法；
2. 求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum Query，简称RMQ）问题了；

最后

以上就是合适宝贝为你收集整理的联想词搜索（suggest）的全部内容，希望文章能够帮你解决联想词搜索（suggest）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。