搜索引擎原理步步分解（1）

用程序诠释生命

其实建这个贴的主要目的是想说：本来想刷版的，后来发现实在刷不下去了，所以决定不刷了。但是又不能只说这一句，那样就变流水贴了，所以把这篇涂鸦从我的Blog复制了过来，嘿嘿。。
郑重申明：这篇Entry只是作为自己的备忘，并不保证说的内容是正确的，有兴趣的权当消遣，说错了别说我误导大家。
　　在我打开编辑页面，写下这篇Entry的题目之前，其实我还不知道我这篇Entry要写什么东西。只是觉得我该写点东西了，于是就打开了这个页面，然后用了十秒钟来思考，十秒钟后，我写下了这个题目。我决定写写我对搜索引擎的设想和理解，前段时间想去了解一下搜索引擎是怎么设计的，可是用了google和baidu都没有找到一点资料，甚至有少许相关的资料都很少。经过一段时间的积累和自己的思考之后，终于对搜索引擎的设计有了一定的理解，现在把它记下来。怕过段时间忘了。这里很多东西都是我自己的想法而已，所以与实际不符，请不要见怪。

　　最简单的说，搜索引擎做的事情就两件：第一爬内容，第二检索内容。

　　首先说说爬内容。爬内容是用Spider来做的。Spider的功能就是不断地浏览网页，对网页内容进行分析然后存储到数据库中。具体来说，就是两部分功能，一是浏览网页，二是对网页内容进行分析。浏览网页就比较简单了，只要给它一个起始地址，并做一些相关的限制，比如深度限制，域名限制，语言限制，大小限制等，它就可以不停地工作下去了，每浏览一个网页，它就会取得页面中的所有地址，放到堆栈中，等待浏览。比较复杂也是最主要的部分是对网页内容进行相关性分析，网页相关性分析主要做两件事情：1，取得网页中的文字内容分析它的关键词，并判断各关键词在这个页面中的重要程度；2，取得网页中所链接到的页面和链接源页面，这些页面的关键词密度同时也会影响一个关键词在原页面中的重要程度；不过这并不是每个搜索引擎都是一样的，各个搜索引擎都有自己的算法。这里值得说一下的就是如果获取页面的关键词，对英文来说当然容易了，每个词两端都是空格或符号，很容易获得网页中的词，到多有一个专有名词会有点难度，关于英文的分词没有细想过，就不多说了，接下来说说中文分词。中文字都是连在一起的，没有明显的空格或是符号来标识词的开始和结束，因此就需要进行些特别的处理。比较合理的做法是使用字典。就是将所有中文词存放在一个数据库中，然后取得要分析的页面的字，与词典进行匹配，根据匹配结果对页面进行分词。然而鉴于中文字的复杂性，分词的同时主要解决的问题有下面几个：1，同音字的问题；2，匹配方向的问题；3，专有名词的问题，比如名字。爬内容先说到这里，以后有空再针对各个点细说。

　　接下来就是检索内容了。检索内容相对来说就比较简单了。它要解决的就个问题，对用户检索参数进行分析，根据分析结果检索数据库并呈现。对中文来说，对用户检索分析实际差不多相当于是分词，在分词之外可以进行一些额外的运算来优化检索结果，比如：根据多个关键字的排列顺序或数量来判断关键字的重要程度；储存用户的搜索信息用于判断于户搜索习惯和常搜索主题以适当的调整检索结果。

　　ＯＫ。完工。先大致记到这里了。下次有空再细说。

adisonlee

阿阿，可以贴你个blog来看看吗？想看看，有兴趣。

用程序诠释生命

嘿嘿，不咯~~~
我怕大家过去那边骂我。

adisonlee

阿阿。

小康

说得很容易

用程序诠释生命

就凭楼上一句话，我想我有必要把我所有的分析都在这里发布，让大家看到，其实搜索引擎原理也不过如此，要不就太对不起楼上了。。。
嘿嘿。。

大鱼

原理这个概念也太大了吧？

乖乖火龙

Originally posted by 用程序诠释生命 at 2005-12-8 20:20:
就凭楼上一句话，我想我有必要把我所有的分析都在这里发布，让大家看到，其实搜索引擎原理也不过如此，要不就太对不起楼上了。。。
嘿嘿。。

搜索引擎有简单的，复杂的。
你说的容易是简单的，
我有一个需求，看你如何设计。

搜索引擎包括几部份，最重要的是“分词”和“检索内容”
你说的爬虫我反倒觉得很简单。

分词的一个最重要的课题不是对已有关键词进行分词的问题，而是对未知的，新出现的关键词的自我学习，比如我的名字，我爸妈没取之前可能没有这个词，比如我的英文名，我的网名。或者一个新的概念。
谈谈你的看法？
你如何能够设计出一个能够自我学习自我完善的算法来满足呢？这时候不能弄一个管理界面让工作人员输入或者修改就行了。


再说说检索，我能够保证单机结构下在收录大概1千万个网页时能够达到0.01秒以下的搜索时间，如果多于1000万或更大，你不得不使用快慢表或者其他技术，而且这时候一台机器的资源已经达到瓶颈（你可以说使用大型机能够满足单表上亿条记录的select和连接请求，那上百亿呢？），分布式计算就十分的必要，这就需要数学的统计技术了。而数学统计不能达到精确的搜索结果，不知道对这方面你有什么看法呢？

我5系高手

LET‘S GET OUTTA HERE，DAT’S GONNA BLOW！

乖乖火龙

Originally posted by 我5系高手 at 2005-12-12 18:55:
LET‘S GET OUTTA HERE，DAT’S GONNA BLOW！

？？？
这句英文什么意思啊？

乖乖火龙

我抛一下砖头吧：
我自己设计了一个搜索引擎，其中的分词采用的主要是词典的方式，我的词库不是放在数据库中的，而是自己设计的一个二进制文件，这个文件第一部分是索引，支持所有单字节和双字节的简繁英文，之后是一个巨大的二叉树结构，大概支持4千万个关键词，利用自己写的分词算法的时间复杂度o(n)，是相对于要进行分析的内容的长度。其主要原理是，扫描要分词的内容，然后每获得一个字（单字节或双字节），对于首字，匹配索引进入数据区，这个索引大大提高了分词效率；对于非首字，根据已进入的数据区进行顺序匹配，这个地方本来是可以做排序的，但为了支持常量时间插入，只好忍痛了。我用的是php实现了我的算法，由于php的解析执行，现在分析一篇有1万字内容的网页需要4秒时间，如果用c实现会快很多。

爬虫用的是简单的linux shell写成的，只能是属于试验的版本。这里就不多说了，其实原理很简单。

检索方面遇到一些麻烦，当表足够大时，无论做什么索引，表连接都是非常慢的，这个瓶颈在我的机子上是1000万条记录。这个糟糕的设计我就不放上来了。

用程序诠释生命

哈哈，楼上以后请多指教。我也只是正在学习当中。
其实我这篇东西只是很简单地感性的介绍而已。
下一篇Entry会是关于搜索引擎的存取的。
只是还没动笔，没想到楼主在这里简单地提了一下。
那我就先说一点点啦，还没有系统地去组织。

要做搜索引擎，我觉得绝对非分布式莫属。不仅是分布式存储，还是分布式运算。
关于存储方面，我觉得google那样做自己的文件系统那是最完美的了，因为搜索引擎的数据存储有它自己的特点（比如：多读，少写，文件大，分布式存储），如果设计一个符合这些特性的文件系统那是最好的选择，当然，成本又高了。
关于运算方面，比如说一次检索，它会提交到一个计算机集群，由集群里的计算机找出自己的相关记录再汇合到一部计算机上进行整合。当然，这里只是粗略地说，如果仔细想，还是有很多细节问题的，暂时就不说那和深入了。

　　关于分词，你说的是，自动学习才是最重要的课题。坦白讲，这个我之前并没有想过。不过刚刚粗略考虑了一下，我认为这就涉及到语言学了，应该从语法方面来分辨是否是新的专有名词或是名字（我记得大概是2000年的时候有一个孙悟空搜索引擎，它就是以提问的方式进行搜索的，它的算法正是我们想要的，我想说到这里你应该可以明白我是怎么想的了吧？），不过不管再怎么智能，或多或少还是需要有人工参与的。至于非专有名词应该就不在自动学习之列了，因为这些词相比于专有名词来说很容易就可以维护一个完整的词典了。
　　

乖乖火龙

Originally posted by 用程序诠释生命 at 2005-12-12 22:34:
哈哈，楼上以后请多指教。我也只是正在学习当中。
其实我这篇东西只是很简单地感性的介绍而已。
下一篇Entry会是关于搜索引擎的存取的。
只是还没动笔，没想到楼主在这里简单地提了一下。
那我就先说一点点啦 ...

你看看我这个,是网通的网络,传输比较慢.
http://218.107.56.6/index.php

用程序诠释生命

刚刚看了一下，我把我发现的说说吧。
第一，爬内容速度不快，大概四五秒才一个页面。可能是网通的速度关系。
第二，分词有点奇怪，不像是左起分词，又不像是右起分词，能不能说说你分词的思路？我查了\"学生\"，“活动”都说明词典中有这两个词，又查了“学生活”，你分出来的词居然是“生活”，以为你是右起分词。再查“学生活动”，居然分出“生活”，不得其解。能不能说说你的分词思路？
第三，好像不支持英文搜索。
暂时就这么多。

乖乖火龙

Originally posted by 用程序诠释生命 at 2005-12-13 20:34:
刚刚看了一下，我把我发现的说说吧。
第一，爬内容速度不快，大概四五秒才一个页面。可能是网通的速度关系。
第二，分词有点奇怪，不像是左起分词，又不像是右起分词，能不能说说你分词的思路？我查了\"学生 ...

实际上我用的是左起分词
如果搜索 \"我的学生活动\"
以我开始,找出\"我的\",如果词库有的话
然后,我的学 失败,则向前
到的, 匹配\"的学\"失败
到\"学\",匹配\"学生\",\"学生活动\"成功
到\"生\",匹配\"生活\"
到\"活\",匹配\"活动\"

所以最后匹配了
我的
学生
学生活动
生活
活动


基本上包含了所有能够分出的词组,这些词组依据词库.更改词库增加条目导致分词结果不同.
我打算在上面增加关键词的权重,例如对于专业名词,搜索频繁的关键词,进行优先处理,这样把权重大的放到前面, 搜索一般对前面的关键词能够有较大关联度.

用程序诠释生命

个人觉得不应该词里面的每个字不应该重复利用。
因为分词的作用是让程序理解用户的意思，但是按你的分法，却一定程度上误解的用户的意思。
“我的学生活动\",相信分解为“我”和“学生活动”会是比较合适的分词结果，这样比较能表达用户的意思。(“的”字应该忽略),如果按你的分法，至少“生活”并不是用户想搜索的内容，这样会影响搜索结果，还毫无意义地增加了分词的开销。
我设计过一个分词算法，它有字表，词表，字表的作用是来做同音字相关的判断和建议，分词的时候长度最长的词优先匹配。匹配过的字就不再重复匹配。

sasadong

Originally posted by 用程序诠释生命 at 2005-12-13 21:13:
个人觉得不应该词里面的每个字不应该重复利用。
因为分词的作用是让程序理解用户的意思，但是按你的分法，却一定程度上误解的用户的意思。
“我的学生活动\",相信分解为“我”和“学生活动”会是比较合适的 ...

谢谢，你的建议很好，
分解为“我”和“学生活动”，的确是最佳的分法。

现在我这样分词也是有我的道理的，
首先，我不否认会产生误解，例如，“生活”是多余的。但这个多余却不是没有用的。
其次，检索算法能够将最大关联度（根据最佳的情况是，网页内容的主题需要符合搜索的主题）的网页靠前，即按照关联度排序，因而，虽然“生活”并不是用户最想搜索的，但如果确实没有“学生活动”的文章，一篇“生活”的文章也许能让用户找到一些线索。如用户搜索“加菲猫”，如果没有“加菲猫”的网页，但是有“加菲”的网页，无疑这是很好的。
最后，我会设计一个关于关键词的权重的算法，将重排根据用户搜索的字符串产生的关键词的顺序。这个顺序关系到判断用户最想搜索的主题是什么。

在我给出的网址是一个试验，现在的网页收录了1477个，检索用时0.7秒，任重道远啊，我debug一下，分词用时0.01，搜索结果（4个关键词）用时是最多的。说明我的数据结构设计不好。