第十六章 布尔搜索

    在本章中，我展示了上一个练习的解决方案。然后，你将编写代码来组合多个搜索结果，并按照它与检索词的相关性进行排序。

    首先，我们来解决上一个练习。我提供了一个WikiCrawler的大纲；你的工作是填写crawl。作为一个提醒，这里是WikiCrawler类中的字段：

    当我们创建WikiCrawler时，我们传入source和 index。最初queue只包含一个元素，source。

    注意，queue的实现是LinkedList，所以我们可以在末尾添加元素，并从开头删除它们 - 以常数时间。通过将LinkedList对象赋给Queue变量，我们将使用的方法限制在Queue接口中；具体来说，我们将使用offer添加元素，以及poll来删除它们。

    这是我的WikiCrawler.crawl的实现：

    1.     public String crawl(boolean testing) throws IOException {
    2.         if (queue.isEmpty()) {
    3.             return null;
    4.         }
    5.         String url = queue.poll();
    6.         System.out.println("Crawling " + url);
    8.         if (testing==false && index.isIndexed(url)) {
    9.             System.out.println("Already indexed.");
    10.             return null;
    11.         }
    13.         Elements paragraphs;
    14.         if (testing) {
    15.             paragraphs = wf.readWikipedia(url);
    16.         } else {
    17.             paragraphs = wf.fetchWikipedia(url);
    18.         }
    19.         index.indexPage(url, paragraphs);
    20.         queueInternalLinks(paragraphs);
    21.         return url;
    22.     }

    这个方法的大部分复杂性是使其易于测试。这是它的逻辑：

    • 如果队列为空，则返回null来表明它没有索引页面。
    • 否则，它将从队列中删除并存储下一个 URL。
    • 如果 URL 已经被索引，crawl不会再次对其进行索引，除非它处于测试模式。
    • 接下来，它读取页面的内容：如果它处于测试模式，它从文件读取；否则它从 Web 读取。
    • 它将页面索引。
    • 它解析页面并向队列添加内部链接。
    • 最后，它返回索引的页面的 URL。

    我在 15.1 节展示了Index.indexPage的一个实现。所以唯一的新方法是WikiCrawler.queueInternalLinks。

    我用不同的参数编写了这个方法的两个版本：一个是Elements对象，包含每个段落的 DOM 树，另一个是Element对象，包含大部分段落。

    第一个版本只是循环遍历段落。第二个版本是实际的逻辑。

    1.     void queueInternalLinks(Elements paragraphs) {
    2.         for (Element paragraph: paragraphs) {
    3.             queueInternalLinks(paragraph);
    4.         }
    5.     }
    7.     private void queueInternalLinks(Element paragraph) {
    8.         Elements elts = paragraph.select("a[href]");
    9.         for (Element elt: elts) {
    11.             if (relURL.startsWith("/wiki/")) {
    12.                 String absURL = elt.attr("abs:href");
    13.                 queue.offer(absURL);
    14.             }
    15.         }
    16.     }

    要确定链接是否为“内部”链接，我们检查 URL 是否以/wiki/开头。这可能包括我们不想索引的一些页面，如有关维基百科的元页面。它可能会排除我们想要的一些页面，例如非英语语言页面的链接。但是，这个简单的测试足以起步了。

    这就是它的一切。这个练习没有很多新的材料；这主要是一个机会，把这些作品组装到一起。

    16.2 信息检索

    这个项目的下一个阶段是实现一个搜索工具。我们需要的部分包括：

    • 一个界面，其中用户可以提供检索词并查看结果。
    • 一种查找机制，它接收每个检索词并返回包含它的页面。
    • 用于组合来自多个检索词的搜索结果的机制。
    • 对搜索结果打分和排序的算法。

    在本练习中，我们将重点介绍步骤 3 和 4 。我们已经构建了一个 2 的简单的版本。如果你有兴趣构建 Web 应用程序，则可以考虑完成步骤 1。

    大多数搜索引擎可以执行“布尔搜索”，这意味着你可以使用布尔逻辑来组合来自多个检索词的结果。例如：

    • 搜索“java + 编程”（加号可省略）可能只返回包含两个检索词：“java”和“编程”的页面。
    • “java OR 编程”可能会返回包含任一检索词但不一定同时出现的页面。
    • “java -印度尼西亚”可能返回包含“java”，不包含“印度尼西亚”的页面。

    包含检索词和运算符的表达式称为“查询”。

    当应用给搜索结果时，布尔操作符+，和-对应于集合操作 交，并和差。例如，假设

    • 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类定义的起始：

    WikiSearch对象包含 URL 到它们的相关性分数的映射。在信息检索的上下文中，“相关性分数”用于表示页面多么满足从查询推断出的用户需求。相关性分数的构建有很多种方法，但大部分都基于“检索词频率”，它是搜索词在页面上的显示次数。一种常见的相关性分数称为 TF-IDF，代表“检索词频率 - 逆向文档频率”。你可以在 上阅读更多信息 。

    你可以选择稍后实现 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”

    填充sort的主体，使结果以递增的相关顺序返回。我建议你使用java.util.Collections提供的sort方法，它可以排序任何种类的List。你可以阅读 http://thinkdast.com/collections 上的文档 。

    有两个sort版本：

    • 单参数版本接受列表并使用它的compareTo方法对元素进行排序，因此元素必须是Comparable。
    • 双参数版本接受任何对象类型的列表和一个Comparator，它是一个提供compare方法的对象，用于比较元素。

    如果你不熟悉Comparable和Comparator接口，我将在下一节中解释它们。

    本书的仓库包含了Card.java，它演示了两个方式来排序Card对象的列表。这里是类定义的起始：

    1. public class Card implements Comparable<Card> {
    3.     private final int rank;
    4.     private final int suit;
    6.     public Card(int rank, int suit) {
    7.         this.rank = rank;
    8.         this.suit = suit;
    9.     }

    Card对象拥有两个整形字段，rank和suit。Card实现了Comparable<Card>，也就是说它提供compareTo：

    1.     public int compareTo(Card that) {
    2.         if (this.suit < that.suit) {
    4.         }
    5.             return 1;
    6.         }
    7.         if (this.rank < that.rank) {
    8.             return -1;
    9.         }
    10.         if (this.rank > that.rank) {
    11.             return 1;
    12.         }
    13.         return 0;
    14.     }

    compareTo规范表明，如果this小于that，则应该返回一个负数，如果它更大，则为正数，如果它们相等则为0。

    如果使用单参数版本的Collections.sort，它将使用元素提供的compareTo方法对它们进行排序。为了演示，我们可以列出52张卡，如下所示：

    并这样排序它们：

    1.         Collections.sort(cards);

    这个版本的sort将元素按照所谓的“自然秩序”放置，因为它由对象本身决定。

    但是可以通过提供一个Comparator对象，来强制实现不同的排序。例如，Card对象的自然顺序将Ace视为最小的牌，但在某些纸牌游戏中，它的排名最高。我们可以定义一个Comparator，将Ace视为最大的牌，像这样：

    1.         Comparator<Card> comparator = new Comparator<Card>() {
    2.             @Override
    3.             public int compare(Card card1, Card card2) {
    4.                 if (card1.getSuit() < card2.getSuit()) {
    5.                     return -1;
    6.                 }
    7.                 if (card1.getSuit() > card2.getSuit()) {
    8.                     return 1;
    9.                 }
    10.                 int rank1 = getRankAceHigh(card1);
    11.                 int rank2 = getRankAceHigh(card2);
    13.                 if (rank1 < rank2) {
    14.                     return -1;
    15.                 }
    16.                 if (rank1 > rank2) {
    17.                     return 1;
    18.                 }
    19.                 return 0;
    20.             }
    22.             private int getRankAceHigh(Card card) {
    23.                 int rank = card.getRank();
    24.                 if (rank == 1) {
    25.                     return 14;
    26.                 } else {
    27.                     return rank;
    28.                 }
    29.             }
    30.         };

    该代码定义了一个匿名类，按需实现compare。然后它创建一个新定义的匿名类的实例。如果你不熟悉 Java 中的匿名类，可以在 上阅读它们。

    使用这个Comparator，我们可以这样调用sort：

    在这个顺序中，黑桃的Ace是牌组上的最大的牌；梅花二是最小的。

    如果你想试验这个部分的代码，它们在Card.java中。作为一个练习，你可能打算写一个比较器，先按照rank，然后再按照suit，所以所有的都应该在一起，所有的二也是。以此类推。

    16.6 扩展

    如果你完成了此练习的基本版本，你可能需要处理这些可选练习：

    • 请阅读 http://thinkdast.com/tfidf 上的 TF-IDF，并实现它。你可能需要修改JavaIndex来计算文档频率；也就是说，每个检索词在索引的所有页面上出现的总次数。
    • 对于具有多个检索词的查询，每个页面的总体相关性目前是每个检索词的相关性的总和。想想这个简单版本什么时候可能无法正常运行，并尝试一些替代方案。
    • 构建用户界面，允许用户输入带有布尔运算符的查询。解析查询，生成结果，然后按相关性排序，并显示评分最高的 URL。考虑生成“片段”，它显示了检索词出现在页面的哪里。如果要为用户界面制作 Web 应用程序，请考虑将 Heroku 作为简单选项，用于 开发和部署 Java Web应用程序。见 。