用户表达的一类query通常符合某种模式，把具有相同模式的query归纳起来就变成一种模板的形式。
使用模板来描述用户需求具有比较强的可控性，且准确率高，属于一种比较实用的基于规则的query分析方法。
通常某类需求的query需要用多种模板来概括，于是就需要对多种模板进行统一管理，本次升级是对前面lexparser的算法进行了比较大的改进，使得在大规模词典数据的情况下，分析效率得到提升，以满足线上大数据量情况下的实时运算。同时把十分常用的通配符功能加入算法中，满足不同应用方的需求。
名词解释
模板：一个query表述模式，比如“[地名][机构核心词]有限公司”就是一个用来表述机构名的常用模板。
模板词：[地名]这个槽中限定的完全匹配的词
目标
预先给定模板、模板中涉及的词库、及可忽略词；
对输入的query，判断其是否有匹配的模板，如果有，输出模板的信息和模板各个部分对应query中的term及其所在词库或函数的信息；
针对现有的代码，在尽可能保持原有接口的情况下，对lexparser模块进行升级，使得query处理速度得到提升。
思路
- 基于trie树来实现模式匹配，每一个节点代表状态，叶子节点代表模板匹配成功。节点之间的边代表转移条件。若成功匹配出当前字符串的前缀，则从当前状态进入该前缀所对应的边所指向的下一状态。
构造一棵trie树形结构，树中的每一个节点代表一个状态：根节点代表初始状态，叶节点代表一次成功的匹配，而中间节点则代表匹配的过程的中间状态。从一个节点到其子节点的边，称为状态转移条件，共分为四种类型：模板词，固定词，函数以及可忽略词。
这个树形结构的示意图如下：
对于模板：[D:huilv_货币][F:num][D:huilv_等于][D:huilv_货币]，他在这棵树中的状态转移路径如下：1-2-8-10-14 。
Trie Tree
我们会注意到一个问题，这棵树初始状态中输入的是一个query，也就是一个具体的字符串，而在上面的图中我们可以看到，节点与节点之间的状态转移条件则是抽象模板词、函数、固定词、可忽略词这四种类型，也就是说，在状态转移之前，还需要一个从当前query中确定转移条件类型的步骤。这将会是一个影响性能的主要瓶颈。
针对这一步骤的思路是：从当前query中匹配出可能的前缀词，通过这个前缀词的类型来确定状态转移。例如：从当前query匹配出的前缀词是“北京”，那么毫无疑问，下一个状态转移类型会是模板词中的[D:train_地名]；若前缀词是“美元”，那么显然，下一状态转移类型会是模板词中的[D:huilv_货币]。
因此，问题的重点就转移到前缀词的匹配了。匹配前缀词所采用的方法依旧是基于trie树的，树中的每一个节点代表一个状态：根节点代表初始状态，叶子节点代表前缀匹配成功，中间节点代表匹配过程的中间状态。从节点到其子节点的边即是转移条件，具体地说就是词语中的单个汉字。
这个字典树的示意图如下：
假设当前词库中有三个词：三江，三江口，三江县。那么构建出的字典树即如下所示：
三江：1-2-6
三江口：1-2-6-7
三江县：1-2-6-8
image.png
综上所述，假设当前query是：“三江口到三江的火车”，整个匹配流程如下：
- 进入模板树的根节点1；
- 进入词库树的根节点1；
- 转移条件“三”，进入节点2；
- 转移条件“江”，进入节点6，匹配出“三江”，即[D:train_地点]；
- 转移条件“口”，进入节点7，匹配出“三江口”，即[D:train_地点]；
- “到”并非转移条件，终止，退出词库树，返回模板树；
- 转移条件：“三江”为[D:train_地点]，进入下一节点，待匹配字符串为“口到三江的火车”；
- 进入词库树的根节点1；
- “口”并非转移条件，终止，退出词库树，返回模板树；
- 转移条件：“三江口”为[D:train_地点]，进入下一节点，带匹配字符串为“到三江的火车”；
- 进入词库树的根节点1；
- 转移条件“到”，进入下一节点，匹配出“到”，即[D:train_到]；
- “三”并非转移条件，终止，退出词库树，返回模板树；
- 转移条件：“到”为[D:train_到]，进入下一节点，带匹配字符串为“三江的火车”。
- 重复上述的过程，直到状态转移至叶子节点。
最后会匹配结果为：[D:train_地点]：三江口，[D:train_到]：到，[D:train_地点]：三江，[可忽略词]：的，[D:train_类型]：火车。
整个匹配过程实际上是分为两个层次的，第一层是模板树中的匹配，第二层是词库中的匹配。
整个过程抽象的来说就是：
image.png
复杂度分析（不使用*+通配符）
- 对于模板树，假定匹配出的模板的长度为L，每个节点向其子节点转移所耗费的时间为T，那么完成一次模板匹配的时间为O（L*T）。
- 上述的时间t，是由词库树的效率来决定的，如果假定当前待匹配字符串的长度为n，最长前缀长度为m，所有能够匹配出的前缀的个数为k。由于词库树是一棵trie树，那么找出这k个前缀所花的时间是O（m），由m<=n，所以也是O( n )的。
- 词库树所返回的这k个前缀即是模板树中的当前节点的所有可能的转移条件，因此要进入接下来的k个状态，所花时间是O（k）的。
因此，我们前面所提到的时间t = O（n）+ O（k）=O（n + k）。
那么，一次query匹配的时间复杂度就是O( L *( n+ k ))。
通配符功能
为了满足一些应用需求，增加通配符识别功能，如果模板中包含通配符，则上述复杂度计算公式失效。
通配符形式如下：[W:2-10] 表示匹配任意2-10个字节字符
实现大体思路：在走模板树的每个节点时，设当前query长度为len，如果这个节点上有通配符[W:2-10]，则截取2-10长度后，再分别递归遍历。
网友评论