联想词匹配-总结

思考：

经过一段时间的学习，对联想词匹配，和前缀树又有了更深刻的认识，也自己写了下，下面就详细说下构建过程与查询过程。

整体算法图：

介绍：

        DataSource 是数据接口，DataSourceImpl是数据接口的实现，主要用于提供联想词数据来源，持久化，恢复等功能。

        QueryInfo 记录每个词出现搜索次数，唯一编号，还有热度，主要到时候用于查找后，根据搜索次数热度等数据，进行排名，取前N个

        DataNode 根据DataSource得到数据后，需要对数据进行处理，生成一些构建搜索树需要的内容，例如queryInfoIdxMap 记录着所有的词，prefixWordSetList按前缀词长度划分的前缀词的结合，suffixCharMap 记录根据前缀找后缀的字符集合，prefixNodeMap根据前缀可以取到对应DictNode节点，拿到搜索词前Top。

        TrieDict  存储着base和check数组，整个搜索树的数据，TrieDict.DictNode 是每个base数组下的节点，存储了 当前节点结尾的搜索词前N名，到时候用于出联想词。

        Teacher 通过DataSource获取到数据源，进行处理放到DataNode里 DataNode 包含QuerInfo和TrieDict.DictNode，数据处理后，再构建TrieDict搜索树。

        Search 主要用于查询，通过TrieDict中的base 和check来检索，并且在查询中对搜索词进行统计搜索词搜索次数和热度，用于排名。

构建过程：

        介绍中已经介绍了一部分过程，这里再详细说下构建过程。

1 获取数据

        根据DataSource获取词列表

2 处理数据生成DataNode中的数据

        1 生成QueryInfo  记录每个词出现的次数，为每个词标一个唯一id，用于到时候每个节点进行词频排序。

        2 prefixWordSetList 按照词的最大限制长度，例如12，来生成，如果是12，prefixWordSetList 的list 0 中 为所有词 开头第一个词的汇总不重复set列表  ，list 1 为 前缀 2个汇总的不重复前缀列表，构建树的时候，要按照 循环list 再循环里面的set顺序构建（构建前缀树的要求）

        3 suffixCharMap 前缀对应直接后缀，在构建前缀树的时候，需要获取当前前缀的所有后缀，根据偏移量等计算，保证 base 数组中都有空余位置，所以需要生成suffixCharMap数据，数据结构为map  key 是前缀   value是前缀后所有的后缀。

        4 prefixNodeMap 每个前缀对应的节点信息，用于构建的时候，直接定位到某个前缀的node节点，不用每次都根据算法查找一次

3 构建查询树

        按照 前缀树构建方式构建，请参照之前的博客

4持久化数据

        需要将 TrieDict中的关键数据持久化到数据库

查询过程：

查询逻辑就是Trie树的匹配逻辑，当根据查询能匹配到最后一个，获取当时base节点中的TrieDict.DictNode，从TrieDict.DictNode中读取查询次数最多的前10个词返回。