Lexparser实质是基于规则推导的query结构分析。
简单介绍
用户表达的一类query通常符合某种模式，把具有相同模式的query归纳起来变成一种模板的形式。使用模板来描述用户需求具有较强的可控性且准确率较高，属于一种比较使用的基于规则的query分析方法。
名词介绍
- 模板：一个query的表述模式，例如 “[地名][机构核心词]有限公司” 即一个用来表述机构名的常用模板
- 模板词：[地名] 这个槽中限定的完全匹配的词
- 词库：模板中涉及的词库
- 可忽略词：模板中涉及的停词
模板
其中，模板文件的格式为: 模板\t属性值
[D:company][D:job] 1001
[D:company][D:level][D:job] 1002
第一列是模板, 第二列是属性值。其中模板[D:company] 对应的词由字典文件决定。
模板中可以支持通配 [W:0-20]（0-20是通配的字符串长度），数字匹配[F:num]
字典文件
字典文件的格式为: 模板tag为第一行，接下来一行一个词
[D:company]
百度
谷歌
微软
腾讯
[D:job]
软件工程师
算法工程师
产品经理
可忽略词文件
可忽略词文件的格式为：一行一个词
的
了
输入query文件
query文件的格式为：一行一个词
今晚7点半
百度工程师
百度hi
啥类型
干啥呢
什么东东
腾讯产品经理
阿森纳足球队
谷歌高级算法工程师
语法
1）D语法：模板中用来标识可枚举的词
比如：
[D:city]
北京
上海
…
2）W语法：通配符，用来匹配任意长度的字符
比如：
[W:2-10]表示匹配任意2-10个字节字符
3）F语法：模板中用来标识函数能够识别的字符串
比如：
“[F:num][D:currency]”可以匹配“5美元”，[F:num]的作用就是匹配能被对应的函数识别的字符串。
4）固定词：模板中直接表达的词
比如：
“[F:num] [D:currency]等于多少[D:currency]”，其中“等于多少”就是一个固定词。
具体实现过程
- 输入的query词
- 判断是否有匹配的模板
- 若命中模板，输出模板的信息和模板各个部门对应query中的term及其所在词库或函数的信息
- 数据结构：模板树+词库树
- 所需数据：预先给定模板、模板中涉及的词库、可忽略词（停用词）
Trie Tree (字典树)
Trie Tree，又叫字典树、前缀树（Prefix Tree）、单词查找树或键树，是一种多叉树结构。Trie树的核心思想是空间换时间，利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。
性质
- 根节点不包含字符，除根节点之外的每个节点仅包含一个字符；
- 从根节点到某一个节点，路径上经过的字符链接起来，为该节点对应的字符串；
- 每个节点的所有子节点包含的字符互不相同。
通常实现的时候，会在节点结构中设置一个标志，用来标记该结点处是否构成一个单词（关键字）。
优缺点
优点：
- 插入和查询的效率很高，都为O(m)O(m)，其中 mm 是待插入/查询的字符串的长度。
- 关于查询，会有人说 hash 表时间复杂度是O(1)O(1)不是更快？但是，哈希搜索的效率通常取决于 hash 函数的好坏，若一个坏的 hash 函数导致很多的冲突，效率并不一定比Trie树高。
Trie树中不同的关键字不会产生冲突。- Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。
- Trie树不用求 hash 值，对短字符串有更快的速度。通常，求hash值也是需要遍历字符串的。
- Trie树可以对关键字按字典序排序。
缺点：
- 当 hash 函数很好时，Trie树的查找效率会低于哈希搜索。
- 空间消耗比较大。
应用
- 字符串检索
检索/查询功能是Trie树最原始的功能。 - 词频统计
Trie树常被搜索引擎系统用于文本词频统计。 - 字符串排序
Trie树可以对大量字符串按字典序进行排序，思路也很简单：遍历一次所有关键字，将它们全部插入trie树，树的每个结点的所有儿子很显然地按照字母表排序，然后先序遍历输出Trie树中所有关键字即可。 - 前缀匹配
trie树前缀匹配常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。 - 作为其他数据结构和算法的辅助结构
如后缀树，AC自动机等。
举例
下图中红点分别表示字符串b、abc、abcd、abd、bcd、efg、hii.
实现
基本实现
可以用数组，HashMap，和指针动态分配。
至于结点对儿子的指向，一般有三种方法：
- 对每个结点开一个字母集大小的数组，对应的下标是儿子所表示的字母，内容则是这个儿子对应在大数组上的位置，即标号；
- 对每个结点挂一个链表，按一定顺序记录每个儿子是谁；
- 使用左儿子右兄弟表示法记录这棵树。
三种方法，各有特点。第一种易实现，但实际的空间要求较大；第二种，较易实现，空间要求相对较小，但比较费时；第三种，空间要求最小，但相对费时且不易写。
高级实现
可以采用双数组（Double-Array）实现。利用双数组可以大大减小内存使用量。
时间复杂度
- 插入、查找的时间复杂度均为O(N)，其中N为字符串长度。
- 空间复杂度是26^n级别的，非常庞大（可采用双数组实现改善）。
