通配符查询与K-gram索引

可视化演示

演示K-gram生成、通配符查询处理流程与K值选择权衡，理解模糊匹配的索引与查询机制。

通配符查询基础

读者小陈跑到咨询台前，脸涨得通红：“我想找一本讲 'Mon' 开头的书，可书名怎么都想不起来了！” 管理员王姐微微一笑，在便签上写下三个字符：mon*。这串看似简单的记号，就是通配符查询——用占位符代表记不清的部分，请搜索引擎帮忙猜。图书馆里每天都有这样的模糊需求：“以 land 结尾的书”、“中间是 a 和 n 的词”……通配符就是表达这种“残缺记忆”的通用语言。

在搜索引擎术语里，通配符有两类最常见的占位符：星号 * 表示匹配任意长度的字符序列（可以为空），问号 ? 表示恰好匹配一个字符。例如 mon* 可以命中 "monitor"、“monday“ 这类以 mon 打头的词；m?ney 则可以命中 ”money”，因为 ? 恰好占掉字母 o 的位置。按通配符的位置，还能分成前缀通配（mon*）、后缀通配（*land）和中缀通配（m*n）三类。

为什么要把这些记不清的查询方式单独拿出来研究？因为真实用户输入并不总是完整准确的。搜索日志里充斥着拼写残缺、记忆模糊的查询串，而搜索引擎必须在倒排索引之外，再设计一套“词项召回”机制来兜底。通配符查询正是这种机制的直接需求来源。它看似只是符号问题，实际却决定了整个检索系统能否“听懂”用户残缺的表达。

回到图书馆，小陈的 mon* 被王姐郑重记下。接下来王姐要先翻那本主题卡片目录——但真正的麻烦，才刚刚开始。

倒排索引的困境

王姐翻开那本厚厚的主题卡片目录：每一张卡片上都写着“主题词 → 一排书名”。比如卡片 “monitor“ 背面列着《显示器维修指南》；卡片 ”monday“ 背面列着《Monday 健身食谱》。这就是倒排索引——从词项指向文档列表的反向映射，检索时靠它一步定位文档。可当王姐想找 mon* 时，她犯了难：目录里根本没有一张叫 ”mon\*” 的卡片！

问题就出在倒排索引的“精确匹配”本性上。倒排索引的词典层通常用哈希表或 B 树实现，查找时拿查询词和词典里的词项做完全相等比较。mon* 作为一个带星号的字符串，既不是 “monitor“ 也不是 ”monday“，它在词典里没有任何对应的槽位。换句话说，倒排索引只回答”这个词在哪些文档里出现“，不回答”哪些词长得像这个模式”。

那能不能绕开索引，把整个词典从头到尾扫一遍？这就是最朴素的暴力解法：把词典中每个词都取出来，用通配符模式逐一做正则匹配。设词典有 N 个词，每个词平均长度为 L，则总耗时是两者的乘积。当 N 达到百万量级时，一次通配查询就要做几千万次字符比较，让搜索引擎的服务延迟彻底失控。

这个复杂度让王姐直摇头：图书馆词典有上百万张卡片，每张卡片上的单词都拿去比一遍“mon\*“，读者怕是要等到闭馆。看来，非得有一本”专门为残缺线索准备”的辅助索引不可。

旋转索引

老馆长笑呵呵地拿出一沓“旋转便签”：“光靠目录当然不行，你得换个角度看单词。” 所谓旋转，就是把每个单词想象成一个圆环，在任意位置切开，再在切口处插一面 $ 小旗子表示单词结尾。比如 "mon"，旋转后可以得到 mon$、on$m、n$mo、$mon 等几种形式。把这些旋转形式全部按字典序排好，就构成旋转索引（Permuterm Index）。

旋转索引的精妙之处在于：它把“后缀通配”偷换成了“前缀查询”。假设读者想找以 land 结尾的书，即查询 *land。管理员只需在旋转索引里查前缀 land$：所有旋转形式以 land$ 开头的条目，对应的原词自然是以 land 结尾的。同理，查询 mon* 可以转成查前缀 $mon。这样原本倒排索引束手无策的通配符问题，就被“转一圈”化解成了普通的前缀查找。

但旋转索引并非免费午餐。每个长度为 L 的词会产生 L+1 种旋转形式，索引总规模膨胀到原词典的 L 倍左右。更头疼的是，它只擅长处理前缀或后缀通配；遇到 m*n 这种中间带星号的查询，需要拆成前后两段分别旋转再交叉求交，复杂度直线上升。王姐记下心得：旋转索引像是“一个方向上的魔法”，灵活但昂贵。

旋转便签虽然好用，但面对“中间缺失”的情况依然捉襟见肘。馆长又拿出一沓更细碎的小卡片：“别急，还有更通用的切片法。”

K-gram 索引原理

老馆长拿出的新工具，是一盒“字母切片卡”。做法很朴素：把每个单词前后各补一个 $，然后切成所有长度为 k 的连续小片，这些小片就叫 k-gram（克）。例如单词 "monday" 加上边界符变成 $monday$，切成 2-gram 后得到：$m、mo、on、nd、da、ay、y$ 共 7 个小片。每一张小卡片正面写一个克，背面写上所有包含这个小片的单词——这就是 K-gram 索引。

为什么这套“切片卡”比旋转便签更通用？因为它把“单词长得像什么”彻底拆解成了“由哪些小零件组成”。无论通配符出现在前缀、后缀还是中间，只要把查询的字面部分也切成同样的克，就能通过“零件交集”找到候选词。旋转索引只是把词转了个圈，而 K-gram 则把词碎成了可以自由组合的积木，通用性大幅提升。

当然，积木不是白来的。对于长度为 L 的词，共产生约 L+k 个克，索引空间近似正比于全部词的总字符数；k 越小，每个克越短，匹配越宽泛、候选越多，但索引更小；k 越大，克越长、选择性越强，但索引更大，且对查询字面长度有要求。实际系统中用得最多的是 k=2 或 k=3，在召回率和空间开销之间取一个平衡点。

王姐看着满抽屉的切片卡，突然意识到：卡片背后那串词项清单，不就是一本微型的“零件倒排索引”吗？现在关键的问题是——读者报出的残缺书名，该怎么利用这些切片卡找到真正的候选书？

查询处理流程

小陈的查询 mon* 又被拿了出来。王姐的处理流程分三步走。第一步，把模式中的通配符剥掉，留下连续的字面部分 "mon"，再用 2-gram 切法得到克集合 {mo, on}。第二步，翻开切片卡，分别查 mo 卡和 on 卡背后的词项清单，然后取两串清单的交集。交集里出现的词，就是同时包含这两个克的候选词项：如 monitor、monday、money，可居然还混进了 demon——它明明不以 mon 开头！

这暴露了克交集的一个本质特点：它只是“候选超集”。demon 虽然同时包含 mo 和 on，却完全不符合 mon* 的前缀约束。因此必须有第三步——用原始通配符模式对候选集再做一次正则匹配过滤，把 demon 这类“零件凑巧相似”的误报剔除。正是因为有这一步，K-gram 索引才能安心负责“广撒网”，最后的“精准收网”交给模式验证完成。

把这个流程写成公式：设查询 q 的字面部分是 ℓ，先对 ℓ 生成克集合，再对每个克查它的倒排候选表 Post(g)，最后把所有这些候选表做交集，得到候选集合 C(q)。最终结果还需满足 q 本身的正则。倒排索引的职责是“文档定位”，而 K-gram 的职责是“词项召回”，两层配合才构成完整答案。

王姐在实践中发现，流程虽然清晰，但当切片卡背后的清单长得吓人时，求交仍然很慢。有没有办法让管理员少翻几张卡、少对几行名？

性能优化策略

王姐的切片卡越攒越多，问题也来了：热门克背后的词项清单长得像流水账，比如 on 卡背面密密麻麻写了几百个词。每一次求交都要把这些清单逐一比对。馆长给她支了三招。第一招叫“稀有优先”：查询时先算每个克的稀有度，从最稀有的克开始求交。因为稀有克的候选少，先把它和其他克交一轮，候选集合会迅速收缩，后续比对成本骤降。

第二招叫“阈值截断”：如果一个克的候选清单已经超过预设阈值（比如 1000 个），说明它区分度太低，直接放弃用它做交集，或者限制只取前若干项。这相当于告诉管理员：“这张卡太没营养，翻都不要翻。” 第三招叫“结果缓存”：高频克（如 on、er）的候选清单经常被反复查询，系统可以把计算结果缓存下来，下次直接取现成的，省去重复读索引的时间。此外，多个克的查询互不依赖，还能并行处理，让多核服务器同时翻好几张卡。

其中“稀有优先”策略背后有一个简洁的排序依据——用类似 IDF 的思想度量克的稀有度：N 是词典总词数，df(g) 是包含克 g 的词项数量，稀有度得分越高的克越值得优先处理。

经过这轮优化，王姐的检索台效率翻倍。她终于理解了馆长的智慧：面对残缺信息，不要硬着头皮全馆扫描，而是先把世界拆成小零件、按零件先过滤、再用原始需求收尾。这就是通配符查询与 K-gram 索引的全部精髓。

AI 应用场景

Python 演示

import re class KGramIndex:    """用 2-gram 索引支持通配符候选生成的小型演示。"""     def __init__(self, k=2):        self.k = k        self.words = set()        self.posting = {}     def grams(self, text):        padded = '$' + text + '$'        return [padded[i:i + self.k] for i in range(len(padded) - self.k + 1)]     def add(self, word):        self.words.add(word)        for g in set(self.grams(word)):            self.posting.setdefault(g, set()).add(word)     def query(self, pattern):        literal = pattern.replace('*', '').replace('?', '')        gram_sets = [self.posting.get(g, set())                     for g in set(self.grams(literal))]        candidates = set.intersection(*gram_sets) if gram_sets else set(self.words)        regex = re.compile('^' + pattern.replace('*', '.*').replace('?', '.') + '$')        return [w for w in self.words if w in candidates and regex.match(w)] if __name__ == '__main__':    vocab = ['monitor', 'monday', 'money', 'noon', 'night', 'onion', 'demon']    index = KGramIndex(2)    for w in vocab:        index.add(w)    print(index.query('mon*'))    print(index.query('*day'))

1. padded = '$' + text + '$'给词首尾补边界符，保证开头的 $m 和结尾的 y$ 也能参与匹配。
2. self.posting.setdefault(g, set()).add(word)每个克对应一个词项集合，构成克级倒排表。
3. literal = pattern.replace('*', '').replace('?', '')先剥离通配符，提取连续字面部分作为切克原料。
4. gram_sets = [self.posting.get(g, set()) for g in set(self.grams(literal))]为每个克取出候选词项集合。
5. set.intersection(*gram_sets)对所有克的候选集合求交集，得到候选超集。
6. regex = re.compile('^' + pattern.replace('*', '.*').replace('?', '.') + '$')把通配模式转成正则，用于最终过滤误报。
7. return [w for w in self.words if w in candidates and regex.match(w)]候选与正则双重校验后才输出，保证结果精确。

常见误区

面试题