16 逆向索引：缩小搜索范围（第2/3页）

Frank看着他，等待着他继续说下去。但看起来店主已经说完了。“所以呢？”Frank问道。

“你只需要找到你想要找的关键词，就可以在索引中看到需要看的页码是哪些了！”他激动地说，“你不再需要在目录中漫无目的地翻阅，而只需要直接找到你想要的词就行了。”

“但是你还是需要在索引中找你想要的词，不是吗？”Frank问道。

“的确。但是因为索引是按关键词首字母的字典序排序的，因而你可以用二分搜索。”

“那如果我所找的关键词出现在了很多页上呢？”

“你需要每一页都看一下。”Cloaksworth让步道。

“那如果你同时在找数个颜色呢？”Frank问道，“比如同时找三种颜色？”

“哈！这才是索引有趣的地方，”Cloaksworth说道，“你只需要找到它们所共同存在的页码就好了。可以算出所有关键词所在的页码集合的交集——也就是找到在所有页码集合中都出现过的页码。如果你的关键词足够多，你通常可以把页码的范围缩小到一两页。

“前几天，我在找一件藏青色和品蓝色组合的有木制扣子的披风。这样的披风总共也没有几种。只有一类人会用那种披风——业余天气预报员联盟。其实直到去年，他们一直用的都是藏蓝色和深绿色组合的披风。但半职业天气预报员联盟说这个颜色和他们披风的颜色——藏蓝色和浅绿色——太像了，所以业余天气预报员联盟只能换成了现在这种颜色。”

Frank想了想，点了点头。“有意思！”他说道。他马上就想到了这种逆向索引可以被用到其他类别的信息上面。警局的记录从来都是按日期排序的。利用这种新的方法，就可以同时把它们按犯罪类型或地点来索引。这些索引可以让研究的过程容易太多了。

“你觉得其他书籍也会用这种逆向索引吗？”Frank问道。

“不太可能，”店主嘲笑地说道，“世界上没有多少学科能复杂到需要使用索引。不是所有学科都像披风学这么有内涵的。”

他们一边说话，店主一边快速地翻动着书。“警察披风，”他最终说道，“Bool andFunctionia部门用的是这种颜色，还有几个其他的首都警察部门也是。财务部、薪酬部、记录部和信号部都用的是这个颜色。当然了，他们的图案设计都不同。从线头来看，这个披风是新派发的。警察局的警官都比较容易把披风穿旧，特别是信号部的。”

“你说这是一件新的警察披风？”Frank确认道。

“几乎肯定是，”Cloaksworth说道，“因为我不觉得这是私人订制的。这些颜色在20年前还挺流行，但在淡色流行起来后它们就不怎么流行了。真可惜——那个年代有好多美丽的披风。曾经我做过一件骑行时穿的披风，有双层扣子和……”

Frank打断了他：“关于这个线头，你还能告诉我什么其他的信息吗？”

店主看着他说：“一件被施了咒语的新的警察披风，除此之外……”

Frank等待着。

“额……没了，”Cloaksworth最终说道，“全都说完了。”

Frank点了点头说道：“谢谢！”他拿起那根线头，转身准备离开。在他走出门的时候，他听到店主倒吸了一口气，Frank想，店主肯定看到他披风尾部那被磨烂的边缘了。

警用算法导论：逆向索引

节选自Drecker教授讲义

逆向索引是计算中要用的一种数据结构，它和书的索引类似。对于每一个值，逆向索引可以告诉你这个值在数据中的哪些地方出现过。如果一个值会在数据中反复出现，这一点就格外有用。

想想我们在讲二分搜索的时候用到的一个例子——在一个账本中查找和一个特定商人进行的所有交易记录。账本上的记录是按交易编号从小到大排的，也就是按交易时间从早到晚排序的。