第十六章 布尔搜索
译者:飞龙
自豪地采用谷歌翻译
在本章中,我展示了上一个练习的解决方案。然后,你将编写代码来组合多个搜索结果,并按照它与检索词的相关性进行排序。
16.1 爬虫的答案
首先,我们来解决上一个练习。我提供了一个WikiCrawler
的大纲;你的工作是填写crawl
。作为一个提醒,这里是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();
}
当我们创建WikiCrawler
时,我们传入source
和 index。最初queue
只包含一个元素,source
。
注意,queue
的实现是LinkedList
,所以我们可以在末尾添加元素,并从开头删除它们 - 以常数时间。通过将LinkedList
对象赋给Queue
变量,我们将使用的方法限制在Queue
接口中;具体来说,我们将使用offer
添加元素,以及poll
来删除它们。
这是我的WikiCrawler.crawl
的实现:
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
对象,包含大部分段落。
第一个版本只是循环遍历段落。第二个版本是实际的逻辑。
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
类定义的起始:
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
对象的列表。这里是类定义的起始:
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
:
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
张卡,如下所示:
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);
这个版本的sort
将元素按照所谓的“自然秩序”放置,因为它由对象本身决定。
但是可以通过提供一个Comparator
对象,来强制实现不同的排序。例如,Card
对象的自然顺序将Ace
视为最小的牌,但在某些纸牌游戏中,它的排名最高。我们可以定义一个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;
}
}
};
该代码定义了一个匿名类,按需实现compare
。然后它创建一个新定义的匿名类的实例。如果你不熟悉 Java 中的匿名类,可以在 http://thinkdast.com/anonclass 上阅读它们。
使用这个Comparator
,我们可以这样调用sort
:
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。