第八章 索引器

原文：Chapter 8 Indexer

譯者：飛龍

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

自豪地采用谷歌翻譯

目前，我們構(gòu)建了一個基本的 Web 爬蟲；我們下一步將是索引服协。在網(wǎng)頁搜索的上下文中，索引是一種數(shù)據(jù)結(jié)構(gòu)啦粹，可以查找檢索詞并找到該詞出現(xiàn)的頁面偿荷。此外，我們想知道每個頁面上顯示檢索詞的次數(shù)唠椭，這將有助于確定與該詞最相關(guān)的頁面跳纳。

例如，如果用戶提交檢索詞“Java”和“編程”贪嫂，我們將查找兩個檢索詞并獲得兩組頁面寺庄。帶有“Java”的頁面將包括 Java 島嶼，咖啡昵稱以及編程語言的網(wǎng)頁力崇。具有“編程”一詞的頁面將包括不同編程語言的頁面斗塘，以及該單詞的其他用途。通過選擇具有兩個檢索詞的頁面亮靴，我們希望消除不相關(guān)的頁面馍盟，并找到 Java 編程的頁面。

現(xiàn)在我們了解索引是什么茧吊，它執(zhí)行什么操作贞岭，我們可以設(shè)計(jì)一個數(shù)據(jù)結(jié)構(gòu)來表示它八毯。

8.1 數(shù)據(jù)結(jié)構(gòu)選取

索引的基本操作是查找；具體來說曹步，我們需要能夠查找檢索詞并找到包含它的所有頁面宪彩。最簡單的實(shí)現(xiàn)將是頁面的集合。給定一個檢索詞讲婚，我們可以遍歷頁面的內(nèi)容尿孔，并選擇包含檢索詞的內(nèi)容。但運(yùn)行時間與所有頁面上的總字?jǐn)?shù)成正比筹麸，這太慢了活合。

一個更好的選擇是一個映射（字典），它是一個數(shù)據(jù)結(jié)構(gòu)物赶，表示鍵值對的集合白指，并提供了一種方法，快速查找鍵以及相應(yīng)值酵紫。例如告嘲，我們將要構(gòu)建的第一個映射是TermCounter，它將每個檢索詞映射為頁面中出現(xiàn)的次數(shù)奖地。鍵是檢索詞橄唬，值是計(jì)數(shù)（也稱為“頻率”）。

Java 提供了Map的調(diào)用接口参歹，它指定映射應(yīng)該提供的方法仰楚；最重要的是：

• get(key)：此方法查找一個鍵并返回相應(yīng)的值。
• put(key, value)：該方法向Map添加一個新的鍵值對犬庇，或者如果該鍵已經(jīng)在映射中僧界，它將替換與key關(guān)聯(lián)的值。

Java 提供了幾個Map實(shí)現(xiàn)臭挽，包括我們將關(guān)注的兩個捂襟，HashMap以及TreeMap。在即將到來的章節(jié)中欢峰，我們將介紹這些實(shí)現(xiàn)并分析其性能葬荷。

除了檢索詞到計(jì)數(shù)的映射TermCounter之外，我們將定義一個被稱為Index的類赤赊，它將檢索詞映射為出現(xiàn)的頁面的集合闯狱。而這又引發(fā)了下一個問題，即如何表示頁面集合抛计。同樣哄孤，如果我們考慮我們想要執(zhí)行的操作，它們就指導(dǎo)了我們的決定吹截。

在這種情況下瘦陈，我們需要組合兩個或多個集合凝危，并找到所有這些集合中顯示的頁面。你可以將此操作看做集合的交集：兩個集合的交集是出現(xiàn)在兩者中的一組元素晨逝。

你可能猜到了蛾默，Java 提供了一個Set接口，來定義集合應(yīng)該執(zhí)行的操作捉貌。它實(shí)際上并不提供設(shè)置交集支鸡，但它提供了方法，使我們能夠有??效地實(shí)現(xiàn)交集和其他結(jié)合操作趁窃。核心的Set方法是：

• add(element)：該方法將一個元素添加到集合中牧挣；如果元素已經(jīng)在集合中，則它不起作用醒陆。
• contains(element)：該方法檢查給定元素是否在集合中瀑构。

Java 提供了幾個Set實(shí)現(xiàn)，包括HashSet和TreeSet刨摩。

現(xiàn)在我們自頂向下設(shè)計(jì)了我們的數(shù)據(jù)結(jié)構(gòu)寺晌，我們將從內(nèi)到外實(shí)現(xiàn)它們，從TermCounter開始澡刹。

8.2 TermCounter

TermCounter是一個類呻征，表示檢索詞到頁面中出現(xiàn)次數(shù)的映射。這是類定義的第一部分：

public class TermCounter {

    private Map<String, Integer> map;
    private String label;

    public TermCounter(String label) {
        this.label = label;
        this.map = new HashMap<String, Integer>();
    }
}

實(shí)例變量map包含檢索詞到計(jì)數(shù)的映射像屋，并且label標(biāo)識檢索詞的來源文檔怕犁；我們將使用它來存儲 URL边篮。

為了實(shí)現(xiàn)映射己莺，我選擇了HashMap，它是最常用的Map戈轿。在幾章中凌受，你將看到它是如何工作的，以及為什么它是一個常見的選擇思杯。

TermCounter提供put和get胜蛉，定義如下：

    public void put(String term, int count) {
        map.put(term, count);
    }

    public Integer get(String term) {
        Integer count = map.get(term);
        return count == null ? 0 : count;
    }

put只是一個包裝方法；當(dāng)你調(diào)用TermCounter的put時色乾，它會調(diào)用內(nèi)嵌映射的put誊册。

另一方面，get做了一些實(shí)際工作暖璧。當(dāng)你調(diào)用TermCounter的get時案怯，它會在映射上調(diào)用get，然后檢查結(jié)果澎办。如果該檢索詞沒有出現(xiàn)在映射中嘲碱，則TermCount.get返回0金砍。get的這種定義方式使incrementTermCount的寫入更容易，它需要一個檢索詞麦锯，并增加關(guān)聯(lián)該檢索詞的計(jì)數(shù)器恕稠。

    public void incrementTermCount(String term) {
        put(term, get(term) + 1);
    }

如果這個檢索詞未見過，則get返回0扶欣；我們設(shè)為1鹅巍，然后使用put向映射添加一個新的鍵值對。如果該檢索詞已經(jīng)在映射中料祠，我們得到舊的計(jì)數(shù)昆著，增加1，然后存儲新的計(jì)數(shù)术陶，替換舊的值凑懂。

此外，TermCounter還提供了這些其他方法梧宫，來幫助索引網(wǎng)頁：

    public void processElements(Elements paragraphs) {
        for (Node node: paragraphs) {
            processTree(node);
        }
    }

    public void processTree(Node root) {
        for (Node node: new WikiNodeIterable(root)) {
            if (node instanceof TextNode) {
                processText(((TextNode) node).text());
            }
        }
    }

    public void processText(String text) {
        String[] array = text.replaceAll("\\pP", " ").
                              toLowerCase().
                              split("\\s+");

        for (int i=0; i<array.length; i++) {
            String term = array[i];
            incrementTermCount(term);
        }
    }

最后接谨，這里是一個例子，展示了如何使用TermCounter：

    String url = "http://en.wikipedia.org/wiki/Java_(programming_language)";
    WikiFetcher wf = new WikiFetcher();
    Elements paragraphs = wf.fetchWikipedia(url);

    TermCounter counter = new TermCounter(url);
    counter.processElements(paragraphs);
    counter.printCounts();

這個示例使用了WikiFetcher從維基百科下載頁面塘匣，并解析正文脓豪。之后它創(chuàng)建了TermCounter并使用它來計(jì)數(shù)頁面上的單詞。

下一節(jié)中忌卤，你會擁有一個挑戰(zhàn)扫夜，來運(yùn)行這個代碼，并通過填充缺失的方法來測試你的理解驰徊。

8.3 練習(xí) 6

在本書的存儲庫中笤闯，你將找到此練習(xí)的源文件：

• TermCounter.java包含上一節(jié)中的代碼。
• TermCounterTest.java包含測試代碼TermCounter.java棍厂。
• Index.java包含本練習(xí)下一部分的類定義颗味。
• WikiFetcher.java包含我們在上一個練習(xí)中使用的，用于下載和解析網(wǎng)頁的類牺弹。
• WikiNodeIterable.java包含我們用于遍歷 DOM 樹中的節(jié)點(diǎn)的類浦马。

你還會發(fā)現(xiàn) Ant 構(gòu)建文件build.xml。

運(yùn)行ant build來編譯源文件张漂。然后運(yùn)行ant TermCounter晶默；它應(yīng)該運(yùn)行上一節(jié)中的代碼，并打印一個檢索詞列表及其計(jì)數(shù)航攒。輸出應(yīng)該是這樣的：

genericservlet, 2
configurations, 1
claimed, 1
servletresponse, 2
occur, 2
Total of all counts = -1

運(yùn)行它時磺陡，檢索詞的順序可能不同。

最后一行應(yīng)該打印檢索詞計(jì)數(shù)的總和，但是由于方法size不完整而返回-1仅政。填充此方法并ant TermCounter重新運(yùn)行垢油。結(jié)果應(yīng)該是4798。

運(yùn)行ant TermCounterTest來確認(rèn)這部分練習(xí)是否完整和正確圆丹。

對于練習(xí)的第二部分滩愁，我將介紹Index對象的實(shí)現(xiàn)，你將填充一個缺失的方法辫封。這是類定義的開始：

public class Index {

    private Map<String, Set<TermCounter>> index = 
        new HashMap<String, Set<TermCounter>>();

    public void add(String term, TermCounter tc) {
        Set<TermCounter> set = get(term);

        // if we're seeing a term for the first time, make a new Set
        if (set == null) {
            set = new HashSet<TermCounter>();
            index.put(term, set);
        }
        // otherwise we can modify an existing Set
        set.add(tc);
    }

    public Set<TermCounter> get(String term) {
        return index.get(term);
    }

實(shí)例變量index是每個檢索詞到一組TermCounter對象的映射硝枉。每個TermCounter表示檢索詞出現(xiàn)的頁面。

add方法向集合添加新的TermCounter倦微，它與檢索詞關(guān)聯(lián)妻味。當(dāng)我們索引一個尚未出現(xiàn)的檢索詞時，我們必須創(chuàng)建一個新的集合欣福。否則我們可以添加一個新的元素到一個現(xiàn)有的集合责球。在這種情況下，set.add修改位于index里面的集合拓劝，但不會修改index本身雏逾。我們唯一修改index的時候是添加一個新的檢索詞。

最后郑临，get方法接受檢索詞并返回相應(yīng)的TermCounter對象集栖博。

這種數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜∠岫矗回顧一下仇让，Index包含Map，將每個檢索詞映射到TermCounter對象的Set躺翻，每個TermCounter包含一個Map丧叽，將檢索詞映射到計(jì)數(shù)。

圖 8.1 Index的對象圖

圖 8.1 是展示這些對象的對象圖获枝。Index對象具有一個名為index 的Map實(shí)例變量蠢正。在這個例子中骇笔，Map只包含一個字符串省店，"Java"，它映射到一個Set笨触，包含兩個TermCounter對象的懦傍，代表每個出現(xiàn)單詞“Java”的頁面。

每個TermCounter包含label芦劣，它是頁面的 URL粗俱，以及map，它是Map虚吟，包含頁面上的單詞和每個單詞出現(xiàn)的次數(shù)寸认。

printIndex方法展示了如何解壓縮此數(shù)據(jù)結(jié)構(gòu)：

    public void printIndex() {
        // loop through the search terms
        for (String term: keySet()) {
            System.out.println(term);

            // for each term, print pages where it appears and frequencies
            Set<TermCounter> tcs = get(term);
            for (TermCounter tc: tcs) {
                Integer count = tc.get(term);
                System.out.println("    " + tc.getLabel() + " " + count);
            }
        }
    }

外層循環(huán)遍歷檢索詞签财。內(nèi)層循環(huán)迭代TermCounter對象。

運(yùn)行ant build來確保你的源代碼已編譯偏塞，然后運(yùn)行ant Index唱蒸。它下載兩個維基百科頁面，對它們進(jìn)行索引灸叼，并打印結(jié)果神汹；但是當(dāng)你運(yùn)行它時，你將看不到任何輸出古今，因?yàn)槲覀円呀?jīng)將其中一個方法留空屁魏。

你的工作是填寫indexPage，它需要一個 URL（一個String）和一個Elements對象捉腥，并更新索引氓拼。下面的注釋描述了應(yīng)該做什么：

public void indexPage(String url, Elements paragraphs) {
    // 生成一個 TermCounter 并統(tǒng)計(jì)段落中的檢索詞

    // 對于 TermCounter 中的每個檢索詞，將 TermCounter 添加到索引
}

它能工作之后抵碟，再次運(yùn)行ant Index披诗，你應(yīng)該看到如下輸出：

...
configurations
    http://en.wikipedia.org/wiki/Programming_language 1
    http://en.wikipedia.org/wiki/Java_(programming_language) 1
claimed
    http://en.wikipedia.org/wiki/Java_(programming_language) 1
servletresponse
    http://en.wikipedia.org/wiki/Java_(programming_language) 2
occur
    http://en.wikipedia.org/wiki/Java_(programming_language) 2

當(dāng)你運(yùn)行的時候，檢索詞的順序可能有所不同立磁。

同樣呈队，運(yùn)行ant TestIndex來確定完成了這部分練習(xí)。