用1000万参考句型交叉重叠进行音字转换的输入算法

hztj

汉语是我们母语，汉字承载了我们五千年的文明，但汉语的信息化始终是我们民族现代化道路上的一道坎。目前使用分词算法和N元文法统计模型进行音字转换，准确率不能满足需要，所以我自2004年以来提出“基于参考句型的语言处理方法”，并给出了相关算法：
　　汉语语句的总数是难以穷尽的，所以一一列举的“基于实例的方法”是不可行的。但许多语句有共同的组成部分，称为“基本句型”，也可以称为“短语”，如：“他毕业五年了”、“他早就毕业了”、“他明年六月毕业”中的“他毕业”。另一方面，一个语句也可以有多个“交叉”“重叠”的“基本句型”，如：“这人的英语说得不流利”中的“这人说英语”、“英语流利”、“不流利”。
　　如果建立起汉语的基本句型数据库，设拼音输入、语音输入中有拼音串“zheren de yingyu shuo de bu liuli”，在数据库中找出“zheren*shuo*yingyu/这人说英语”，“yingyu*liuli/英语流利”、“bu*liuli /不流利”等作为参考句型。从多个参考句型中，首先选用最长的“这人说英语”，第2步以其中的“英语”去联想“英语流利”，第3步用“流利”去联想“不流利”，则可以处理为“这人de英语说得不流利”，最后用语法、词频等方法作补充，应能大幅度提高准确率。
　　计算机处理语言给出参考句型，就好比绘图中给出模板：要徒手画一个2厘米的等边三角形是很难的，更别说复杂的图案，如果给出许多的大小不一的各种形状模板，利用这些模板可以组合出千变万化的图案，再复杂的图案也可以画得八九不离十。同样，对于一种语言如果给出数百万乃至数千万的基本句型，利用这些基本句型交叉重叠就可能很好地解决音字转换问题。
　　由于语言中普遍存在的交叉现象，传统的索引方法不能发现“shixian-weida-lixiang/实现伟大理想”、“lixiang-yijing-shixian/理想已经实现”同数据库“shixian*lixiang/实现理想”有内在联系。当然，对字符串进行“逐字符比较”，也能发现两者之间存在包含关系，但响应速度不能满足需要。
　　所以我提出质数代换、位标记等方法来提高参考句型的查找速度，对比字符匹配，将速度提高了5-10倍，最高可以提高30倍。用VC独立编程模拟测试表明，一般情况下，在赛扬800的CPU上0.1-0.5秒能从400万条记录中查找出参考句型。据此推算，在高档微机0.1-0.5秒能为一个拼音串从1000万个句型中找到参考句型，在未来3-5年内，0.1-0.5秒应能从4000万个句型中比对出参考句型。
　　“基于参考句型”的语言算法完全兼容了“分词”算法，并采用“非连续音节的转移概率”进行语句生成决策，比“N元文法统计模型”采用的“连续音节的转移概率”，更符合语言的规律，用若干个“参考句型”确定了一个拼音串的主干后，再用语法分析做补充，应能大幅度提高拼音输入、语音输入的水平。我逢山开路遇水搭桥解决了算法，但提取1000万-4000万个最有代表性的基本句型需要社会各界的支持，诚邀业界人士参与讨论分析，推进技术的发展！也呼吁社会各界提供语料！
　　2006-7-18
　　技术方案《语言处理技术》word文档见“附件”.
       也可在下面网页的“附件”中下载：  
　　http://www.pkucn.com/viewthread. ... e%3D3#pid1218072646

[ 本帖最后由 hztj 于 2006-7-20 17:18 编辑 ]

湘里妹子

语料如何提供给您？
可不可以就在论坛直接跟帖提供呢？

胡吉成

hztj

原帖由 湘里妹子 于 2006-7-20 20:48 发表
语料如何提供给您？
可不可以就在论坛直接跟帖提供呢？

非常感谢站长的热情和诚意，语料可以用附件方式发到下面邮箱：
hztj2005@yahoo.com.cn
在论坛跟贴作附件，让我下载也可以。

[ 本帖最后由 hztj 于 2006-7-21 10:56 编辑 ]

湘里妹子

还是帮楼主把附件帖出来吧，这样更便于有兴趣者参与

基于参考句型的语言算法简介

作者：徐文新
2006-7-18
联系方式：hztj2005@yahoo.com.cn   xvxxvx@tom.com

1.基于参考句型的语言处理方法         
2. 语言的协同现象与相关算法         
3参考句型数量估计       
4.参考句型提炼       
5.音字转换分析       
6.其它问题       
7.项目计划
8.参与方式       

本项目提出了“基于参考句型”的语言模型并给出相关算法，对比字符匹配快5-10倍，最高可以提高30倍，可以在0.1-0.5秒为一个拼音串从1000万个句型中找到参考句型，用参考句型来合成语句。“基于参考句型”的语言算法完全兼容了“分词”算法，并采用“非连续音节的转移频率”进行语句生成决策，比“N元文法统计模型”采用的“连续音节的转移频率”，更符合语言的规律，可能代表了计算机处理语言的发展方向。申请了4项PCT国际专利，前2项已收到国际检索报告，通过了检索。寻求资金申请外国专利及开发软件，同时诚邀业界精英参与软件开发。

1.基于参考句型的语言处理方法

目前汉语拼音输入、语音输入的语言模型主要有两种：一种是“分词”算法，简单的说，就是对拼音串按不同方法切分后，到词汇表去查找，并以概率、语法规则作辅助；另一种是“N元文法统计模型”，2元文法模型准确率不高，3元统计模型则存在统计数据稀疏、程序数据量大的问题。目前做得最好的是IBM，准确率是95%。这些方法的准确率不能满足需要，所以我提出“基于参考句型的语言算法”。
汉语语句的总数可以说是难以穷尽的，所以“基于实例的方法”是不可行的。但很多语句有共同的组成部分，称为“基本句型”，也可以称为“短语”，如：
他毕业五年了
他早就毕业了
他明年六月毕业
--------他毕业
                                                        
另一方面，一个语句也可以有多个“交叉”“重叠”的“基本句型”：
这人的英语说得不流利
-----------------这人说英语
-----------------英语流利
----------------不流利

如果建立起汉语的基本句型数据库，设拼音输入、语音输入中有拼音串“zheren de yingyu shuo de bu liuli”，在数据库中找出“zheren*shuo*yingyu/这人说英语”，“yingyu*liuli/英语流利”、“bu*liuli /不流利”等作为参考句型。从多个参考句型中，首先选用最长的“这人说英语”，第2步以其中的“英语”去联想“英语流利”，第3步用“流利”去联想“不流利”，则处理为“这人de英语说得不流利”，最后用语法、词频等方法作补充，应能大幅度提高准确率。
计算机处理语言给出参考句型，就好比绘图中给出模板：要徒手画一个2厘米的等腰三角形是很难的，更别说复杂的图案，如果给出许许多多的大小不一的各种形状模板，利用这些模板可以组合出千变万化的图案，再复杂的图案也可以画得八九不离十。同样，对于一种语言如果给出数百万乃至数千万的基本句型，利用这些基本句型交叉重叠就可能很好地解决音字转换问题。

2. 语言的协同现象与相关算法

单独给出一个音节“xue”、或“sheng”，我们不能确定其意义及所指的汉字，但“xuesheng”两个音节连用，则意为“学生”，这里“xue”与“sheng”起了“互证”作用，称为语言的“协同现象”。

音为“shixian”的词语有“实现、事先、失陷、视线、时限、时鲜、时贤”，音为“lixiang”的词语有“理想、里巷”。如果有人说“shixianlixiang”，我们会理解为“实现理想”，而不会理解为“视线里巷”，这里“shixian”与“lixiang”起了“互证”作用。总之，音节越多，语义越确定。对于汉语来说，三音节、四音节词句中，“同音多词”或“同音多义”的概率越来越少，并且出现大量“有音无义”现象。正是由于三音节中“有音无义”的概率大，如果他人谈话中提及一个三音节的陌生人名，如“lifuhao”，我们多数时候能判断出这是一个人的名字，而不是词语。

既然三音节、四音节中，“同音多义”的概率越来越少，如将单音节词语、双音节词语，按语义搭配组成三、四字乃至五字以上的短语、句型，给出相应的拼音，建立数据库，由于音、义一一对应性好，根据这种数据库进行音字转换，就能提高准确率。设语音转换或拼音输入的T为“shixianlixiangxuyaonuli”，用“正向最大匹配法”进行分词，可以在数据库找到拼音串：“shixian*lixiang”，其相应的汉字串为“实现理想”，将T处理为“实现理想xuyaonuli”，可以避免用“shixian”“lixiang”分别处理时的选词错误。

如果有人说“shixianweidalixiang”，我们会理解为“实现伟大理想”，而不是“时贤伟大里巷”，说明语言的“协同现象”是可以“跨音节”的；如果有人说“lixiangyijingshixian”，我们会理解为“理想已经实现”，而不是“理想意境视线”，说明语言的“协同现象”是可以一定程度上“无序”的。但是，通常的分词“索引”查找方法不能发现“shixian-weida-lixiang”、“lixiang-yijing-shixian”同数据库“shixian*lixiang/实现理想”有内在联系，也就是对“跨音节协同现象”“无序协同现象”无效。而用shixian、lixiang分别处理，又无法做出正确的选择。试想对lixiangyijingshixian这样一个拼音串，如果连其主要部分都不能确定的话，语法分析就无成下手，这也就是自上世纪50年代以来自然语言处理未能取得成功的原因。如果我们将lixiangyijingshixian这样一个拼音串同参考句型进行比较，发现同“shixian*lixiang”有内在联系，就可以处理成“理想yijing实现”，就不难进一步处理为“理想已经实现”。

要发现“shixian-weida-lixiang”、“lixiang-yijing-shixian”同数据库“shixian*lixiang/实现理想”有内在联系，一个笨方法是对拼音串进行“逐字符比较”，但响应速度不能满足需要。因此，我提出用400多个质数代换汉语的400个音节，“实现理想”的拼音为“shixian*lixiang”，代换成29*67*281*11，即6005813。设语音输入的T=“lixiang-yijing-shixian”，代换成29*67*97*23*281*11，即Ft=13398968803。以Ft为被除数，以数据库全部字词搭配及基本句型的Fn值为除数，若能整除或模运算余数为0，则该句型为可参考的基本句型或字词搭配。13398968803/6005813=2231，余数为0，则“shixian*lixiang/实现理想”是“lixiang-yijing-shixian”的参考句型。对通过整除筛选的记录，可以再进行语法分析，剔除结构不合的记录。

如用 个质数代换含有 个字符元的字符串，其中必含有某 个质数的概率的一般计算公式是：

其中
计算出现某1个质数的概率，一般公式简化为：
计算出现某2个质数的概率，一般公式简化为：
计算出现某3个质数的概率，一般公式简化为：

这里计算的是平均概率，精确计算某n个不同频率的音节同时出现的概率，可用多项式计算。
整除也是费时的运算，但1个64bit的整数可以代表6个音节，减少了读取数据的时间，因此质数代换比字符比较快1-2倍。质数代换速度也不能满足需要，所以需要用“位标记字符串检索技术”进行预处理。“位标记字符串检索技术”的基本方法是将汉语的400个音节分为32组，用一个数据的32个bit来标记，记为W，如果某个句型S的第1个音节属第i组，则将W的第i个bit标记为1；同样方法处理其它音节。通过对Wa和Wb进行一次逻辑比较可以判断Sa可能包含或不包含Sb的所有音节，大大提高了检索效率。

如果 Wa & Wb = Wa 则Sa可能包含所有音节，再用质数代换整除进行判断。
如果 Wa & Wb≠ Wa 则Sa不包含所有音节，放弃。

从理论上分析，该方法比“BM”和“位向量”方法快，在微软 SQL Server 2000中实际测试，用该方法能将字符串模糊检索速度提高5-10倍。

设标记所用位数为n，字符串位值的“1”为m个，检索关键词位值的“1”为k个，则位比较的筛选概率可以用下式计算，其值越小越好：

n为32，m和k部分取值的筛选概率计算如下：
m         k=1         k=2                              k=3         k=4
24        0.75        0.556451613        0.408065        0.295495
22        0.6875        0.465725806        0.310484        0.20342
20        0.625        0.383064516        0.229839        0.134733
18        0.5625        0.308467742        0.164516        0.085095
16        0.5        0.241935484        0.112903        0.050612
14        0.4375        0.183467742        0.073387        0.027836
12        0.375        0.133064516        0.044355        0.013765
10        0.3125        0.090725806        0.024194        0.00584
8        0.25        0.056451613        0.01129        0.001947

就是说，当语句8-16个汉字时，当句型为3个汉字时，通过标记筛选的句型概率为1.12903%-11.29%，10M句型通过筛选的句型约为11.29-112.9万条，需要进行质数代换整除判断；当句型为4个汉字时，筛选效果更好。应用中如果内存足够多，用位标记筛选2次，则质数代换整除记录可以控制在20万条以下。更长的句型可以切分为短句处理。

每次句型查找用时=10M次逻辑比较判断用时+11.29至112.9万次整除判断用时
分组标记会发生重叠，以n个位标记，字符串长为m个字符元，重叠为k个“1”的概率计算公式是：

其中
句型分组标记会发生重叠，但属于小概率事件，因为数据库记录达10M，不会产生实质影响。
用VC独立编程模拟测试表明，一般情况下，在赛扬800的cpu上0.1-0.5秒能从400万条记录中查找出参考句型。语音输入中的参考句型一般只有5-7个音节，可以用第3项技术，结合位标记方法进行加速，最高可以提高检索速度30倍，该技术也申请了PCT。第4项相关技术也进入了PCT，此处不作介绍。据此推算，在高档cpu上0.1-0.5秒甚至更少时间可以搜索10M个句型，在未来3-5年内，0.1-0.5秒应能从4000万个句型、短语中比对出参考句型、短语。在64位的CPU中，筛选效果更好。

3.参考句型数量估计

每个参考句型越长，数据库参考句型数量越多，转换正确率越高。对于10M个句型的方案，如果给出200万条专有名词，则可以包含20万条地名、20万个机构、10万条人名、50万条书名、50万条动物、植物、化学等各学科名词，50万条名言、诗句、习语，可以想象，“固定词句”的覆盖面应该相当高。更重要的是其余800万个“非固定句型”的提炼。800万个句型的覆盖面有多大？由于语言研究的不足，没有关于汉语句型的资料，但我们可以做一个
估计：

一个人到30岁可以认为已经完全掌握了母语，能很好地表达自己的思想，理解他人的语言，阅读一般的报刊书籍。如果每天接触800个新的基本句型，到30岁算1万天，则共接触800万个基本句型。当然，各个人的知识结构不同，所掌握的基本句型是有差别的，相应的，我们也可以考虑对参考句型按学科进行分类，如通用600万条，文史200万条，科技200万条，报刊200万条，用户如果录入科技文章，则调入600万+200万的数据库。一个学科的分库200万句型约800万字，《人民日报》全年就是2000万字；800万字相当于20-30本教科书的容量，可以把一个专业的本科全部教材中每个句子包含进来。

我们再从另一个角度分析参考句型的数量：
汉语约400个音节，《现代汉语词典》约12000个汉字，平均每个音节30个汉字。双音节总量有400*400，《现代汉语词典》总词条56000，其中双音节词语约40000，据此估计汉语有意义的双音节词语及句型约60000条，平均每个双音节有15/40=0.375条；60000/400=150，则每个单音节平均可以扩展150个双音节词语。

三音节总量有400*400*400，有意义的三音节有多少？按单音节扩展双音节的150计算，则60000*150=9，000，000，该值可以看为有意义的三音节数量的最大值。按经验，双音节扩展为三音节的比例应小于150，我们取70-80，则有意义的三音节数量约420-480万条。除以400*400*400，则三音节有意义的概率约0.06-0.08。
高频音节约有200-300个汉字，高频双音节约有20个词语，所以高频三音节可能对应数个有意义的句型，需要继续扩展为四音节、五音节句型，但数量不会很大。

根据以上估计，800万个句型应能比较好的满足需要。随着cpu运算速度、存贮技术的提高，可以增加容错句型，解决口音问题。

4.参考句型提炼

汉语词语主要是动词、名词、形容词三类，搭配相应主要有三类：动词和名词、动词和形容词、名词和形容词。名词的数量很大，但名词中相当多是多字词，计算机容易识别处理。动词是语句的枢纽，又是语言中最灵活的词语，有资料认为现代汉语约有1200-2000个比较常用的动词；一般来说，动词是一两个汉字。所以，就计算机处理来说，提炼参考句型重点是动词，尤其是单字动词与其他词语的搭配，有的动词组句能力强，如，打：打电话、打牌、打扑克。但有的动词组句能力弱，如，跺：跺脚。

动词与名词的关系有动宾关系、主谓关系。动宾关系如：打电话、打牌、打扑克；跺脚。主谓关系如：兔子跑、敌人跑。“说*法语”可以形成主主谓关系：“他法语说得好”；也可以形成动宾关系：“他说法语”，因为算法的改进，参考句型数据库中“说*法语”只需出现一次。

动词与形容词的关系有动补关系、状谓关系。动补关系如：跑快：“他跑得很快！”状谓关系如：“认真学习”，而“他学习很认真”又是动补关系，“学习认真”可以认为是主谓关系，同样，句型数据库中“认真*学习”只需出现一次。

名词与形容词的关系有修饰关系、主谓关系。如：热天，天很热。参考句型数据库中“天*热”只需出现一次。
把“他说英语”作为一个基本句型，无疑利于计算机处理。但“主谓宾”俱全，会增加句型的数量，所以可以考虑，把“他说英语”切分为“他说”、“说英语”两个基本句型，同样的，有“我说”、“说法语”、“说阿拉伯语”等，则整体上可以减少基本句型的数量。随着计算机处理能力的提高，逐步扩大数据库句型数量。

再举2个例子说明“基于参考句型的语言处理方法”的优势：
微软拼音，如果我们想输入“十除以五等于二”，输入拼音“shichuyiwudengyuer”，出现的是：“使出义务等于二”。就是说，计算机不能正确选字。我提出的解决方案是，将“除以*等于/chuyi”“十*五*二/shiwuer”等作为搭配收入数据库作为“参考句型”。对于输入的“shichuyiwudengyuer”，迅速地从数据库中找出“chuyi/除以等于”“shiwuer/十五二”等“参考句型”，在多个“参考句型”中按“长词优先”的原则采用，应该可以提高“拼音串”到“字符串”转换的正确率。再如：如果我们想输入“568978”，输入拼音“wuliubajiuqiba”，如果数据库有“wuliuqi/5*6*7”“qibajiu/7*8*9”等，就可以处理。显然，“参考句型”越长越多，准确率越高。

如果我们说“dayin di bashijiu ye”，设在数据库中找到“打印第*页/dayindi*ye”作为参考句型，分析的处理为“打印第89页”，则有语音操作系统的功能了。

5.音字转换分析

对于汉语来说，三音节、四音节中，“同音多义”的概率越来越少，并且出现大量“有音无义”现象，所以我提出将将单音节词语、双音节词语，按语义搭配组成三、四字乃至五字以上的短语、句型，给出相应的拼音，建立数据库，根据这种数据库进行音字转换，以提高音字转换的正确率。但是对于拼音串“zheren de yingyu shuo de bu liuli”，用质数代换整除筛选，除了在数据库中找出“zheren*shuo*yingyu/这人说英语”、“yingyu*liuli/英语流利”、“bu*liuli /不流利”等参考句型之外，无疑会出现由这10个音节构成的、但不是我们所想要句型，比如“zhe*liyu/这利于”之类。我们会问，这种句型有多少，又如何从中找出我们想要的句型。

理论上，10个音节选3的排列有1000个，按上文分析，汉语中三音节有意义的概率应该小于0.06-0.08，也就是说，小于60-80个。汉语中tian和re可以构成“天热”“热天”，我们加*号标记为“tian*re/天*热”，但多数时候语序是不能调换，且中间不能插入其他词语。音为liyu的词语有“礼遇、利于、鲤鱼、俚语”，yuli词语有“渔利、余沥、余利、狱吏”，而“zheren de yingyu shuo de bu liuli”中yu和li有其他音节，所以“liyu”和“yuli”所有的8个词语均无效，由它们扩展构成的句型如“zhe*liyu/这利于”之类也无效，可以剔除。考虑语序计算，10个音节选3可构成的组合有120个，按上文分析的概率0.06-0.08，则有意义的句型为7-10个。用这些句型可能合成2-3个语句，可以用语法分析、频率确定最优、次优结果供用户选择，也可以通过上下文分析直接确定结果。

汉语中连续2个音节有意义的平均概率约为0.375，就“zheren de yingyu shuo de bu liuli”来说，其中“deying”“debu”“buliu”无意义，而yingyu的词有“英语、赢余、盈余、萦纡、硬玉”5个，liuli的词有“流利、流离、流丽、琉璃”4个。设数据库中没有“zheren*shuo*yingyu/这人说英语”，找到的最长句型是“yingyu”与“liuli”可以互证为“英语流利”，那么“yingyu”“liuli”与其它音节互证为4音节句型的概率有多大？

如果“liuli*shisuo/流利失所”、“sichu*liuli/四处流离”、“meiyou*yingyu/没有盈余”、“qude*yingyu/取得盈余”有n个。对于一个10音节的语句来说，减去“yingyu”、“liuli”4个音节，余下6个音节中出现“shi”或“suo”的平均概率约为6/400，同时出现“shi”“suo”的概率约为（6/400）*（5/400）=0.000188，而连续出现“shisuo”的概率只有于0.000188的几分之一。对于“sichu”也是如此。这些4音节句型的累计概率，是“长词优先”规则下计算机选错第1个句型的最高概率：0.000188*n。如果语句更长，出错的概率越大。不过，语音输入中如果考虑声调的话，出错的概率又会大幅减少。

更进一步，一个语句可以分解为多个重叠的句型，所以按“长词优先”的方法确定第一个句型后，可用“联想”的方法去确定其它句型，重叠部分越高，越可信。反之，参考句型的音节少、参考句型之间重叠不高，生成的语句可信度就低，可以排除。“我怕上学”可以分解为“我上学”“怕上学”两个3音节句型，如果输入“wopashangxue”，用“woshangxue/我上学”“pashangxue/怕上学”可以合成“我怕上学”，用“woshangxue/我上学”“pashang/爬上”则合成“我爬上学”。其中“我怕上学”的两个参考句型长、重叠高，更可信。并可以参考频率决定“基于参考句型”，由于采用的是“非连续音节的转移概率”，比“N元文法模型”采用的“连续音节的转移概率”，更符合语言的规律。

当然，“长词优先”只是一般原则，应用中还要考虑构成句型的音节是固定的还是灵活的，并结合统计频率、语法、语境进行决策。比如：理论上连续出现某3个音节的与随机出现某4个音节的概率相去不大，这时统计频率与语法、语境分析就有意义了。

其实，基于参考句型的语音输入算法也兼容了“分词算法”。如果把“他*毕业”、“明年六月”均列为参考句型，则“他明年六月毕业”这个句子，有2个可参考的基本句型。如果数据库中没有“明年六月”，则找到的是“他毕业”和“明年”“六月”，当然准确率会下降。

6.其它问题

1）内存使用量：10M句型，每个句型的位标记值4个byte，质数代换值8个byte，汉字串平均12个byte，频率1个byte，共25个byte，如果考虑10个byte的语法信息，则35个byte。语法信息可用压缩方式给出，总计需250-350M内存，对于高档微机可以接受。

低档微机，可以让部分高频句型常居内存，其余句型仅将位标记值W、质数代换值居留内存，对通过整除筛选的记录，从硬盘中读取其它信息，通常为1个语句10-15个汉字，参考句型一般3-5个汉字，找出30条参考句型，从中做语法分析得到10个有效句型应可完成处理。即使全部句型从硬盘中随机读取，30个扇区的数据用时也只500ms。通常语速每分钟为200-300个汉字，一个语句平均10个汉字，即每分钟20-30个语句，如果计算机处理1个语句用时0.5-1秒，有些慢，但可以接受。而且存贮、接口技术发展迅速，内存使用量不会构成太大问题。

对高端的用户，内存成本可以忽略，可以把句型数量扩大到20M ，程序设计采取一些方法，在确保响应时间低于0.5秒的前提下，争取使拼音到汉字转换准确率达到99%以上。由于参考句型越长，生成的语句准确率越高，生成一个语句需要查找的参考句型数量越少，读盘次数越少，只要位标记值W、质数代换值不超过内存限制即可，所以我们甚至可以考虑40M句型的方案：采用两次标记筛选加质数代换，需要40M*（4+4+8）byte=560M内存；全部居留内存，约需1600M，采取一些优化，约需1200M。

句型多，准确率高，就可以补偿声学模型的不足，发展容错功能，解决口音问题，提高语音输入的水平。如果语音输入的水平的真实准确率能98%以上，40M句型占用1600M内存，对于某些用户也是可以接受的，正如1万多元的电视机有市场一样。

2）声学模型问题。据报道，最近洛克菲勒大学数学物理实验室负责人马克罗•曼戈纳斯教授提出数学新算法为噪音分析提供了更佳途径。http://www.physorg.com/news69001445.html。

7.项目计划

1）申请美国、欧盟、日本、印度的专利，每个国家每项专利平均5万元，4项为20万元，合计80万元。资金充足，则申请所有人口5000万国家的专利。

2）软件开发计划分3步：
第1步：拼音输入软件
开发汉语处理软件，就是对汉语进行分析，提取10M个句型、短语、搭配。我设想的方案是：先收集网页、报刊光盘、扫描录入部分书籍，建一个1亿条语句的总库，再从总库中按2000个比较常用的动词提取语句建立2000个分库。对每个“动词”的分库，用名词、形容词、副词、量词进行扫描，得到该“动词”搭配这些词语的“基本句型”。汉语常用形容词约2000个，只需要对其中单字、双字形容词与单字、双字名词的搭配用同样方式处理。但计算机扫描的结果会出现不符合语义的搭配，需要人工确认。

a.进度
平均每篇文章3000字，约300个语句，平均每本书30万字，约3万个语句。1亿条语句需要30万篇文章，或3000本书。语料库要求学科、行业覆盖面广，比例合理，又要考虑语料提取的成本，多人同时收集如何减少无效的重复。方案设计1个月。

网上找文章需要浏览，并略做筛选、分类，每人每天100篇文章，需要3000个工作日，即30人3个月。报刊书籍光盘的文章质量较好，可以减少时间，但扫描录入书籍需要时间较多。如果公关能力强，从报社、出版社、图书馆取得更多的语料，可以节省时间。建库3个月。
也可以考虑写一个spider程序从网页上自动下载语料，自动下载语料的质量不如人工筛选，但成本低，可以通过增加语料库句型数量来弥补不足。

每个动词的分库假设100万条语句，每扫描一次及保存数据约需要0.5秒。搭配6万个词语，需要3万秒，除以3600秒=约9小时。每台微机每天处理2个动词的句型，50台微机共处理100个句型，20天处理完2000个动词。部分形容词也需要处理，再加10天。共1个月。如果某个搭配出现频率高于n，可以认为该词语与该动词是相关的。某个搭配出现频率低于n，该词语与该动词可能无语义关系，需要人工复核。如果20%需要人工复核，则有200万条需要人工复核，每人每天复核1000条，30人为3万条，一个月90万条，与计算机扫描同步进行。则句型提炼2个月。

产品化编程、句型数据库优化、语法分析3-6个月。

总进度：6个月左右可以大体判断该项目的前景，1年左右可以完成产品的开发。

b人员
一般本科生30人：需要熟练计算机操作，学习能力强。任务是收集文章，复核计算机扫描结果，帮助进行语法分析。月薪奖金3300元。共10万。
程序员5人：编程，执行计划，系统维护。月薪奖金5000-10000元。共4万。
语料库方案设计、语法分析方案设计人员：5人。月薪奖金6000元。共3万。
10+4+3=17万/月。

a.资金
月总工资17万。
房租、办公费用、上网费用每人每月1500元*40人=6万。
17万+6万=23万。

半年23*6=138万。
全年23*12=276万。

50台微机*6000元=30万。
4万图书资料费。
专利申请80万
276+30+4+80=390万
考虑留有余地，则500万比较可靠。上海的成本较高，如果落户其它地方，成本就会比较低，

资金回收：用1000万个句型交叉重叠，毫无疑问准确率会超过目前任何一种拼音输入法。拼音输入正确率如果能达到99%，可以每套50元进入市场，销售10万套收回成本。那么这么多免费的拼音输入法的情况下，如何定价销售？
我的看法是，除非从社会效益着眼，得到国家资助开发，免费发行之外，商业化运行，卖10元20元，就不如卖50元100元，着眼高端用户、政府、企业采购。当然，对于某些公司来说，投入资金开发成产品，以卓越的性能淘汰所有的拼音输入法，免费发行，提高公司知名度，就当广告费投入，也未尝不可。
当然，本技术的盈利点不是拼音输入，而是作为良好的语言模型与适当的声学模型结合，提高语音输入的水平。

第2步：语音输入软件
本语言模型“兼容了分词方法”并“部分兼容了N元统计模型”，就拼音输入来说，转换准确率应该高于95%。如果直接用参考句型能把拼音到汉字准确率提高到97%，这个语言模型的效果就很好，再进行语法分析有希望将准确率再提高2%，达到99%，可以很好地占领市场。如果这个语言模型的最终效果能达到99.5%，则绝对占领市场。
在软件开发中，可以测试1000万、2000万 、4000万句型以及分学科的不同方案。总之，希望某个方案能将整句输入准确率提高到99%以上，树立品牌，满足某些高端用户的需要。

美国有评论，语音输入准确率每提高0.5%，就是几十亿美元的市场，虽然在中国不能这样乐观，但前景还是很好的。语音输入需要考虑声学模型的水平，如果本语言模型能达到99.5%的正确率，则可以补充声学模型的不足，校正声学模型的某些错误。另外，语音输入中声调、停顿是有助于提高准确率的。开发语音输入软件，需要语音实验设备、语音实验人员、方言分析人员，可以考虑同其它公司合作。
语音输入软件真实准确率如果达到99%，可以销售每套1000元。如果达到97%，可以销售每套200-500元。
第3步：语音输入软件如果效果好，可以同office捆绑销售，进一步向语音操作系统、人工智能发展。

8.参与方式

1）欢迎社会各界以独资、联合投资及其它任何方式投入资金。
经过一段时间的网上讨论分析，为分散风险，用10万元*50手=500万元的方式小额集资运作也是可以的，我保证所有资金会得到合理的利用，但不能保证一定盈利，这一点投资者务必有清醒的认识。

2）欢迎社会各界提供语料。
语料可以是任何行业、任何学科的可公开的文件；可以是整篇文章，也可以是文章的一部分；有重要内容的文件请勿提供，我未必能很好地控制文件的流转；最好是word或txt格式，词语、书名、机构名等以数据库提供更好，无密码的压缩文档也可。请以附件方式发给联系信箱。对于提供语料的朋友，我本人深表谢意。

3）欢迎业界参与讨论分析，推进技术的发展。
对于提出了有益建议的朋友，如果这个项目运作成功，我会在适当的时机邀请加盟。

hztj

难得难得，谢谢站长！

hztj

NP问题之质数代换、位标记解法探讨

数学上著名的NP问题，完整的叫法是NP完全问题，也即“NP COMPLETE”问题，简单的写法，是 NP=P？的问题。问题就在这个问号上，到底是NP等於P，还是NP不等於P。证明其中之一，便可以拿百万美元大奖。 这个奖还没有人拿到，也就是说，NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。 NP里面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。 什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢？这样的公式是没有的。再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少？也没有这样的公式。 这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。 完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。 人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们於是就猜想，是否这类问题，存在一个确定性算法，可以在指数 时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。 解决这个猜想，无非两种可能，一种是找到一个这样的算法，只要针对某个特定NP完全问题找到一个算法，所有这类问题都可以迎刃而解了，因为他们可以转化为同一个问题。另外的一种可能，就是这样的算法是不存在的。那么就要从数学理论上证明它为什么不存在。 前段时间轰动世界的一个数学成果，是几个印度人提出了一个新算法，可以在多项式时间内，证明某个数是或者不是质数，而在这之前，人们认为质数的证明，是个非多项式问题。可见，有些看来好象是非多项式的问题，其实是多项式问题，只是人们一时还不知道它的多项式解而已。


上回说到可怜的旅行商想找出走遍所有城市的最短路径。让我们用计算机帮他搜索一下。这就需要用到本篇文章中要介绍的第一门学科了：《人工智能》。人类的许多活动，如解算题、猜谜语、进行讨论、编制计划和编写计算机程序，甚至驾驶汽车和骑自行车等等，都需要"智能"。如果机器能够执行这种任务，就可以认为机器已具有某种性质的"人工智能"。现在我们就要利用人工智能，用计算机模拟人的思维来搜索最短路径。想像一下，我们人思考问题时，有两种方法：一种是精确搜索，就是试验所有的可能性，找出最精确的一个方案。但它在搜索过程中不改变搜索策略，不利用搜索获得的中间信息，它盲目性大，效率差，用于小型问题还可以，用于大型问题根本不可能；另一种叫做启发式搜索，它在搜索过程中加入了与问题有关的启发性信息，用以指导搜索向着一个比较小的范围内进行，加速获得结果。对于旅行商问题这种NP完全问题，精确式搜索是不可能实现的，只能采用下面的几种启发式搜索方法：
1.        近邻法(nearest neighbor)推销员从某个城镇出发，永远选择前往最近且尚未去过的城镇，最后再返回原先的出发点。这方法简单，也许是多数人的直觉做法，但是近邻法的短视使其表现非常不好，通常后段的路程会非常痛苦。
2.        插入法(insertion) 先产生连接部分点的子路线，再根据某种法则将其它的点逐一加入路线。比如最近插入法(nearest insertion)，先针对外围的点建构子路线，然后从剩余的点里面评估何者加入后路线总长度增加的幅度最小，再将这个点加入路线。又比如最远插入法(farthest，insertion)，是从剩余的点里面选择距离子路线最远的点，有点先苦后甜的滋味。
3.        模拟退火算法(Recuit Algorithm)模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。
4.        遗传算法遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法，从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。 生物种群的生存过程普遍遵循达尔文进化准则，群体中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程的结果反映在个体的结构上，其染色体包含若干基因，相应的表现型和基因型的联系体现了个体的外部特性与内部机理间逻辑关系。通过个体之间的交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码，仍叫染色体，有时也叫个体；适应能力是对应着一个染色体的一个数值来衡量；染色体的选择或淘汰则按所面对的问题是求最大还是最小来进行。
5.        神经网络算法根据一个简化的统计，人脑由百亿条神经组成 — 每条神经平均连结到其它几千条神经。通过这种连结方式，神经可以收发不同数量的能量。神经的一个非常重要的功能是它们对能量的接受并不是立即作出响应，而是将它们累加起来，当这个累加的总和达到某个临界阈值时，它们将它们自己的那部分能量发送给其它的神经。大脑通过调节这些连结的数目和强度进行学习。尽管这是个生物行为的简化描述。但同样可以充分有力地被看作是神经网络的模型。看了上面的介绍是不是已经眼冒金星，哈欠连天了？其实这些还都只是些理论模型，要想用计算机程序来实现，还需要大量更加枯燥乏味的工作。

以上文字摘自网页。
“基于参考句型的语言算法” 有效地解决了“结构化语言处理”的“语句生成算法”，为NP问题的解决提供了一种新思路，下面就有100个城市的旅行商问题，探讨质数代换、位标记解法：

100个城市用《千字文》中前100个字代表：
天地玄黄　宇宙洪荒　日月盈昃　辰宿列张　寒来暑往；
秋收冬藏     闰馀成岁　律吕调阳　云腾致雨　露结为霜；
金生丽水　玉出昆冈     剑号巨阙　珠称夜光　果珍李柰；
菜重芥姜　海咸河淡　鳞潜羽翔  龙师火帝　鸟官人皇；
始制文字　乃服衣裳　推位让国　有虞陶唐     吊民伐罪。

100个城市联接的路径有100！/2！（100-2）！=4950条，从短至长，以2、3、5、7、11…48023共4950个质数代表。

天陶        2
黄月        3
列玄        5
天盈        7
…        …
吕水        48023

1个质数代表一条路径，连接2个城市，如2连接天、陶2个城市，通过“陶”又连接“天”之外的98个城市，即98条路径，98个质数。下一步将2与“陶”通网的其他98条路径之98质数相乘，不排序：

城市        Fn
天陶地        2*151
天陶月        2*1567
天陶玄        2*35531
天陶辰        2*271
…        …
       

这样共有4950*98=485100个质数乘积Fn。

最理想的情况下是确有一条由Ft=2*3*5*…*541共m=100个质数构成的路径，能连通所有的城市，如果是这样，我们以Ft为被除数，以485100个Fn为除数，用整除判断可以筛选出这些路径，如果这样“天陶地/251”显然入选。
但出现这样理想的路径概率很少，所以我们得留有余地，用Ft=2*3*5*…*1223共m=200个质数作被除数，以485100个Fn为除数，用整除判断筛选出Ft/Fn=0的记录，得到R1。对R1进行分析：1.首先检查“城市”一栏是否包含所有的100个城市。2.检查这些Fn是否可以连通所有的城市，这个算法需要探讨。而m取值多少，或者说留多大的余地最合理，也值得探讨。大数整除判断的方法也值得探讨。另一个问题是质数乘积最少的路径是否一定是质数和最少的路径。

大数整除判断也是费时的运算，按语言处理中的方法，我们也可以用位标记进行预处理以提高速度。分4950为64组，每组有4950/64=77个质数。用64个bit 标记，第1个bit对应2-389共77个质数，第2个bit对应397-887共77个质数，如此类推。如果经过分析用用Ft=2*3*5*…*1223共m=200个质数作被除数最合理，将第1、2、3个bit标记为1，即Wt=7。
用Wt和Wn进行逻辑比较可以筛选出77*3=231个最小质数相乘得到的Fn，再用质数整除判断。