January 2008
Monthly Archive
隐含语义索引LSI (Latent Semantic Index) 与搜索引擎的关系
上次写了一篇文章介绍Google搜索引擎的工作原理。 大家可以看出Google搜索引擎成功的法宝是Google计算方向链接决定网页的PageRank算法。如果你对SEO（搜索引擎优化）有一点了解，并且细心观察的话，你会发现：现在google的搜索结果中，有一些PageRank很高的网页排在PageRank很低的网页之后。这是不是说PageRank不起作用了呢？
答案当然是否定的。PageRank在Google的搜索引擎算法中依然起着十分重要的地位。但Google更加看重那些从相关网站过来的链接，而对那些不相关的网站的链接在最后计算网页排名不起作用（但这些不相关的网页链接在计算PageRank是还是有用的）， 所以就出现了大家看到的PageRank很高的网页排在PageRank很低的网页之后这种现象了。
那么Google是如果判断网站的相关性的呢？这就是我今天要介绍的隐含语义索引LSI (Latent Semantic Index)。
隐含语义索引LSI除了计算一个网页包含的关键字以外，还参考了其它网页或者文档所包含的关键字的组成。LSI认为具有很多相同关键字的网页， 他们的文章内容也比较接近。尽管LSI算法并不理解单词的意思，但它最后计算出来的结果却是表现的非常高的智能。
LSI是如何工作的？
首先将网页所有的单词做一个列表，然后将那些没有语义的单词做过滤。将所有的文档均作出单词列表。利用这个列表可以就可以做一个以文档为X轴， 单词为Y轴的巨型矩阵。如果单词出现在某个文档，则在对应的位置表示为1，反之为0。 这样检查Y轴的某个单词就可以发现所有包含着个单词的文档。
为了使计算更加正确，LSI引入关键字的权重。关键字的权重计算基于以下常识推理：
1）单词在一篇文章中出现多次比只出现一次的单词更有意义；
2）不经常出现的单词比到处出现的单词更有意义；
第一个推理适用于单个文件，叫做本地权重。那些在一个文档中多次出现的单词就比那些只出现一次的单词有更高的本地权重。
第二个推理适用于单词在所有文档的权重计算，叫全局权重。有各种不同的全局权重计算方法，但其思路均体现为在少数文档中出现的单词比那些到处出现的单词有更深刻的含义。一个典型的关键字在矩阵中的权重计算方法是TF-IDF (term frequency–inverse document frequency)。
利用这个巨型的单词文档矩阵，LSI还可以算出某个主题在其它文档中所出现的相关的关键字以及出现频率。这样即使有的相关文档不出现你所搜索的关键字，也可能将相关文档搜索出来。这比以前只对照关键字的搜索方法更进一步。所以如果你还是采用传统的关键词匹配的方法作网页优化的话，其优化效果将大大降低。
LSI还可以用来分析网页的链接描述文本（Anchor Text）。如果你的网页反向链接全部采用相同的链接描述文本， 而不采用其它相关的关键字，那么你的反向链接的有效性也必将大大降低。
举例来说：如果你是做“书”这个关键词，那么其相关的关键词可以是“手册”“指南”“报告”等等。
如果你想了解更多有关LSI (Latent Semantic Index)的知识，请访问http://www.knowledgesearch.org/lsi/lsa_definition.htm。
转载请注明：
转载自SEO Expert蒋海明的网络创业营销博客
Google搜索引擎工作原理简介
这篇文章是基于Google创始人Lawrence Page和Sergey Brin一篇早期的论文翻译整理简化而成。尽管Google一直在修正不同因素对网页的权重影响以期排除作弊网站对搜索结果的干扰和获得最好的搜索结果，但其核心思路并没有改。
Google采用了两个重要的特性，因此而获取了准确的查询结果：第一，Google利用网页的链接结构计算出每个网页的等级排名，这就是所谓的PageRank；第二，Google利用了链接提供的信息进一步改善搜索结果。
PageRank的计算：
PageRank的基本思路是：如果一个网也被其他网页多次指向，这就说明本网页比较重要或者质量较高。除了考虑网页链接数量之外，Google还要参考链接网页本身的级别， 以及这个网页有多少正向链接到其它网页。当然“重要”的网页的链接就会有更高的权重。 PageRank的简化计算公式：
PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
• PR(A) :网页A页的PageRank值；
• PR(Ti) :链接到A页的网页Ti的PageRank值；
• C(Ti) :网页Ti的出站链接数量；
• d :阻尼系数，0<d<1， 通常设为0.85
PageRank可以通过结合链接权重的向量矩阵的提归计算而获得（关于PageRank的深入分析，我在方便的时候会另外写一篇文章介绍）。
随机冲浪模型：
PageRank可以被理解为用户的一个行为模型。我们假设一个随机的网站浏览者”random surfer”给以一个随机的网页，他会继续点击网页中的链接直到他厌倦了而从新开始浏览一个新的随机的网页。PageRank可以理解为某个网页被随机访问的概率。而阻尼系数d则是随机访客不顺着网页的链接继续浏览下去，而从新开始一个随机冲浪的概率。对有一些网页，可能会人为的改变它的阻尼系数， 这样就可以阻止一些作弊网站误导Google而获得较高的PageRank的可能性。
你也可以这样自觉理解PageRank：一个高PageRank的网页是那些有很多网页指向的网页，或者是有一些重要网页指向的网页。Google假定，如果一个网页被很多其他不同的网页引用，就说明这个网也值得一看。另外，如果一个网页为yahoo这样的网站指向，也通常值得一看。
链接描述文本（anchor text）
Google对连接描述文字进行了特殊的处理。大多数的搜索引擎都是把链接文本和它所在的页面相关联，而Google还把链接文本和它指向的文档相关联。这样做的原因是链接描述往往提供了一个对被指向的网页更准确地描述。
除了PageRank和链接描述以外，Google还采用了一些其它的特性：首先，Google记录了所有关键字的位置信息（hits），它在搜索中充分的使用了关键字的相关性分析。其次，Google记录了一些视觉信息，比如字体的大小等等。大字以及加粗的字体比网页中的其它字体有更高的权重。
另外，Google认为，不是直接呈现给访问者的的文本信息都可能被烂用， 并用以误导搜索引擎。所以Google对metadata的文本给以较小的重视。
系统结构分析：
Google的整体系统结构如图所示：
先由URLserver发送一系列的URL地址让网站爬虫crawlers去采集。网页采集后交给存储服务器Store server。存储服务器压缩网页内容后存放到信息仓库repository。所有的新的网页都被赋予一个docID。 索引功能由索引器indexer 和排序器sorter来执行完成。Indexer读取repository的文件，并将其转换为一系列的关键字排序，称为命中hits。Hits记录了关键字，出现在文件的位置，字体的相对大小和字母的大小写。Indexer然后将这些hits放到一系列的桶barrels中，建立了部分排序的好了的正向索引。Indexer还分离出网页中的所有链接，将重要的信息存放在Anchors文件之中。这个文件包含的信息可以确定链接的指向和链接的描述文本。
URLresolver读取Anchors文件并将相对URLs转换为绝对URLs，并依次放到docIDs中。它再将链接的描述文本放到正向索引，并将docIDs与链接的描述文本相对应。同时，它也产生一个链接links和docIDs相对应的数据库。这个links数据库将被用于计算所有网页的PageRanks。
然后，排序器sorter从barrels中取得按docID排序的网页，再将其按照wordID产生一个反向索引。Sorter还在反向索引产生一个wordIDs及其偏移的列表。一个叫做DumpLexicon的程序将这个列表结合搜索引擎的词库再产生一个可以被搜索器searcher使用的新的词库Lexicon。由网页服务器构成的搜索引擎Searcher利用这个新的词库配合反向索引和PageRanks来回答查询。
命中列表Hit Lists
命种列表Hit Lists记录了一系列的关键字出现在一个网页中的信息，包括在网页中的位置，字体的相对大小和字母的大小写。Hit Lists占用了正向和反向索引里的绝大部分的空间。
命中分为两类：特别命中fancy hits 和普通命中plain hits。fancy hits包括了在URL, 标题, anchor text, or meta tag出现的关键字， 所有在其它位置出现的关键字均为plain hits。一个plain hit由大小写位1 bit， 字体大小3bits和用来表示关键字在网页的位置所组成12位bits信息(所有位置大于4095的均表志为4096)。
正向索引：
正向索引由64个桶barrel组成。每个barrel存放了一个特定范围的wordID’s。如果一个网页包含的关键字属于某个barrel范围，这个docID就记录到这个特定的barrel之中。docID与wordID’s以及这些关键字的命中列表hit lists一起记录在这个barrel中。
反向索引
反向索引与正向使用相同的barrels， 唯一的区别是反向索引由排序器sorter处理。对每一个有效的wordID， 词库lexicon中包含了指针指向具体的barrel。 它指向由docID组成的doclist列表，以及他们的所对应的命中列表hit lists。这个doclist代表了那个单词在所有文件中所出现的列表。
Google采用了两组反向索引inverted barrels。 一组包含了标题和anchor hits，另一组则包含所有的hits。 这样，google先检查第一组short barrels， 如果返回的匹配结果不够多，然后再查询第二组long barrels
Google查询流程如下：
1. 解析查询关键字
2. 转换关键字为wordIDs
3. 在短桶short barrels中寻找每个关键字在doclist的起点
4. 扫描这个doclists直到有个网页与查询全部匹配
5. 计算这个网页的查询排名Rank
6. 如果在短桶short barrels doclist列表已经查完，寻找每个关键字在长桶long barrels doclist的起点，重复第4步
7. 如果还没有查完doclist，重复第4步
8. 将匹配的网页根据计算出的rank排序，并返回前k个查询结果。
Google的排名系统
Google包含了比其它搜索引擎更多的网页信息。每一个hit list包含了位置，字体，大小写信息。另为Google还参考了anchor text以及网页的PageRank。 没有一个单一的因素会对搜索结果的排序产生太大的影响。
让我们来看一下单个关键字的查询：Google先查看对应于这个单词的网页的命中列表hit list。Google区分每个hit由几种不同的类型 （标题, anchor, URL, 大字体, 小字体等等）, 每一种类型都有自己的类型权重type-weight。 这些type-weights 组成一个由类型向量。 Google计算每一种类型的命中记数，然后这些命中记数又转换为计数权重Count-weights。计数权重开始以线性增加，然后很快就逐渐停止，这样太多的命中记数就会没有作用。Google在将Count-weights和type-weight相乘计算出网页的IR score。 最后这个IR score与PageRank相结合得到最终的搜索排序结果。
对于多关键词的搜索，计算方法就比较复杂一些。现在多个命中列表必须要全部扫描，这样对那些出现在文章中靠近的hits就比那些分开较远的hits有更高的权重。 那些相接近的hits被匹配到一起，然后计算出这些相匹配的hits的相关度proximity。相关度是基于这些hits出现在文章中的距离决定的，并被分为10个不同的值，分别表示为短语匹配（phrase match)到根本不匹配（not even close)。命中计数不仅计算每种类型，而且还计算每个类型和他们的相关度匹配。 每个类型和相关度配对有一个type-prox-weight权重。这个记数器被转换为计数权重。然后这个计数权重于与类型相关权重type-prox-weights相乘得到文章的IR score。当然最后是IR score与PageRank相结合得到最终的搜索排序结果。
最后的话
整理这篇文章的目的是为了让自己更好地了解Google搜索引擎，同时也希望能够帮助大家对Google的工作原理有一个大致的了解。如果你看了我的文章还是不太明白，英文原文可以在这里找到。 http://infolab.stanford.edu/~backrub/google.html。
转载请注明：转载自蒋海明的网络创业营销博客http://www.jianghaiming.com
儿子终于会叫爸爸了!
儿子上个星期开始会叫爸爸了，我这个做爸爸的当然是最开心。我吗说我小的时候也是先开始会叫爸爸的。儿子长得像我的地方不多，这一点倒还是像他爸的，嘿嘿。
自从孩子出生以后，他所给我带来的快乐和满足是我以前无法想象的。尽管我自认为从来都是很喜欢孩子的，但是现在发现，看别人的孩子和看自己的孩子还是会有很大的差异的。儿子给我带来最深刻的印象由这些：
- 每天都在进步：从孩子出身时哇哇大哭得那个柔弱的小生命开始，到现在能够满地奔跑。 我可以看到孩子几乎每天都在变化，学习和进步。跟儿子的巨大变化相比，而我觉得自己好像在原地踏步
- 纯真的笑容：所有的父母都会觉得，天底下最美的笑容，就数自己孩子纯洁无瑕的笑脸了。无论自己有多么的苦闷和烦恼， 看到自己孩子对着你的灿烂笑容，所有的烦恼立刻烟消云散。孩子的笑脸会让你觉得，如果你不是以同样灿烂的笑脸回报，你实在是的有点对不起他；
- 亲密无间的感觉：几个月以前，我就发现，有时候抱着儿子的时候，他会将两个手臂伸到到我的肩膀下面，上身紧紧地贴着我的胸部。世界上，还有谁能跟发生我如此亲密的接触？
- 无比的信任：我最喜欢的一个姿势，是我抱起儿子的时候，他将头靠在我肩膀上的感觉。每当这个时候，我都有一种极大的成就感和幸福感，让我感受到了生命的意义，以及自己肩膀所要承受的责任。
我想，随着孩子年龄的增长，现在这样一种亲密和信任感可能会减弱。 因为我觉得成人之间好像很难保持这样亲密的感觉的。如果真是这样的话，我应该现在多花一点时间跟孩子一起玩耍游戏，尽情享受这样的天人之乐啊。
写到这里，我忽然明白了一个道理，就是做妈妈的人为什么会那么宠爱孩子。因为大多数的时间，孩子是跟妈妈一起的，明显儿子跟他妈的关系比儿子跟我的关系要亲密的多了。孩子跟他妈的亲密关系使他妈更加觉得爱护儿子成为她的一种神圣职责。
孩子他妈，我这样说得对吗？
转载请注明：
转载自蒋海明的网上创业博客