第十六章布爾搜索 · 數據結構思維中文版

# 第十六章布爾搜索 > 原文：[Chapter 16 Boolean search](http://greenteapress.com/thinkdast/html/thinkdast017.html) > 譯者：[飛龍](https://github.com/wizardforcel) > 協議：[CC BY-NC-SA 4.0](http://creativecommons.org/licenses/by-nc-sa/4.0/) > 自豪地采用[谷歌翻譯](https://translate.google.cn/) 在本章中，我展示了上一個練習的解決方案。然后，你將編寫代碼來組合多個搜索結果，并按照它與檢索詞的相關性進行排序。 ## 16.1 爬蟲的答案首先，我們來解決上一個練習。我提供了一個`WikiCrawler`的大綱；你的工作是填寫`crawl`。作為一個提醒，這里是`WikiCrawler`類中的字段： ```java public class WikiCrawler { // keeps track of where we started private final String source; // the index where the results go private JedisIndex index; // queue of URLs to be indexed private Queue<String> queue = new LinkedList<String>(); // fetcher used to get pages from Wikipedia final static WikiFetcher wf = new WikiFetcher(); } ``` 當我們創建`WikiCrawler`時，我們傳入`source`和 index。最初`queue`只包含一個元素，`source`。注意，`queue`的實現是`LinkedList`，所以我們可以在末尾添加元素，并從開頭刪除它們 - 以常數時間。通過將`LinkedList`對象賦給`Queue`變量，我們將使用的方法限制在`Queue`接口中；具體來說，我們將使用`offer`添加元素，以及`poll`來刪除它們。這是我的`WikiCrawler.crawl`的實現： ```java public String crawl(boolean testing) throws IOException { if (queue.isEmpty()) { return null; } String url = queue.poll(); System.out.println("Crawling " + url); if (testing==false && index.isIndexed(url)) { System.out.println("Already indexed."); return null; } Elements paragraphs; if (testing) { paragraphs = wf.readWikipedia(url); } else { paragraphs = wf.fetchWikipedia(url); } index.indexPage(url, paragraphs); queueInternalLinks(paragraphs); return url; } ``` 這個方法的大部分復雜性是使其易于測試。這是它的邏輯： + 如果隊列為空，則返回`null`來表明它沒有索引頁面。 + 否則，它將從隊列中刪除并存儲下一個 URL。 + 如果 URL 已經被索引，`crawl`不會再次對其進行索引，除非它處于測試模式。 + 接下來，它讀取頁面的內容：如果它處于測試模式，它從文件讀取；否則它從 Web 讀取。 + 它將頁面索引。 + 它解析頁面并向隊列添加內部鏈接。 + 最后，它返回索引的頁面的 URL。我在 15.1 節展示了`Index.indexPage`的一個實現。所以唯一的新方法是`WikiCrawler.queueInternalLinks`。我用不同的參數編寫了這個方法的兩個版本：一個是`Elements`對象，包含每個段落的 DOM 樹，另一個是`Element`對象，包含大部分段落。第一個版本只是循環遍歷段落。第二個版本是實際的邏輯。 ```java void queueInternalLinks(Elements paragraphs) { for (Element paragraph: paragraphs) { queueInternalLinks(paragraph); } } private void queueInternalLinks(Element paragraph) { Elements elts = paragraph.select("a[href]"); for (Element elt: elts) { String relURL = elt.attr("href"); if (relURL.startsWith("/wiki/")) { String absURL = elt.attr("abs:href"); queue.offer(absURL); } } } ``` 要確定鏈接是否為“內部”鏈接，我們檢查 URL 是否以`/wiki/`開頭。這可能包括我們不想索引的一些頁面，如有關維基百科的元頁面。它可能會排除我們想要的一些頁面，例如非英語語言頁面的鏈接。但是，這個簡單的測試足以起步了。這就是它的一切。這個練習沒有很多新的材料；這主要是一個機會，把這些作品組裝到一起。 ## 16.2 信息檢索這個項目的下一個階段是實現一個搜索工具。我們需要的部分包括： + 一個界面，其中用戶可以提供檢索詞并查看結果。 + 一種查找機制，它接收每個檢索詞并返回包含它的頁面。 + 用于組合來自多個檢索詞的搜索結果的機制。 + 對搜索結果打分和排序的算法。用于這樣的過程的通用術語是“信息檢索”，你可以在 <http://thinkdast.com/infret> 上閱讀更多信息。在本練習中，我們將重點介紹步驟 3 和 4 。我們已經構建了一個 2 的簡單的版本。如果你有興趣構建 Web 應用程序，則可以考慮完成步驟 1。 ## 16.3 布爾搜索大多數搜索引擎可以執行“布爾搜索”，這意味著你可以使用布爾邏輯來組合來自多個檢索詞的結果。例如： + 搜索“java + 編程”（加號可省略）可能只返回包含兩個檢索詞：“java”和“編程”的頁面。 + “java OR 編程”可能會返回包含任一檢索詞但不一定同時出現的頁面。 + “java -印度尼西亞”可能返回包含“java”，不包含“印度尼西亞”的頁面。包含檢索詞和運算符的表達式稱為“查詢”。當應用給搜索結果時，布爾操作符`+`，`OR`和`-`對應于集合操作交，并和差。例如，假設 + `s1`是包含“java”的頁面集， + `s2`是包含“編程”的頁面集，以及 + `s3`是包含“印度尼西亞”的頁面集。在這種情況下： + `s1`和`s2`的交集是含有“java”和“編程”的頁面集。 + `s1`和`s2`的并集是含有“java”或“編程”的頁面集。 + `s1`與`s2`的差集是含有“java”而不含有“印度尼西亞”的頁面集。在下一節中，你將編寫實現這些操作的方法。 ## 16.4 練習 13 在本書的倉庫中，你將找到此練習的源文件： + + `WikiSearch.java`，它定義了一個對象，包含搜索結果并對其執行操作。 + `WikiSearchTest.java`，它包含`WikiSearch`的測試代碼。 + `Card.java`，它演示了如何使用`java.util.Collections`的`sort`方法。你還將找到我們以前練習中使用過的一些輔助類。這是`WikiSearch`類定義的起始： ```java public class WikiSearch { // map from URLs that contain the term(s) to relevance score private Map<String, Integer> map; public WikiSearch(Map<String, Integer> map) { this.map = map; } public Integer getRelevance(String url) { Integer relevance = map.get(url); return relevance==null ? 0: relevance; } } ``` `WikiSearch`對象包含 URL 到它們的相關性分數的映射。在信息檢索的上下文中，“相關性分數”用于表示頁面多么滿足從查詢推斷出的用戶需求。相關性分數的構建有很多種方法，但大部分都基于“檢索詞頻率”，它是搜索詞在頁面上的顯示次數。一種常見的相關性分數稱為 TF-IDF，代表“檢索詞頻率 - 逆向文檔頻率”。你可以在 <http://thinkdast.com/tfidf> 上閱讀更多信息。你可以選擇稍后實現 TF-IDF，但是我們將從一些更簡單的 TF 開始： + 如果查詢包含單個檢索詞，頁面的相關性就是其詞頻；也就是說該詞在頁面上出現的次數。 + 對于具有多個檢索詞的查詢，頁面的相關性是檢索詞頻率的總和；也就是說，任何檢索詞出現的總次數。現在你準備開始練習了。運行`ant build`來編譯源文件，然后運行 `ant WikiSearchTest`。像往常一樣，它應該失敗，因為你有工作要做。在`WikiSearch.java`中，填充的`and`，`or`以及`minus`的主體，使相關測試通過。你不必擔心`testSort`。你可以運行`WikiSearchTest`而不使用`Jedis`，因為它不依賴于 Redis 數據庫中的索引。但是，如果要對索引運行查詢，則必須向文件提供有關`Redis`服務器的信息。詳見 14.3 節。運行`ant JedisMaker`來確保它配置為連接到你的 Redis 服務器。然后運行`WikiSearch`，它打印來自三個查詢的結果： + “java” + “programming” + “java AND programming” 最初的結果不按照特定的順序，因為`WikiSearch.sort`是不完整的。填充`sort`的主體，使結果以遞增的相關順序返回。我建議你使用`java.util.Collections`提供的`sort`方法，它可以排序任何種類的`List`。你可以閱讀 <http://thinkdast.com/collections> 上的文檔。有兩個`sort`版本： + 單參數版本接受列表并使用它的`compareTo`方法對元素進行排序，因此元素必須是`Comparable`。 + 雙參數版本接受任何對象類型的列表和一個`Comparator`，它是一個提供`compare`方法的對象，用于比較元素。如果你不熟悉`Comparable`和`Comparator`接口，我將在下一節中解釋它們。 ## 16.5 `Comparable`和`Comparator` 本書的倉庫包含了`Card.java`，它演示了兩個方式來排序`Card`對象的列表。這里是類定義的起始： ```java public class Card implements Comparable<Card> { private final int rank; private final int suit; public Card(int rank, int suit) { this.rank = rank; this.suit = suit; } ``` `Card`對象擁有兩個整形字段，`rank`和`suit`。`Card`實現了`Comparable<Card>`，也就是說它提供`compareTo`： ```java public int compareTo(Card that) { if (this.suit < that.suit) { return -1; } if (this.suit > that.suit) { return 1; } if (this.rank < that.rank) { return -1; } if (this.rank > that.rank) { return 1; } return 0; } ``` `compareTo`規范表明，如果`this`小于`that`，則應該返回一個負數，如果它更大，則為正數，如果它們相等則為`0`。如果使用單參數版本的`Collections.sort`，它將使用元素提供的`compareTo`方法對它們進行排序。為了演示，我們可以列出`52`張卡，如下所示： ```java public static List<Card> makeDeck() { List<Card> cards = new ArrayList<Card>(); for (int suit = 0; suit <= 3; suit++) { for (int rank = 1; rank <= 13; rank++) { Card card = new Card(rank, suit); cards.add(card); } } return cards; } ``` 并這樣排序它們： ```java Collections.sort(cards); ``` 這個版本的`sort`將元素按照所謂的“自然秩序”放置，因為它由對象本身決定。但是可以通過提供一個`Comparator`對象，來強制實現不同的排序。例如，`Card`對象的自然順序將`Ace`視為最小的牌，但在某些紙牌游戲中，它的排名最高。我們可以定義一個`Comparator`，將`Ace`視為最大的牌，像這樣： ```java Comparator<Card> comparator = new Comparator<Card>() { @Override public int compare(Card card1, Card card2) { if (card1.getSuit() < card2.getSuit()) { return -1; } if (card1.getSuit() > card2.getSuit()) { return 1; } int rank1 = getRankAceHigh(card1); int rank2 = getRankAceHigh(card2); if (rank1 < rank2) { return -1; } if (rank1 > rank2) { return 1; } return 0; } private int getRankAceHigh(Card card) { int rank = card.getRank(); if (rank == 1) { return 14; } else { return rank; } } }; ``` 該代碼定義了一個匿名類，按需實現`compare`。然后它創建一個新定義的匿名類的實例。如果你不熟悉 Java 中的匿名類，可以在 <http://thinkdast.com/anonclass> 上閱讀它們。使用這個`Comparator`，我們可以這樣調用`sort`： ```java Collections.sort(cards, comparator); ``` 在這個順序中，黑桃的`Ace`是牌組上的最大的牌；梅花二是最小的。如果你想試驗這個部分的代碼，它們在`Card.java`中。作為一個練習，你可能打算寫一個比較器，先按照`rank`，然后再按照`suit`，所以所有的`Ace`都應該在一起，所有的二也是。以此類推。 ## 16.6 擴展如果你完成了此練習的基本版本，你可能需要處理這些可選練習： + 請閱讀 <http://thinkdast.com/tfidf> 上的 TF-IDF，并實現它。你可能需要修改`JavaIndex`來計算文檔頻率；也就是說，每個檢索詞在索引的所有頁面上出現的總次數。 + 對于具有多個檢索詞的查詢，每個頁面的總體相關性目前是每個檢索詞的相關性的總和。想想這個簡單版本什么時候可能無法正常運行，并嘗試一些替代方案。 + 構建用戶界面，允許用戶輸入帶有布爾運算符的查詢。解析查詢，生成結果，然后按相關性排序，并顯示評分最高的 URL。考慮生成“片段”，它顯示了檢索詞出現在頁面的哪里。如果要為用戶界面制作 Web 應用程序，請考慮將 Heroku 作為簡單選項，用于開發和部署 Java Web應用程序。見 <http://thinkdast.com/heroku>。