文本索引与检索
本質上，非常多實際須要解決的問題歸根究竟都是搜索問題 - 在某個空間中尋找特定的目標。
而， 文本檢索又是當中最典型最基礎的一種。文本檢索之所以重要，也是由于非常多更復雜對象或者結構的檢索能夠轉化為文本檢索，或者參考利用文本檢索的思想。
談及文本檢索。 各種各樣的算法不一而足。
大體能夠分成兩類：
? ? ? ? 1. 模式固定。文本不定
? ? ? ? ? ? ? ? 這類算法的一個典型場景： 事先定義一些模式(比方說黃色關鍵詞)。 對每個給定的文本。確定是否含有這些關鍵詞
? ? ? ? 2. 文本固定，模式不定
? ? ? ? ? ? ? ? 這類算法的一個典型場景：已知網絡上的網頁庫，給定一個字符串，尋找含有這些字符串的網頁
不考慮進行文本檢索。 對問題，使用直接的文本查找算法當然也能夠完畢任務。但，這些直接暴力的方法，絕大多數情況都無法滿足實際應用的需求。試想。假設搜索引擎在接收到每個用戶的查詢關鍵詞之后。開始一個網頁一個網頁地查找，恐怕須要長年累月才干返回結果了。 提高文本檢索的效率， 重點在于構造文本索引。一個好的文本索引能極大地提升檢索效率。
關于第一類場景“模式固定， 文本不定”， 文本索引主要是針對模式。 事先對模式實現構建文本索引之后， 新來的查詢文本能夠進行高速掃描。 本質上，模式索引幫助我們規避無關模式的干擾，避免不必要的計算。 經常使用的算法有：
? ? ? ? 1. 單模式 (僅僅有單一模式文本)
? ? ? ? ? ? ? ? KMP算法:?http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
? ? ? ? 2. 多模式
? ? ? ? ? ? ? ? AC(Aho-Corasick)算法 (事實上是KMP的升級版本號):?http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
關于第二類場景“文本固定，模式不定”，文本索引主要針對文本。
小到查找一個文檔中包括的關鍵詞。大到搜索引擎中的文本索引。
經常使用的算法有：
? ? ? ? 1. 文本索引數據結構
? ? ? ? ? ? ? ? 1.a TRIE樹
? ? ? ? ? ? ? ? ? ? ? ??http://en.wikipedia.org/wiki/Trie
? ? ? ? ? ? ? ? 1.b Suffix Tree/Suffix Array
? ? ? ? ? ? ? ? ? ? ? ??http://en.wikipedia.org/wiki/Suffix_tree
? ? ? ? ? ? ? ? ? ? ? ??http://en.wikipedia.org/wiki/Suffix_array
? ? ? ? 2. 倒排表索引。 眼下已經被廣泛應用于絕大多數搜索引擎
? ? ? ? ? ? ? ??http://en.wikipedia.org/wiki/Inverted_index
大體上，似乎這些不同的文本索引都找到它們的“定位”。
Three Body 我也認為倒排表這種結構簡直就是為大規模文本索引而生， 原本優美的Suffix Array僅僅能望“文本海洋”興嘆。 倒排表，對檢索性能的提升讓人贊嘆， 只是也有一些不及Suffix Array的地方。
比方：
? ? ? ? 1. 像中文類似的文本。假設要構建文本索引。首當其沖的問題是須要對中文文本進行分詞，然后才干基于詞語進行倒排索引
? ? ? ? 2. 像生物基因系列的檢索。文本的字符集非常小，普通的倒排表會出現倒排表的每一條倒排索引鏈非常長，檢索效果退化。另外。基因系列也無法進行“分詞”
怎么辦？Compressed Suffix Array給我們帶來了希望。Compressed Suffix Array在解決Suffix Array存儲和搜索方面都有了長足的進展，已經在一些領域的全文檢索系統中使用。
相比Suffix Array。 CSA使用了下面一些富有啟示性的改進:
? ? ? ? 1. 相比傳統后綴數組中的SA[], 壓縮后綴數組引入Successor數組 Psi[]。 Psi[i] = rSA[T[SA[i] + 1]] (當中 rSA[SA[i]] = i) Psi[] 數組的引入， 帶來了數據壓縮和索引檢索上潛能;
? ? ? ? 2. 有序系列的壓縮算法 a. Delta-encoding; b. Quotienting with Elias-Fano
? ? ? ? 3. 基于Psi數組和少量額外存儲, 文本的檢索能夠脫離原始文本
? ? ? ? 4. 壓縮后綴數組能夠進一步壓縮，假設原始文本能夠壓縮
很多其它內容。推薦大家閱讀：
? ? ? ? 1. Compressed Suffix Array wiki:?http://en.wikipedia.org/wiki/Compressed_suffix_array
? ? ? ? 2. 淺顯易懂的文章 A simple introduction to Compressed Suffix Array:?http://www.cs.cmu.edu/~dga/csa.pdf
從后綴數組怎樣進一步得到擴展和改進以適應更大規模數據的需求。除了得到很多其它索引算法設計方面的啟示，還有兩點深刻的感受：
? ? ? ? 1. New wine in old bottles
? ? ? ? ? ? 這已經一遍又一遍地在計算機發展中被驗證。
一個“古老”的想法。在新的環境下，煥發了新的生命。
短時間內受挫的方法，在新的背景下，因為一些突破。又一次得到發展。 近來火爆的深度神經網絡，不也是度過一段寒冬之后的再次重生嘛。
? ? ? ? 2. 數組索引 (index of array)的潛力
? ? ? ? ? ? 數組索引。在這里指指向數組元素的索引。如array[i]中的i。 一般數組的索引i僅僅是為了編號計數。或者是定義一種關系array[i] v.s array[j], ?i vs j。CSA中的Psi[i]數組定義通過i跟SA數組建立起一種巧妙關系。 數組索引本身不構成內存消耗，假設能巧妙設計充分利用。 會在算法設計上有意外收獲。
關于這點，是否存在理論上的指導呢？
總結
- 上一篇： 手把手教你做产品经理，视频课教程已经发布
- 下一篇： python多线程编程(1): pyth