C/C++基础

C/C++基础 [都是极品学习资料]

C/C++基础
Windows C 程序设计入门与提高

http://download.chinaitlab.com/program/files/13246.html

单片机C语言入门

http://download.chinaitlab.com/program/files/12907.html

C++ 入门基础教程

http://download.chinaitlab.com/program/files/7617.html

C语言常用算法源代码

http://download.chinaitlab.com/program/files/12893.html

C常用算法程序集

http://download.chinaitlab.com/program/files/6225.html

C++ 语言命令详解

http://download.chinaitlab.com/program/files/4556.html

C语言编程要点

http://download.chinaitlab.com/program/files/11823.html

C语言编程基础

http://download.chinaitlab.com/program/files/11074.html

Borland c++使用手册

http://download.chinaitlab.com/program/files/4553.html

C语言数值算法程序大全(第二版)

http://download.chinaitlab.com/program/files/9247.html

Borland c++4.0安装与使用

http://download.chinaitlab.com/program/files/4546.html

C++ Builder 5.0经典入门

http://download.chinaitlab.com/program/files/4438.html

非C程序员C++入门自学教程

http://download.chinaitlab.com/program/files/3924.html

C语言常用函数手册

http://download.chinaitlab.com/program/files/1818.html

C++标准程序库自修教程与参考手册

http://download.chinaitlab.com/program/files/12644.html

C/C++指令字典

http://download.chinaitlab.com/program/files/13237.html

C语言图形函数介绍

http://download.chinaitlab.com/program/files/11643.html

C语言数值计算初步

http://download.chinaitlab.com/program/files/11640.html

C++Builder基础进阶

http://download.chinaitlab.com/program/files/6316.html

C++ 设计新思维

http://download.chinaitlab.com/program/files/6037.html

C++Builder英文帮助

http://download.chinaitlab.com/program/files/6315.html

C语言初学者入门讲座

http://download.chinaitlab.com/program/files/11641.html

C++完全参考手册

http://download.chinaitlab.com/program/files/9845.html

C游戏编程从入门到精通

http://download.chinaitlab.com/program/files/9253.html

《C++Builder学习大全》中文版

http://download.chinaitlab.com/program/files/2141.html

C++ Builder编程研究文档

http://download.chinaitlab.com/program/files/12888.html

C常用函数

http://download.chinaitlab.com/program/files/3867.html

C++程序调试实用手册

http://download.chinaitlab.com/program/files/6131.html

Borland c++4.0从入门到精通

http://download.chinaitlab.com/program/files/4592.html

实用教程
经典C语言教程

http://download.chinaitlab.com/program/files/12625.html

C++捷径教程(第三版)

http://download.chinaitlab.com/program/files/12591.html

Borland c++实用教材

http://download.chinaitlab.com/program/files/4552.html

嵌入式系统中C的开发

http://download.chinaitlab.com/program/files/6027.html

C++上机实践指导教程(第三版)

http://download.chinaitlab.com/program/files/11635.html

C++程序设

Share

数学之美 系列二 — 谈谈中文分词



谈谈中文分词
—– 统计语言模型在中文处理中的一个应用

上回我们谈到利用统计语言模型进行语言处理,由于模型是建立在词的基础上的,对于中日韩等语言,首先需要进行分词。例如把句子 “中国航天官员应邀到美国与太空总署官员开会。”

分成一串词:
中国 / 航天 / 官员 / 应邀 / 到 / 美国 / 与 / 太空 / 总署 / 官员 / 开会。

最容易想到的,也是最简单的分词办法就是查字典。这种方法最早是由北京航天航空大学的梁南元教授提出的。

用 “查字典” 法,其实就是我们把一个句子从左向右扫描一遍,遇到字典里有的词就标识出来,遇到复合词(比如 “上海大学”)就找最长的词匹配,遇到不认识的字串就分割成单字词,于是简单的分词就完成了。这种简单的分词方法完全能处理上面例子中的句子。八十年代, 哈工大的王晓龙博士把它理论化,发展成最少词数的分词理论,即一句话应该分成数量最少的词串。这种方法一个明显的不足是当遇到有二义性 (有双重理解意思)的分割时就无能为力了。比如,对短语 “发展中国家” 正确的分割是”发展-中-国家”,而从左向右查字典的办法会将它分割成”发展-中国-家”,显然是错了。另外,并非所有的最长匹配都一定是正确的。比如”上海大学城书店”的正确分词应该是 “上海-大学城-书店,” 而不是 “上海大学-城-书店”。

九十年代以前,海内外不少学者试图用一些文法规则来解决分词的二义性问题,都不是很成功。90年前后,清华大学的郭进博士用统计语言模型成功解决分词二义性问题,将汉语分词的错误率降低了一个数量级。

利用统计语言模型分词的方法,可以用几个数学公式简单概括如下:
我们假定一个句子S可以有几种分词方法,为了简单起见我们假定有以下三种:
A1, A2, A3, …, Ak,
B1, B2, B3, …, Bm
C1, C2, C3, …, Cn

其中,A1, A2, B1, B2, C1, C2 等等都是汉语的词。那么最好的一种分词方法应该保证分完词后这个句子出现的概率最大。也就是说如果 A1,A2,…, Ak 是最好的分法,那么 (P 表示概率):
P (A1, A2, A3, …, Ak) 〉 P (B1, B2, B3, …, Bm), 并且
P (A1, A2, A3, …, Ak) 〉 P(C1, C2, C3, …, Cn)
因此,只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概率,并找出其中概率最大的,我们就能够找到最好的分词方法。

当然,这里面有一个实现的技巧。如果我们穷举所有可能的分词方法并计算出每种可能性下句子的概率,那么计算量是相当大的。因此,我们可以把它看成是一个 动态规划(Dynamic Programming) 的问题,并利用 “维特比”(Viterbi) 算法快速地找到最佳分词。

在清华大学的郭进博士以后,海内外不少学者利用统计的方法,进一步完善中文分词。其中值得一提的是清华大学孙茂松教授和香港科技大学吴德凯教授的工作。

需要指出的是,语言学家对词语的定义不完全相同。比如说 “北京大学”,有人认为是一个词,而有人认为该分成两个词。一个折中的解决办法是在分词的同时,找到复合词的嵌套结构。在上面的例子中,如果一句话包含”北京大学”四个字,那么先把它当成一个四字词,然后再进一步找出细分词 “北京” 和 “大学”。这种方法是最早是郭进在 “Computational Linguistics” (《计算机语言学》)杂志上发表的,以后不少系统采用这种方法。

一般来讲,根据不同应用,汉语分词的颗粒度大小应该不同。比如,在机器翻译中,颗粒度应该大一些,”北京大学”就不能被分成两个词。而在语音识别中,”北京大学”一般是被分成两个词。因此,不同的应用,应该有不同的分词系统。Google 的葛显平博士和朱安博士,专门为搜索设计和实现了自己的分词系统。

也许你想不到,中文分词的方法也被应用到英语处理,主要是手写体识别中。因为在识别手写体时,单词之间的空格就不很清楚了。中文分词方法可以帮助判别英语单词的边界。其实,语言处理的许多数学方法通用的和具体的语言无关。在 Google 内,我们在设计语言处理的算法时,都会考虑它是否能很容易地适用于各种自然语言。这样,我们才能有效地支持上百种语言的搜索。

对中文分词有兴趣的读者,可以阅读以下文献:

1. 梁南元
书面汉语自动分词系统
http://www.touchwrite.com/demo/LiangNanyuan-JCIP-1987.pdf

2. 郭进
统计语言模型和汉语音字转换的一些新结果
http://www.touchwrite.com/demo/GuoJin-JCIP-1993.pdf

3. 郭进
Critical Tokenization and its Properties
http://acl.ldc.upenn.edu/J/J97/J97-4004.pdf

4. 孙茂松
Chinese word segmentation without using lexicon and hand-crafted training data
http://portal.acm.org/citation.cfm?coll=GUIDE&dl;=GUIDE&id;=980775

Share

数学之美 系列一 — 统计语言模型

系列一: 统计语言模型 (Statistical Language Models)

Google 的使命是整合全球的信息,所以我们一直致力于研究如何让机器对信息、语言做最好的理解和处理。长期以来,人类一直梦想着能让机器代替人来翻译语言、识别语音、认识文字(不论是印刷体或手写体)和进行海量文献的自动检索,这就需要让机器理解语言。但是人类的语言可以说是信息里最复杂最动态的一部分。为了解决这个问题,人们容易想到的办法就是让机器模拟人类进行学习 – 学习人类的语法、分析语句等等。尤其是在乔姆斯基(Noam Chomsky 有史以来最伟大的语言学家)提出 “形式语言” 以后,人们更坚定了利用语法规则的办法进行文字处理的信念。遗憾的是,几十年过去了,在计算机处理语言领域,基于这个语法规则的方法几乎毫无突破。

其实早在几十年前,数学家兼信息论的祖师爷 香农 (Claude Shannon)就提出了用数学的办法处理自然语言的想法。遗憾的是当时的计算机条件根本无法满足大量信息处理的需要,所以他这个想法当时并没有被人们重视。七十年代初,有了大规模集成电路的快速计算机后,香农的梦想才得以实现。

首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克 (Fred Jelinek)。当时贾里尼克在 IBM 公司做学术休假 (Sabbatical Leave),领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。

给大家举个例子:在很多涉及到自然语言处理的领域,如机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询中,我们都需要知道一个文字序列是否能构成一个大家能理解的句子,显示给使用者。对这个问题,我们可以用一个简单的统计模型来解决这个问题。

如果 S 表示一连串特定顺序排列的词 w1, w2,…, wn ,换句话说,S 可以表示某一个由一连串特定顺序排练的词而组成的一个有意义的句子。现在,机器对语言的识别从某种角度来说,就是想知道S在文本中出现的可能性,也就是数学上所说的S 的概率用 P(S) 来表示。利用条件概率的公式,S 这个序列出现的概率等于每一个词出现的概率相乘,于是P(S) 可展开为:

P(S) = P(w1)P(w2|w1)P(w3| w1 w2)…P(wn|w1 w2…wn-1)

其中 P (w1) 表示第一个词w1 出现的概率;P (w2|w1) 是在已知第一个词的前提下,第二个词出现的概率;以次类推。不难看出,到了词wn,它的出现概率取决于它前面所有词。从计算上来看,各种可能性太多,无法实现。因此我们假定任意一个词wi的出现概率只同它前面的词 wi-1 有关(即马尔可夫假设),于是问题就变得很简单了。现在,S 出现的概率就变为:

P(S) = P(w1)P(w2|w1)P(w3|w2)…P(wi|wi-1)…
(当然,也可以假设一个词又前面N-1个词决定,模型稍微复杂些。)

接下来的问题就是如何估计 P (wi|wi-1)。现在有了大量机读文本后,这个问题变得很简单,只要数一数这对词(wi-1,wi) 在统计的文本中出现了多少次,以及 wi-1 本身在同样的文本中前后相邻出现了多少次,然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。

也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是常人,就连很多语言学家都曾质疑过这种方法的有效性,但事实证明,统计语言模型比任何已知的借助某种规则的解决方法都有效。比如在 Google 的中英文自动翻译 中,用的最重要的就是这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测,Google 的系统是不仅是全世界最好的,而且高出所有基于规则的系统很多。

现在,读者也许已经能感受到数学的美妙之处了,它把一些复杂的问题变得如此的简单。当然,真正实现一个好的统计语言模型还有许多细节问题需要解决。贾里尼克和他的同事的贡献在于提出了统计语言模型,而且很漂亮地解决了所有的细节问题。十几年后,李开复用统计语言模型把 997 词语音识别的问题简化成了一个 20 词的识别问题,实现了有史以来第一次大词汇量非特定人连续语音的识别。

Share