第二天早上，Frank來到了位於首都中心的一家小店：Cloaks andMore。這間小店裡幾乎每一寸地方都被放滿了披風。Frank好不容易擠出了一條路，來到了櫃檯前。
一個矮小的快要禿頂了的男人戴著厚厚的眼鏡，抬頭看了看Frank，說道：「歡迎來到Cloaks andMore。我是Gilbert Cloaksworth，能幫你做點什麼？」
他上下打量著Frank，眼睛不停地看著Frank那件有些破舊的披風式大衣。當他看到那件披風上的補丁時，突然靈機一動。
「我知道了，你是來買披風的，」他用那些勢利的商人所慣用的熱情語氣說道，「那你真是來對地方了。我們剛剛到了一批很好的森林旅行披風。」
「我是來尋找信息的，」Frank說道。他拿出從Array Cart上拿到的線頭，放到那個人面前，說道：「我需要知道這個線頭是哪件披風上的。」
Cloaksworth先生一動不動地說道：「所以你不買披風嗎？」
「我只需要信息。」
「太遺憾了，」Cloaksworth冷淡地說道，「不過你還是來對地方了。我是這個城市裡關於披風最權威的專家。」他拿過線頭，看了幾眼，接著，他從櫃檯下方拿出了一個巨大的放大鏡，仔細地研究起來。
「黑色和黃色，用的是交叉編織的針法，」Cloaksworth輕聲地說，「質量還不錯。當然，還比不上我的標準。不過還算可以了。」
「你還能告訴我任何其他信息嗎？」Frank說道，「有用一些的？」
店主皺了皺眉，不過緊接著便繼續開始研究那個線頭。「有一絲燒焦的痕跡。」他終於這樣說道。
「被火燒過嗎？」Frank問道。
「不，這個痕跡看起來太規律了。這種痕跡我只見過幾次，而且都是在巫師的披風上見到的。這個披風上有一個咒語。」
「你知道是什麼咒語嗎？」Frank問道。
Cloaksworth搖了搖頭：「這個你應該去問巫師。我是這城市裡最懂披風的，又不是最懂咒語的。」
「那顏色呢？」Frank問道，「我很少見到這種顏色的披風。你能告訴我它是從哪來的嗎？」
Cloaksworth笑道：「當然可以。我可是這個王國中最懂披風的人。」
他轉身從身後的架子上拿下了一本巨大的書，並砰的一聲將它放在櫃檯上。他隨即翻到了書的最後。
「你在幹什麼？」Frank問道。
「我在《披風和紋章學索引》的第五卷中找這個披風的顏色，」店主回答道，「你不是想知道這種披風是從哪裡來的嗎？」
「那你為什麼直接看書的最後？」Frank問道，「你難道不應該從目錄開始看嗎？」
Cloaksworth終於真心地笑了一回，說道：「這幾年來，紋章分類學有不少大的突破！」他激動地說道，「曾幾何時，我們找東西時都是像你說的那樣，先從目錄裡開始瀏覽，找到後再翻到相應的頁碼。當然，翻頁的過程是用二分搜索法。
「目錄的確可以為書本的內容提供一個索引。但是對於我們現在想要進行的這種搜索來說，目錄的整個結構就是錯誤的。它將書本裡面的內容都按出現的順序列出來了。如果你是想知道每個內容後面緊接著的是什麼，那麼這個順序再合適不過了。但是整個王國現在已經有超過一萬種披風花紋了！如果按這個順序，光在目錄裡面找就需要花費很長時間。
「所以Amanda Cloakington，我的偶像，也是《披風和紋章學索引》的作者，發明了逆向索引。她將一些重要的詞，比如披風的顏色，都在書本最後列了出來。幾乎就像另一個目錄一樣。」
「這有什麼用呢？」Frank問道，「她只是將目錄中的信息又重複了一次。」
「是，她的確是在重複信息，但這一次她使用了一個不同的順序。書本最後的索引是按關鍵詞的順序排序的。對於每一個詞，她列出了它們在書本中出現的頁數。」
Frank看著他，等待著他繼續說下去。但看起來店主已經說完了。「所以呢？」Frank問道。
「你只需要找到你想要找的關鍵詞，就可以在索引中看到需要看的頁碼是哪些了！」他激動地說，「你不再需要在目錄中漫無目的地翻閱，而只需要直接找到你想要的詞就行了。」
「但是你還是需要在索引中找你想要的詞，不是嗎？」Frank問道。
「的確。但是因為索引是按關鍵詞首字母的字典序排序的，因而你可以用二分搜索。」
「那如果我所找的關鍵詞出現在了很多頁上呢？」
「你需要每一頁都看一下。」Cloaksworth讓步道。
「那如果你同時在找數個顏色呢？」Frank問道，「比如同時找三種顏色？」
「哈！這才是索引有趣的地方，」Cloaksworth說道，「你只需要找到它們所共同存在的頁碼就好了。可以算出所有關鍵詞所在的頁碼集合的交集——也就是找到在所有頁碼集合中都出現過的頁碼。如果你的關鍵詞足夠多，你通常可以把頁碼的範圍縮小到一兩頁。
「前幾天，我在找一件藏青色和品藍色組合的有木製扣子的披風。這樣的披風總共也沒有幾種。只有一類人會用那種披風——業餘天氣預報員聯盟。其實直到去年，他們一直用的都是藏藍色和深綠色組合的披風。但半職業天氣預報員聯盟說這個顏色和他們披風的顏色——藏藍色和淺綠色——太像了，所以業餘天氣預報員聯盟只能換成了現在這種顏色。」
Frank想了想，點了點頭。「有意思！」他說道。他馬上就想到了這種逆向索引可以被用到其他類別的信息上面。警局的記錄從來都是按日期排序的。利用這種新的方法，就可以同時把它們按犯罪類型或地點來索引。這些索引可以讓研究的過程容易太多了。
「你覺得其他書籍也會用這種逆向索引嗎？」Frank問道。
「不太可能，」店主嘲笑地說道，「世界上沒有多少學科能複雜到需要使用索引。不是所有學科都像披風學這麼有內涵的。」
他們一邊說話，店主一邊快速地翻動著書。「警察披風，」他最終說道，「Bool andFunctionia部門用的是這種顏色，還有幾個其他的首都警察部門也是。財務部、薪酬部、記錄部和信號部都用的是這個顏色。當然了，他們的圖案設計都不同。從線頭來看，這個披風是新派發的。警察局的警官都比較容易把披風穿舊，特別是信號部的。」
「你說這是一件新的警察披風？」Frank確認道。
「幾乎肯定是，」Cloaksworth說道，「因為我不覺得這是私人訂製的。這些顏色在20年前還挺流行，但在淡色流行起來後它們就不怎麼流行了。真可惜——那個年代有好多美麗的披風。曾經我做過一件騎行時穿的披風，有雙層扣子和……」
Frank打斷了他：「關於這個線頭，你還能告訴我什麼其他的信息嗎？」
店主看著他說：「一件被施了咒語的新的警察披風，除此之外……」
Frank等待著。
「額……沒了，」Cloaksworth最終說道，「全都說完了。」
Frank點了點頭說道：「謝謝！」他拿起那根線頭，轉身準備離開。在他走出門的時候，他聽到店主倒吸了一口氣，Frank想，店主肯定看到他披風尾部那被磨爛的邊緣了。
警用算法導論：逆向索引
節選自Drecker教授講義
逆向索引是計算中要用的一種數據結構，它和書的索引類似。對於每一個值，逆向索引可以告訴你這個值在數據中的哪些地方出現過。如果一個值會在數據中反覆出現，這一點就格外有用。
想想我們在講二分搜索的時候用到的一個例子——在一個賬本中查找和一個特定商人進行的所有交易記錄。賬本上的記錄是按交易編號從小到大排的，也就是按交易時間從早到晚排序的。
在知道交易編號的情況下，這種排序可以讓我們很快找到交易記錄，但它並不能幫助我們找到與某個特定商人進行的所有交易。當然，我們可以按照商人的名字重新排序。但這樣做的工作量很大，因為這意味著我們需要重新做一本賬本。
我們可以建立一個額外的數據結構：一個以商人名字作為關鍵詞的逆向索引。對於每一個商人，我們可以在索引中存下所有相關交易的編號。因為我們已經可以從編號很容易地找到交易記錄，所以這個額外的索引就可以讓我們很容易地找到與某個特定商人相關的所有交易記錄了。
逆向索引是一個很典型的需要在運行時間和內存佔用兩者之間取捨的例子。添加一個逆向索引會占掉更多的內存，但它也讓我們在一個新的維度上進行搜索的效率得到了極大提升。