最近接到一个项目，是关于信息抽取方面的，仔细分析下来，还真的是挺难的。对于现实的应用，如何选取一个最有效的数学模型，这个是非常考验算法功力的事情。因此，这几天把自己闷在家里，网也不上了，Blog也不读了，潜心研究信息抽取(Information Extraction)方面的算法。这其中，又把隐马尔可夫算法(HMM)好好地啃了一下。google china blog 上面有一篇文章《数学之美 系列三 — 隐含马尔可夫模型在语言处理中的应用》，比较经典地讲解了隐马尔可夫算法的应用，是一篇很好的文章。之前，我曾经比较系统地研究过《数学之美》系列的前几篇，还把这几篇放到了我的“每日一贴”栏目中，算是对自己学习的一个记录。虽然把这个栏目的名字定为“每日一贴”，但其实频率远达不到每日一贴。这些 文字不是自己写的，所以更需要咀嚼之后，才能真正地为我所用。如果仅仅就是“贴”一下的话，那还真没这个必要了，浪费时间。因此希望加入“每日一贴”的文 章，都能够真正地对自己有所帮助。
简单陈列一下信息抽取的三大类方法。
- 基于规则的方法。这个方法解决特定的问题效果比较好，但同时它对被提取信息的要求也比较苛刻。此方法主要基于规则库进行信息抽取，因此，规则库的质量直接绝对了算法的召回率和准确率。通常情况下，尤其是应用在商业项目中，要想编制一个高质量的规则库是不经济的。项目起始不能将此方法作为核心，待有了足够的数据积累之后，通过制作训练模型和算法，可以对整个项目的质量有一定程度的提升。
- 隐马尔可夫方法。这是经典的信息抽取算法。但它要求信息源的内容之间是有顺序关联的，即，要求数据的排列是有逻辑关系的。对于内容之间相互独立的信息，它的效果不是很好。非常不幸，我这个项目的数据源这是如此。它的内容是分段的，对于这些段落中国人有习惯顺序，但这种习惯顺序并不能抽象化成逻辑关系，因此不适合使用应马尔可夫算法。
- 基于文本分类的方面。这种方法利用信息之间的独立假设，使用分类算法抽取信息，适用于处理出现次序相互独立信息的抽取问题。配合质量比较高的中文分词算法，信息抽取的精确率与召回率较高。我要做的项目准备以此方法为核心算法。
最近在作一个搜索引擎相关的项目，不说大家也清楚肯定是基于Lucene进行开发的，站在前人的肩膀上啊，呵呵！熟悉Lucene的人都知道， Lucene中并没有很好的中文分词实现，本人目前已经完成了中文分词部分的功能，初步测试效果还不错。围绕中文分词的讨论已经不少了，但通过这次实际的 开发，本人确实还是有了一些自己的体会，本打算就这方面写一篇博文，没想到今天突然发现，自己的合作伙伴已经写了一篇，细读了一下，感觉自己想要说的，他 都提到了，因此，转载了过来。
以下为转载内容，《小议分词》，勇者之心，http://leaphy.cnblogs.com/archive/2006/07/06/Segment.html。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
全文信息检索系统中，创建倒排索引时应当使用什么分词方式一直是众说纷纭，毫无定论。
具我所知，已有某某 paper “研究指出”采用二元切分的方式构建索引是“最好的”；也看到过园子里的一位兄弟认为单字切分最准确（sorry，忘记具体出处）；当然，将某个基于词典或者共现频率的中文分词组件包装一下加入自己的项目中也是非常流行的做法。
既然存在这么多的看法与做法，难免会让人生出一较高下或者明辨真伪的决心；
不过作为一个成熟而又理智的热血青年，偶认为这种决心并无必要，原因在于信息检索系统的评价标准是多样化的——召回率、准确率与查询效率三个指标相互矛 盾，只有取舍、不能调和；人们关心的指标不尽相同自然会提出不同的观点、奉行不同的做法。假设你在做一个Web搜索引擎，首先要保证的一定是查询效率，因 为它所要处理的海量数据与并发请求是一种天然的障碍；其次，在召回率与准确率中你会更倾向于后者，因为最终用户与Web搜索引擎的关系恰如负心男人与痴情 女人的关系——用户希望尽快得到最满意的结果，并在下一个瞬间把你抛弃，直到他们再次需要你为止（当然，如果你提供了代号为 Good Morni 的竞价排名服务，为了不致客户投诉，最好还是关心一下召回率。所以说，广大小白和一小撮VIP之间的利益冲突是深刻、长远以及不可调和的。。。）；同时， 对于一个传统的图书信息检索系统，情况会大不相同——书籍与文章有良好的关键字索引，包括标题、作者、摘要、正文、收录时间等定义明确的结构化数据，文档 集合相对稳定并且规模相对较小——这一切都使你的决策更倾向于提高系统的召回率，原因很简单，你有这么做的可能性或者说是先天优势。
既然我们已经明确评价信息检索系统的指标是多元化的，现在让我们来看看不同的索引分词策略到底如何影响这些指标。
首先让我们来比较两个对立的策略，单字切分 vs 中文分词：
单字切分的支持者们最强有力的证据大概如下：
“世界杯”是一个词，用单字切分的话，查“世界”也可以命中这篇文档，而用中文分词就查不到了；
而中文分词的支持者们的反驳大概是：
“参加过世界杯”，用单字切分的话，查“过世”也可以命中这篇文档，但事实上并没有人挂掉；
通过以上陈述我们可以观察得到这样的结论，采用单字切分会提高系统的召回率，而降低准确率；而中文分词则恰恰相反，它提高了准确率，并降低的召回率，并且分词的颗粒越粗糙（平均词长越长）这种趋势就越明显。
这个结论似乎有助于理解为什么 google、百度等等这些理论上更需要高准确率的Web搜索引擎都采用了中文分词技术。但是如果我们的认识仅停留在这种水平就未免显得过于肤浅：事实情况是，需要高吞吐量的Web搜索引擎在处理中文内容时必须采用中文分词技术。
让我们把倒排索引想象成一张表，其中每一行都有一个TermText以及所有包含该TermText的文档编号列表。这样在我们查询某个关键字时，可以一 次性获得所有包含该关键字的文档，而不用在原始文档集合中逐一查找。 而采用不同的分词策略创建索引，事实上既是将文档编号集合以不同的程度打散到索引中不同的行。单字切分可以说是打散程度最低的一种方式，行数仅等于汉字数 目，而整个倒排索引表会非常的“宽”；相反，颗粒较粗的中文分词将文档编号集合分配到更多的不同行，使得倒排索引表的宽度变小。并且随着分词粒度的增加宽 度会逐渐减小，最极端的情况就是将每一篇文档看作一个“词”，此时倒排索引表的宽度处处等于1。
基于以上讨论，我们看出以下两点：
一、在文档集合数量非常庞大时，系统的吞吐量会受到存储倒排索引文件的磁盘的性能限制，因此，采用中文分词，缩短倒排索引表的宽度将有助于提高系统的吞吐量。
二、无论使用布尔查询或者是基于位置信息的查询（如 Lucene 中的 PhraseQuery）单字切分的单词查询性能不会好于中文分词。
这样看来，在Web搜索引擎中使用中文分词就不是一件难以理解的事情了；同样，在文档规模较小时，使用单字切分的策略也不会有什么重大问题。
至于二元切分，在偶看来，这种方法试图以一种战场外科手术的粗犷气质实现中庸之道的思想，单字切分与中文分词之间形成了一种在某些方面不尽人意的折中（歧 义、无意义的二元组等）。在实现上它更接近单字切分，而非中文分词。按照偶滴设想，如果实现一种对标准意义的中文分词策略的改进，使其能够在一定程度上缓 解中文分词降低召回率的问题，也许会成为一种在各方面都更加平衡的解决方案。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
因为本次做的是一个商业项目，因此不能公布源代码以及相关的技术文档。但稍后会放出本人实现的中文分词算法所依据的一篇论文，并就其中的一些问题进行讨论。有兴趣的朋友欢迎讨论，wendell.gu@gmail.com。
