分词又叫,切词,划词等 我感觉是seo中应该仔细学好的技术。
我有个实验站1000左右ip的站，首页是按照分词写的，每天可以在
百度得到100~200的ip 效果还是很明显的。
网上这类详细讲解的文章比较少 我找了几篇转过来，大家可以学下看。
---------------------------------------------------------
查询处理以及分词技术
随着搜索经济的崛起，人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业，会根据搜索引擎的知名度以及日流量来选择是否要投放广告等；作为普通网民，会根据搜索引擎的性能和技术来选择自己喜欢的引擎查找资料；作为技术人员，会把有代表性的搜索引擎作为研究对象. 搜索引擎经济的崛起，又一次向人们证明了网络所蕴藏的巨大商机。网络离开了搜索将只剩下空洞杂乱的数据，以及大量等待去费力挖掘的金矿。
但是,如何设计一个高效的搜索引擎?我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎.搜索引擎涉及到许多技术点,比如查询处理,排序算法,页面抓取算法,CACHE机制,ANTI-SPAM等等.这些技术细节,作为商业公司的搜索引擎服务提供商比如百度,GOOGLE等是不会公之于众的.我们可以将现有的搜索引擎看作一个黑盒,通过向黑盒提交输入,判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节.
查询处理与分词是一个中文搜索引擎必不可少的工作,而百度作为一个典型的中文搜索引擎一直强调其”中文处理”方面具有其它搜索引擎所不具有的关键技术和优势.那么我们就来看看百度到底采用了哪些所谓的核心技术.
我们分两个部分来讲述:查询处理/中文分词.
一. 查询处理
用户向搜索引擎提交查询,搜索引擎一般在接受到用户查询后要做一些处理,然后在索引数据库里面提取相关的信息.那么百度在接受到用户查询后做了些什么工作呢?
1. 假设用户提交了不只一个查询串,比如”信息检索 理论 工具”.那么搜索引擎首先做的是根据分隔符比如空格,标点符号,将查询串分割成若干子查询串,比如上面的查询就会被解析为:<信息检索,理论,工具>三个子字符串;这个道理简单,我们接着往下看.
2. 假设提交的查询有重复的内容,搜索引擎怎么处理呢?比如查询”理论 工具 理论”,百度是将重复的字符串当作只出现过一次,也就是处理成等价的”理论 工具”,而GOOGLE显然是没有进行归并,而是将重复查询子串的权重增大进行处理.那么是如何得出这个结论的呢?我们可以将”理论 工具”提交给百度,返回341,000篇文档,大致看看第一页的返回内容.OK.继续,我们提交查询”理论 工具 理论”,在看看返回结果,仍然是那么多返回文档,当然这个不能说明太多问题,那看看第一页返回结果的排序,看出来了吗?顺序完全没有变化,而GOOGLE则排序有些变动,这说明百度是将重复的查询归并成一个处理的,而且字符串之间的先后出现顺序基本不予考虑(GOOGLE是考虑了这个顺序关系的).
3. 假设提交的中文查询包含英文单词,搜索引擎是怎么处理的?比如查询”电影BT下载”,百度的方法是将中文字符串中的英文当作一个整体保留,并以此为断点将中文切分开,这样上述的查询就切为<电影,BT,下载>,不论中间的英文是否一个字典里能查到的单词也好,还是随机的字符也好,都会当作一个整体来对待.至于为什么,你用查询” 电影dfdfdf下载”看看结果就知道了.当然如果查询中包含数字,也是如此办理.
到目前为止,一切很简单,也很清楚,百度怎么处理用户查询的呢?归纳如下:首先根据分割符号将查询分开,然后看看是否有重复的字符串,如果有,就抛弃多余的,只保留一个,接着判断是否有英文或者数字,如果有的话,把英文或者数字当作一个整体保留并把前后的中文切开.
接着该干什么呢?该考虑分词的问题了.
二. 中文分词
首先,讲讲百度的分词时机或者条件问题,是否是个中文字符串百度就拿来切一下呢?非也,要想被百度的分词程序荣幸的切割一下也是要讲条件的,哪能是个字符串就切割啊?你当百度是卖锯条的么?
那么什么样的字符串才满足被切割的条件呢?简单说来,如果字符串只包含小于等于3个中文字符的话,那就保留不动,当字符串长度大于4个中文字符的时候,百度的分词程序才出马大干快上,把这个字符串肢解掉.
怎么证明呢?我们向百度提交”电影下载”,看看返回结果中标为红字的地方,不难看出来,查询已经被切割成<电影,下载>两个单词了,说明分词程序已经开工了,如果是比4个中文字符更长的字符串,那分词程序就更不客气了,一定大卸八块而后快.我们来看看三个字符的情况,提交查询”当然择”,看起来这个查询不伦不类,那是因为我希望看到这个字符串被切分为<当然,择>,返回结果365篇相关页面,翻到最后一页,发现标红的关键字都是”当然择”连续出现的情况,好像没有切分,但是还不确定,那么再提交人工分好的查询”当然 择”看看,返回结果1,090,000篇,基本上可以确定没有进行分词了,当然另外一种解释是:对于三个字符先切分,然后将切分后的结果当作一个短语查询,这样看到的效果和没有切分是相似的.但是我倾向于判断百度对于少于3个字符的串没有切分,奥卡姆不是说了么”如无必要,勿增实体”,干吗做无用功呢.那么如果没有切分,会有一个随之而来的问题,怎么从索引库里面提取未切分的字符串呢?这牵扯到索引的问题,我觉得百度应该采取了两套索引机制,一种是按照单词索引,一种是按照N-GRAM索引,至于索引的具体问题,以后在详细论述.
下面我们看看百度是采取的何种分词算法,现在分词算法已经算是比较成熟了,有简单的有复杂的,比如正向最大匹配,反向最大匹配,双向最大匹配,语言模型方法,最短路径算法等等,有兴趣的可以用GOOGLE去搜索一下以增加理解.这里就不展开说了.但是要记住一点的是:判断一个分词系统好不好,关键看两点,一个是消除歧义能力;一个是词典未登录词的识别比如人名,地名,机构名等.
那么百度用的是什么方法?我的判断是用双向最大匹配算法.至于怎么推理得出的,让我们一步步来看.当然,这里首先有个假设,百度不会采取比较复杂的算法,因为考虑到速度问题.
我们提交一个查询”***北京华烟云”,又一个不知所云的查询,尽管不知所云但是自有它的道理,我想看看百度的分词是如何消歧以及是否有词典未登录词的识别的功能,如果是正向最大匹配算法的话,那么输出应该是:”***/北京/华/烟云”,如果是反向最大匹配算法的话,那么输出应该是:”毛/泽/东北/京华烟云”,我们看看百度的分词结果:”***/北/京华烟云”,一个很奇怪的输出,跟我们的期望相差较多,但是从中我们可以获得如下信息:百度分词可以识别人名,也可以识别”京华烟云”,这说明有词典未登录词的识别的功能,我们可以假设分词过程分为两个阶段:第一阶段,先查找一个特殊词典,这个词典包含一些人名,部分地名以及一些普通词典没有的新词,这样首先将”***”解析出来,剩下了字符串”北京华烟云”,而”北/京华烟云”,可以看作是反向最大匹配的分词结果.这样基本说得通.为了证明这一点,我们提交查询”发***北”,我们期望两种分词结果,一个是正向最大匹配<发毛,泽,东北>,一个是上述假设的结果<发,***,北>,事实上百度输出是第二种情况,这样基本能确定百度分词采取了至少两个词典,一个是普通词典,一个是专用词典(人名等).而且是专用词典先切分,然后将剩余的片断交由普通词典来切分.
继续测验,提交查询”古巴比伦理”,如果是正向最大匹配,那么结果应该是<古巴比伦,理>,如果是反向最大匹配,那么结果应该是<古巴,比,伦理>,事实上百度的分词结果是<古巴比伦,理>,从这个例子看,好像用了正向最大匹配算法;此外还有一些例子表明好像是使用正向最大匹配的;但是且慢,我们看这个查询”北京华烟云”,正向最大匹配期望的结果是<北京,华,烟云>,而反向最大匹配期望的结果是<北,京华烟云>,事实上百度输出的是后者,这说明可能采用的反向最大匹配;从这点我们可以猜测百度采用的是双向最大匹配分词算法,如果正向和反向匹配分词结果一致当然好办,直接输出即可;但是如果两者不一致,正向匹配一种结果,反向匹配一种结果,此时该如何是好呢?从上面两个例子看,在这种情况下,百度采取最短路径方法,也就是切分的片断越少越好,比如<古巴,比,伦理>和<古巴比伦,理>相比选择后者,<北京,华,烟云>和<北,京华烟云>相比选择后者.还有类似的一些例子,这样基本可以解释这些输出结果.
但是仍然遗留的问题是:如果正向反向分词不一致,而且最短路径也相同,那怎么办?输出正向的还是反向的结果?我们再来看一个例子.提交查询”遥远古古巴比伦”,这个查询被百度切分为<遥远,古古,巴比伦>,说明词典里面有”巴比伦”,但是是否有”古巴比伦”这个词汇不确定,此时看不出是正向切分还是反向切分得出的结果,换查询为”遥远古巴比伦”,此时被切分为”遥远/古巴比伦”,这说明词典里面有”古巴比伦”这个词汇,这说明了”遥远古古巴比伦”是正向最大匹配的结果.那为什么”遥远古古巴比伦”不会被反向切分为”遥/远古/古巴比伦”呢,百度的可能选择是这种情况下选择单字少的那组切分结果.
当然还可以继续追问:如果切分后单字也一样多,那怎么办?最后看一个例子,查询”王强大小:”,百度将其切分为”王/强大/小”,是正向切分的结果,如果是反向的会被切分为”王/强/大小”,这说明有歧义而且单字也相同则选择正向切分结果.
OK,看到这里可能头已经有些晕了,最后总结一下百度的分词算法,当然里面还是有猜测的成分,算法如下:
首先查询专用词典(人名,部分地名等),将专有名称切出,剩下的部分采取双向分词策略,如果两者切分结果相同,说明没有歧义,直接输出分词结果.如果不一致,则输出最短路径的那个结果,如果长度相同,则选择单字词少的那一组切分结果.如果单字也相同,则选择正向分词结果..
百度一直宣传自己在中文处理方面的优势,从上面看,分词算法并无特殊之处,消歧效果并不理想,即使百度采取比上述分词算法复杂些的算法也难以说成是优势,如果说百度有优势的话,唯一的优势就是那个很大的专用词典,这个专用词典登录了人名(比如大长今),称谓(比如老太太),部分地名(比如阿联酋等),估计百度采用学术界公布的比较新的命名实体识别算法从语料库里面不断识别出词典未登录词,逐渐扩充这个专门词典.如果这就是优势的话,那么这个优势能够保持多久就是个很明显的问题.
baidu分词算法分析之二
版主实习中，争取转正。大家多多支持 ：）
------------------------------------------------------------
接《百度分词算法分析一》
Spelling Checker拼写检查错误提示(以及拼音提示功能)
拼写检查错误提示是搜索引擎都具备的一个功能,也就是说用户提交查询 给搜索引擎,搜索引擎检查看是否用户输入的拼写有错误,对于中文用户来说一般造成的错误是输入法造成的错误.那么我们就来分析看看百度是 怎么实现这一功能的.
我们分析拼写检查系统关注以下几个问题:
(1)系统如何判断用户的输入是有可能发生错误的查询呢?
(2)如果判断是可能错误的查询输入,如何提示正确的词汇呢?
那么百度是如何做的呢?百度判断用户输入是否错误的 标准,我觉得应该是查字典,如果发现字典里面不包含这个词汇,那么很有可能是个错误的输入,此时启动错误提示功能,这个很好判断,因为如果 是一个正常词汇的话,百度一般不会有错误提示,而你故意输入一个词典不可能包含的所谓词汇,此时百度一般会提示你正确的检索词汇.
那么百度是怎么提示正确词汇的呢?很明显是通过拼音的方式,比如我输入查询" 制才",百度提供的提示词汇为: “:制裁 质材 纸材",都是同 音字.所以百度必然维持着一个同音词词典,里面保留着同音词信息,比如可能包含着下面这条词条: “ zhi cai à制裁,质材,纸材",另外还有一 个标注拼音程序,现在能够看到的基本流程是: 用户输入" 制才",查词典,发现没有这个词汇,OK,启动标注拼音程序,将" 制才"标注为拼音"zhi cai",然后查找同音词词典,发现同音词" 制裁,质材,纸材",那么提示用户可能的正确拼写.
整体流程看起来很简单,但是还有一些遗留 的小问题,比如是否将词表里面所有同音词都作为用户的提示信息呢?比如某个拼音有10个同音词,是否都输出呢?百度并没有将所有同音词都输 出而是选择一定筛选标准,选择其中几个输出.怎么证明这一点?我们看看拼音"liu li"的同音词,紫光输入法提示同音词汇有" 流丽 流离 琉璃 流利"4个,我们看看百度返回几个,输入"流厉"作为查询,这里是故意输入一个词典不包含的词汇,这样百度的拼写检查才开始工作,百度提示: " 琉璃刘丽 刘莉 ",这说明什么?说明不是所有同音词都输出,而是选择输出,那么选择的标准是什么?我能够猜测到的方法是对于用户查询LOG进行 统计,提取用户查询次数多的那些同音词输出,如果是这样的话,上面的例子说明用户搜索"琉璃"次数比其它的都要高些,次之是" 刘丽",再次是" 刘莉",看来大家都喜欢查询自己或者认识的人的名字.
另外一个小问题:同音词词典包含2字词,3字词,那么是否包含4字词以及更长的词 条?是否包含一字词? 这里一字词好回答,不用测试也能知道肯定不包含,因为你输入一个字,谁知道是否是错误的呢?反正只要是汉字就能在词表 里面找到,所以没有判断依据.二字词是包含的,上面有例子,三字词也包含,比如查询 "中城药"百度错误提示:"中成药",修改查询为"重城药",还 是提示"中成药" ,再次修改查询 "重城要",百度依然提示"中成药". 那么4字词汇呢?
百度还是会给你提示的,下面是个例子:
输入:静华烟云 提示 京华烟云
输入:静话烟云 提示 京华烟云
输入:静话阎晕 提示 京华烟云
那么更长的词汇是否提 示呢?也提示,比如我输入: "落花世界有风军",这个查询是什么意思,估计读过古诗的都知道,看看百度的提示"落花时节又逢君",这说明什么?说 明同音词词典包含不同长度的同音词信息,另外也说明了百度的核心中文处理技术,也就是那个词典,还真挺大的.
但是,如果用户输入的 查询由两个或者两个以上子字符串构成,那么百度的错误提示功能就罢工了,比如输入查询"哀体",百度提示"艾提 挨踢",但是.输入为 "我 哀体 ",则没有任何错误提示.
还有一个比较重要的问题:如果汉字是多音字那么怎么处理?百度呢比较偷懒,它根本就没有对多音字做处理.我 们来看看百度的一个标注拼音的错误,在看这个错误前先看看对于多音字百度是怎么提示错误的,我们输入查询"俱长",百度提示"剧场 局长", “俱长"的拼音有两个:"ju zhang /ju chang" ,可见如果是多音字则几种情况都提示..现在我们来看看错误的情况, 我们输入查询"剧常",百度 提示":剧场局长",提示为"剧场"当然好解释,因为是同音字,但是为什么 "局长"也会被提示呢?这说明百度的同音字词典有错误,说明在"ju chang"这个词条里面包含"局长"这个错误的同音词.让我们顺藤摸瓜,这个错误又说明什么问题呢?说明百度的同音词典是自动生成的,而且没有 人工校对.还说明在自动生成同音词典的过程中,百度不是根据对一篇文章标注拼音然后在抽取词汇和对应的拼音信息获得的,而是完全按照某个 词典的词条来标注音节的,所以对于多音字造成的错误无法识别出来,如果是对篇章进行拼音标注,可能就不会出现这种很容易发现的错误标注. 当然还有另外一种解释,就是"局长"是故意被百度提示出来可能的正确提示词汇,因为考虑到南方人"zh"和 "ch"等前后鼻音分不清么,那么是这 样的么?我们继续测试到底是何种情况.是百度有错误还是这是百度的先进的算法?
我们考虑词汇"长大 ",故意错误输入为"赃大",如果 百度考虑到了前后鼻音的问题,那么应该会提示"长大",但是百度提示是"藏大".这说明什么?说明百度并没有考虑前后鼻音问题,根本就是系统错 误. 我们输入查询"悬赏",故意将之错误输入为"悬桑",没有错误提示,说明确实没有考虑这种情况.前鼻音没有考虑,那么后鼻音考虑了么,我们 输入":经常",故意改为后鼻音 "经缠",百度提示为"经产 经忏",还是没有考虑后鼻音.这基本可以确定是百度系统的错误导致.
根据以 上推导, 我们可以得出如下结论:百度是将分词词典里面每个词条利用拼音标注程序标注成拼音,然后形成同音词词典,所以两个词典是同样大的 ,而且这个词典也随着分词词典的增长而在不断增长. 至于标注过程中多音字百度没有考虑,如果是多音字就标注成多个发音组合,通过这种方式 形成同音词词典.这样的同音词词典显然包含着很多错误.
最后一个问题:百度对于英文进行拼写检查么?让我们试试看,输入查 询"china",不错,搜到不少结果,专注中文搜索的百度还能搜索到英文,真是意外的惊喜.变换一下查询"chine",会更加意外惊喜的给我们提 示"china"吗?百度提示的是: 吃呢持呢,原来是不小心触发了百度的拼音搜索功能了.那么拼音搜索和中文检查错误是否采用同一套同音词词典 呢,让我们来实验一下,搜索"rongji",百度提示" 榕基 溶剂 容积",OK,换个中文查询"容机",百度提示" 榕基 溶剂容积",看来使用的是同一套 同音词词典.也就是说百度的中文纠错和拼音检索使用的机制相同,中文纠错多了一道拼音注音的过程而已.难道这就是传说中那个百度的"事实 上是一个无比强大的拼音输入法"的拼音提示功能么?
最后让我们总结归纳一下百度的拼写检查系统:
后台作业: (1)前面的文 章我们说过,百度分词使用的词典至少包含两个词典一个是普通词典,另外一个是专用词典(专名等),百度利用拼音标注程序依次扫描所有词典中 的每个词条,然后标注拼音,如果是多音字则把多个音都标上,比如"长大",会被标注为"zhang da/chang da"两个词条.
(2)通过标注完的 词条,建立同音词词典,比如上面的"长大",会有两个词条: zhang daà长大" , chang daà长大.
(3)利用用户查询LOG频率信息给予每个 中文词条一个权重;
(4)OK,同音词词典建立完成了,当然随着分词词典的逐步扩大,同音词词典也跟着同步扩大;
拼写 检查:
(1)用户输入查询,如果是多个子字符串,不作拼写检查;
(2)对于用户查询,先查分词词典,如果发现有这个单词词条,OK, 不作拼写检查;
(3)如果发现词典里面不包含用户查询,启动拼写检查系统;首先利用拼音标注程序对用户输入进行拼音标注;
(4)对于标注好的拼音在同音词词典里面扫描,如果没有发现则不作任何提示;
(5)如果发现有词条,则按照顺序输出权重比较大的几个提 示结果;
拼音提示:
(1)对于用户输入的拼音在同音词词典里面扫描,如果没有发现则不作任何提示;
(2)如果 发现有词条,则按照顺序输出权重比较大的几个提示结果;
baidu分词算法分析之三
分词系列最后一章
------------------
之三:对百度分词算法的进一步分析
上面说过,经过分析得出百度的分词系统采用双向最大匹配分词,但是后来发现推理过程中存在一个漏洞,而且推导出来的百度分词算法步骤还是过于繁琐,所以进一步进行分析,看看是否前面的推导有错误.
那么以前的分析有什么漏洞呢?我们推导百度分词有反向最大匹配的依据是百度将"北京华烟云"分词为<北,京华烟云>,从这里看好像采用了反向最大匹配,因为正向最大匹配的结果应该是<北京,华,烟云>,但是由此就推论说百度采用了双向最大匹配还是太仓促了,前面文章我们也讲过,百度有两个词典,一个普通词典,一个专有词典,而且是专有词典的词汇先切分,然后将剩余片断交给普通词典去切分.所以上面的"北京华烟云"之所以被切分成<北,京华烟云>,另外一个可能是:京华烟云这个词汇是在专有词典里面存储的,所以先分析,这样得出"京华烟云",剩下"北",没什么好切分的,所以输出<北,京华烟云>.
这里只是假设,那么是否确实"京华烟云"在专有词典呢?我们再看一个例子"山东北京华烟云",百度切分的结果是<山东,北,京华烟云>,如果"京华烟云"在普通词典,如果是反向切分,那么结果应该是<山,东北,京华烟云>,如果是正向切分应该是<山东,北京,华,烟云>,无论如何都分不出<山东,北,京华烟云>.这说明什么?说明"京华烟云"是在那个专有词典,所以先切分出"京华烟云",然后剩下的"山东北"交由普通词典切分,明显是正向最大匹配的结果输出<山东,北>.当然按照我们在第一篇文章的算法推导"山东北"的切分也会得出<山东,北>的结论,但是明显比正向最大匹配多几个判断步骤,既然效果一样,另外一个更加简洁的方法也能说得通,那当然选择简便的方法了.所以初步判断百度采取的是正向最大匹配.
我们继续测试采用何种分词算法,为了减少专有词典首先分词造成的影响,那么查询里面不能出现相对特殊的词汇,构筑查询"天才能量级",这里应该没有专有词典出现过的词汇,百度切分为<天才,能量,级>,看来是正向最大匹配的结果.另外,如果所有查询词汇都出现在专有词典,那么采取的是何种方法?这样首先就得保证词汇都出现在专有词典,这么保证这一点呢?我们构造查询"铺陈晓东方",百度切分为<铺,陈晓东,方>,可以看出"陈晓东"是在专有词典的所以先切分出来.另外一个例子 "山东京城",百度切分为<山东,京城>,说明"东京"是在普通词典的.OK,构造查询"陈晓东京华烟云",通过前面分析可以看出两个词汇都在专有词典里面,百度切分为<陈晓东,京华烟云>,说明对于专有词典词汇也是采取正向最大匹配或者双向最大匹配.那么使用反向最大匹配了吗?构造查询例子"陈晓东方不败",首先我们肯定"陈晓东"和"东方不败"都是在专有词典出现的,如果是正向切分,那么应该是<陈晓东,方,不败>或者<陈晓东,方,不,败>如果是反向切分则是<陈,晓,东方不败>,可以看出百度的切分是<陈晓东,方,不败>或者<陈晓东,方,不,败>,说明采用的是正向最大匹配.通过分析,百度的词典不包含"不败"这个单词,所以实际上百度的切分结果是<陈晓东,方,不,败>,很明显这和我们以前推导的算法是有矛盾的,所以以前的分析算法确实有问题,所以结论是百度采取的是正向最大匹配算法.
重新归纳一下百度的分词系统:首先用专有词典采用最大正向匹配分词,切分出部分结果,剩余没有切分交给普通词典,同样采取正向最大匹配分词,最后输出结果.
另外,GOOGLE也是采用正向最大匹配分词算法,不过好像没有那个专用词典,所以很多专名都被切碎了.
从这点讲,GOOGLE在中文词典构建上比百度差些,还需要加把子力气才行,不过这也不是什么多难的事.
2010年4月3日星期六
Cygwin 使用
Using MinGW-w64 for 64bit applications on 64bit Windows.
1. 前言
使用 MinGW-w64 的工具與程式庫來編寫 64 位元程式，只要透過 Cygwin 其實非常簡單。
但如前文所述，Cygwin 目前只能編譯 32 位元的程式，使用的是 GCC 3.4.4 的版本，編譯的概念是 MinGW 與 Cygwin 程式庫二選一。
這裡要做的，則是將 Cygwin ，MinGW，MinGW-w64 視為不同的平台，以 cross compiler 的概念來進行編譯，分為三個步驟。
第一，重新安裝 Cygwin 的GCC為 4.3.4版本，可以呼叫 POSIX API 與 Windows API，但是執行時需要 cygwin1.dll。
第二，安裝 MinGW 來編譯 32 位元程式，編譯出來的是一般 Windows 32位元執行檔。
第三，安裝 MinGW-w64 來編譯 64 位元程式，編譯出來的是一般 Windows 64位元執行檔。
2. 重新安裝 Cygwin
要更新 Cygwin 的 GCC 為 4.3.4 版本，直接移除 c:\cygwin 這個目錄比較快，但是記得備份 c:\cygwin\home\Administrator 目錄下的檔案。
安裝的過程，請參考前文，到了套件選擇的步驟時，選擇 file, gcc4-core， gcc4-g++, make, vim 。
安裝完成後，進入 bash 輸入：
$ cc -v
Using built-in specs.
Target: i686-pc-cygwin
Configured with: /gnu/gcc/releases/packaging/4.3.4-3/gcc4-4.3.4-3/src/gcc-4.3.4/
configure --srcdir=/gnu/gcc/releases/packaging/4.3.4-3/gcc4-4.3.4-3/src/gcc-4.3.
4 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin --sbindir=/usr/sbin
(略)
Thread model: posix
gcc version 4.3.4 20090804 (release) 1 (GCC)
可知這次 GCC 版本為 4.3.4， 編譯目標為 i686-pc-cygwin。
以 a.c 為例，編譯出來的檔案，可以使用 file 來測試， 輸入：
$ file a.exe
a.exe: PE32 executable for MS Windows (console) Intel 80386 32-bit
可知為 PE 格式執行檔，但在檔案管理員中點選執行時，會產生找不到 cygwin1.dll 的錯誤，原因如前文所述。
另外，可以使用 objdump 反組譯來查看， 輸入：
$ objdump -d a.exe | grep '%esp,%ebp'
401001: 89 e5 mov %esp,%ebp
(略)
可知使用的是 32 位元暫存器。
這時候，如果要使用 -mno-cygwin 是不行的, 以 b.c 為例：
$ cc -o b b.c -mno-cygwin -mwindows
cc: The -mno-cygwin flag has been removed; use a mingw-targeted cross-compiler.
3. 安裝 MinGW
接下來到 http://mingw-w64.sourceforge.net/ 下載 mingw-w64-bin_i686-mingw_20100123_sezero.zip ，將壓縮檔內的 mingw32 目錄解壓縮到 c:\目錄內， 然後在 bash 內 輸入：
$ ln -s /cygdrive/c/mingw32 /mingw32
這個步驟讓我們能夠使用 /mingw32/bin/gcc 來進行編譯，輸入：
$ /mingw32/bin/gcc -v
Using built-in specs.
Target: i686-w64-mingw32
Configured with: ../gcc44-svn/configure --target=i686-w64-mingw32 --host=i686-w6
4-mingw32 --disable-multilib --disable-nls --disable-win32-registry --prefix=/mi
ngw32 --with-sysroot=/mingw32 --with-gmp=/mingw32 --with-mpfr=/mingw32 --enable-
languages=c,c++
Thread model: win32
gcc version 4.4.3 (GCC)
可知編譯目標為 i686-w64-mingw32。
以檔案 b.c 為例，輸入：
$ /mingw32/bin/gcc -o b b.c -mwindows
完成編譯後，以使用 file 來測試， 輸入：
$ file b.exe
b.exe: PE32 executable for MS Windows (GUI) Intel 80386 32-bit
可知為 32 位元 PE 執行檔。
使用 objdump 反組譯來查看， 輸入：
$ /mingw32/bin/objdump -d b.exe | grep '%esp,%ebp'
401001: 89 e5 mov %esp,%ebp
(略)
可知使用的是 32 位元暫存器。
4. 安裝 MinGW-w64
接下來到 http://mingw-w64.sourceforge.net/ 下載 mingw-w64-bin_x86_64-mingw_20100123_sezero.zip ，將壓縮檔內的 mingw64目錄解壓縮到 c:\目錄內。
製作 /mingw64 連結, 在 bash 內 輸入：
$ ln -s /cygdrive/c/mingw64 /mingw64
這個步驟讓我們能夠使用 /mingw/mingw64/bin/gcc 來進行編譯，輸入：
$ /mingw64/bin/gcc -v
Using built-in specs.
Target: x86_64-w64-mingw32
Configured with: ../gcc44-svn/configure --target=x86_64-w64-mingw32 --host=x86_6
4-w64-mingw32 --disable-multilib --disable-nls --disable-win32-registry --prefix
=/mingw64 --with-sysroot=/mingw64 --with-gmp=/mingw64 --with-mpfr=/mingw64 --ena
ble-languages=c,c++
Thread model: win32
gcc version 4.4.3 (GCC)
可知編譯目標為 x86_64-w64-mingw32。
以檔案 b.c 為例，輸入：
$ /mingw64/bin/gcc -o b b.c -mwindows
完成編譯後，以使用 file 來測試， 輸入：
$ file b.exe
b.exe: PE32+ executable for MS Windows (GUI)
可知為 64 位元 PE 執行檔。
使用 objdump 反組譯來查看， 輸入：
$ /mingw64/bin/objdump -d b.exe|grep '%rsp,%rbp'
401731: 48 89 e5 mov %rsp,%rbp
(略)
可知使用的是 64 位元暫存器。
5. 使用 GNU as 編寫 64 位元組合語言
安裝完 MinGW-w64 後，可以直接使用 /mingw64/bin/gcc 來組譯 GNU as 語法的 64位元組合語言。
舉例來說， 將下面的文字複製為 d.s 檔案：
.globl _main
.data
str: .string "hello"
.text
_main:
lea str, %rcx
call _printf
ret
之後輸入：
$ /mingw64/bin/gcc -o d d.s
即可組譯 d.s 為執行檔 d.exe， 輸入以下指令可執行
$ ./d
hello
6. 使用 ML64 編寫 64 位元組合語言
目前(2010) 並沒有 Masm615 這類隨書附贈的 64 位元 MASM 語法組譯器，不嫌麻煩的話，可以使用 Visual Studio 提供的 ML64 來進行組譯：
a) 安裝 Microsoft Visual Studio 2008， 完成加入這個連結：
$ ln -s '/cygdrive/c/Program Files (x86)/Microsoft Visual Studio 9.0/VC/bin/amd64' /vc
並且複製 libcmt.lib 這個檔案到工作目錄。
$ cp '/cygdrive/c/Program Files (x86)/Microsoft Visual Studio 9.0/VC/lib/amd64/libcmt.lib' .
b) 安裝 Microsoft SDK， 完成後複製 Kernel32.lib 到工作目錄。
$ cp '/cygdrive/c/Program Files/Microsoft SDKs/Windows/v6.0A/Lib/x64/Kernel32.lib' .
之後編寫以下程式為 e.asm 來進行測試：
printf PROTO
.data
s BYTE "hello",0
.code
main proc
lea rcx, s
call printf
ret
main endp
end
輸入以下指令來組譯：
$ /vc/ml64 -c e.asm
$ /vc/link e.obj libcmt.lib Kernel32.lib
即可組譯 e.asm 為執行檔 e.exe， 輸入以下指令可執行
$ ./e
hello
7. 總結
以 MinGW-w64，GNU as，或是 ML64 來編寫 64位元 C 語言或是組合語言非常方便， 提供給修習計算機組織的同學參考。
另外，64 位元與32位元呼叫 API 時的 ABI(Application Binary Interface) 差異很大, 要稍微留意。
Eih-Zhe Liang
ezliang@mail.dwu.edu.tw
cygwin下dll和lib的生成方法
luckythc | 03 四月, 2008 16:44
cygwin可以编译生成windows下供调用的dll,包括vc可识别的lib。
Cygwin-GCC : Cygwin自带了一个GCC, 用于把C/C++-Source编译成Cygwin平台下的EXE/DLL (使用Cygwin必须用其自带的GCC, 因为内部会生成一些针对于平台的特定的初始化代码， 如果用其余版本的GCC则很有可能导致程序不能正常运行．)
Cygwin-GCC : Cygwin自带了一个GCC, 用于把C/C++-Source编译成Cygwin平台下的EXE/DLL (使用Cygwin必须用其自带的GCC, 因为内部会生成一些针对于平台的特定的初始化代码， 如果用其余版本的GCC则很有可能导致程序不能正常运行．)
说明 - Cygwin-GCC :
在Cygwin-Shell中可直接使用gcc . 如下 :
gcc -shared xxx.c -o xxx.dll //编译成DLL, 注意， Cygwin-GCC默认导出所有的Function.
gcc -c xxx.c -o xxx.o //编译成OBJ
gcc xxx.c -o xxx.exe //编译成EXE
ar r xxx.lib xxx1.o xxx2.o //打包多个obj成一个Lib (非连接)
gcc xxx.c ./L aaa.dll -o xxx.exe //引用外部DLL生成EXE
gcc xxx.c yyy.c -o zzz.exe //连接多个C文件， 生成EXE.
gcc -I"/bin/include" -c xxx.c -o xxx.o //引用/bin/include目录下头文件，生成OBJ
gcc -L"dll.a" xxx.c -o xxx.exe //连接dll.a， 生成EXE
如果想知道编译时具体的信息， 可以使用--verbose这个编译选项， 对于了解GCC的工作是很有帮助的．
额外的，也可以写自己的导出Lib文件， 以方便其余程序引用DLL (如Cobol2002编译器就不支持直接引用DLL, 这个时候可以写一个Def， 并导出Lib文件， 便于Cobol2002使用)
具体方法如下：
1. 编译生成DLL :
如： gcc -shared MyTest.c -o MyTest.dll, 生成MyTest.dll.
2. 写一个DEF文件 (这里是MyTest.def)， 简单的格式大致如下：
LIBRARY MyTest //这里的MyTest对应于MyTest.dll
EXPORTS
AllocMemory @1 //导出的第一个function : 对应于MyTest.dll里面的AllocMemory(...), 注意， 参数可不用写
ReadMemory @2 //导出的第二个function : 对应于MyTest.dll里面的ReadMemory-Function.
//注意： function可以不用全部导出， 可以只选择你需要的Function.
3. 用LIB工具（VC6有提供）生成LIB文件 (这里是MyTest.lib) :
lib /def:MyTest.def //默认生成的名称为MyTest.lib.
4. 到此生成完毕， 连接的时候只需要引用MyTest.lib即可， 但要注意XXX.exe 和MyTest.dll要放在同一目录下．
可以用 gcc --help 查看具体的命令 etc..
1. 前言
使用 MinGW-w64 的工具與程式庫來編寫 64 位元程式，只要透過 Cygwin 其實非常簡單。
但如前文所述，Cygwin 目前只能編譯 32 位元的程式，使用的是 GCC 3.4.4 的版本，編譯的概念是 MinGW 與 Cygwin 程式庫二選一。
這裡要做的，則是將 Cygwin ，MinGW，MinGW-w64 視為不同的平台，以 cross compiler 的概念來進行編譯，分為三個步驟。
第一，重新安裝 Cygwin 的GCC為 4.3.4版本，可以呼叫 POSIX API 與 Windows API，但是執行時需要 cygwin1.dll。
第二，安裝 MinGW 來編譯 32 位元程式，編譯出來的是一般 Windows 32位元執行檔。
第三，安裝 MinGW-w64 來編譯 64 位元程式，編譯出來的是一般 Windows 64位元執行檔。
2. 重新安裝 Cygwin
要更新 Cygwin 的 GCC 為 4.3.4 版本，直接移除 c:\cygwin 這個目錄比較快，但是記得備份 c:\cygwin\home\Administrator 目錄下的檔案。
安裝的過程，請參考前文，到了套件選擇的步驟時，選擇 file, gcc4-core， gcc4-g++, make, vim 。
安裝完成後，進入 bash 輸入：
$ cc -v
Using built-in specs.
Target: i686-pc-cygwin
Configured with: /gnu/gcc/releases/packaging/4.3.4-3/gcc4-4.3.4-3/src/gcc-4.3.4/
configure --srcdir=/gnu/gcc/releases/packaging/4.3.4-3/gcc4-4.3.4-3/src/gcc-4.3.
4 --prefix=/usr --exec-prefix=/usr --bindir=/usr/bin --sbindir=/usr/sbin
(略)
Thread model: posix
gcc version 4.3.4 20090804 (release) 1 (GCC)
可知這次 GCC 版本為 4.3.4， 編譯目標為 i686-pc-cygwin。
以 a.c 為例，編譯出來的檔案，可以使用 file 來測試， 輸入：
$ file a.exe
a.exe: PE32 executable for MS Windows (console) Intel 80386 32-bit
可知為 PE 格式執行檔，但在檔案管理員中點選執行時，會產生找不到 cygwin1.dll 的錯誤，原因如前文所述。
另外，可以使用 objdump 反組譯來查看， 輸入：
$ objdump -d a.exe | grep '%esp,%ebp'
401001: 89 e5 mov %esp,%ebp
(略)
可知使用的是 32 位元暫存器。
這時候，如果要使用 -mno-cygwin 是不行的, 以 b.c 為例：
$ cc -o b b.c -mno-cygwin -mwindows
cc: The -mno-cygwin flag has been removed; use a mingw-targeted cross-compiler.
3. 安裝 MinGW
接下來到 http://mingw-w64.sourceforge.net/ 下載 mingw-w64-bin_i686-mingw_20100123_sezero.zip ，將壓縮檔內的 mingw32 目錄解壓縮到 c:\目錄內， 然後在 bash 內 輸入：
$ ln -s /cygdrive/c/mingw32 /mingw32
這個步驟讓我們能夠使用 /mingw32/bin/gcc 來進行編譯，輸入：
$ /mingw32/bin/gcc -v
Using built-in specs.
Target: i686-w64-mingw32
Configured with: ../gcc44-svn/configure --target=i686-w64-mingw32 --host=i686-w6
4-mingw32 --disable-multilib --disable-nls --disable-win32-registry --prefix=/mi
ngw32 --with-sysroot=/mingw32 --with-gmp=/mingw32 --with-mpfr=/mingw32 --enable-
languages=c,c++
Thread model: win32
gcc version 4.4.3 (GCC)
可知編譯目標為 i686-w64-mingw32。
以檔案 b.c 為例，輸入：
$ /mingw32/bin/gcc -o b b.c -mwindows
完成編譯後，以使用 file 來測試， 輸入：
$ file b.exe
b.exe: PE32 executable for MS Windows (GUI) Intel 80386 32-bit
可知為 32 位元 PE 執行檔。
使用 objdump 反組譯來查看， 輸入：
$ /mingw32/bin/objdump -d b.exe | grep '%esp,%ebp'
401001: 89 e5 mov %esp,%ebp
(略)
可知使用的是 32 位元暫存器。
4. 安裝 MinGW-w64
接下來到 http://mingw-w64.sourceforge.net/ 下載 mingw-w64-bin_x86_64-mingw_20100123_sezero.zip ，將壓縮檔內的 mingw64目錄解壓縮到 c:\目錄內。
製作 /mingw64 連結, 在 bash 內 輸入：
$ ln -s /cygdrive/c/mingw64 /mingw64
這個步驟讓我們能夠使用 /mingw/mingw64/bin/gcc 來進行編譯，輸入：
$ /mingw64/bin/gcc -v
Using built-in specs.
Target: x86_64-w64-mingw32
Configured with: ../gcc44-svn/configure --target=x86_64-w64-mingw32 --host=x86_6
4-w64-mingw32 --disable-multilib --disable-nls --disable-win32-registry --prefix
=/mingw64 --with-sysroot=/mingw64 --with-gmp=/mingw64 --with-mpfr=/mingw64 --ena
ble-languages=c,c++
Thread model: win32
gcc version 4.4.3 (GCC)
可知編譯目標為 x86_64-w64-mingw32。
以檔案 b.c 為例，輸入：
$ /mingw64/bin/gcc -o b b.c -mwindows
完成編譯後，以使用 file 來測試， 輸入：
$ file b.exe
b.exe: PE32+ executable for MS Windows (GUI)
可知為 64 位元 PE 執行檔。
使用 objdump 反組譯來查看， 輸入：
$ /mingw64/bin/objdump -d b.exe|grep '%rsp,%rbp'
401731: 48 89 e5 mov %rsp,%rbp
(略)
可知使用的是 64 位元暫存器。
5. 使用 GNU as 編寫 64 位元組合語言
安裝完 MinGW-w64 後，可以直接使用 /mingw64/bin/gcc 來組譯 GNU as 語法的 64位元組合語言。
舉例來說， 將下面的文字複製為 d.s 檔案：
.globl _main
.data
str: .string "hello"
.text
_main:
lea str, %rcx
call _printf
ret
之後輸入：
$ /mingw64/bin/gcc -o d d.s
即可組譯 d.s 為執行檔 d.exe， 輸入以下指令可執行
$ ./d
hello
6. 使用 ML64 編寫 64 位元組合語言
目前(2010) 並沒有 Masm615 這類隨書附贈的 64 位元 MASM 語法組譯器，不嫌麻煩的話，可以使用 Visual Studio 提供的 ML64 來進行組譯：
a) 安裝 Microsoft Visual Studio 2008， 完成加入這個連結：
$ ln -s '/cygdrive/c/Program Files (x86)/Microsoft Visual Studio 9.0/VC/bin/amd64' /vc
並且複製 libcmt.lib 這個檔案到工作目錄。
$ cp '/cygdrive/c/Program Files (x86)/Microsoft Visual Studio 9.0/VC/lib/amd64/libcmt.lib' .
b) 安裝 Microsoft SDK， 完成後複製 Kernel32.lib 到工作目錄。
$ cp '/cygdrive/c/Program Files/Microsoft SDKs/Windows/v6.0A/Lib/x64/Kernel32.lib' .
之後編寫以下程式為 e.asm 來進行測試：
printf PROTO
.data
s BYTE "hello",0
.code
main proc
lea rcx, s
call printf
ret
main endp
end
輸入以下指令來組譯：
$ /vc/ml64 -c e.asm
$ /vc/link e.obj libcmt.lib Kernel32.lib
即可組譯 e.asm 為執行檔 e.exe， 輸入以下指令可執行
$ ./e
hello
7. 總結
以 MinGW-w64，GNU as，或是 ML64 來編寫 64位元 C 語言或是組合語言非常方便， 提供給修習計算機組織的同學參考。
另外，64 位元與32位元呼叫 API 時的 ABI(Application Binary Interface) 差異很大, 要稍微留意。
Eih-Zhe Liang
ezliang@mail.dwu.edu.tw
cygwin下dll和lib的生成方法
luckythc | 03 四月, 2008 16:44
cygwin可以编译生成windows下供调用的dll,包括vc可识别的lib。
Cygwin-GCC : Cygwin自带了一个GCC, 用于把C/C++-Source编译成Cygwin平台下的EXE/DLL (使用Cygwin必须用其自带的GCC, 因为内部会生成一些针对于平台的特定的初始化代码， 如果用其余版本的GCC则很有可能导致程序不能正常运行．)
Cygwin-GCC : Cygwin自带了一个GCC, 用于把C/C++-Source编译成Cygwin平台下的EXE/DLL (使用Cygwin必须用其自带的GCC, 因为内部会生成一些针对于平台的特定的初始化代码， 如果用其余版本的GCC则很有可能导致程序不能正常运行．)
说明 - Cygwin-GCC :
在Cygwin-Shell中可直接使用gcc . 如下 :
gcc -shared xxx.c -o xxx.dll //编译成DLL, 注意， Cygwin-GCC默认导出所有的Function.
gcc -c xxx.c -o xxx.o //编译成OBJ
gcc xxx.c -o xxx.exe //编译成EXE
ar r xxx.lib xxx1.o xxx2.o //打包多个obj成一个Lib (非连接)
gcc xxx.c ./L aaa.dll -o xxx.exe //引用外部DLL生成EXE
gcc xxx.c yyy.c -o zzz.exe //连接多个C文件， 生成EXE.
gcc -I"/bin/include" -c xxx.c -o xxx.o //引用/bin/include目录下头文件，生成OBJ
gcc -L"dll.a" xxx.c -o xxx.exe //连接dll.a， 生成EXE
如果想知道编译时具体的信息， 可以使用--verbose这个编译选项， 对于了解GCC的工作是很有帮助的．
额外的，也可以写自己的导出Lib文件， 以方便其余程序引用DLL (如Cobol2002编译器就不支持直接引用DLL, 这个时候可以写一个Def， 并导出Lib文件， 便于Cobol2002使用)
具体方法如下：
1. 编译生成DLL :
如： gcc -shared MyTest.c -o MyTest.dll, 生成MyTest.dll.
2. 写一个DEF文件 (这里是MyTest.def)， 简单的格式大致如下：
LIBRARY MyTest //这里的MyTest对应于MyTest.dll
EXPORTS
AllocMemory @1 //导出的第一个function : 对应于MyTest.dll里面的AllocMemory(...), 注意， 参数可不用写
ReadMemory @2 //导出的第二个function : 对应于MyTest.dll里面的ReadMemory-Function.
//注意： function可以不用全部导出， 可以只选择你需要的Function.
3. 用LIB工具（VC6有提供）生成LIB文件 (这里是MyTest.lib) :
lib /def:MyTest.def //默认生成的名称为MyTest.lib.
4. 到此生成完毕， 连接的时候只需要引用MyTest.lib即可， 但要注意XXX.exe 和MyTest.dll要放在同一目录下．
可以用 gcc --help 查看具体的命令 etc..
2009年8月12日星期三
Grammer checking project
1. open office project:
From: http://lingucomponent.openoffice.org/grammar.html
start:
Lingucomponent Sub-Project: Grammar Checking
One of the goals of the Lingucomponent project is to design, develop, and implement a Grammar checker for English and other supported languages.
News
* October 2008: A grammar checking API is now part of OpenOffice.org 3.0. LanguageTool now makes use of this new API which allows on-the-fly checking, i.e. checking text while you type. More information about the API is available at the following sources:
o Grammar Checking page in Wiki
o Specification (.odt)
o All grammar checker issues
If you have any interest in helping to implement a grammar checker for the OpenOffice.org project, please subscribe to the mailing list dev@lingucomponent.openoffice.org and introduce yourself, your skills, and your willingness to help this project.
Links to Open Source grammar checkers
* An Gramadóir, a grammar checker for the Irish language
* CoGrOO, a grammar checker for Portuguese
* GRAC, corpus-based grammar checker written in Python
* graviax, grammar rules and grammar checker for the English language
* Higgins, a prototype English-language parser
* LanguageTool, a style and grammar checker with OpenOffice.org integration, for English, German, Polish, Dutch, and other languages
* Link Grammar, not really a grammar checker but a parser for the English language, also see the link grammar page at AbiWord
Links to commercial grammar checkers
* Cysgliad, a Welsh grammar checker
Created: 2001 June. Last Modified: $Date: 2008/11/08 21:32:59 $, $Revision: 1.25 $
2. Requirement (not totally true)
From: http://wiki.services.openoffice.org/wiki/Grammar_Checking
Grammar checking of mixed language text
It is believed that even for sentences that uses several languages there is only a single language the whole sentence is in. (How that language is identified is a completely different matter and probably a complex task though!) And thus that sentence should only be grammar checked in that single language. For example:
The German word for television is Fernseher.
This sentence should be grammar checked in English and not German
If possible though (for example if language attributes are set correctly) it should be noted that Fernseher is not in English and thus at the very least no spelling error should for English should be reported for that word. And probably it is also impossible to report any grammar error that involves embedded foreign words. Thus the best to hope for probably is for the foreign word to be recognized as correct by the respective spell checker.
Even with completely embedded sentence like
In Gallica Caesar said 'Alea iacta est.' and continued his battle.
the above text is in a single language English and not Latin. If an existing grammar checker is smart enough to cope with embedded sentences of a different language I don't know. To keep it simple for the time being the whole text should be grammar checked as one sentence in English and in only that language.
Grammar checking and spell checking at the same time
Should spell checking have an iterator of it's own with a thread of it's own? Or should spell checking be handled by the GrammarCheckingIterator as well?
Other Questions / problems:
* checking is limited to paragraphs (unless the implementation of XFlatParagraph chooses to hide sth. more behind it which is unlikely). Though one could think of enumerations as a possible application for this behavior.
* in the case of several grammar checkers for one languages, what do we do if they report different end-of-sentence positions? We really can't handle each checker individually here.
* does a grammar checker that requires knowledge of the previous text in this paragraph need to have those text presented even if it is in a language it does not know?
* How to achieve consistency of usage (e.g. spelling) when having grammar checkers in multiple languages? E.g. e-mail vs. email? Or does it need to be consistent on a per language base only?
* How to determine the language of a sentence? Use the language of the first word, or language guessing, or the language with the most words,... ?
* Problems related to a specific UI, namely the grammar checking dialog still to be defined, not yet covered.
* The troublesome case of having for example three grammar checkers for one language and two of them wanting to use their own dialog while the third will go with the office internal one is left out. Because if all of them report errors in the same sentence and like to use their own dialog as well we will have to cope with switching between three dialogs just to edit a single sentence. That's just plain awful to even think about. And I doubt there will be even one user to appreciate such a scenario.
* Should the document (e.g. XFlatParagraph) be in charge to determine the language for checking or should it be the GrammarCheckingIterator? Probably the latter...
From: http://lingucomponent.openoffice.org/grammar.html
start:
Lingucomponent Sub-Project: Grammar Checking
One of the goals of the Lingucomponent project is to design, develop, and implement a Grammar checker for English and other supported languages.
News
* October 2008: A grammar checking API is now part of OpenOffice.org 3.0. LanguageTool now makes use of this new API which allows on-the-fly checking, i.e. checking text while you type. More information about the API is available at the following sources:
o Grammar Checking page in Wiki
o Specification (.odt)
o All grammar checker issues
If you have any interest in helping to implement a grammar checker for the OpenOffice.org project, please subscribe to the mailing list dev@lingucomponent.openoffice.org and introduce yourself, your skills, and your willingness to help this project.
Links to Open Source grammar checkers
* An Gramadóir, a grammar checker for the Irish language
* CoGrOO, a grammar checker for Portuguese
* GRAC, corpus-based grammar checker written in Python
* graviax, grammar rules and grammar checker for the English language
* Higgins, a prototype English-language parser
* LanguageTool, a style and grammar checker with OpenOffice.org integration, for English, German, Polish, Dutch, and other languages
* Link Grammar, not really a grammar checker but a parser for the English language, also see the link grammar page at AbiWord
Links to commercial grammar checkers
* Cysgliad, a Welsh grammar checker
Created: 2001 June. Last Modified: $Date: 2008/11/08 21:32:59 $, $Revision: 1.25 $
2. Requirement (not totally true)
From: http://wiki.services.openoffice.org/wiki/Grammar_Checking
Grammar checking of mixed language text
It is believed that even for sentences that uses several languages there is only a single language the whole sentence is in. (How that language is identified is a completely different matter and probably a complex task though!) And thus that sentence should only be grammar checked in that single language. For example:
The German word for television is Fernseher.
This sentence should be grammar checked in English and not German
If possible though (for example if language attributes are set correctly) it should be noted that Fernseher is not in English and thus at the very least no spelling error should for English should be reported for that word. And probably it is also impossible to report any grammar error that involves embedded foreign words. Thus the best to hope for probably is for the foreign word to be recognized as correct by the respective spell checker.
Even with completely embedded sentence like
In Gallica Caesar said 'Alea iacta est.' and continued his battle.
the above text is in a single language English and not Latin. If an existing grammar checker is smart enough to cope with embedded sentences of a different language I don't know. To keep it simple for the time being the whole text should be grammar checked as one sentence in English and in only that language.
Grammar checking and spell checking at the same time
Should spell checking have an iterator of it's own with a thread of it's own? Or should spell checking be handled by the GrammarCheckingIterator as well?
Other Questions / problems:
* checking is limited to paragraphs (unless the implementation of XFlatParagraph chooses to hide sth. more behind it which is unlikely). Though one could think of enumerations as a possible application for this behavior.
* in the case of several grammar checkers for one languages, what do we do if they report different end-of-sentence positions? We really can't handle each checker individually here.
* does a grammar checker that requires knowledge of the previous text in this paragraph need to have those text presented even if it is in a language it does not know?
* How to achieve consistency of usage (e.g. spelling) when having grammar checkers in multiple languages? E.g. e-mail vs. email? Or does it need to be consistent on a per language base only?
* How to determine the language of a sentence? Use the language of the first word, or language guessing, or the language with the most words,... ?
* Problems related to a specific UI, namely the grammar checking dialog still to be defined, not yet covered.
* The troublesome case of having for example three grammar checkers for one language and two of them wanting to use their own dialog while the third will go with the office internal one is left out. Because if all of them report errors in the same sentence and like to use their own dialog as well we will have to cope with switching between three dialogs just to edit a single sentence. That's just plain awful to even think about. And I doubt there will be even one user to appreciate such a scenario.
* Should the document (e.g. XFlatParagraph) be in charge to determine the language for checking or should it be the GrammarCheckingIterator? Probably the latter...
2009年1月19日星期一
Top coder
假设有这样一种字符串，它们的长度不大于26，而且若一个这样的字符串其长度为
m，则这个字符串必定由a, b, c, . . . , z 中的前m 个字母构成，同时我们保证每个字母出
现且仅出现一次。比方说某个字符串长度为5，那么它一定是由a, b, c, d, e 这5 个字母
构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些
字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
现在我们用一个由大写字母A 和B 构成的序列来描述这类字符串里各个字母的前
后顺序：
1. 如果字母b 在字母a 的后面，那么序列的第一个字母就是A（After），否则序列的
第一个字母就是B（Before）；
2. 如果字母c 在字母b 的后面，那么序列的第二个字母就是A，否则就是B；
3. 如果字母d 在字母c 的后面，那么??不用多说了吧？直到这个字符串的结束。
这规则甚是简单，不过有个问题就是同一个AB 序列，可能有多个字符串都与之相
符，比方说序列"ABA"，就有"acdb"、"cadb" 等等好几种可能性。说的专业一点，这一
个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的AB 序列，
问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多
大？注意，只要求个数，不要求枚举所有的字符串。
注：如果结果大于10 亿就返回-1。
我把题目总结为:给定一个字符串"ABAB..."(以下称为模式串),计算出符合要求的所有"abcd..."字符串(以下称为结果串)的个数.
要解答这个问题,首先需要明确两点(为什么就不要说了吧,呵呵):
1. 如果模式串的长度为n,那么结果串的长度为n+1
2. 一个模式串至少对应一个结果串,一个结果串对应而且只能对应一个模式串
下面我把我的思考过程写出来:
一. 从一个给定的模式串递推出所有的结果串,假设给定的模式串是"ABAB":
1.对于第一个字母"A",那么结果串只能是"ab"
2.对于第二个字母"B",说明c在b之前,而b之前有2个空位可以插入,所以可能的结果串是"cab","acb"
3.对于第三个字母"A",说明d在c之后.在"cab"中,d可以插到3个空位中,可能的结果串是"cdab","cadb","cabd";在"acb"中,d可以插到2个空位中----"acdb","acbd".所以总的可能数是5
4.对于第四个字母"B",同样的道理可以算出总的可能的结果串有16个.
二. 总结一下刚才的递推过程,可以发现每一次递推只和前一次递推的结果和模式串相应位置的字母有关,而模式串是给定的,所以确切的说,只和前一次递推结果中最大字母(最大字母指的是按字母排序的大小,如z>y>x>...>c>b>a)的位置有关.
现在有点事没时间写了,明天接着写,不过规律已经给出了,就是根据前一次结果的最大字母的位置来计算.大家可以先自己想想.
接着写.
既然找到了问题的本质,那么就构造一个数据结构存储每次递推的最大字母的位置即可.本题可以用一个简单数组记录便可.如下所示,用一个整型数组num记录.(数组的具体大小视情况而定,在此不做细究,题目中说不会大于26).num[a] = b的含义是,在位置a上(第a位上)最大字母出现的次数是b次.
const int maxNum = 30;
int num[maxNum];
用string moduleString;记录模式串.
程序的思想是:
1. 输入模式串的长度为n时,从模式串的第一个字母开始递推.
2. 数组num的第一位即num[0]做边界处理,真正的记录从num[1]开始.
3. 在递推时,如果当前字母是”A”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”右边的情况有几种.如果是”B”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”左边的情况有几种
下面举个具体的例子来分析:以输出”ABAB”为例,每一行表示每次递推之后num数组的变化
模式串/位置 第零位 第一位 第二位 第三位 第四位 第五位
A 0 0 1
AB 0 1 1 0
ABA 0 0 1 2 2
ABAB 0 5 5 4 2 0
1) A: 此时最大字母为b,显然它出现在第2位(记住第零位永远是0,真正的记录从第一位开始)
2) AB:此时最大字母为c,它要求出现在b之前,分别是cab,acb.所以c在第一位,第二位上各出现一次.
3) ABA: 此时最大字母为d,它要求出现在c之后.显然d出现在第一位是不可能的,所以在第一位出现的次数是0.因为c在前一次结果的第一位出现过一次,所以d在那种情况下可以在第二位出现一次.下面来看d在第三位可能出现的次数,因为前一次结果中,在第三位之前c出现过2次,那么d可以在那两种情况下出现在第三位,所以d在第三位出现的次数为2.最后看d在第四位出现的次数,还是因为前一次结果中c在第四位之前出现的次数是2次,所以d在第四位出现的次数是2
4) ABAB: 此时最大字母是e,计算它出现的次数的方法和前面的一样,只是它要求是在前一次最大字母d的左边,只要反过来从右往左遍历就行了,在此不再累述.
最终的程序为:
int main(int argc, char* argv[])
{
const int maxNum = 30;
int num[maxNum]; //num[0] = 0;
string moduleString;
int length;
cout<<"Input Module String"<
length = moduleString.length();
if(moduleString[0] == 'A')
{
num[1] = 0;
num[2] = 1;
}
else
{
num[1] = 1;
num[2] = 0;
}
num[0] = 0;
int preNum0 = 0;
int preNum1 = 0;
for(int i = 1; i < length; i++)
{
if(moduleString[i] == 'A')
{
preNum0 = num[0];
preNum1 = num[1];
for(int j = 1; j <= i+2; j++)
{
num[j] = num[j-1] + preNum0;
preNum0 = preNum1;
preNum1 = num[j+1];
}
}
else
{
num[i+2] = 0;
for(int j = i+1; j > 0; j--)
{
num[j] = num[j+1] + num[j];
}
}
}
int totalNum = 0;
for(int i = 0;i < length + 2;i++)
{
totalNum += num[i];
}
cout< < totalNum < < endl;
return 0;
}
对程序的几点说明:
1. 该程序缺少头部信息.(,)
2. 该程序已调试通过,为可用版本
3. 该程序的输入为一个形如”ABA..”的模式串,输出为符合要求的结果串的个数.
4. 该程序的时间复杂度为n^2
5. 该程序只为展示如何解决此类问题,输入输出可能与原题不符,相信读者可根据此程序作少许修改以通过Top coder的测试.
m，则这个字符串必定由a, b, c, . . . , z 中的前m 个字母构成，同时我们保证每个字母出
现且仅出现一次。比方说某个字符串长度为5，那么它一定是由a, b, c, d, e 这5 个字母
构成，不会多一个也不会少一个。嗯嗯，这样一来，一旦长度确定，这个字符串中有哪些
字母也就确定了，唯一的区别就是这些字母的前后顺序而已。
现在我们用一个由大写字母A 和B 构成的序列来描述这类字符串里各个字母的前
后顺序：
1. 如果字母b 在字母a 的后面，那么序列的第一个字母就是A（After），否则序列的
第一个字母就是B（Before）；
2. 如果字母c 在字母b 的后面，那么序列的第二个字母就是A，否则就是B；
3. 如果字母d 在字母c 的后面，那么??不用多说了吧？直到这个字符串的结束。
这规则甚是简单，不过有个问题就是同一个AB 序列，可能有多个字符串都与之相
符，比方说序列"ABA"，就有"acdb"、"cadb" 等等好几种可能性。说的专业一点，这一
个序列实际上对应了一个字符串集合。那么现在问题来了：给你一个这样的AB 序列，
问你究竟有多少个不同的字符串能够与之相符？或者说这个序列对应的字符串集合有多
大？注意，只要求个数，不要求枚举所有的字符串。
注：如果结果大于10 亿就返回-1。
我把题目总结为:给定一个字符串"ABAB..."(以下称为模式串),计算出符合要求的所有"abcd..."字符串(以下称为结果串)的个数.
要解答这个问题,首先需要明确两点(为什么就不要说了吧,呵呵):
1. 如果模式串的长度为n,那么结果串的长度为n+1
2. 一个模式串至少对应一个结果串,一个结果串对应而且只能对应一个模式串
下面我把我的思考过程写出来:
一. 从一个给定的模式串递推出所有的结果串,假设给定的模式串是"ABAB":
1.对于第一个字母"A",那么结果串只能是"ab"
2.对于第二个字母"B",说明c在b之前,而b之前有2个空位可以插入,所以可能的结果串是"cab","acb"
3.对于第三个字母"A",说明d在c之后.在"cab"中,d可以插到3个空位中,可能的结果串是"cdab","cadb","cabd";在"acb"中,d可以插到2个空位中----"acdb","acbd".所以总的可能数是5
4.对于第四个字母"B",同样的道理可以算出总的可能的结果串有16个.
二. 总结一下刚才的递推过程,可以发现每一次递推只和前一次递推的结果和模式串相应位置的字母有关,而模式串是给定的,所以确切的说,只和前一次递推结果中最大字母(最大字母指的是按字母排序的大小,如z>y>x>...>c>b>a)的位置有关.
现在有点事没时间写了,明天接着写,不过规律已经给出了,就是根据前一次结果的最大字母的位置来计算.大家可以先自己想想.
接着写.
既然找到了问题的本质,那么就构造一个数据结构存储每次递推的最大字母的位置即可.本题可以用一个简单数组记录便可.如下所示,用一个整型数组num记录.(数组的具体大小视情况而定,在此不做细究,题目中说不会大于26).num[a] = b的含义是,在位置a上(第a位上)最大字母出现的次数是b次.
const int maxNum = 30;
int num[maxNum];
用string moduleString;记录模式串.
程序的思想是:
1. 输入模式串的长度为n时,从模式串的第一个字母开始递推.
2. 数组num的第一位即num[0]做边界处理,真正的记录从num[1]开始.
3. 在递推时,如果当前字母是”A”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”右边的情况有几种.如果是”B”,那么只关心”这次最大字母”在”前一次递推的结果中最大字母”左边的情况有几种
下面举个具体的例子来分析:以输出”ABAB”为例,每一行表示每次递推之后num数组的变化
模式串/位置 第零位 第一位 第二位 第三位 第四位 第五位
A 0 0 1
AB 0 1 1 0
ABA 0 0 1 2 2
ABAB 0 5 5 4 2 0
1) A: 此时最大字母为b,显然它出现在第2位(记住第零位永远是0,真正的记录从第一位开始)
2) AB:此时最大字母为c,它要求出现在b之前,分别是cab,acb.所以c在第一位,第二位上各出现一次.
3) ABA: 此时最大字母为d,它要求出现在c之后.显然d出现在第一位是不可能的,所以在第一位出现的次数是0.因为c在前一次结果的第一位出现过一次,所以d在那种情况下可以在第二位出现一次.下面来看d在第三位可能出现的次数,因为前一次结果中,在第三位之前c出现过2次,那么d可以在那两种情况下出现在第三位,所以d在第三位出现的次数为2.最后看d在第四位出现的次数,还是因为前一次结果中c在第四位之前出现的次数是2次,所以d在第四位出现的次数是2
4) ABAB: 此时最大字母是e,计算它出现的次数的方法和前面的一样,只是它要求是在前一次最大字母d的左边,只要反过来从右往左遍历就行了,在此不再累述.
最终的程序为:
int main(int argc, char* argv[])
{
const int maxNum = 30;
int num[maxNum]; //num[0] = 0;
string moduleString;
int length;
cout<<"Input Module String"<
length = moduleString.length();
if(moduleString[0] == 'A')
{
num[1] = 0;
num[2] = 1;
}
else
{
num[1] = 1;
num[2] = 0;
}
num[0] = 0;
int preNum0 = 0;
int preNum1 = 0;
for(int i = 1; i < length; i++)
{
if(moduleString[i] == 'A')
{
preNum0 = num[0];
preNum1 = num[1];
for(int j = 1; j <= i+2; j++)
{
num[j] = num[j-1] + preNum0;
preNum0 = preNum1;
preNum1 = num[j+1];
}
}
else
{
num[i+2] = 0;
for(int j = i+1; j > 0; j--)
{
num[j] = num[j+1] + num[j];
}
}
}
int totalNum = 0;
for(int i = 0;i < length + 2;i++)
{
totalNum += num[i];
}
cout< < totalNum < < endl;
return 0;
}
对程序的几点说明:
1. 该程序缺少头部信息.(
2. 该程序已调试通过,为可用版本
3. 该程序的输入为一个形如”ABA..”的模式串,输出为符合要求的结果串的个数.
4. 该程序的时间复杂度为n^2
5. 该程序只为展示如何解决此类问题,输入输出可能与原题不符,相信读者可根据此程序作少许修改以通过Top coder的测试.
2008年12月3日星期三
2008年9月18日星期四
9.18
From each vertex B to each vertex C there is either a one-step path (a single edge) or a unique two-step path. But we'll analyze the problem by looking at three-step paths as well. Fix two vertices B and C. Suppose there are k different vertices H such that (H,C) is an edge. Call these vertices the "predecessors" of C. Suppose also that there are m different vertices G such that (B,G) is an edge; call these vertices the "followers" of B. How many paths, of length either two or three (but not one) are there from B to C? First answer: there are m such paths. Each two- or three-step path from B to C consists of an edge from B to some vertex G, followed by the unique one- or two-step path from that vertex G to the destination C. Since there are m edges leading out of B, and each can be completed to exactly one path of length 2 or 3 to C, there are m such paths. Second answer: k. Each two- or three-step path from B to C is a one- or two-step path from B to one of C's predecessors H, followed by a one-step path from that vertex to C. Each of the k predecessors of J accounts for exactly one such path. So we must have k=m. By the same reasoning, each vertex D has exactly k two- or three-step paths to C, and so has exactly k successors. Similarly we can see that each vertex has exactly k predecessors. (In graph terminology, each vertex has in-degree k and out-degree k.) Now consider one- or two-step paths starting at B. There are exactly k vertices H reachable by a one-step path. Since each of these vertices also has exactly k followers, there are exactly (k*k) vertices reachable from B via two-step paths. This accounts for all the vertices, so the total number of vertices is k+(k*k). We know there are thirty to forty vertices, so we must have k=5 and the number of vertices is thirty. It turns out (though this is harder to prove) that the vertices can be given consistent labels of the form Vij, where i and j are two different indices from the set {1,2,...,k+1}, and where an edge goes from Vij to Vkh if and only if j=k. Illustrating in a smaller case k=2, we would have 6=2+4 vertices V12, V13, V21, V23, V31, V32, and twelve edges (two coming out of each vertex): (V12,V21), (V12,V23), (V13,V31), (V13,V32), (V21,V12), (V21,V13), (V23,V31), (V23,V32), (V31,V12), (V31,V13), (V32,V21), (V32,V23).
订阅：
博文 (Atom)