Search Engines: Information Retrieval in Practice – 第4章

Topic:Processing Text…

本章主题:文本处理

1、本章的主题:文本变换(Text Transformation)和文本处理(Text Processing)

2、将单词(Words)转化为可建索引的词项(Terms)的形式。

3、最懒的方法是:什么都不处理,这样,所有词都可以且只能被精确匹配。这样,诸如大小写、词形变换等导致的单词,就无法被检索出来。

4、分词(Tokenization):将段落转化为Words的过程。

5、归一化(Stemming):将相似的词化为统一形式,例如run和running。

6、格式化(Structure):划分出统一格式,如title/content等

7、搜索引擎的基础,一般是以词的出现次数(词频)或多个词的共现(co-occurences)来进行Ranking的判定的。这一过程是一个统计过程(text statistics)。

8、更高级的文本处理方法,会理解语义、判断上下文,即自然语言处理NLP(Natural language processing)。但在一般的搜索引擎中并不主流。一般多用于Q&A系统等。

9、信息抽取/命名实体识别(Information extraction)将文本中的人名、地址、电话、日期等自动的抽取、识别出来。

10、从上面的Text Statistics观点来看,信息检索中,对于文档是可预测的。首先要讨论的是单个词的分布,从大量统计数据表明,词的分布是极端不均衡(skeded)的:排名前2的词of和the占据了20%的词项频率。

11、词的排名(Rank)和它的出现频率可用zipf定律表示:

r · Pr = c

对于英语来说,c一般是0.1,例如排名第一的词,它的词频约为0.1/1 = 10%,第二的为0.1/2  = 5%。zipf定律对于中间的估计非常准确,两头的偏差比较大。

12、另一个有名的估计是词汇增长定律Vocabulary Growth。它描述了再Collection中,总词数和单词数量(unique word)的关系.

v = k ·  (n^β)

v为在大小为n的collection下,词汇量的估计值。k 在 0 ~ 100之间,β=0.5。根据大量实验表明,这个估计是非常精确的。

两个估计zipf和Vocabulary Growth,对于估计倒排索引的大小,具有非常重要的意义!

13、如何估计检索结果的大小:

基础版:用P(a ∩ b ∩ c)计算,假设词项之间独立,则

P(a ∩ b ∩ c) =  P(a) ∩ P(b) ∩ P(c)

可以用df来代替P(a/b/c),设fa为单词a出现的文档个数。

f(abc) = (fa · fb · fc) / (N^2)

加强版:利用共现数据:P(a ∩ b ∩ c) = P(a ∩ b) · P(c|a ∩ b)

14、如何估算某个搜索引擎的网页规模:

找两个相对独立的词项a和b,分别查找fa:包含a的文档个数,fb:包含b的文档个数。则同时包含a和b的fab与我们要求的总文档树N和fa、fab的关系为:

fab/N = fa/N · fb/N,即

N  = (fa · fb)/fab

15、文档解析(Document Parsing):处理内容、处理结构(meta/images/graphics/code/table)。

16、对于结构的解析,可以借助HTML/XML 标签结构。对于Web搜索引擎,必须对标签解析具有一定的容错机制,因为很多网页写的都很不规范。

17、分词(Tokenizing):将文本串分割,转化为一系列单词的过程。

18、简单的分词策略(以下讨论限定在西文等有空格的情况下):按照空格分开,忽略’s、-、缩写等特殊符号。这样性能会很高,但效果比较差,因为丢失了很多信息。

19、好的分词策略应该简单、高效、灵活,可以分步骤实现:第一轮,通过HTML标签分析出各个结构,如content、title等;第二轮,对每个结构执行细化分词,如处理空格、’s等。至于stopping和stemming,交给别的轮实现。

20、一种常用的分词策略:将-、’、……、等当做空格来处理,然后按空格切词。这样的话,bob’s => bob s,做到了最小信息损失和性能之间的权衡。可以在上述基础上细化规则,如将I.B.M => ibm。以进一步提高性能。

21、停用词(Stopping):the、a、that等词无实际语义,但是出现频率非常高,占用了大量的磁盘空间。可以将它们移除,但要注意”to be or not to be”这种极端的例子。所以,如果空间允许,应该不进行停用词处理。

22、停用词表的生成方法:
(1)top n最频繁出现的词,但这种方法不太靠谱。
(2)自定义一些,如click/here等
还是那句话,如果磁盘够用,就不要做停用词处理。

23、归一化(Stemming):将语义相同的词归为一个,以提升检索效果/性能。如用户输入查询:mark spitz swimming ,但多数文档都是 mark spitz swam。那么就会出现查不到的情况。

24、归一化对于英语来说,只有小范围的提升,而对俄语、阿拉伯语等词变化频繁的语言来说,一个好的归一化工具具有决定性的作用!

25、归一化策略:程序机械处理 和 词典。

26、机械处理归一化:例如将s去掉、将ed->去掉,ess->s等。优点是基于规则的,很简单,效率高,缺点是容易误报或者漏掉。最经典是Porter Stemming算法,具体步骤见书吧,比较简单。它的False Positive比较高,目前的改进版本Porter 2。见:http://snowball.tartarus.org

27、基于词典:人工(或机器学习)构造一个词典,可以将语义相关的词搞出来,例如I和me,这是机械处理很难达到的。缺点是构造词典的代价很大。因此也有人提出机械和词典结合的方法。著名的如Krovetz Stemmer

28、对于阿拉伯语,好的Stemmer可以将性能提高50%以上!机器学习的方法构造Stemmer也是很好的选择。

29、短语/词组(Phrases)是信息检索中很重要的课题。很多Query本身就是一个短语/词组。如apple store

30、短语的定义:名词+名词或名词+形容词。这个词性是可以在分词时候分析出来的,叫做Part of speecb,词性标注。

31、但是词性标注的性能堪忧,一般不会在Index时候按照词性标注去搞短语,而是直接记录各个词的位置。然后在查询时候,将Query结合Index时候词的位置,来确定短语(即几个词出现在一个Window内,按照Position)。

32、另一种处理短语/词组的方法是n-gram,例如I have a dream => I have/ have a/ a dream。对一个1000个单词的文章,n~2,5之间的话,有3990个这样的n-grams,虽然开销很大,但可以有效的提高检索效果。

33、八卦:Google2007年公布了英文网页中,最常见的短语是:all rights reserved。而中文中是“有限责任公司”。好囧啊……

33、对于桌面、E-Mail等检索系统,作者、日期等域具有和正文同等重要的地位。当然,在Web Search中,一般不会过于看中这些域(不拿来做为检索条件)。

34、对于Web检索,HTML的一些标记结构,如Header, Strong等,具有非常重要的作用。同时,锚文本和链接等结构具有重要的意义/

35、在HTML中,一些tag是带有属性的,录入<meta name=”keyword1 keyword2″>,这些属性也是又意义的。

36、链接<a href=”/wiki/Fish” title=”Fish”>fish</a>中。herf为url,fish为锚文本,Fish是鼠标移动上去后显示的文本。这些信息一般用于PageRank等链接分析。

37、XML的tag是可自定义的称为schema,因此可用它构成具有语义的文档描述。有检索语言XQuery,用于XML检索。

38、链接分析:帮助搜索引擎理Web页面链接之间的关系,辅助Ranking页面。

39、锚文本的两个属性:
(1)很短,但足够有效的描述指向的页面。是对目标页面的有效概述,锚文本一般用于附加域,配合其他域Rank,而不是独立使用。因为不是所有页面都有指向它们的锚文本。
(2)可以从不同的角度描述指向的页面。
(3)锚文本已经称为了TREC、以及很多Web搜索引擎中最重要的指标之一。

40、互联网上有数不清的网页,当我们输入淘宝时候,怎么才能把taobao.com首页排在第一位呢?最基本的:计inlink的数量,但此方法容易受到spam的影响。

41、PageRank给予random surfer(随机游走模型),在90年代末期和200x年早起取得了不错的效果。具体公式不解释了,很多了。

求页面u的PageRank值

PR(u) = a/N + (1-a)/N * Sum(PR(v)/L(v)), v是所有指向u的页面,N是所有链接综述,a是随机游走模型参数。

此外,还有Dangling links等问题。

42、PageRank的缺点:查询无关(query independent),即一旦计算后,每个页面的PageRank就不会改变,无法适应不同的Query。

43、PageRank的另一个缺点:被广大SEO分析,形成了各种各样的作弊方法,已经很难反应真实链接关系情况了。

44、HITS算法:查询相关。

45、链接质量:如43所述,link spam很多。并且链接分析将每个页面的质量同等对待,这是不对的。例子:一个人写了一篇很精彩的Blog A,另一个人在自己的Blog引用A,称为B,然后B发了一个TraceBack给了A。这样的话,按照PageRank的理论,A和B就等同了。

46、解决上述问题的简单方法:定义<a href=”” rel=nofollow></a>这样,就不会把A页面分出去的权重交给B页面了。当然啦,是不能指望很多脑残的爬虫懂得nofollow的。

47、信息抽取:从文本中提取特定的结构信息,识别它们并用于辅助Ranking。例如命名实体识别、关系识别、事件识别等。

48、命名实体(named entities):描述特定人或事件的词或词组。

49、语义标注(semantic annotation):识别并标注命名实体的类型。

50、命名实体识别(named entity recognizers)的方式:基于规则、基于统计。规则的不多说了,需要专家领域知识。统计的一般基于隐式马尔科夫模型,需要大量的语料。而且语料需要人工标注,这个工作量比规则更多。。。

51、命名实体识别对于Web Search应用不太多,对于Q&A系统很重要。

52、跨语言检索(monolingual search engine):同时提供多种语言的支持,如Google。

53、跨语言检索主要在以下方面有区别,其他技术都一样:分词(对于CJK如中文)、Stemming(对俄语等很重要,中文没必要)、编码(都转换成UTF-8是好方法)。

54、此外,有一些语言说的人很多,但网山很少又这些语种的网页,称为低密度语言(low-density language),它们的检索是更大的一个挑战。

第四章完。

Leave a Reply

Your email address will not be published.