Geekly articles weekly

《算法和数据结构》一书。 Java信息检索»

图片 哈Ha！ 了解如何基于Java语言中最重要的数据结构实现高效的算法，以及如何衡量这些算法的性能。 每章均附有练习以帮助巩固材料。

  • 学习使用数据结构，例如使用列表和字典，了解它们如何工作。
  • 编写一个应用程序，该应用程序可以读取Wikipedia页面，进行解析并提供对结果数据树的导航。
  • 分析代码并学习如何预测其运行速度和消耗的内存量。
  • 编写实现Map接口的类，并使用哈希表和二进制搜索树。
  • 用自己的搜索引擎创建一个简单的Web搜索引擎：它将为网页编制索引，保存其内容并返回所需的结果。

摘录“树走”


在本章中，我们将研究本书其余部分将开发的搜索引擎应用程序。 我（作者）描述了搜索引擎的元素，并展示了第一个应用程序，即一个搜索机器人，该机器人从Wikipedia下载并分析页面。 本章还介绍了递归深度搜索实现和使用Java的Deque来实现“后进先出”堆栈的迭代实现。

搜索引擎


诸如Google搜索或Bing之类的搜索引擎接受一组搜索词，并返回与这些词相关的网页列表。 您可以在thinkdast.com上阅读更多内容 ，但是我将在您解释的同时解释您的需求。

考虑一下搜索引擎的主要组成部分。

  • 数据收集（抓取）。 您将需要一个程序，该程序可以加载网页，对其进行分析并提取文本以及指向其他页面的任何链接。
  • 索引编制 我们需要一个索引，使我们能够找到搜索查询以及包含该查询的页面。
  • 搜索（检索）。 您需要一种从索引收集结果并确定与搜索词最相关的页面的方法。

让我们从搜索机器人开始。 其目的是检测并加载一组网页。 对于Google和Bing等搜索引擎而言，挑战在于查找所有网页，但这些机器人通常仅限于较小的域。 在我们的情况下，我们只会从Wikipedia中读取页面。

第一步，我们将创建一个搜索机器人，该机器人将读取Wikipedia页面，找到第一个链接，然后转到另一个页面并重复前面的步骤。 我们将使用此搜索引擎来测试“入门哲学”假设。 它说：

“通过单击Wikipedia文章正文中的第一个小写链接，然后对后续文章重复此操作，您很可能被带到有关哲学文章的页面。”

您可以在thinkdast.com/getphil上查看此假设及其历史。
测试一个假设将使您能够创建搜索机器人的主要部分，而无需绕过整个Internet甚至整个Wikipedia。 而且我认为此练习非常有趣！

在几章中，我们将研究索引器，然后继续进行搜索引擎。

HTML解析


加载网页时，其内容以超文本标记语言（HTML）编写。 例如，以下是一个简单的HTML文档：

<!DOCTYPE html> <html> <head> <title>This is a title</title> </head> <body> <p>Hello world!</p> </body> </html>

短语这是标题和Hello World！ （“ Hello world！”）-真正显示在页面上的文字； 其他元素是指示应如何显示文本的标记。

加载页面时，我们的机器人需要解析HTML代码以提取文本并找到链接。 为此，我们将使用jsoup，这是一个开放源Java库，旨在加载和解析（解析）HTML。
HTML解析的结果是一个包含文档元素（包括文本和标签）的DOM（文档对象模型）树。

树是一种相关的数据结构，由表示文本，标签和文档其他元素的顶点组成。

顶点之间的关系由文档的结构确定。 在前面的示例中，第一个节点称为根，它是一个标签，其中包含指向它所包含的两个顶点的链接； 这些节点是根节点的子节点。

一个节点有一个子顶点，一个节点有一个子顶点

（段落，英文。段落）。 在图。 6.1是此树的图形表示。

图片

每个顶点都包含指向其子节点的链接； 此外，每个节点都包含一个指向其父节点的链接，因此您可以在任何节点上上下移动树。 实际页面的DOM树通常比描述的示例更复杂。

大多数浏览器都有用于检查您正在查看的页面的DOM的工具。 在Chrome浏览器中，您可以右键单击网页的任意部分，然后在出现的菜单中选择查看代码项。 在Firefox中，您可以右键单击并从上下文菜单中选择“浏览项目”。 Safari提供了Web Inspector工具，该工具位于thinkdast.com/safari上 。 单击以下链接可以阅读Internet Explorer的说明： thinkdast.com/explorer 。

在图。 图6.2显示了有关Java的Wikipedia页面的DOM树的屏幕截图。 高亮显示的元素是文章正文的第一段，包含在id =“ mw-content-text”的<div>元素中。 我们将使用此元素标识符来确定我们上传的每篇文章的正文。

Jsoup应用


通过jsoup库，可以轻松加载和分析网页以及浏览DOM树。 例如：

 String url = "http://en.wikipedia.org/wiki/Java_(programming_language)"; //     Connection conn = Jsoup.connect(url); Document doc = conn.get(); //         Element content = doc.getElementById("mw-content-text"); Elements paragraphs = content.select("p");

Jsoup.connect元素接受URL作为字符串，并建立与Web服务器的连接。 get方法加载HTML代码，对其进行解析，然后返回Document对象（即DOM）。

图片

该对象包括用于导航树和选择节点的方法。 实际上，它提供了很多方法，可能会造成混淆。 下面的示例演示了两种选择节点的方法。

  • getElementByld使用字符串类型参数，并为具有相应id字段的元素查找树。 找到它后，他选择出现在每个Wikipedia页面上的节点<div id =“ mw-content-text” lang =“ en” dir =“ ltr” class =“ mw-content-ltr”>以标识该元素包含页面正文的<div>，与侧面导航栏和其他元素不同。
  • select接受一个String，遍历树，并返回所有具有与String匹配的标签的元素。 在此示例中，它返回出现在内容中的所有段落标签。 返回值是类型为Elements的对象。

在继续之前，您应该查看这些类的文档，以了解它们可以执行哪些操作。 最重要的类是Element，Elements和Node，您可以通过单击thinkdast.com/jsoupelt，thinkdast.com/jsoupelts和thinkdast.com/jsoupnode链接来阅读 。

Node类是DOM树的顶部。 有几个扩展Node的子类，包括Element，TextNode，DataNode和Comment。 Elements类是Element类型的对象的集合。

在图。 6.3是UML类的图，显示了它们之间的关系。 带有空箭头的线表示一个类别扩展到另一个类别。 例如，此图表表明Elements扩展了ArrayList。 我们将在第11章的同名部分中返回UML类图。

图片

遍历DOM树


为了使您的生活更轻松，我提供了WikiNodelterable类，该类使您可以遍历DOM树。 以下是显示如何使用此类的示例：

 Elements paragraphs = content.select("p"); Element firstPara = paragraphs.get(0); Iterable<Node> iter = new WikiNodeIterable(firstPara); for (Node node: iter) { if (node instanceof TextNode) { System.out.print(node); } }

此示例从上一个停止的那一刻开始。 他在段落中选择第一段，然后创建一个实现Iterable接口的WikiNodeIterable类。 此类进行了深入搜索，并按照它们在页面上出现的顺序创建了节点。

在当前示例中，仅当Node是TextNode时，我们才显示Node，并忽略其其他类型，尤其是表示标签的Element类型的对象。 结果是纯HTML段落文本，没有任何标记。 他的结论是：

Java是一种通用的计算机编程语言，它是并发的，基于类的，面向对象的[13]，并且经过专门设计...

Java是一种通用的计算机编程语言，它是一种基于类的面向对象的语言，可以进行并行编程[13]，并且经过专门设计...

深度搜寻


有几种智能遍历树的方法。 我们从深度优先搜索（DFS）开始。 搜索从树的根开始，并选择第一个子节点。 如果后者有子节点，则再次选择第一个子节点。 当遇到没有子峰的峰时，您需要返回，将树上移到父节点，在该父节点处选择下一个子峰（如果有）。 否则，您需要再次返回。 检查最后一个子根节点后，遍历完成。

有两种普遍接受的实现深度搜索的方式：递归和迭代。 递归实现简单而优雅：

 private static void recursiveDFS(Node node) { if (node instanceof TextNode) { System.out.print(node); } for (Node child: node.childNodes()) { recursiveDFS(child); } }

从树根开始，为树中的每个Node调用此方法。 如果Node是TextNode，则将打印其内容。 如果Node有子节点，它将按顺序为每个子节点调用recursiveDFS。

在当前示例中，我们在访问每个TextNode的子节点之前先打印其内容，即，这是直接（预定）遍历的示例。 通过转到thinkdast.com/treetrav链接，可以了解有关直接，反向（后置）和对称（按顺序） 解决方法的信息 。 对于此应用程序，爬网顺序无关紧要。

进行递归调用时，recursiveDFS使用调用堆栈（请参见thinkdast.com/callstack ）跟踪子顶点并以正确的顺序对其进行处理。 另外，您可以使用堆栈数据结构自己跟踪节点。 这将避免递归并迭代遍历树。

Java中的堆栈


在解释深度搜索的迭代版本之前，我将看一下堆栈的数据结构。 我们从堆栈的一般概念开始，然后讨论定义堆栈方法的两个Java接口：Stack和Deque。

堆栈是一个类似列表的数据结构：它是一个维护元素顺序的集合。 堆栈和列表之间的主要区别在于，前者包含的方法较少。 按照约定，堆栈提供以下方法：

  • 推送，在堆栈顶部添加一个元素；
  • pop，执行删除操作并返回栈顶元素的值；
  • 窥视，返回堆栈的最顶层元素，而不更改堆栈本身；
  • isEmpty，指示堆栈是否为空。

由于pop始终返回最顶层的元素，因此堆栈也称为LIFO，这意味着“后进先出”。 堆栈的替代方法是一个队列，该队列按添加项目的顺序返回项目，即“先进先出”或FIFO。

乍看之下，不清楚为什么堆栈和队列有用：它们没有提供无法从列表中获得的任何特殊功能； 实际上，他们的机会更少。 那么为什么不总是应用列表呢？ 证明堆栈和队列合理的原因有两个。

1.如果您将自己限制为一小组方法（即一个小的API），那么您的代码将更具可读性，并且不易出错。 例如，当使用列表表示堆栈时，您可能会以错误的顺序意外删除项目。 使用堆栈API，这种错误实际上是不可能的。 避免错误的最佳方法是使它们不可能。

2.如果数据结构提供的API较小，则更容易高效地实现。 例如，实现堆栈的一种简单方法是使用单个列表。 将项目推入堆栈，我们将其添加到列表的顶部； 弹出一个元素，我们从一开始就将其删除。 对于链表，从一开始就添加和删除是固定时间的操作，因此此实现有效。 相反，大型API更难以有效实施。

有三种方法可以用Java实现堆栈。

1.应用ArrayList或LinkedList。 使用ArrayList时，您需要记住从头开始添加和删除，以便这些操作在恒定时间内执行。 避免将项目添加到错误的位置或以错误的顺序删除它们。

2. Java有一个Stack类，提供了一组标准的堆栈方法。 但是该类是Java的旧部分：它与后来出现的Java Collections Framework不兼容。

3.也许最好的选择是使用Deque接口的一种实现，例如ArrayDeque。

双端队列由双端队列形成，这意味着“双向队列”。 在Java中，Deque接口提供push，pop，peek和isEmpty方法，因此可以将其用作堆栈。 它包含其他方法，有关信息，请访问thinkdast.com/deque ，但目前我们不会使用它们。

迭代深度搜索


下面是DFS的迭代版本，它使用ArrayDeque表示一堆Node类型的对象：

 private static void iterativeDFS(Node root) { Deque<Node> stack = new ArrayDeque<Node>(); stack.push(root); while (!stack.isEmpty()) { Node node = stack.pop(); if (node instanceof TextNode) { System.out.print(node); } List<Node> nodes = new ArrayList<Node>(node. chiidNodesQ); Collections.reverse(nodes); for (Node child: nodes) { stack.push(chiid); } } }

root参数是我们要绕过的树的根，因此我们首先创建一个堆栈并将此参数添加到其中。

循环继续进行，直到堆栈为空。 每次通过都会将Node推出堆栈。 如果接收到TextNode，则打印其内容。 然后，将子顶点添加到堆栈中。 要以正确的顺序处理后代，您需要以相反的顺序将它们推入堆栈。 这是通过将子顶点复制到ArrayList中，将元素重新排列到适当位置，然后迭代反转的ArrayList来完成的。
深度搜索的深度版本的优点之一是，它更容易在Java中实现为Iterator。 下一章将介绍如何执行此操作。

但是首先，要对Deque接口做最后的说明：除了ArrayDeque，Java还提供了Deque的另一个实现，即我们的老朋友LinkedList。 后者实现两个接口：List和Deque。 生成的接口取决于其用途。 例如，在将LinkedList分配给Deque变量时：

 Deqeue<Node> deque = new LinkedList<Node>();

您可以从Deque界面应用方法，但不能从List界面应用所有方法。 通过将其分配给变量List：

 List<Node> deque = new LinkedList<Node>();

您可以使用List方法，但不能使用所有Deque方法。 并将它们分配如下：

 LinkedList<Node> deque = new LinkedList<Node>();

可以使用所有方法。 但是，当组合来自不同接口的方法时，代码将更不易读且更容易出错。

»这本书的更多信息可以在出版商的网站上找到
» 目录
» 摘录

Java发酵罐优惠券20％的折扣-Java

Source: https://habr.com/ru/post/zh-CN419503/

More articles:


All Articles