搜索引擎如何工作

我们整理了旧信件，并发现了Ilya Segalovich iseg在2002年为《互联网世界》杂志撰写的一篇文章。 在其中，他将互联网和搜索引擎与世界奇观进行了比较，反思了搜索技术并回顾了它们的历史。 尽管工作量很大，Ilya还是在创纪录的时间内写了一篇文章，甚至提供了足够详细的术语表，今天阅读起来特别有趣。 我们找不到包含该文章的电子杂志，因此今天我们将其发布在博客上，顺便说一句，第一作者是Ilya。



世界上已经有成百上千个搜索引擎 ，如果算上在各种程序中实现的搜索功能，则需要跟踪成千上万个。 无论搜索过程如何实现，无论它基于什么数学模型，实现搜索的想法和程序都非常简单。 尽管这种简单性显然属于他们所说的“简单但有效”的类别。 一种或另一种方式是，搜索引擎成为世界上两个新奇事物之一，使智人可以不受限制地即时访问信息。 很明显，第一个奇迹就是具有通用通信功能的互联网。

历史搜索引擎

人们普遍认为，新一代的程序都比上一代更完善。 可以说，在一切还不完美之前，现在几乎到处都是人工智能 。 另一个极端的观点是“一切新事物都被遗忘了。” 我认为对于搜索引擎而言，真相介于两者之间。

但是，近年来真正发生了什么变化？ 不是算法或数据结构，不是数学模型。 虽然他们也是。 使用系统的范例已经改变。 简而言之，一名家庭主妇正在寻找便宜的熨斗，并从一所辅助寄宿学校毕业，以期找到汽车修理工的工作，但他却被搜寻线所吸引。 除了出现在前Internet时代不可能出现的因素（占搜索引擎总需求的因素）外，还出现了其他一些变化。 首先，很明显，人们不仅“思考单词”，而且“寻找单词”。 在系统的响应中，他们希望看到在查询字符串中键入的单词。 第二点：很难“训练寻求者”以“训练寻求者”，就像很难训练说或写一样。 60年代和80年代关于迭代优化查询，理解自然语言，关于按意义搜索，关于问题的连贯答案的梦想现在几乎无法经受现实的残酷考验。

算法+数据结构=搜索引擎

像任何程序一样，搜索引擎使用数据结构进行操作并执行算法。 算法的种类不是很大，但是很大。 除了量子计算机，它使我们有望在搜索的“算法复杂性”方面取得神奇的突破，并且作者几乎一无所知，此外还有四类搜索算法。 四分之三的算法需要“索引”，即对文档的初步处理，这会创建一个辅助文件，即“索引”，旨在简化和加快搜索本身。 这些是反向文件，后缀树，签名的算法。 在简并的情况下，没有初步的索引步骤，而是通过顺序查看文档来执行搜索。 这样的搜索称为直接搜索。

直接搜寻

最简单的版本是很多人熟悉的，并且没有程序员会一生中至少不会编写这样的代码：
尽管看起来很简单，但是在过去30年中，直接搜索一直在深入发展。 已经提出了大量的想法，这些想法有时会减少搜索时间。 这些算法在各种文献中都有详细描述，并且有它们的摘要和比较。 可以在诸如Sedgwick或Cormen的教科书中找到对直接搜索方法的良好评价。 应当记住，新算法及其改进的选项不断出现。

尽管直接查看所有文本是一项相当缓慢的任务，但是您不应认为Internet上没有使用直接搜索算法。 挪威搜索引擎Fast（www.fastsearch.com）使用了一种芯片 ，该芯片实现了简化的正则表达式的直接搜索逻辑，并将这些芯片中的256个放置在一块板上。 这使Fast可以在每单位时间内处理相当数量的请求。

另外，有许多程序结合了索引搜索来查找文本块，并在块内进行进一步的直接搜索。 例如， 瞥见非常流行，包括在Runet上。

通常，直接算法从根本上具有双赢的独特特征。 例如，近似和模糊搜索的无限可能性。 实际上，任何索引编制总是与术语的简化和规范化相关，因此，也与信息的丢失有关。 直接搜索可直接对原始文档进行操作而不会产生任何失真。

倒档

尽管有神秘的外来名称，但这种简单的数据结构在直觉上对于任何有识之士和甚至没有进行全文搜索的任何数据库程序员都是熟悉的。 根据“一致性”，第一类人知道这是什么-按字母顺序排列一个文本或属于一个作者的单词的详尽列表（例如，“普希金的诗句一致性”，“陀思妥耶夫斯基新闻辞典”） ） 后者在构建或使用“按关键字段的数据库索引”时处理倒排列表的一种形式或另一种形式。

我们将在莫斯科宗主教官针对圣经的主音节翻译文本发行的精彩的俄罗斯和谐音“交响曲”的帮助下，说明这种结构。



这是单词的字母顺序列表。 对于每个单词，列出出现该单词的所有“位置”。 搜索算法包括找到正确的单词并将已经扩展的位置列表加载到内存中。

为了节省磁盘空间并加快搜索速度，通常采用两种技巧。 首先，您可以保存职位本身的详细信息。 确实，这样的位置设置得越详细，例如，在“交响曲”的情况下，它是“书+章+诗句”，则将需要更多空间来存储倒排文件。

在最详细的版本中，您可以在倒排的文件中存储单词号，距文本开头的字节偏移量，字体的颜色和大小等等。 通常，它们仅表示文件的数量，例如圣经的书，以及该单词在其中的使用数量。 这种简化的结构在经典的信息检索理论-信息检索（IR）中被认为是基础。

第二种压缩方法（与第一种压缩方法无关）：以地址的升序排列每个单词的位置，每个位置不存储其完整地址，而是存储与前一个地址的差异。 假设我们记得到章节编号为止的位置，则此列表在我们的页面上将如下所示：

: [.1],[+11],[0],[+2],[+4],[+2],[+4],..

另外，在存储地址的差异方法上强加了一些简单的打包方法：为什么将固定的“大量”字节分配给一个小整数，因为您可以为其分配几乎所有的字节。 在这里应该提及Golomb代码或流行的Perl语言的内置功能： pack(“w”) 。

在文献中，还有一门火力最大的包装算法大炮：算术，霍夫曼，LZW等。这方面的进展是连续的。 实际上，它们很少用在搜索引擎中：增益很小，并且处理器的效率低下。

作为所有上述技巧的结果，根据寻址细节，通常情况下，反向文件的大小是源文本大小的7％至30％。

在红皮书中列出

反复提出了除反向搜索和直接搜索以外的算法和数据结构。 首先，这些是后缀树（请参阅Manber和Gonnet的书）以及签名 。

它们中的第一个在Internet上起作用，是搜索系统OpenText的专利算法。 我在国内搜索引擎中遇到了后缀索引。

第二种-签名方法-是文档转换为其单词的哈希值的块表的表-“签名”和在搜索过程中顺序查看“签名”。

两种方法都没有被广泛采用，因此在这篇简短的文章中不应该进行详细的讨论。

数学模型

5个搜索引擎和模块中大约有3个在没有任何数学模型的情况下运行。 更准确地说，他们的开发人员没有为自己设定实现抽象模型的任务，并且/或者没有意识到它的存在。 这里的原理很简单：如果只有程序找到了东西。 不管怎么说 然后用户会弄清楚。

但是，关于提高搜索质量，除了经验上附加的系数外，关于大量信息，关于用户查询流的信息一经发现，使用某种简单的理论装置就很有用。 搜索模型是对现实的某种简化，在此基础上可以获得一个公式（任何人都不再需要该公式），该公式使程序可以做出决定：认为可以找到哪个文档以及如何对其进行排名。 在采用模型之后，系数通常具有物理意义，并且对于开发人员本人来说更易于理解，因此选择它们变得更加有趣。

传统信息检索（IR）的各种模型通常分为三种类型：集合论（布尔，模糊集，扩展布尔）， 代数 （向量，广义向量，潜语义，神经网络）和概率。

实际上，布尔模型系列是实现全文搜索的程序员首先想到的。 有一个词-认为已找到文档，否-未找到。 实际上，经典的布尔模型是连接信息检索理论与搜索和数据处理理论的桥梁。

布尔模型的批评很公平，在于其极度的僵化和不适合排名。 因此，早在1957年，乔伊斯和李约瑟（Joyce and Needham） 建议考虑单词的频率特性，以便“ ...比较操作将是向量之间的距离之比...”。 矢量模型是由信息检索科学的开国元勋Gerard Salton（Gerard Salton）于1968年在搜索引擎SMART（萨尔顿的神奇文本自动检索器）中成功实现的。 此模型中的排名基于自然的统计观察，即术语在文档中的局部频率（TF）越大，并且在集合（IDF）中术语的“稀有”（即文档中的返还次数 ）越多，则该文档相对于术语的权重越高。

---

^{杰拉德·萨尔顿（Gerard Salton）（萨尔曼），1927-1995年。 他是塞尔顿，他是Zalton甚至是Zalman，他是Gerard，Gerard，Gerard甚至是Gerald，具体取决于翻译人员的口味和所作的错字。
http://www.cs.cornell.edu/Info/Department/Annual95/Faculty/Salton.html
http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/s/Salton:Gerald.html
http://www.cs.virginia.edu/~clv2m/salton.txt}

IDF的名称是由Karen Sparck-Jones（Karen Spark-Jones）于1972年在有关特异性一词的文章中引入的。 从现在开始，名称TF * IDF被广泛用作矢量模型的同义词。

最后，在1977年，Robertson和Sparck-Jones（ Robertson和Spark-Jones）证实并实施了概率模型 （早在1960年就提出 ），这也为整个家庭奠定了基础。 在该模型中的相关性被认为是该文档可能是用户感兴趣的可能性。 这意味着存在由用户选择或在某种简化的假设下自动接收的相关文档的现有初始集合。 与每个后续文档相关的概率是根据相关集中术语的出现与集合中其余“不相关”部分的比率来计算的。 尽管概率模型具有一定的理论优势，但是由于它们以“相关概率”的降序排列文档，因此在实践中它们并未得到太多分配。

我不会详细介绍每个模型的公式。 他们的摘要以及讨论在《现代信息搜索》一书中以压缩形式占据了35页。 唯一重要的是要注意，在每个族中，最简单的模型是从单词独立性的假设出发的，并且具有简单的过滤条件：永远不会找到不包含查询词的文档。 每个系列的高级（“替代”）模型都不会将查询词视为独立的词，但是，此外，您还可以从查询中查找不包含单个词的文档。

搜索“按感觉”

查找和排序不包含来自查询的单词的文档的能力通常被认为是人工智能的标志或通过含义进行搜索，并且先验与模型的优势有关。 是否如此的问题，我们将不在本文的讨论范围之内。

例如，我将仅描述一种可能是按含义起作用的最受欢迎的模型。 在信息检索理论中，此模型称为潜在语义索引 （换句话说，揭示了隐藏的含义）。 该代数模型基于将单词与文档相关联的矩形矩阵的奇异分解。 矩阵的元素是频率响应，反映了单词和文档的连接程度，例如TF * IDF。 代替最初的百万维矩阵， Furnas和Deerwester方法的作者建议使用与奇异分解的第一主要成分相对应的50-150 “隐藏含义”。

大小为m * n 的实数矩阵A的奇异分解称为形式为A = USV的任何分解，其中U为大小为m * m的正交矩阵，V为大小为n * n的正交矩阵，S为大小为m * n的对角矩阵，其元素为s _ij如果i不等于j ，则s = 0，并且s _ii = s _i > = 0 ^。 在英语文献中，奇异分解通常称为SVD分解 。

很久以前就证明了 ，如果我们不考虑前k个奇异数（将其余的等于零），就可以得到秩k初始矩阵的最接近近似值（在某种意义上，它是“秩k的最近语义解释”）。 通过降低排名，我们可以过滤掉无关的细节； 越来越多，我们试图反映真实数据结构的所有细微差别。

由于每个单词和每个文档都与k个含义的相对较短的向量（相应矩阵的行和列）相关联， 因此大大简化了搜索或查找相似文档的操作。 但是，由于“含义”的意义低，或者由于其他原因，在额头上使用LSI进行搜索尚未普及。 尽管出于辅助目的（自动过滤，分类，集合分离，其他模型的尺寸初步降低），此方法似乎找到了应用。

质量评估

一致性检查表明，任何两个评估者之间相关文档的重叠平均约为40％...评估者的召回率和约65％的精确度...这意味着检索系统性能的实际上限为65％...
唐娜·哈曼
我们从TREC中学到了什么，但没有学到

笔译

“ ...稳定性检查表明，任何两个评估者之间相关文档的重叠平均大约为40％...评估者之间测得的准确性和完整性约为65％...这在65％的范围内对搜索质量施加了实际上限...”

无论采用哪种模型，搜索引擎都需要“调整”-评估搜索质量和调整参数。 质量评估是搜索理论的基础。 因为有了质量评估，我们可以讨论特定模型的适用性或不适用性，甚至可以讨论它们的理论方面。

特别是，搜索质量的自然限制之一是在题词中所进行的观察：两个“评估者”（专家对相关性做出结论的专家）的平均意见在很大程度上并不一致！ 这也意味着搜索质量的自然上限，因为质量是通过与评估者的意见进行比较来衡量的。

通常，会测量两个参数以评估搜索的质量：

• 精度-搜索引擎响应中相关材料的比例
• 完整性（召回）-相关文件占相关收集文件总数的比例

在由美国标准学会（NIST）创建的文本检索评估会议（TREC） *的框架中，使用并定期使用这些参数来选择模型及其参数。 从1992年开始，这个由25个小组组成的联盟在会议成立的第12年时，已经积累了重要的资料，搜索引擎仍在此基础上进行研究。 对于每次例行会议，每个感兴趣的领域都在准备新的材料（所谓的“曲目”）。 “轨道”包括文件和请求的集合。 我将举一些例子：

-跟踪随机请求（ 临时 ）-在所有会议上出席
-多语言搜索
-路由和过滤
-高精度搜索（一个答案，准时执行）
-用户互动
-自然语言的“路径”
-对“问题”的回答
-搜索“脏”（仅扫描）文本
-语音搜索
-在很大的情况下（20GB，100GB等）进行搜索
-WEB军团（在最近的会议上，它以.gov域的一部分表示）
-分布式搜索和合并来自不同系统的搜索结果

---

^{*会议资料可在trec.nist.gov/pubs.html上公开获得。}

不仅搜索

从TREC的“路径”可以看出，许多任务与搜索本身紧密相连，它们具有共同的意识形态（分类，路由，过滤，注释），或者是搜索过程中不可或缺的一部分（聚类结果，扩大和缩小查询范围，反馈， “与查询相关的”注释，搜索界面和查询语言）。 没有一个搜索引擎实际上不必解决这些任务中的至少一项。

在搜索引擎竞争中，一个或另一个附加属性的存在通常是决定性的论据。 例如，由一些文件的信息性引号组成的简短批注，一些搜索引擎将其与工作结果一同提供帮助，使它们在竞争中保持领先半步。

不可能说明所有任务以及如何解决它们。 例如，考虑“查询扩展”，这通常是通过参与关联词的搜索来完成的。 解决此问题的方式有两种：局部（动态）和全局（静态）。 当地技术人员依靠查询文本并仅分析在其上找到的文档。 全局“扩展”可以与叙词表一起使用，既可以先验（语言），又可以在整个文档收集过程中自动构建。 根据普遍接受的观点，通过叙词表进行的全局查询修改效率低下，从而降低了搜索的准确性。 一种更成功的全局方法是基于手动建立的静态分类，例如WEB目录。 此方法广泛用于Internet搜索引擎中的缩小或查询扩展操作。

通常，附加功能的实现是基于与搜索本身相同或非常相似的原理和模型。 , , , ( – TF*IDF), . (relevance feedback), () , .

, , «Term Vector Database» , «» ( ).

语言学

, . . , (, , ), . , (, ) , . , , :

—
— ( ): ,
— ( - )
— (, ): «», ,
— () (, )
— :
—

, . - (LSI, ), - , .

“Things that work well on TREC often do not produce good results on the web… Some argue that on the web, users should specify more accurately what they want and add more words to their query. We disagree vehemently with this position. If a user issues a query like «Bill Clinton» they should get reasonable results since there is a enormous amount of high quality information available on this topic”
Sergei Brin, Larry Page
The Anatomy of a Large-Scale Hypertextual Web Search Engine

笔译

«, TREC, … , , , . . « », , ...»

«I was struck when a Google person told me at SIGIR that the most recent Google ranking algorithm completely ignores anything discovered at TREC, because all the good Ad Hoc ranking algorithms developed over the 10 years of TREC get trashed by spam»
Mark Sanderson

笔译

« , - Google , TREC, , « » ...»

, : ?

, , , - , ( , . .) . (off-page) , ́ , . , , , , – .

C , -. , «» , . , , , « » , , .

, , , , , . ( – ), . .

.

. , 1999-2000 . ( ) , .

( ) , . , . 1998 . , , . 1998 PageRank – , , . , (, , 80- ), .

, PageRank, ( , ) – HITS , - . , (. . ) , .

, , , . , , : , . . , : (, www.teoma.com ), .., . .

, . , Google Fast, . : «» , , 100 , 30% – . .

, , : , .. , , , « ».

. : ; – .

– , , , . . : , , , , . . , .

, , , : , , .

, , . - .

Udi Manber ( ) ( agrep) 1994 , Andrei Broder ( ) 1997- «» ( shingles, «», «»). .



( ). , , , . (, , 9) , , , 25. , . , – , , , , ( ) : ! 25 !

, , .. : « » ! . ( ; , 0%; .)

, , - , . , ( ), -.

. , . .

, , . , 1997 ( Inktomi) 32- (Linux, Solaris, FreeBSD, Win32) . AltaVista, «» 64- Alpha.

(, , c) . . , , , , . Pruning ( . , ) , . pruning, , .

– , , . , .

, (, - ) . , , , , : , .

, , , . , , , . , , , 2-4 , , , , . .

<sup>Modern Information Retrieval
Baezo-Yates R. and Ribeiro-Neto B.
ACM Press Addison Wesley, 1999

The Connectivity Server: fast access to linkage information on the Web
K. Bharat, A. Broder, M. Henzinger, P. Kumara, and S. Venkatasubramanian
WWW7, 1998
http://www7.scu.edu.au/programme/fullpapers/1938/com1938.htm

The Anatomy of a Large-Scale Hypertextual Web Search Engine
S.Brin and L. Page
WWW7, 1998
http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm

Syntactic Clustering of the Web
Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse
WWW6, 1997

Indexing by Latent Semantic Analysis
S. Deerwester, ST Dumais, GW Furnas, TK Landauer, R. Harshman
JASIS, 1990
http://citeseer.nj.nec.com/deerwester90indexing.html

The approximation of one matrix by another of lower rank
C. Eckart, G. Young
Psychometrika, 1936

Description and performance analysis of signature file methods
C. Faloutsos, S. Christodoulakis
ACM TOIS 1987

FAST PMC — The Pattern Matching Chip
http://www.fast.no/product/fastpmc.html
www.idi.ntnu.no/grupper/KS-grp/microarray/slides/heggebo.pdf ( , web.archive.org – . .)

Information retrieval using a Singular Value Decomposition Model of Latent Semantic Structure
GW Furnas, S. Deerwester, ST Dumais, TK Landauer, RA Harshman, LA Streeter, and KE Lochbaum
ACM SIGIR, 1988

Glimpse, Webglimpse, Unix-based search software…
http://webglimpse.org

Examples of PAT applied to the Oxford English Dictionary
Gonnet G.
University of Waterloo, 1987

What we have learned, and not learned, from TREC
Donna Harman
http://irsg.eu.org/irsg2000online/papers/harman.htm

The Thesaurus Approach to Information Retrieval
T. Joyce and RM Needham
American Documentation, 1958

Authoritative Sources in a Hyperlinked Environment
Jon M. Kleinberg
JACM, 1998
http://citeseer.nj.nec.com/87928.html

An efficient method to detect duplicates of Web documents with the use of inverted index
S. Ilyinsky, M. Kuzmin, A. Melkov, I. Segalovich
WWW2002, 2002

Suffix Arrays: A New Method for On-line String Searches
U. Manber, G. Myers
1st ACM-SIAM Symposium on Discrete Algorithms, 1990

Finding similar files in a large file system
U. Manber
USENIX Conference, 1994

ME Maron and JL Kuhns
On relevance, probabilistic indexing and information retrieval
Journal of the ACM, 1960

Open Text Corporation
http://www.opentext.com

SE Robertson and Sparck Jones K.
Relevance Weighting of Search Terms
JASIS, 1976

Algorithms in C++, Robert Sedgewick
Addison-Wesley, 1992

A Statistical Interpretation of Term Specificity and Its Application in Retrieval
Karen Sparck Jones
Journal of Documentation, 1972

The Term Vector Database: fast access to indexing terms for Web pages
R. Stata, K. Bharat, F. Maghoul
WWW9, 2000
http://www9.org/w9cdrom/159/159.html

Natural Language Information Retrieval
Tomek Strzalkowski (ed.)
Kluwer Academic Publishers, 1999

: , . , . , .
, 2000
https://www.ozon.ru/context/detail/id/33769775/

- . .. , .., ..
- , 1995</sup>