目录
介绍
信息检索的基本概念
文本和网页预处理
非索引字删除
堵塞
文本的其他预处理任务
网页预处理
重复检测
网络搜索
分步演练
结论和兴趣点
- 下载源代码（来自GitHub）
text-mining.ro 主页
网络搜索不需要介绍。由于其便利性和网络上信息的丰富性，搜索网络正日益成为主要的信息搜索方法。人们去图书馆的次数越来越少，但在网络上的搜索却越来越多。Web搜索起源于信息检索（或简称IR），这是一个帮助用户从大量文本文档中查找所需信息的研究领域。传统的IR假设基本信息单元是一个文档，并且有大量的文档可用于形成文本数据库。在Web上，文档是网页。
检索信息仅意味着查找与用户查询相关的一组文档。通常还会根据文档集与查询的相关性分数来执行文档集的排名。最常用的查询格式是关键字列表，也称为术语。IR与使用SQL查询的数据库中的数据检索不同，因为数据库中的数据是高度结构化的，存储在关系表中，而文本中的信息是非结构化的。没有像SQL这样的结构化查询语言用于文本检索。
可以肯定地说，网络搜索是IR最重要的应用。在很大程度上，网络搜索也有助于IR。事实上，搜索引擎的巨大成功已经将IR推向了中心舞台。然而，搜索不仅仅是传统IR模型的简单应用。它使用了一些红外结果，但它也有其独特的技术，给红外研究带来了许多新问题。
首先，效率是Web搜索的首要问题，但在传统IR系统中只是次要问题，主要是因为大多数IR系统中的文档集合不是很大。但是，网络上的页面数量是巨大的。例如，在撰写本文时，谷歌索引了超过8亿页。网络用户也需要非常快速的响应。无论算法多么有效，如果检索不能有效地完成，很少有人会使用它。
网页也与传统IR系统中使用的传统文本文档有很大不同。首先，网页有超链接和锚文本，这在传统文档中是不存在的（研究出版物中的引用除外）。超链接对于搜索极为重要，在搜索排名算法中起着核心作用，我们将在下一节中看到。与超链接关联的锚文本也很重要，因为一段锚文本通常是对其超链接所指向的页面的更准确描述。其次，网页是半结构化的。网页不像传统文档那样只是几段文本。网页具有不同的字段，例如标题、元数据、正文等。某些字段（例如，标题字段）中包含的信息比其他字段更重要。此外，页面中的内容通常以多个结构化块（矩形）进行组织和呈现。有些块很重要，有些则不重要（例如，广告、隐私政策、版权声明等）。有效地检测网页的主要内容块对Web搜索很有用，因为出现在这些块中的术语更为重要。
最后，垃圾邮件是Web上的一个主要问题，但对传统IR来说不是问题。之所以如此，是因为搜索引擎返回的页面的排名位置非常重要。如果一个页面与查询相关，但排名非常低（例如，低于前30名），那么用户不太可能查看该页面。如果页面销售产品，那么这对业务不利。为了提高某些目标页面的排名，“非法”手段，称为垃圾邮件，通常用于提高其排名位置。检测和打击网络垃圾邮件是一个关键问题，因为它可以将低质量（甚至不相关）的页面推到搜索排名的顶部，从而损害搜索结果的质量和用户的搜索体验。
通用IR系统架构
信息检索（IR）是帮助用户查找符合其信息需求的信息的研究。从技术上讲，IR研究信息的获取、组织、存储、检索和分发。从历史上看，I是关于文档检索的，强调文档是基本单位。具有信息需求的用户通过查询操作模块向检索系统发出查询（user query）。检索模块使用文档索引来检索那些包含某些查询词的文档（此类文档可能与查询相关），计算它们的相关性分数，然后根据分数对检索到的文档进行排名。然后，排名后的文档将呈现给用户。文档集合也称为文本数据库，它由索引器编制索引，以便进行高效检索。
用户查询表示用户的信息需求，其形式如下：
- 关键字查询：用户使用（至少一个）关键字（或术语）列表来表达他/她的信息需求，旨在查找包含部分（至少一个）或所有查询术语的文档。假定列表中的术语与逻辑AND的“软”版本相关联。例如，如果有兴趣查找有关Web挖掘的信息，则可以向IR或搜索引擎系统发出查询“Web挖掘”。“Web mining”被撤回为“Web AND mining”。然后，检索系统会找到那些可能相关的文档，并对它们进行适当的排序以呈现给用户。请注意，检索到的文档不必包含查询中的所有术语。在一些红外系统中，单词的顺序也很重要，会影响检索结果。
- 布尔查询：用户可以使用布尔运算符AND、OR和NOT来构造复杂的查询。因此，此类查询由术语和布尔运算符组成。例如，“data OR Web”是一个布尔查询，它请求包含单词“data”或“Web”的文档。如果布尔查询在页面中逻辑上为true（即完全匹配），则返回该页面。尽管可以使用这三个运算符编写复杂的布尔查询，但用户很少编写此类查询。搜索引擎通常支持受限版本的布尔查询。
- 短语查询：此类查询由构成短语的一系列单词组成。每个返回的文档必须至少包含该短语的一个实例。在搜索引擎中，短语查询通常用双引号括起来。例如，可以发出以下短语查询（包括双引号），“Web挖掘技术和应用程序”来查找包含确切短语的文档。
- 邻近查询：邻近查询是短语查询的简化版本，可以是术语和短语的组合。邻近查询查找彼此非常接近的查询词。接近度用作对返回的文档或页面进行排名的一个因素。例如，包含所有查询词的文档被认为比查询词相距很远的页面更相关。某些系统允许用户指定查询词之间允许的最大距离。大多数搜索引擎在检索时都会考虑术语邻近性和术语排序。
- 完整文档查询：当查询是完整文档时，用户希望查找与查询文档类似的其他文档。一些搜索引擎（例如，Google）允许用户通过提供查询页面的URL来发出这样的查询。此外，在搜索引擎返回的结果中，每个片段可能都有一个名为“更像这个”或“类似页面”的链接。当用户单击链接时，将返回一组与代码段中的页面类似的页面。
- 自然语言问题：这是最复杂的情况，也是最理想的情况。用户将他/她的信息需求表达为自然语言问题。然后系统会找到答案。然而，由于自然语言理解的困难，这样的查询仍然很难处理。然而，这是一个活跃的研究领域，称为问答。一些检索系统开始为某些特定类型的问题提供问答服务，例如定义问题，要求对技术术语进行定义。定义问题通常更容易回答，因为有很强的语言模式表明定义句子，例如，“定义为”、“指代”等。通常可以脱机提取定义。
查询操作模块的范围可以从非常简单到非常复杂。在最简单的情况下，它什么都不做，只是在一些简单的预处理后将查询传递给检索引擎，例如，删除停用词（在文本中经常出现但意义不大的词，例如，“the”、“a”、“in”等）。我们将在下一节中讨论文本预处理。在更复杂的情况下，它需要将自然语言查询转换为可执行查询。它还可以接受用户反馈，并使用它来扩展和优化原始查询。
索引器是在某些数据结构中对原始原始文档进行索引以实现高效检索的模块。结果是文档索引。在下一节中，我们将研究一种特殊类型的索引方案，称为倒排索引，它用于搜索引擎和大多数IR系统。倒排索引易于构建，搜索效率也非常高。
检索系统计算每个索引文档与查询的相关性分数。根据其相关性分数，对文档进行排名并呈现给用户。请注意，它通常不会将用户查询与集合中的每个文档进行比较，这太低效了。相反，首先从索引中仅找到包含至少一个查询词的一小部分文档，然后仅针对此文档子集计算与用户查询的相关性分数。
在使用集合中的文档进行检索之前，通常会执行一些预处理任务。对于传统的文本文档（没有HTML标记），任务是删除非索引字、词干提取以及处理数字、连字符、标点符号和字母大小写。对于网页，还需要仔细考虑其他任务，例如删除HTML标记和识别主要内容块。我们将在本节中讨论它们。
停用词是语言中经常出现的无关紧要的词，有助于构建句子，但不代表文档的任何内容。冠词、介词和连词以及一些代词是自然的候选词。英语中常见的停用词包括：a、about、an、are、as、at、be、by、for、from、how、in、is、of、on、or、that、the、these、this、to、was、what、when、where、who、will、with。在对文档进行索引和存储之前，应删除此类词语。在执行检索之前，还会删除查询中的非索引字。
在许多语言中，一个词具有各种句法形式，具体取决于它所使用的上下文。例如，在英语中，名词有复数形式，动词有动名词形式（通过添加“ing”），过去时态使用的动词与现在时态不同。这些被认为是相同词根形式的句法变体。这种变化会导致检索系统的召回率较低，因为相关文档可能包含查询词的变体，但不包含确切的单词本身。这个问题可以通过词干提取部分解决。
词干提取是指将单词还原为词干或词根的过程。词干是单词在去除其前缀和后缀后留下的部分。在英语中，单词的大多数变体都是通过引入后缀（而不是前缀）生成的。因此，英语中的词干提取通常意味着后缀删除或剥离。例如，“computer”、“computing”和“compute”被简化为“comput”。“walks”、“walking”和“walker”被简化为“walk”。词干提取可以在检索中考虑单词的不同变体，从而提高回忆率。有几种词干提取算法，也称为词干提取器。
多年来，许多研究人员评估了使用词干提取的优缺点。显然，词干提取增加了召回率并减小了索引结构的大小。但是，它可能会损害准确性，因为许多不相关的文档可能被认为是相关的。例如，“cop”和“cope”都简化为词干“cop”。但是，如果正在寻找有关警察的文件，则仅包含“cope”的文件不太可能相关。尽管研究人员已经进行了许多实验，但仍然没有确凿的证据。在实践中，应该尝试使用手头的文档集合，看看词干提取是否有帮助。
数字：在传统的IR系统中，包含数字的数字和术语被删除，但某些特定类型除外，例如日期、时间和其他用正则表达式表示的预先指定类型。但是，在搜索引擎中，它们通常被编入索引。
连字符：通常使用断字符来处理用法的不一致。例如，有些人使用“最先进的”，但其他人使用“最先进的”。如果删除了第一种情况下的连字符，我们将消除不一致问题。但是，有些单词可能带有连字符作为单词的组成部分，例如“Y-21”。因此，一般来说，系统可以遵循一般规则（例如，删除所有连字符），并且也有一些例外。请注意，有两种类型的删除，即（1）每个连字符替换为空格，以及（2）简单地删除每个连字符而不留下空格，以便“最先进的”可以替换为“最先进的”或“stateoftheart”。在某些系统中，由于很难确定哪个是正确的，因此两种表单都被索引，例如，如果将“预处理”转换为“预处理”，则如果查询词为“预处理”，则找不到某些相关页面。
标点符号：标点符号可以像连字符一样处理。
字母大小写：所有字母通常转换为大写或小写。
我们在本节的开头已经指出，网页不同于传统的文本文档。因此，需要额外的预处理。我们在下面描述一些重要的。
识别不同的文本字段：在HTML中，有不同的文本字段，例如标题、元数据和正文。识别它们允许检索系统以不同的方式处理不同字段中的术语。例如，在搜索引擎中，出现在页面标题字段中的术语被认为比出现在其他字段中的术语更重要，并且被赋予更高的权重，因为标题通常是页面的简明描述。在正文中，那些强调的术语（例如，在标题标签下<h1>、<h2>、...、粗体标签<b>等）也被赋予更高的权重。
识别锚文本：与超链接关联的锚文本在搜索引擎中会受到特殊处理，因为锚文本通常表示对其链接指向的页面中包含的信息的更准确描述。如果超链接指向外部页面（不在同一站点中），则它特别有价值，因为它是由其他人而不是页面的作者/所有者提供的页面摘要描述，因此更值得信赖。
删除HTML标记：删除 HTML标记的处理方式与标点符号类似。有一个问题需要仔细考虑，它会影响邻近查询和短语查询。HTML本质上是一种可视化表示语言。在典型的商业页面中，信息以许多矩形块的形式呈现。简单地删除HTML标记可能会因连接不应联接的文本而导致问题。它们将导致短语查询和邻近查询出现问题。在写这本书的时候，搜索引擎还没有令人满意地处理这个问题。
识别主要内容块：典型的网页，尤其是商业页面，包含大量不属于页面主要内容的信息。例如，它可能包含横幅广告、导航栏、版权声明等，这可能会导致搜索和挖掘结果不佳。在维基百科中，页面的主要内容块是包含“今日精选文章”的块。不希望将导航链接的锚文本作为此页面内容的一部分进行索引。几位研究人员研究了识别主要内容块的问题。他们表明，如果只使用主要内容块，搜索和数据挖掘结果可以得到显着改善。我们简要讨论了在网页中查找此类块的两种技术。
在传统的IR中，重复的文档或页面不是问题。然而，在Web的背景下，这是一个重要的问题。Web上有不同类型的页面和内容复制。复制页面通常称为复制或复制，复制整个网站称为镜像。由于不同地理区域的带宽有限以及网络性能不佳或不可预测，重复页面和镜像站点通常用于提高全球浏览和文件下载的效率。当然，一些重复的页面是抄袭的结果。检测此类页面和网站可以减小索引大小并改善搜索结果。可以使用多种方法来查找重复信息。最简单的方法是对整个文档进行哈希处理，例如，使用MD5算法，或计算聚合数字（例如，校验和）。但是，这些方法仅对检测精确重复项有用。在网络上，人们很少能找到完全相同的重复项。例如，即使是不同的镜像站点也可能具有不同的URL、不同的网站管理员、不同的联系信息、不同的广告以满足本地需求等。
我们现在把它们放在一起，描述搜索引擎的工作原理。由于很难知道商业搜索引擎的内部细节，因此本节的大部分内容都是基于研究论文，尤其是早期的谷歌论文。由于效率问题，潜在语义索引可能尚未用于Web搜索。目前的搜索算法仍然主要基于向量空间模型和术语匹配。
搜索引擎从抓取Web上的页面开始。然后对已爬网的页面进行解析、索引和存储。在查询时，索引用于高效检索。我们不会在这里讨论爬行。搜索引擎的后续操作描述如下：
- 解析：解析器用于解析输入HTML页面，该页面生成要编制索引的标记或术语流。解析器可以使用词法分析器生成器（如YACC和Flex（来自GNU项目）来构建。前面几节中描述的一些预处理任务也可以在解析之前或之后执行。
- 索引：此步骤将生成倒排索引，可以使用前面部分中描述的任何方法完成。为了提高检索效率，搜索引擎可能会构建多个倒置索引。例如，由于标题和锚文本通常是对页面的非常准确的描述，因此可以仅根据其中出现的术语来构建一个小的倒排索引。请注意，此处的锚文本用于索引其链接指向的页面，而不是包含它的页面。然后，根据每个页面中的所有文本（包括锚文本）构建完整索引（一段锚文本既会为包含它的页面，也会为其链接指向的页面编制索引）。在搜索中，算法可以先搜索小索引，然后再搜索完整索引。如果在小索引中找到足够数量的相关页面，系统可能无法在完整索引中搜索。
- 搜索和排名：给定用户查询，搜索涉及以下步骤：
- 使用前几节中描述的一些方法对查询词进行预处理，例如，删除停用词和词干提取;
- 在倒排索引中查找包含所有（或大部分）查询词的页面;
- 对页面进行排名并将其返回给用户。
排名算法是搜索引擎的核心。然而，人们对商业搜索引擎中使用的算法知之甚少。我们根据早期谷歌系统中的算法给出一个一般的描述。正如我们之前所讨论的，传统的IR使用余弦相似度值或任何其他相关度量来对文档进行排名。这些措施仅考虑每个文件的内容。对于Web来说，这种基于内容的方法是不够的。问题在于，在网络上，几乎任何查询都有太多的相关文档。例如，使用“网络挖掘”作为查询，搜索引擎谷歌估计有46,500,000个相关页面。显然，任何用户都不可能查看如此庞大的页面。因此，问题在于如何对页面进行排名并在顶部向用户展示“最佳”页面。
网络上一个重要的排名因素是页面的质量，这在传统的IR中几乎没有研究过，因为IR评估中使用的大多数文档都来自可靠的来源。然而，在网络上，任何人都可以发布几乎任何东西，所以没有质量控制。尽管页面可能是100%相关的，但由于多种原因，它可能不是高质量的页面。例如，作者可能不是查询主题的专家，页面中给出的信息可能不可靠或有偏见等。
但是，Web确实有一个重要的机制，即超链接（链接），可以在一定程度上用于评估每个页面的质量。从第x页到第y页的链接是第x页到第y页的隐式权限传递。也就是说，第x页的作者认为第y页包含质量或权威信息。也可以将第x页指向第y页这一事实视为第x页对第y页的投票。可以利用Web的这种民主性质来评估每个页面的质量。一般来说，一个页面收到的票数越多，它就越有可能是一个高质量的页面。实际的算法比简单地计算指向页面的投票数或链接数（称为内链接）更复杂。我们将在下一章中描述这些算法。PageRank是最著名的此类算法。它利用网页的链接结构来计算每个页面的质量或声誉分数。因此，可以根据网页的内容因素和声誉来评估网页。基于内容的评估取决于两种信息：
- 出现类型：页面中有几种类型的查询词出现：
- 标题：查询词出现在页面的标题字段中。
- 锚点文本：查询词出现在指向当前正在评估的页面的锚点文本中。
- URL：查询词出现在页面的URL中。许多URL地址都包含页面的一些描述。例如，Web挖掘上的页面可能具有URL http://www.domain.edu/Web-mining.html。
- 正文：查询词出现在页面的正文字段中。在这种情况下，将考虑每个术语的突出性。突出是指在文本中是否使用大字体、粗体和/或斜体标签强调该术语。可以在系统中使用不同的突出级别。请注意，页面中的锚文本可以被视为纯文本，以便对页面进行评估。
- 计数：每种类型的术语的出现次数。例如，查询词可能会在页面的标题字段中出现2次。然后，该术语的标题计数为2。
- 位置：这是每个术语在每种事件类型中的位置。该信息用于涉及多个查询词的邻近评估。彼此靠近的查询词比相距较远的查询词更好。此外，以与查询相同的顺序出现在页面中的查询词也更好。
对于基于内容的分数（也称为IR分数）的计算，每种出现类型都会被赋予一个关联的权重。所有类型的权重都形成一个固定的向量。每个原始项计数都转换为计数权重，所有计数权重也形成一个向量。
现在让我们看一下两种查询，单字查询和多字查询。单个单词查询是只有单个术语的最简单情况。从倒排索引中获取包含该项的页面后，我们计算类型权重向量和每个页面的计数权重向量的点积，从而得到页面的IR分数。然后，将每个页面的IR分数与其声誉分数相结合，以产生该页面的最终分数。
对于多词查询，情况类似，但更复杂，因为现在存在考虑术语邻近性和排序的问题。让我们通过忽略页面中的术语排序来简化问题。显然，页面中彼此靠近的术语的权重应该高于相距较远的术语。因此，需要匹配多个出现的术语，以便可以识别附近的术语。对于每个匹配的集，都会计算一个邻近值，该值基于页面中术语的相距。此外，还会计算每种类型和邻近度的计数。每个类型和邻近度对都有一个类型邻近权重。计数将转换为计数权重。计数权重和类型邻近权重的点积为页面提供IR分数。术语排序可以类似地考虑并包含在IR分数中，然后将其与页面声誉分数相结合以产生最终的排名分数。
搜索引擎近乎实时地维护以下过程：网络爬虫、索引、搜索。
这张图片显示了Web Crawler的架构。
我的网络爬虫在行动。
用于创建MySQL数据库的Python脚本：
用于在队列中添加和删除URL的Python脚本：
用于抓取Internet的Python脚本：
INDEX.HTML text-mining.ro 中的文件：
搜索。来自https://www.text-mining.ro/ 的PHP文件：
我正在开发Web Crawler的Kotlin版本，具有与Python脚本相同的实现/功能。