第十六章 布爾搜索

原文：Chapter 16 Boolean search

譯者：飛龍

協(xié)議：CC BY-NC-SA 4.0

自豪地采用谷歌翻譯

在本章中，我展示了上一個(gè)練習(xí)的解決方案。然后，你將編寫代碼來組合多個(gè)搜索結(jié)果，并按照它與檢索詞的相關(guān)性進(jìn)行排序。

16.1 爬蟲的答案

首先，我們來解決上一個(gè)練習(xí)。我提供了一個(gè)WikiCrawler的大綱；你的工作是填寫crawl。作為一個(gè)提醒，這里是WikiCrawler類中的字段：

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();
}

當(dāng)我們創(chuàng)建WikiCrawler時(shí)，我們傳入source和 index。最初queue只包含一個(gè)元素，source。

注意，queue的實(shí)現(xiàn)是LinkedList，所以我們可以在末尾添加元素，并從開頭刪除它們 - 以常數(shù)時(shí)間。通過將LinkedList對(duì)象賦給Queue變量，我們將使用的方法限制在Queue接口中；具體來說，我們將使用offer添加元素，以及poll來刪除它們。

這是我的WikiCrawler.crawl的實(shí)現(xiàn)：

    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;
    }

這個(gè)方法的大部分復(fù)雜性是使其易于測(cè)試。這是它的邏輯：

• 如果隊(duì)列為空，則返回null來表明它沒有索引頁面。
• 否則，它將從隊(duì)列中刪除并存儲(chǔ)下一個(gè) URL。
• 如果 URL 已經(jīng)被索引，crawl不會(huì)再次對(duì)其進(jìn)行索引，除非它處于測(cè)試模式。
• 接下來，它讀取頁面的內(nèi)容：如果它處于測(cè)試模式，它從文件讀??；否則它從 Web 讀取。
• 它將頁面索引。
• 它解析頁面并向隊(duì)列添加內(nèi)部鏈接。
• 最后，它返回索引的頁面的 URL。

我在 15.1 節(jié)展示了Index.indexPage的一個(gè)實(shí)現(xiàn)。所以唯一的新方法是WikiCrawler.queueInternalLinks。

我用不同的參數(shù)編寫了這個(gè)方法的兩個(gè)版本：一個(gè)是Elements對(duì)象，包含每個(gè)段落的 DOM 樹，另一個(gè)是Element對(duì)象，包含大部分段落。

第一個(gè)版本只是循環(huán)遍歷段落。第二個(gè)版本是實(shí)際的邏輯。

    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);
            }
        }
    }

要確定鏈接是否為“內(nèi)部”鏈接，我們檢查 URL 是否以/wiki/開頭。這可能包括我們不想索引的一些頁面，如有關(guān)維基百科的元頁面。它可能會(huì)排除我們想要的一些頁面，例如非英語語言頁面的鏈接。但是，這個(gè)簡(jiǎn)單的測(cè)試足以起步了。

這就是它的一切。這個(gè)練習(xí)沒有很多新的材料；這主要是一個(gè)機(jī)會(huì)，把這些作品組裝到一起。

16.2 信息檢索

這個(gè)項(xiàng)目的下一個(gè)階段是實(shí)現(xiàn)一個(gè)搜索工具。我們需要的部分包括：

• 一個(gè)界面，其中用戶可以提供檢索詞并查看結(jié)果。
• 一種查找機(jī)制，它接收每個(gè)檢索詞并返回包含它的頁面。
• 用于組合來自多個(gè)檢索詞的搜索結(jié)果的機(jī)制。
• 對(duì)搜索結(jié)果打分和排序的算法。

用于這樣的過程的通用術(shù)語是“信息檢索”，你可以在 http://thinkdast.com/infret 上閱讀更多信息 。

在本練習(xí)中，我們將重點(diǎn)介紹步驟 3 和 4 。我們已經(jīng)構(gòu)建了一個(gè) 2 的簡(jiǎn)單的版本。如果你有興趣構(gòu)建 Web 應(yīng)用程序，則可以考慮完成步驟 1。

16.3 布爾搜索

大多數(shù)搜索引擎可以執(zhí)行“布爾搜索”，這意味著你可以使用布爾邏輯來組合來自多個(gè)檢索詞的結(jié)果。例如：

• 搜索“java + 編程”（加號(hào)可省略）可能只返回包含兩個(gè)檢索詞：“java”和“編程”的頁面。
• “java OR 編程”可能會(huì)返回包含任一檢索詞但不一定同時(shí)出現(xiàn)的頁面。
• “java -印度尼西亞”可能返回包含“java”，不包含“印度尼西亞”的頁面。

包含檢索詞和運(yùn)算符的表達(dá)式稱為“查詢”。

當(dāng)應(yīng)用給搜索結(jié)果時(shí)，布爾操作符+，OR和-對(duì)應(yīng)于集合操作 交，并和差。例如，假設(shè)

• s1是包含“java”的頁面集，
• s2是包含“編程”的頁面集，以及
• s3是包含“印度尼西亞”的頁面集。

在這種情況下：

• s1和s2的交集是含有“java”和“編程”的頁面集。
• s1和s2的并集是含有“java”或“編程”的頁面集。
• s1與s2的差集是含有“java”而不含有“印度尼西亞”的頁面集。

在下一節(jié)中，你將編寫實(shí)現(xiàn)這些操作的方法。

16.4 練習(xí) 13

在本書的倉(cāng)庫中，你將找到此練習(xí)的源文件：

• WikiSearch.java，它定義了一個(gè)對(duì)象，包含搜索結(jié)果并對(duì)其執(zhí)行操作。
• WikiSearchTest.java，它包含WikiSearch的測(cè)試代碼。
• Card.java，它演示了如何使用java.util.Collections的sort方法。

你還將找到我們以前練習(xí)中使用過的一些輔助類。

這是WikiSearch類定義的起始：

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對(duì)象包含 URL 到它們的相關(guān)性分?jǐn)?shù)的映射。在信息檢索的上下文中，“相關(guān)性分?jǐn)?shù)”用于表示頁面多么滿足從查詢推斷出的用戶需求。相關(guān)性分?jǐn)?shù)的構(gòu)建有很多種方法，但大部分都基于“檢索詞頻率”，它是搜索詞在頁面上的顯示次數(shù)。一種常見的相關(guān)性分?jǐn)?shù)稱為 TF-IDF，代表“檢索詞頻率 - 逆向文檔頻率”。你可以在 http://thinkdast.com/tfidf 上閱讀更多信息 。

你可以選擇稍后實(shí)現(xiàn) TF-IDF，但是我們將從一些更簡(jiǎn)單的 TF 開始：

• 如果查詢包含單個(gè)檢索詞，頁面的相關(guān)性就是其詞頻；也就是說該詞在頁面上出現(xiàn)的次數(shù)。
• 對(duì)于具有多個(gè)檢索詞的查詢，頁面的相關(guān)性是檢索詞頻率的總和；也就是說，任何檢索詞出現(xiàn)的總次數(shù)。

現(xiàn)在你準(zhǔn)備開始練習(xí)了。運(yùn)行ant build來編譯源文件，然后運(yùn)行 ant WikiSearchTest。像往常一樣，它應(yīng)該失敗，因?yàn)槟阌泄ぷ饕觥?/p>

在WikiSearch.java中，填充的and，or以及minus的主體，使相關(guān)測(cè)試通過。你不必?fù)?dān)心testSort。

你可以運(yùn)行WikiSearchTest而不使用Jedis，因?yàn)樗灰蕾囉?Redis 數(shù)據(jù)庫中的索引。但是，如果要對(duì)索引運(yùn)行查詢，則必須向文件提供有關(guān)Redis服務(wù)器的信息。詳見 14.3 節(jié)。

運(yùn)行ant JedisMaker來確保它配置為連接到你的 Redis 服務(wù)器。然后運(yùn)行WikiSearch，它打印來自三個(gè)查詢的結(jié)果：

• “java”
• “programming”
• “java AND programming”

最初的結(jié)果不按照特定的順序，因?yàn)?code>WikiSearch.sort是不完整的。

填充sort的主體，使結(jié)果以遞增的相關(guān)順序返回。我建議你使用java.util.Collections提供的sort方法，它可以排序任何種類的List。你可以閱讀 http://thinkdast.com/collections 上的文檔 。

有兩個(gè)sort版本：

• 單參數(shù)版本接受列表并使用它的compareTo方法對(duì)元素進(jìn)行排序，因此元素必須是Comparable。
• 雙參數(shù)版本接受任何對(duì)象類型的列表和一個(gè)Comparator，它是一個(gè)提供compare方法的對(duì)象，用于比較元素。

如果你不熟悉Comparable和Comparator接口，我將在下一節(jié)中解釋它們。

16.5 Comparable和Comparator

本書的倉(cāng)庫包含了Card.java，它演示了兩個(gè)方式來排序Card對(duì)象的列表。這里是類定義的起始：

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對(duì)象擁有兩個(gè)整形字段，rank和suit。Card實(shí)現(xiàn)了Comparable<Card>，也就是說它提供compareTo：

    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規(guī)范表明，如果this小于that，則應(yīng)該返回一個(gè)負(fù)數(shù)，如果它更大，則為正數(shù)，如果它們相等則為0。

如果使用單參數(shù)版本的Collections.sort，它將使用元素提供的compareTo方法對(duì)它們進(jìn)行排序。為了演示，我們可以列出52張卡，如下所示：

    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;
    }

并這樣排序它們：

        Collections.sort(cards);

這個(gè)版本的sort將元素按照所謂的“自然秩序”放置，因?yàn)樗蓪?duì)象本身決定。

但是可以通過提供一個(gè)Comparator對(duì)象，來強(qiáng)制實(shí)現(xiàn)不同的排序。例如，Card對(duì)象的自然順序?qū)?code>Ace視為最小的牌，但在某些紙牌游戲中，它的排名最高。我們可以定義一個(gè)Comparator，將Ace視為最大的牌，像這樣：

        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;
                }
            }
        };

該代碼定義了一個(gè)匿名類，按需實(shí)現(xiàn)compare。然后它創(chuàng)建一個(gè)新定義的匿名類的實(shí)例。如果你不熟悉 Java 中的匿名類，可以在 http://thinkdast.com/anonclass 上閱讀它們。

使用這個(gè)Comparator，我們可以這樣調(diào)用sort：

        Collections.sort(cards, comparator);

在這個(gè)順序中，黑桃的Ace是牌組上的最大的牌；梅花二是最小的。

如果你想試驗(yàn)這個(gè)部分的代碼，它們?cè)?code>Card.java中。作為一個(gè)練習(xí)，你可能打算寫一個(gè)比較器，先按照rank，然后再按照suit，所以所有的Ace都應(yīng)該在一起，所有的二也是。以此類推。

16.6 擴(kuò)展

如果你完成了此練習(xí)的基本版本，你可能需要處理這些可選練習(xí)：

• 請(qǐng)閱讀 http://thinkdast.com/tfidf 上的 TF-IDF，并實(shí)現(xiàn)它。你可能需要修改JavaIndex來計(jì)算文檔頻率；也就是說，每個(gè)檢索詞在索引的所有頁面上出現(xiàn)的總次數(shù)。
• 對(duì)于具有多個(gè)檢索詞的查詢，每個(gè)頁面的總體相關(guān)性目前是每個(gè)檢索詞的相關(guān)性的總和。想想這個(gè)簡(jiǎn)單版本什么時(shí)候可能無法正常運(yùn)行，并嘗試一些替代方案。
• 構(gòu)建用戶界面，允許用戶輸入帶有布爾運(yùn)算符的查詢。解析查詢，生成結(jié)果，然后按相關(guān)性排序，并顯示評(píng)分最高的 URL?？紤]生成“片段”，它顯示了檢索詞出現(xiàn)在頁面的哪里。如果要為用戶界面制作 Web 應(yīng)用程序，請(qǐng)考慮將 Heroku 作為簡(jiǎn)單選項(xiàng)，用于 開發(fā)和部署 Java Web應(yīng)用程序。見 http://thinkdast.com/heroku。