隨著信息量的增長，高效地定位特定信息變得越來越重要。本專欄將探討全文索引領域，並集中討論作者的公共域 indexer 模塊。 本專欄將探討我的 Python 項目：indexer 模塊，並且還有一項特殊目的：我和你們一樣也一直盡力學習更多知識，為此，本專欄歡迎讀者
隨著信息量的增長，高效地定位特定信息變得越來越重要。本專欄將探討全文索引領域，並集中討論作者的公共域 indexer 模塊。
本專欄將探討我的 Python 項目：indexer 模塊，並且還有一項特殊目的：我和你們一樣也一直盡力學習更多
知識，為此，本專欄歡迎讀者提出自己的意見和想法。您的投稿將會在項目中或在未來的專欄裡出現。通常，我希望本專欄能反映出讀者的興趣和知識而不僅僅是我一個人的。這就讓我們開始吧。
我希望 indexer 模塊，即使是早期的版本也能證明給讀者是有用的。此全文 indexer 可作為單獨的實用工具或大型項目的一個模塊。其設計說明了可重復使用的
面向對象編碼的准則和文本索引（極其精妙而豐富的主題）的基本原理。盡管 Knuth曾經忠告我們：“不成熟的優化是問題的根源”，但索引的目的在於快速地找到信息，因此本專欄同時也將討論性能問題。
indexer 模塊大約是來源於某大學希望尋求一種好的方法來查找大量文本和 HTML 幫助文檔。也是我想利用多年積累下來的信件、
新聞和寫作檔案的一個小動機。很簡單， indexer 讓用戶定位文檔時，很難甚至無法以規則表達式來指定搜索條件，並且快速的執行。雖然有些商業軟件或免費工具能完成類似的工作，但大多都是針對 Web 索引。他們（即使是通過 LOGALHOST 也）需要 CGI 接口，安裝和使用都相當困難，其中只有唯一一個為 Python 設計的軟件（有不同的側重點）。另一方面，indexer 必須設計成易於使用。當然，有些更早期並且更復雜的軟件功能更強大，但 indexer 設計目的是在不失其簡單易用特性的前提下拓展功能。
關於搜索引擎 本專欄的名稱“全文 indexer”隸屬於另一個更寬泛的類別 -- “搜索引擎”。對大多數用戶，搜索引擎通常是用來定位 URL 和 WWW 的。的確，WWW 肯定是人類有史以來最大的公共文檔庫，它的非正規組織結構使其非常需要有好的搜索引擎。而且，其他文檔集 -- 特別是包括本地硬盤上不斷增加的文件 -- 也將獲益於搜索引擎。分級文件系統和文件命名規范是好方法，但他們的發展還遠遠不夠；有些時候您只需找到 包含某條信息的文檔。
互聯網搜索引擎有一半的問題在於定位其內容要被索引的文檔。雖然有很多方法可以找到許多相關的 URL，但卻沒有羅列每個有效 URL 的算法。幸運的是，當索引本地文檔（正如目前版本的 indexer 這樣）時，找到所有文檔非常簡單；這些文檔都位於明確而可定位的地方。而當用戶進一步希望索引某些目錄的子目錄樹而非其它時，文檔列表就能變得精確而無遺漏。
在設計本地搜索引擎時有兩種不同的策略。可以在搜索時察看文件的實際內容以判斷是否和搜索條件相符，也可以准備一個包含每個文件內容的
數據庫，然後搜索數據庫而不搜索文件本身。第一種方法的優點在於始終保持精確，始終能准確的定位在哪裡有您想要的哪些內容。這種特別方法的 最大缺點在於速度特別慢，而且如果進行許多次搜索的話，成本很高。
第二種方法的優點在於如果實施得當，它將快得多。一次搜索傳遞能生成文檔可搜索特性的摘要，後繼搜索就不必再次閱讀這些文檔。這使得搜索成本 更低。缺點在於，數據庫可能與文件內容不同步，需要周期性重新索引，而且這種做法會占用額外的空間（被索引文本的大小的 1% 到 100%，由搜索特性和設計選擇而定）。
這種特殊方法的示例有
Windows 下的 "File Find"、類 Unix 操作系統的 find 和 grep 工具（與 KDE 中的 kfind）、OS/2 中的 PMSeek.exe 工具和 "Find Object" 還有 MacOS 7 中的 "Finder"。數據庫方法包括 Microsoft Office 中的 "Fast Find"，Corel Office 中的 "QuickFinder"、 MacOS 8+ 中的 "Sherlock" 還有很有局限性的 Linux 的 locate 實用工具。BeOS 的 "Find" 是兩種方法的結合，但功能非常局限 -- 非全文搜索。其他操作系統也提供類似的實用工具。
有許多不同方法來指定要搜索的內容。以下為一些示例：
詞語出現頻率指出一系列搜索詞語在文檔中的出現頻度。此處假設對於給定的搜索，文檔中被搜索到的條件出現的比較頻繁，就屬於“更好”的匹配。
布爾搜索允許出現的文字與短語之間有復雜的關系。例如 "(spam AND eggs) OR (ham AND cheese)" 中，任何括號中的組合都將符合條件，而不必包括另一頭分離的詞匯。
規則表達式搜索滿足（盡可能復雜）的模式。這種方法更有利於查找高度結構化的數據，而不適合識別概念化的內容。
短語搜索只是允許多詞條件的搜索。規則表達式搜索雖然能完成相同的搜索，但更簡單的系統也能做到。
近似搜索查找一系列相互“接近”的詞語或短語。有多接近通常是一項查找選項。
詞干搜索，有時候搜索詞干而不是整個單詞。將 "run"、"runner"、"running" 和 "runs" 當作相關詞匯來考慮而將他們全部找到，而不是試圖單獨搜索符合條件的每個詞語，這種做法有時非常有效。
概念搜索通過辨別具有類似涵義的詞語來查詢具有類似主題的文檔。此類搜索需要在搜索引擎中集成某些詞典。
探測法搜索可以查詢不規則拼寫，特別是針對英語。搜索並不使用單詞在文中的拼寫，而是根據發音將其轉換為規則拼寫。然後將轉換後的文字與轉換後的搜索條件做比較。
關於 indexer indexer 使用出現的詞語的數據庫。版本 0.1X （alpha 測試版）只能搜索全文單詞結構固定的文檔。作為可選項，搜索能將符合條件的文檔按照搜索詞語的出現頻率並且對比文檔長度來排列。 indexer 能以不同方式進行擴展，某些擴展方式邏輯化而直接，其它則更為復雜。
布爾能力很簡單而且也已經在按計劃實施。由於 indexer 跟蹤哪些文檔中包含哪些單詞（和出現次數），因此如果要在規則中加入邏輯或者根據搜索詞語出現或不出現來包括文件是很容易實現的。實際上，目前的功能本質上默認為在每個查找詞語中間加 AND。（我的直覺是大多數現行的搜索都是這種 "x AND y AND z" 方式的搜索。）
規則表達式幾乎無法加入到 indexer 中，據我所知沒有一個數據庫搜索系統具有哪些文件包含符合哪些規則表達的內容的列表。實用起見，規則表達式需要以特殊方式處理 -- 為此我們使用 grep。
短語和近似搜索現在並未實行，但實施並不困難。基本上，除了每個文件中的每個詞語的出現頻率，還必須收集每個文件中詞語出現的偏移列表。根據該列表，我們能推論短語和近似度。然而，我認為這樣做會大幅增加數據庫的大小和搜索時間。
概念上，詞干和探測法搜索可能已在現有的基本框架之中，但其需要花費很大的工作量。這種方法的確能減小數據庫大小，因為只需存儲正則形式而不必存儲變化形式，但詞語轉換需要消耗外部類屬詞典和變化規則形態。
indexer 編程 建議讀者
下載 indexer 源代碼 （請參閱本文後的參考資料）。它只有一個文件，而且有詳盡的注解，相當於一本編程書籍。
以下是有關程序結構的備注。請注意文檔是編號的，每個文檔都關聯一個整數 "fileid"。
indexer 有一個 Python 詞典，其關鍵字為詞語，其值本身又是詞典，這個詞典的關鍵字為 "fileid"，其值為 "fileid" 指定的詞語在文件中的出現次數。Python 詞典的查找效率很高，而且連結 "fileid" 和實際文件名的附加工作相對很少。
從大體上說，indexer 包含一個被稱為 GenericIndexer 的抽象類。在 GenericIndexer 中定義的最重要的方法為 add_files() 和 find()。如果存儲機制需要最終化（大部分都需要）的話， save_index() 方法也很重要。
使 GenericIndexer 抽象的原因是它不能被實例化；而其子類只要完成進一步的工作後就能被實例化。術語"抽象"來源於 C++，在 C++ 中它可以是類的正規聲明。在 Python 中並沒有該正規聲明，而類的“抽象”只是類的
開發者給其用戶的建議。Python 是這樣處理的 -- 不強制數據隱藏、成員可見、繼承
需求和類似的做法，而是遵從在何時完成的規范。然而， GenericIndexer 能很好的強制執行其建議，因為它的許多方法由 "raise NotImplementedError" 行組成。特別是 __init__() 調用 "NotImplemented" 的方法之一的 load_index()。
GenericIndexer 的派生在實際存儲索引中有不同的實現方法。其中最實用的是 ZPickleIndexer，將 zlib 和 cPickle 合並，存儲壓縮的詞典。一方面為了興趣，一方面又由於令人吃驚的
性能測試結果（請參閱基准測試模塊），我創建了許多其它 SomethingIndexer 類。如果願意，shelve、XML、flat-file 和 cPickle 的類都已經具備。創建 NullIndexer 派生，高效地將每個索引存放到 /dev/null 是可能的（雖然有些無意義），而且每次開始搜索時都需要重新索引。
在提供 load_index() 和 save_index() 實現的同時，具體的（與“抽象”相反） SomethingIndexer 類從“mixin 類”中繼承 SomethingSplitter。目前，這樣的類只有 TextSplitter，但是其他相似的類會不斷出現。SomethingSplitter 提供非常重要的 splitter() 方法，它獲得一個文本字符串並把它分割成組成其的單詞。這種方法比想象的要難得 多；區分是或者不是一個單詞是非常微妙的。以後，我希望創建 TextSplitter 的派生，比如 XMLSplitter、TeXSplitter、PDFSplitter 和相似的類。而現在我們試圖以相對原始的方法查找文本單詞。
“mixin 類”是個有趣的概念，也常常是個很好的設計選擇。類似 TextSplitter 的類（或其未來的派生類）往往會包含針對許多具體派生類的有用功能。和抽象類相似，mixin 類不能直接被實例化（其有效性與禁止不同，在 mixin 中我並沒有提出 NotImplementedError。）然而，與抽象類不同的是，mixin 並不試圖包括子類的框架。TextSplitter.splitter() 基本上類似於全局通用函數，但其對范圍的控制更好。
公開 indexer 的問題 indexer 中有些具體的問題需要解決。最終，這些問題都歸結到性能。
在目前的設計中，索引被保存在單一的數據庫中，數據庫在啟動時被讀入內存（ ShelveIndexer 實際上使用三個 "書架"，但是 WORD 書架是唯一的容易引起問題的大型書架）。在一台 333 Mhz、96 MB 的 Linux 系統上讀取 3 到 4-MB 的數據庫，找到匹配的單詞然後生成結果只需要 5 秒鐘。這是非常合理的，而且比特別的搜索工具快得多。然而，隨著數據庫的擴大，性能急劇地呈非線性發展。一個 12-MB 的數據庫的讀入、裝載和查找時間增加到一分鐘。這實在難以接受，與數據庫大小增長 4 倍不成比例。看上去就象是高速緩存丟失的影響，但根據系統的實際內存它不會對於我有任何意義。
對於大型數據庫問題的一種很簡單的解決方法是將數據庫分解開。例如，不同字母開頭的索引單詞可使用不同的文件。由於大多數搜索只有幾個單詞 -- 只命中極少的首字母 -- 對於一個給定的搜索只有一小部分文件會被裝載。即使是不規則分配首字母，這樣也能很大程度上減少讀取。當然，讀取每個數據庫文件後在內存中合並詞典需要額外的處理，但這也比讀取所有文件的消耗小得多。
另一個更好的解決讀取數據庫的消耗的方法是完全避免讀取。使用 shelve 似乎可以做到這一點，它能把磁盤文件作為詞典使用而不必讀入內存。然而，在兩台測試機上安裝的 dbm 產生了 dumbdbm 和 dbhash，兩者荒唐地生成了膨脹的數據庫（其規模比 ZPickleIndexer 還大）。這不能接受，我想讀者可能也無法安裝更好的類似 gdbm 或 bsddb 的 dbm。
然而，數據庫大小的問題還會引起更重大的問題。理想狀態下，當更多文件被索引時，不會引起詞語詞典惡性增長。但是，某種情況下，好像所有可能的單詞都會被加入。可是很不幸，這樣的理想狀態並不存在。
識別真實單詞以及把它們與亂碼區分開變得非常困難，這些真實單詞中有許多在普通的英語詞典上也無法查到。一種原因是由於文檔是其它語言寫成的。商標、用戶名、URL、公司名、開放源碼項目以及許多其它場所使用的文字在 indexer 的理解下當然都是“單詞”。某些包含數據和文本的文件，類似 base64 和 uuencoding 的半二進制編碼，甚至二進制編碼意外地生成了假詞。TextSplitter 使用某些啟發式方法消除了部分此類亂碼，但是改進的 splitter 類將會使索引更接近惡性狀況。將單詞限制在一系列字母能減少大量的亂碼，但是又有太多的真實字母與數字的組合（"P2P"、"Win95"、"4DOM" 等）。歡迎提出您的建議。
總結 本專欄只涉及了 indexer 模塊和全文索引這個更廣泛主題的皮毛。隨著模塊的不斷改進以及讀者的獻計獻策，後續專欄將再次談及模塊和其背後的更多理論。
