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)，它们的检索是更大的一个挑战。

第四章完。