當用戶在文本編輯器或者文字處理軟件中搜索一個單詞或者句子的時候，軟件就會對文件進行掃描并尋找那個單詞或者句子。如果讀者曾經使用過linux、Unix或者OS X的grep程序，或者曾經使用過windows內置的文件搜索功能來查找包含特定單詞或者句子的文件，那么應該就會注意到，被搜索文件的數量越多、體積越大，搜索花費的時間也會越長。

與在本地電腦上面進行的搜索不同，在Web上面搜索Web頁面或者其他內容的速度總是非常快的，即使在文檔的體積和數量都非常巨大的情況下，也是如此。在這一節中，我們將學習如何改變程序搜索數據的方式，并使用redis來減少絕大部分基于單詞或者關鍵字進行的內容搜索操作的執行時間。

為了給遇到問題的用戶予以幫助，Fake Garage創業公司建立了一個由疑難解答文章組成的知識庫。最近幾個月以來，隨著知識庫文章的數量和品種不斷增多，使用數據庫驅動的搜索程序也變得越來越慢。因為Redis具備構建內容搜索引擎所需的全部功能，所以我們決定使用Redis來構建一個新的搜索程序，從而提高對知識庫文章的搜索速度。

我們首先要做的就是思考這樣一個問題：比起一個單詞接一個單詞地掃描文檔，如何才能以更快的速度對文檔進行搜索？

7.1.1　基本搜索原理

為了獲得比掃描文檔更快的搜索速度，我們需要對文檔進行預處理，這個預處理步驟通常被稱為建索引（indexing），而我們要創建的結構則被稱為反向索引（inverted indexes）。反向索引是互聯網上絕大部分搜索引擎所使用的底層結構，它在搜索領域里面幾乎無人不知。從很多方面來看，創建反向索引就像是在生成一些類似于書本末尾的索引那樣的東西。我們選擇使用Redis來創建反向索引的原因在于，Redis自帶的集合和有序集合①都非常適合于處理反向索引。

具體來說，反向索引會從每個被索引的文檔里面提取出一些單詞，并創建表格來記錄每篇文章都包含了哪些單詞。對于只包含標題《lord of the rings》的文檔docA以及只包含標題《lord of the dance》的文檔docB，程序將在Redis里面為lord這個單詞創建一個集合，并在集合里面包含docA和docB這兩個文檔的名字，以此來表示docA和docB這兩個文檔都包含了單詞lord。圖7-1展示了程序為這兩個文檔創建的所有反向索引。

圖7-1　為docA和docB創建的反向索引

在知道了索引操作的最終執行結果就是產生一些Redis集合之后，我們接下來要了解的就是生成這些集合的具體方法。

1．基本索引操作

為了給文檔構建索引集合，程序首先需要對文檔包含的單詞進行處理。從文檔里面提取單詞的過程通常被稱為語法分析（parsing）和標記化（tokenization），這個過程可以產生出一系列用于標識文檔的標記（token），標記有時候又被稱為單詞（word）。

生成標記的方法有很多種。用于處理Web頁面的方法，與處理關系數據庫的行或者處理文檔數據庫的文檔所使用的方法，可能會有所不同。為了讓標記化過程保持簡單，我們認定單詞只能由英文字母和單引號(')組成，并且每個單詞至少要有兩個字符長。這一規則可以覆蓋大部分英文單詞，并忽略諸如I和a這樣的單詞。

標記化的一個常見的附加步驟，就是移除內容中的非用詞（stop word）。非用詞就是那些在文檔中頻繁出現但是卻沒有提供相應信息量的單詞，對這些單詞進行搜索將返回大量無用的結果。移除非用詞不僅可以提高搜索性能，還可以減少索引的體積。圖7-2展示了對示例文本進行標記化并移除非用詞的過程。

圖7-2　將本節的一部分原文標記化為多個單詞，并移除其中的非用詞

因為不同類型的文檔都有各自的常用單詞，而這些常用單詞也許會對非用詞產生影響，所以移除非用詞的關鍵就是要找到合適的非用詞清單。代碼清單7-1展示了從非用詞清單，以及對文檔進行標記化處理、移除非用詞并創建索引的函數。

代碼清單7-1　對文檔進行標記化處理并創建索引的函數

因為of和the都是非用詞，所以在使用代碼清單7-1展示的標記化函數和索引函數去處理之前提到的docA和docB的時候，程序將為單詞lord、rings和dance創建相應的集合，而不是為單詞lord、of、the、rings和dance都創建集合。

從索引里面移除文檔　如果被索引文檔的內容可能會隨著時間而出現變化，那么就需要有一個功能來自動刪除文檔已有的索引并重新建立索引，或者智能地為文檔刪除無效的索引并添加新索引。實現這個功能的一個比較簡單的方法，就是使用JSON編碼的列表把文檔已經建立了索引的單詞記錄起來，并通過SET命令將這個列表存儲到一個鍵里面，最后再在index_document()函數的開頭添加一些刪除不必要索引的代碼。

既然我們已經掌握了為知識庫文檔生成反向索引的方法，那么接下來是時候學習如何搜索這些文檔了。

2．基本搜索操作

在索引里面查找一個單詞是非常容易的，程序只需要獲取單詞集合里面的所有文檔就可以了。但是要根據兩個或多個單詞查找文檔的話，程序就需要把給定單詞集合里面的所有文檔都找出來，然后再從中找到那些在所有單詞集合里面都出現了的文檔。第3章中曾經介紹過如何使用Redis的SINTER命令和SINTERSTORE命令來找出那些同時存在于所有給定集合的元素，而這一次，我們同樣可以使用這兩個命令來找出那些包含了所有給定單詞的文檔。

使用交集操作處理反向索引的好處不在于能夠找到多少文檔，甚至不在于能夠多快地找出結果，而在于能夠徹底地忽略無關的信息。在以文本編輯器的方式對文本進行搜索的時候，很多無用的數據都會被仔細檢查，但是因為反向索引已經知道了每篇文檔包含的單詞，所以程序只需要對文檔進行過濾，找出那些包含了所有給定單詞的文檔就可以了。

用戶有些時候可能會想要使用多個具有相同意思的單詞進行搜索，并把它們看作是同一個單詞，我們把這樣的單詞稱為同義詞。為了處理這種情況，程序可以取出同義詞對應的全部文檔集合，并從中找出所有獨一無二的文檔，或者直接使用Redis內置的SUNION命令或者SUNIONSTORE命令。

除此之外，用戶可能偶爾也想要搜索那些包含了某些特定單詞或者句子，但是并不包含另外一些單詞或句子的文檔，使用Redis的SDIFF和SDIFFSTORE這兩個集合命令可以做到這一點。

通過使用Redis的集合操作以及一些輔助代碼，程序可以對文檔執行各種復雜的單詞查詢操作。代碼清單7-2展示了一組輔助函數，它們可以對給定單詞對應的集合執行交集計算、并集計算和差集計算，并將計算結果存儲到一個默認過期時間為30秒的臨時集合里面。

代碼清單7-2　對集合進行交集計算、并集計算和差集計算的輔助函數

函數intersect()、union()和difference()都會調用同一個輔助函數來完成實際的工作，因為它們要做的事情本質上是一樣的：準備好相關的數據庫鍵，執行正確的集合命令，更新過期時間并返回新集合的ID。圖7-3以文氏圖的方式形象地展示了3個不同的集合命令SINTER、 SUNION和SDIFF的執行過程。

圖7-3　在文氏圖上進行交集計算、并集計算和差集計算的樣子

以上就是實現一個搜索引擎所需的全部代碼，我們接下來要考慮的是如何對用戶給定的搜索查詢語句進行語法分析。

3．分析并執行搜索

到目前為止，我們已經具備了建立索引和進行搜索所需的絕大部分工具，包括標記化函數、索引函數以及基本的交集計算函數、并集計算函數和差集計算函數，唯一缺少的就是一個將文本查詢語句轉換成搜索操作的函數。為此，我們將實現一個搜索函數，它可以查找那些包含了所有給定單詞的文檔，并允許我們指定同義詞以及不需要的單詞。

最基本的搜索旨在找出那些包含了所有給定單詞的文檔。如果用戶只是單純地給出了一些單詞，那么搜索程序只需要直接執行一個intersect()調用就可以了。如果用戶在某個單詞的前面加上了一個減號（-），那么就表示用戶不希望包含這個單詞的文檔出現在搜索結果里面，搜索程序就需要使用difference()移除相應的文檔。如果用戶在某個單詞的前面加上了一個加號（+），那么就表示這個單詞是前一個單詞的同義詞，搜索程序首先會收集各個同義詞組并對它們執行union()操作，然后再執行高層次的intersect()調用（如果帶+號的單詞前面有帶-號的單詞，那么程序會略過那些帶-號的單詞，并把最先遇到的不帶-號的單詞看作是同義詞）。

根據以上介紹的區分同義詞和不需要單詞的規則，代碼清單7-3展示了一段代碼，它可以將用戶輸入的查詢語句解釋為一個Python列表，這個列表里面記錄了哪些單詞是同義詞，哪些單詞是不需要的單詞。

代碼清單7-3　搜索查詢語句的語法分析函數

為了對這個語法分析函數進行測試，我們需要使用它在知識庫里面搜索一些與連接聊天室有關的問題。我們想要找的是一些包含connect、connection、disconnect或disconnection以及chat等一系列單詞的文章。此外，因為我們沒有使用代理，所以我們希望能夠跳過那些帶有proxy或proxies單詞的文檔。以下交互示例展示了這一查詢的執行過程（為了方便閱讀，對代碼進行了分組格式化）：

從執行結果可以看到，函數正確地為connect和disconnect提取出了同義詞，并將chat單獨劃分為一個單詞，另外還找出了不需要的單詞proxy和proxies。除非是為了進行調試，否則這些分析結果一般都不會被傳遞到其他地方——因為parse_and_search()函數會在內部直接調用parse()函數，并根據需要使用union()函數對各個同義詞列表進行并集計算，使用intersect()函數對最終挑選出的單詞列表進行交集計算，以及使用difference()函數移除那些不需要的單詞。代碼清單7-4展示了parse_and_search()函數的完整代碼。

代碼清單7-4　用于分析查詢語句并搜索文檔的函數

和之前介紹的集合計算輔助函數一樣，parse_and_search()函數也會返回一個集合ID作為執行結果，這個ID對應的集合里面包含了與用戶給定的搜索參數相匹配的文檔。現在，Fake Garage創業公司只要使用之前介紹過的index_document()函數為他們的所有文檔創建索引，就可以使用parse_and_search()函數對那些文檔進行搜索了。

雖然我們現在擁有了一個能夠根據給定條件搜索文檔的程序，但是隨著文檔數量變得越來越大，能夠讓搜索結果根據特定的順序進行排序將變得非常重要。為了做到這一點，我們需要學習如何對搜索結果進行排序。

7.1.2　對搜索結果進行排序

雖然我們已經可以根據給定的單詞對索引內的文檔進行搜索，但這只是我們檢索所需信息的第一步。搜索程序在取得多個文檔之后，通常還需要根據每個文檔的重要性對它們進行排序——搜索領域把這一問題稱為關聯度計算問題，而判斷一個文檔是否比另一個文檔具有更高關聯度的其中一種方法，就是看哪個文檔的更新時間最接近當前時間。接下來我們將學習如何在搜索結果中引入對關聯度的支持。

本書在第3章中曾經介紹過，Redis的SORT命令可以對列表或者集合存儲的內容進行排序，甚至還可以引用外部數據。Fake Garage創業公司的知識庫把每篇文章的相關信息都存儲在散列里面，這些信息包括文章的標題、文章創建時的時間戳、文章最后一次更新時的時間戳以及文檔ID。圖7-4展示了一個存儲著文檔信息的散列示例。

圖7-4　使用散列存儲文檔信息的示例

對于圖7-4這種存儲在散列里面的文檔，使用SORT命令可以根據文檔的不同屬性對文檔進行排序。雖然前面介紹的parse_and_search()函數會為搜索結果設置較短的過期時間，使得搜索結果在使用完畢之后能夠盡快被刪掉，但是對于排序之后的搜索結果，我們可以多保存它們一會兒，以便在有需要的時候對它們進行重新排序或者執行分頁操作。代碼清單7-5展示了一個整合了結果緩存功能以及重新排序功能的搜索函數。

代碼清單7-5　分析查詢語句然后進行搜索，并對搜索結果進行排序的函數

search_and_sort()函數除了可以搜索文檔并對結果進行排序之外，還允許用戶通過更新start參數和num參數對搜索結果進行分頁；通過sort參數改變排序依據的屬性，從而改變結果的排列順序；通過修改ttl參數改變結果的緩存時間；以及通過id參數引用已有的搜索結果，從而節約計算時間。

盡管這些搜索函數還不足以讓我們創建一個媲美google的搜索引擎，但筆者當初就是因為被這個問題以及它的解決方法所吸引，才開始使用Redis的。SORT命令的一些限制使得我們需要使用有序集合才能實現形式更為復雜的文檔搜索操作，其中包括基于多個分值進行的復合排序操作，具體的信息將在接下來的一節介紹。

7.2　有序索引

上一節主要討論了如何使用Redis實現搜索功能，并通過引用存儲在散列里面的數據對搜索結果進行排序。這種排序方法非常適合在元素的排列順序（sort order）可以用字符串或者數字表示的情況下使用，但它并不能處理元素的排列順序由幾個不同分值組合而成的情況。本節將展示如何使用集合以及有序集合實現基于多個分值的復合排序操作，它能夠提供比SORT命令更高的靈活性。

稍早之前，在使用SORT命令從散列里面獲取排序所需數據的時候，散列的作用與關系數據庫里面的行非常相似。如果我們把文章的更新時間存儲到有序集合里面，然后通過ZINTERSTORE命令以及它的MAX聚合函數，對存儲了文章搜索結果的集合以及存儲了文章更新時間的有序集合執行交集計算，那么就可以根據文章的更新時間對搜索結果內的所有文章進行排序。

本文摘自《Redis實戰》