Step 1 更新到4.2
如果你的Wii買回來已經是4.2，以下內容可以不理，可直去下面Step 2，如果你的Wii還是4.1或以下，請跟著做，如果是3.0以下，請用碟更新到3.0以上，例如Mario Kart可以直上3.2
又如果你的Wii是4.2，但安裝左好多不明的IOS或cIOS，重新做一次也可以，但要把4.2用的bannerbomb替換到 update.zip 內，否則無法運行Banner Bomb！
原則上4.1和4.2分別不大，4.2主要是封殺非官方軟件的使用，當然今時今日已經全破了，教學指定要升上4.2的原因係統一方法，減少出錯及問題而己！
官方Wii System 4.3 已出，專業區用家請勿線上更新！按我 (2010年6月23日消息)
準備一張SD卡，非SDHC及最好有1G以上空位
日版機專用update.zip
美版機專用update.zip
歐版機專用update.zip
首先下載你所屬的 update.zip 檔案，然後解壓到SD卡，再放到Wii裡去
安裝 The Homebrew Channel Bootmii
使用 bannerbomb 方法來安裝，首先放上SD記憶卡後，到Wii Option (菜單) > Data Management (資料管理) > Channels (頻道)> SD Card (SD卡), 然後Wii 會查問你是否執行 "Load boot.elf?" , 揀 'Yes' 後會進入 Hackmii installer 程序
如果不行，沒有跳出來問你，可以到Banner Bomb官網 的第6點，試用其它版本的破解文件，替換private資料夾即可，因為不同主機可能需要不同破解文件！
然後 Hackmii Installer 會出來，跟著指示安裝 Homebrew Channel, DVDX [optional], Bootmii as boot2 或 IOS .
真正開始更新你的Wii
於The Homebrew Channel執行 Yet Another WAD Manager Mod
現在開始千萬不要亂來跳Step，否則後悔終生
選單向下 尋找及安裝(install)以下wad檔:
用 + 來揀選 IOS70-64-v6687.wad
及 System Menu-NUS-v480.wad [NTSC-J(日) = v480;NTSC-U(美) = v481; PAL(歐) = v482] (只安裝你要的那個，錯區就玩完)
然後按 A 安裝
然後再用 + 來揀選安裝其它 22 個不同的 IOS 檔案 及 Shopping Channel-NUS-v18.wad，然後按 A 安裝，理論上應該有23個檔案要你安裝，之後按 Home 離開即可
完成
現在你可以清空你的SD Card了
Step 2 破解4.2
準備一張SD卡，非SDHC及最好有1G以上空位
如果你是Step 1 過來的，請一定要先清空你的SD卡，當然有理無理都清空佢係最好的
首先下載 modify.zip 檔案，然後解壓到SD卡，再放到Wii裡去 (12-12-2010更新)
安裝 The Homebrew Channel & Bootmii
如果你Step 1已經安裝好，再安裝多一次亦無不可，好處係呢個係新的HBC v1.0.8，原則上唔再裝，跳step都可以！
使用 bannerbomb 方法來安裝，首先如下圖點選 SD Card 然後揀 yes to load boot.dol/elf
如果不行，沒有跳出來問你，可以到Banner Bomb官網 的第6點，試用其它版本的破解文件，替換private資料夾即可，因為不同主機可能需要不同破解文件！
然後 Hackmii Installer 會出來，跟著指示安裝 Homebrew Channel, DVDX [optional], & Bootmii as boot2 或 as IOS .
Bootmii 可做可唔做，做左就好似買左保險咁，多份保障而己
先來個 NAND backup 吧
可做可唔做，做左就好似買左保險咁，多份保障而己
重開Wii後，如果BootMii係 installed as boot2，咁樣BootMii係會自動出來的！
如果 Bootmii 係 installed as IOS，咁樣你就要去 HBC 按Home鍵，揀選Launch Bootmii啦
按 3 次開機鍵power去到最尾的選項 然後按 reset 鍵，當然如果你有GC手掣就方便得多啦
按reset 去揀第一個選項，然後跟著指示去 make your NAND backup，遇見Bad blocks可以不理
做完後用電腦抄起 Bootmii 資料夾, NAND.bin, & keys.bin ，之後係SD卡上刪去呢幾個檔案(改名亦可)
返回The Homebrew Channel
安裝 Trucha 漏洞
執行 MMM [Multi-Mod Manager]
揀選 install & patch IOS36
揀選 Express mode 全部揀 A 直至安裝完為止!
刪除不應該存在的 IOS
揀選Remove stubbed IOS，然後按A，你只需要刪除 IOS 222, 223, 249, 250, 254.，其它可以不理！
安裝 cIOS 及 修改System Menu IOS
執行 WAD Manager
安裝你有需要用到的 IOS 檔，可按 1 掣來一次過安裝全部的IOS (紅色為必需)
各 IOS 用途
IOS70-64-v6687[TB+ES_diV+NAND].wad
System 4.2的破解版
cIOS202[57]-v5.wad
cIOS222[38]-v5.wad
cIOS223[37]-v5.wad
cIOS224[57]-v5.wad
cIOS249[56]-v20.wad
cIOS250[37]-v20.wad
以上都係cIOS，玩USB Loader/NeoGamma都需要用到，理論上必裝，否則你破解來做什麼
IOS56-64-v5662.wad
Shopping Channel-NUS-v20
如果需要上 Shop Channel的，以上兩個都要安裝
NeoGamma_Forwarder.wad
USB_Loader_WiiFlow_Forwarder.wad
以上兩個是主力玩備份遊戲的Forwarder，讓你不用每次都先到HBC，可裝可不裝，隨自己喜歡
最後按 home 離開.
教學視頻
啟用 System Menu Hacks
可做可唔做，我自己就無做啦
執行 Priiloader 去安裝 preloader 去你部Wii.
啟用 (Enable) desired hacks 及去 settings 揀 make to use the system menu IOS.
先下載所需的 dol 檔
Wii Sport Resort 日文版:
Wii Sport Resort 中文版:
Wii Sport Resort 美國版:
以USB Loader GX 為例子，解壓 dol 檔到根目錄，然後於setting揀選 Alternate DOL: ON 就可以 (緊記Error 002 fix 也要on啊)
以NeoGamma為例，解壓 dol 檔到NeoGamma目錄，然後於setting揀選 Set "Alternate dol" to DISC、Set "002 Fix" to YES、And set "Save Config" to YES即可，當進入遊戲前，會要求你揀選你要使用的 dol 檔，揀好後就可開始遊戲
基本上只需進行第一次遊戲時使用 Alternate DOL: ON ，第二次開始可以揀回 Alternate DOL: OFF即可！
Q and A
Q: 係咪一定要上4.2？
A: 唔一定，原則上1.0裝晒所有必需的IOS都可以玩晒全部Game，教學用4.2係方便統一大家的版本而己，你喜歡的話用3.2，4.0都無問題
Q: 我見有中文化的MENU，用唔用好？
A: 任何修改主機的方法都係有風險的，為了看中文而增加風險，在我個人意見，當然唔值得，不過你係都要裝，當然無話唔得！
Q: Error001點解決？
A: Error001係指Wii主機查到你有改機晶片，最簡單的方法係查下你粒改機晶片有無得更新防001，例如Wiikey 的1.9s，又或拆番粒改機晶片出來！
Q: 點解改完機入碟落部Wii，佢又叫我更新？
A: 因為你改機後，變相好多IOS都係舊版，如果你唔想見到d更新，可以用preloader修改，又或睇下你粒choips有無得block update，不過我會建議你唔好用原裝的 disc channel load碟就算，因為咁係最簡單！
Q: 如果不幸部機壞左，例如讀唔到碟之類，點樣還原比番代理？
A: 上網更新一次就會還原官方的了，你唔講你改過，邊個知
Q: 用USB Loader，應該插邊個USB頭？
A: 插靠近機底果邊果個
Q: 買咩HDD好？
A: 基本上買大牌子如 Buffalo、Imation、MAXTOR 都99%得，如果真係怕，建議去電腦商場如黃金旺電等，然後再問問鋪頭邊隻可以比Wii用，問定佢唔得可唔可以換貨，有部分好人d的鋪頭或專業d的鋪頭應該會幫到你！
Q: USB Loader 有咩壞處？
A: 已知CAPCOM會針對USB Loader上網玩Monster Hunter 時 ban account，估計主要為對付使用金手指的使用者而出手，但CAPCOM只能分辨你係咪用正版，所以會有機會有殺錯，無放過而被(CAPCOM)禁止上線
Q: 我係韓版機，又好想上4.2，點算？
A: 原則上4.1都可以玩遊戲的，但你死都要上4.2，可以試試用 cIOScorp 3.6 來 install cIOS70 ，然後再裝 4.2 menu，係唔重開機的情況下，一口氣係HBC裝埋priiloader就可以了，過程比較複雜，有興趣可以去google 找找外國文章，關鍵字已經比晒你，亦肯定係work的，不過煩而己！
2010年12月26日星期日
2010年11月23日星期二
中文分词以及索引的时候为什么要分词
全文检索lucene中文分词的一些总结
2010-03-23 14:53
全文检索几乎是所有内容管理系统软件（CMS）必备的功能，在对公司的CMS产品的开发维护过程中，全文检索始终是客户重点关注的模块，为满足客户各式各样越来越高的要求，对全文检索曾做过一段时间相对深入的研究，尤其是对分词机制，趁如今换工作比较空闲之际做个简单总结。
1、 什么是中文分词
学过英文的都知道，英文是以单词为单位的，单词与单词之间以空格或者逗号句号隔开。而中文则以字为单位，字又组成词，字和词再组成句子。所以对于英文，我们可以简单以空格判断某个字符串是否为一个单词，比如I love China，love 和 China很容易被程序区分开来；但中文“我爱中国”就不 一样了，电脑不知道“中国”是一个词语还是“爱中”是一个词语。把中文的句子切分成有意义的词，就是中文分词，也称切词。我爱中国，分词的结果是：我 爱 中国。
目前中文分词还是一个难题———对于需要上下文区别的词以及新词（人名、地名等）很难完美的区分。国际上将同样存在分词问题的韩国、日本和中国并称为CJK(Chinese Japanese Korean)，对于CJK这个代称可能包含其他问题，分词只是其中之一。
2、 中文分词的实现
Lucene自带了几个分词器WhitespaceAnalyzer， SimpleAnalyzer， StopAnalyzer， StandardAnalyzer， ChineseAnalyzer， CJKAnalyzer等。前面三个只适用于英文分词，StandardAnalyzer对可最简单地实现中文分词，即二分法，每个字都作为一个词，这样分出来虽然全面，但有很多缺点，比如，索引文件过大，检索时速度慢等。ChineseAnalyzer是按字分的,与StandardAnalyzer对中文的分词没有大的区别。 CJKAnalyzer是按两字切分的, 比较武断,并且会产生垃圾Token，影响索引大小。以上分词器过于简单，无法满足现实的需求，所以我们需要实现自己的分词算法。
现有的中文分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。后面两者只是听说过，没深入接触过，这里着重讲下基于字符串匹配的分词方法。
基于字符串匹配的分词方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机 器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不 同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化 方法。常用的几种机械分词方法如下：
1）正向最大匹配法（由左到右的方向）；
2）逆向最大匹配法（由右到左的方向）；
3）最少切分（使每一句中切出的词数最小）。
这种分词方法，首先要有一个词库。一个好的分词器需要一个庞大优良的词库以及设计优秀的数据结构来缓存该词库。下面使用一个名为MMAnalyzer的开源分词器做简单的分词演示，然后大致讲下怎么样基于lucene实现自己的分词器。MMAnalyzer 简介：
1、支持英文、数字、中文（简体）混合分词
2、常用的数量和人名的匹配
3、超过22万词的词库整理
4、实现正向最大匹配算法
5、词典的动态扩展
6、分词效率： 第一次分词需要1－2秒（读取词典），之后速度基本与Lucene自带分词器持平。内存消耗： 30M+
MMAnalyzer的分词算法如下：
1、读取一个字，然后联想，直到联想到不能为止。如果当前可以构成词，便返回一个Token。
2、如果当前不能构成词语，便回溯到最近的可以构成词语的节点，返回。
3、最差的情况就是返回第一个单字。
4、然后从返回结果的下一个字重新开始联想。
public static void main(String[] args) throws IOException {
String text = "2008年前三季度，美国次贷危机升级，全球金融持续动荡，世界经济增长全面放缓，全球经济增长动力减弱，世界主要经济体与新兴市场正面临巨大的外部冲击。";
Analyzer analyzer = new MMAnalyzer();
TokenStream stream = analyzer.tokenStream("xxx", new StringReader(text));
while (true) {
Token token = stream.next();
if (token == null) break;
System.out.print("[" + token.termText() + "] ");
}
}
返回结果如下：
[2008] [年前] [三季度] [美国] [次] [贷] [危机] [升级] [全球] [金融] [持续] [动荡] [世界经济] [增长] [全面] [放] [缓] [全球] [经济] [增长] [动力] [减弱] [世界] [主要] [经济] [体] [新兴] [市场] [正] [面临] [巨大] [外部] [冲击]
MMAnalyzer分词器有两个构造函数MMAnalyzer()和MMAnalyzer(int n)。
MMAnalyzer():采用正向最大匹配的中文分词算法，相当于分词粒度等于0。
MMAnalyzer(int n):参数为分词粒度：当字数 >= n，且能成词，该词就被切分出来。
另外MMAnalyzer还有以下常用方法：
addDictionary(FileReader reader)：增加一个新词典，采用每行一个词的读取方式。
addWord(String newWord)：往词库里新增加一个新词。
其中addWord方法测试了好像只会把新词加入到缓存了的词库中，并不会并永久性写入词典文件中。如果需要写入词典文件，可再按以下方法处理。
URL dictionaryPath = URLUtil.getResourceFileUrl("resources/dictionary.txt");
if(dictionaryPath != null){
// new FileWriter(String, boolean) 第二个参数true表示追加文件到尾部
BufferedWriter bw = new BufferedWriter(new FileWriter(dictionaryPath.getPath(), true));
bw.write(searchStr);//追加文件内容
bw.newLine();
bw.close();
}
当然也可自己实现分词器，实现过程很简单，首先实现一个Tokenizer（需要继承lucene包里的Tokenizer抽象类），覆写里面的next()方法，这也是lucene分词器实现的最关键的地方。然后再实现一个Analyzer（需要继承lucene包里的Analyzer抽象类），将上面实现的Tokenizer指定给该Analyzer。
3、 中文分词一些常见问题及解决办法
3.1 分词的缺失
比如同义词。用户搜 "北京 饭店" 能不能把" 首都 饭店"也列出来呢？ 这个分词器无能为力。所以这个问题，解决办法就只能是在分词之前，我们再加一层：同义词返回模块。这个思路很不错，也比较简单，很容易实现。关键是词库的建立。
3.2 优先级
例如：我还清晰地记得我们坐在江边聊天的情境。
分出来是： 我 还清 晰 地 记得 我们 坐在 江边 聊天 的 情境。
结果： 清晰 被拆开了。
这个是基于词库的分词算法固有的问题。没有很好的解决方法。有统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。有一种解决方案是正向匹配结果后再逆向匹配一次，然后比较结果，消除歧义。最好加入词汇概率统计功能.有歧义的用概率决定。
3.3 最大匹配的问题
比如搜索“三季度”这个词，词库里同时有 “三季度” 和 “季度”这两个词，分词时按最大正向匹配 则 “三季度” 被分成一个完整的词，按 “季度” 去检索反而搜不出来了。
解决办法：缩短分词粒度，当字数等于或超过该粒度参数，且能成词，该词就被切分出来。
3．4 新词识别
新词，也就是那些在字典中都没有收录过，但又确实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州了”中，“王军虎”是个词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把“王军虎”做为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的人名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存在问题，例如：在句子“王军虎头虎脑的”中，“王军虎”还能不能算词？
新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。
其他的还有如热度、高亮显示等问题。总言之，中文分词机制的好坏，直接影响到用户对搜索结果的满意度，所以如何分词是搜索引擎的重中之重。
2010-03-23 14:53
全文检索几乎是所有内容管理系统软件（CMS）必备的功能，在对公司的CMS产品的开发维护过程中，全文检索始终是客户重点关注的模块，为满足客户各式各样越来越高的要求，对全文检索曾做过一段时间相对深入的研究，尤其是对分词机制，趁如今换工作比较空闲之际做个简单总结。
1、 什么是中文分词
学过英文的都知道，英文是以单词为单位的，单词与单词之间以空格或者逗号句号隔开。而中文则以字为单位，字又组成词，字和词再组成句子。所以对于英文，我们可以简单以空格判断某个字符串是否为一个单词，比如I love China，love 和 China很容易被程序区分开来；但中文“我爱中国”就不 一样了，电脑不知道“中国”是一个词语还是“爱中”是一个词语。把中文的句子切分成有意义的词，就是中文分词，也称切词。我爱中国，分词的结果是：我 爱 中国。
目前中文分词还是一个难题———对于需要上下文区别的词以及新词（人名、地名等）很难完美的区分。国际上将同样存在分词问题的韩国、日本和中国并称为CJK(Chinese Japanese Korean)，对于CJK这个代称可能包含其他问题，分词只是其中之一。
2、 中文分词的实现
Lucene自带了几个分词器WhitespaceAnalyzer， SimpleAnalyzer， StopAnalyzer， StandardAnalyzer， ChineseAnalyzer， CJKAnalyzer等。前面三个只适用于英文分词，StandardAnalyzer对可最简单地实现中文分词，即二分法，每个字都作为一个词，这样分出来虽然全面，但有很多缺点，比如，索引文件过大，检索时速度慢等。ChineseAnalyzer是按字分的,与StandardAnalyzer对中文的分词没有大的区别。 CJKAnalyzer是按两字切分的, 比较武断,并且会产生垃圾Token，影响索引大小。以上分词器过于简单，无法满足现实的需求，所以我们需要实现自己的分词算法。
现有的中文分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。后面两者只是听说过，没深入接触过，这里着重讲下基于字符串匹配的分词方法。
基于字符串匹配的分词方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机 器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不 同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化 方法。常用的几种机械分词方法如下：
1）正向最大匹配法（由左到右的方向）；
2）逆向最大匹配法（由右到左的方向）；
3）最少切分（使每一句中切出的词数最小）。
这种分词方法，首先要有一个词库。一个好的分词器需要一个庞大优良的词库以及设计优秀的数据结构来缓存该词库。下面使用一个名为MMAnalyzer的开源分词器做简单的分词演示，然后大致讲下怎么样基于lucene实现自己的分词器。MMAnalyzer 简介：
1、支持英文、数字、中文（简体）混合分词
2、常用的数量和人名的匹配
3、超过22万词的词库整理
4、实现正向最大匹配算法
5、词典的动态扩展
6、分词效率： 第一次分词需要1－2秒（读取词典），之后速度基本与Lucene自带分词器持平。内存消耗： 30M+
MMAnalyzer的分词算法如下：
1、读取一个字，然后联想，直到联想到不能为止。如果当前可以构成词，便返回一个Token。
2、如果当前不能构成词语，便回溯到最近的可以构成词语的节点，返回。
3、最差的情况就是返回第一个单字。
4、然后从返回结果的下一个字重新开始联想。
public static void main(String[] args) throws IOException {
String text = "2008年前三季度，美国次贷危机升级，全球金融持续动荡，世界经济增长全面放缓，全球经济增长动力减弱，世界主要经济体与新兴市场正面临巨大的外部冲击。";
Analyzer analyzer = new MMAnalyzer();
TokenStream stream = analyzer.tokenStream("xxx", new StringReader(text));
while (true) {
Token token = stream.next();
if (token == null) break;
System.out.print("[" + token.termText() + "] ");
}
}
返回结果如下：
[2008] [年前] [三季度] [美国] [次] [贷] [危机] [升级] [全球] [金融] [持续] [动荡] [世界经济] [增长] [全面] [放] [缓] [全球] [经济] [增长] [动力] [减弱] [世界] [主要] [经济] [体] [新兴] [市场] [正] [面临] [巨大] [外部] [冲击]
MMAnalyzer分词器有两个构造函数MMAnalyzer()和MMAnalyzer(int n)。
MMAnalyzer():采用正向最大匹配的中文分词算法，相当于分词粒度等于0。
MMAnalyzer(int n):参数为分词粒度：当字数 >= n，且能成词，该词就被切分出来。
另外MMAnalyzer还有以下常用方法：
addDictionary(FileReader reader)：增加一个新词典，采用每行一个词的读取方式。
addWord(String newWord)：往词库里新增加一个新词。
其中addWord方法测试了好像只会把新词加入到缓存了的词库中，并不会并永久性写入词典文件中。如果需要写入词典文件，可再按以下方法处理。
URL dictionaryPath = URLUtil.getResourceFileUrl("resources/dictionary.txt");
if(dictionaryPath != null){
// new FileWriter(String, boolean) 第二个参数true表示追加文件到尾部
BufferedWriter bw = new BufferedWriter(new FileWriter(dictionaryPath.getPath(), true));
bw.write(searchStr);//追加文件内容
bw.newLine();
bw.close();
}
当然也可自己实现分词器，实现过程很简单，首先实现一个Tokenizer（需要继承lucene包里的Tokenizer抽象类），覆写里面的next()方法，这也是lucene分词器实现的最关键的地方。然后再实现一个Analyzer（需要继承lucene包里的Analyzer抽象类），将上面实现的Tokenizer指定给该Analyzer。
3、 中文分词一些常见问题及解决办法
3.1 分词的缺失
比如同义词。用户搜 "北京 饭店" 能不能把" 首都 饭店"也列出来呢？ 这个分词器无能为力。所以这个问题，解决办法就只能是在分词之前，我们再加一层：同义词返回模块。这个思路很不错，也比较简单，很容易实现。关键是词库的建立。
3.2 优先级
例如：我还清晰地记得我们坐在江边聊天的情境。
分出来是： 我 还清 晰 地 记得 我们 坐在 江边 聊天 的 情境。
结果： 清晰 被拆开了。
这个是基于词库的分词算法固有的问题。没有很好的解决方法。有统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。有一种解决方案是正向匹配结果后再逆向匹配一次，然后比较结果，消除歧义。最好加入词汇概率统计功能.有歧义的用概率决定。
3.3 最大匹配的问题
比如搜索“三季度”这个词，词库里同时有 “三季度” 和 “季度”这两个词，分词时按最大正向匹配 则 “三季度” 被分成一个完整的词，按 “季度” 去检索反而搜不出来了。
解决办法：缩短分词粒度，当字数等于或超过该粒度参数，且能成词，该词就被切分出来。
3．4 新词识别
新词，也就是那些在字典中都没有收录过，但又确实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州了”中，“王军虎”是个词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把“王军虎”做为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的人名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存在问题，例如：在句子“王军虎头虎脑的”中，“王军虎”还能不能算词？
新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。
其他的还有如热度、高亮显示等问题。总言之，中文分词机制的好坏，直接影响到用户对搜索结果的满意度，所以如何分词是搜索引擎的重中之重。
2010年11月17日星期三
软件测试
软件测试
培训目的
什么是软件测试
如何做好软件测试
什么是软件测试
软件测试是以发现软件的缺陷为目的，使软件运行，将软件运行中所产生的危险性降低到允许的范围，是一个为发现错误而执行程序的过程
软件的缺陷是对软件产品预期属性的偏离现象。包括对产品规格说明书的偏离；对客户/用户的期望的偏离，客户/用户的要求没有纳入软件产品中（可能是产品规格说明书说明时的遗漏,也可能是软件实现的问题）。
软件测试的几个基本概念
单体测试：是指对单个模块或者是一个函数等更小单位的测试
集成测试：是指多个模块组合起来，或者一个子系统的所有模块都结合起来后进行的测试
系统测试：是指整个系统的所有子系统都结合起来以后进行的测试
回归测试：是指修复或调整好软件环境之后进行测试
差分测试：是指当测试时间较短时（不足以进行一遍系统测试时），而只对整个系统中新变更或者新追加功能的相关部分的测试
手动测试：是指测试人员，根据功能规格说明书、编写的测试大纲或者其他测试文档，直接运行程序而完成的测试
自动化测试：是指测试人员，使用自动测试工具、或者编写测试脚本，让程序自动运行而进行的测试
软件产品周期简介
根据需求文档进行分析制定测试策略和测试计划
分别根据需求分析、概要设计和详细设计的输出进行测试设计
使用测试设计文档，进行各个阶段的测试执行
产品Release之后进行测试工作的总结
当软件产品周期，需求文档变化时，将重新进行前三个工作
测试计划的制定
主要输入：需求文档和里程碑
主要输出：测试进度的制定和采取的测试策略
测试进度内容包括测试设计开始和结束的时间，测试执行的开始和结束时间，测试总结开始和结束时间，还包括测试设计、测试执行和测试总结所花费的工作量
测试策略内容包括采取测试方法、测试资源的分配和测试中风险的控制计划
测试设计
根据测试阶段的不同，测试设计包括以下几种
系统测试的测试设计
集成测试的测试设计
性能测试的测试设计
单体测试的测试设计
其中单体测试的测试设计由开发人员完成，其他一般情况下由测试人员完成
系统测试、集成测试的 测试设计
CheckList的编写
根据需求分析文档得到软件产品应该包括的功能点（包括大小功能点），组成CheckList的第一部分，要求CheckList必须覆盖软件产品应该包括的全部功能点
理解需求分析文档得到每个功能点的细化部分，组成CheckList的第二部分，要求覆盖需求文档中所有可测试的内容
根据测试经验和业务知识，进一步分析需求分析文档，得到需求分析文档上没有描述的内容，补充CheckList的第二部分
对每个功能点的细化部分，确定其测试方法（或者测试步骤）和预计的正确测试结果
测试用例的编写
需要特殊条件才能测试的功能点，编写测试用例以对应
编写一些测试用例，以覆盖主要的功能点，以供功能验证时使用
性能测试的测试设计
根据性能指标，选择测试用例
根据需求文档得到用户明确要求的性能指标
版本升级的项目，各功能的性能指标不得低于旧版本的性能指标
模型产品，新模型各功能的性能指标以不低于旧模型的性能为要求
根据收集的性能指标，建立性能测试的CheckList
单体测试的测试设计
白盒测试的测试设计
命令覆盖
分支覆盖
路径覆盖
单体测试_白盒测试设计1
单体测试_白盒测试设计2
单体测试_黑盒测试设计
黑盒测试的测试设计
等价类划分
边界值分析
测试执行
根据测试阶段的不同，测试执行分成
单体测试的测试执行
单集成测试的测试执行
集成测试和系统测试的测试执行
性能测试的测试执行
单体测试的测试执行
根据白盒测试设计和黑盒测试设计得到测试用例
编写对待测试代码进行输入和得到输出程序，或者找到能对待测试代码进行输入和得到输出的调试方法
使用测试用例逐一输入，收集输出结果，检查输出结果是否正确
单集成测试的测试执行-1
自顶向下法
单集成测试的测试执行-2
自底向上法
集成测试和系统测试的执行－1
判定需求，执行测试设计和测试用例，填写结果
及时准确反馈产品缺陷
定期完成修改的确认
分析缺陷发生趋势，制定测试策略
需求变更时，对应变更测试设计文档
收集测试数据，分析并使用
集成测试和系统测试的执行－2
判定需求，执行测试设计和测试用例，填写结果
获得测试版本的同时要获得版本对应的测试需求，根据需求选择相关的测试设计文档和测试用例文档
根据选择的文档进行测试，要求至少完成一遍的覆盖，覆盖测试后填写测试结果（OK和NG）
完成版本的测试时，把完成的文档测试结果和该版本发现的缺陷一起提交
注意：这里提到的需要提交文档测试结果的版本一般上是比较大的版本（项目负责人决定），普通的版本之提交发现的缺陷即可
集成测试和系统测试的执行－3
及时准确反馈产品缺陷
测试中发现缺陷（包括不确定的）时，首先要进行记录，其次在进行是否缺陷的分析
当天发现的缺陷要尽量在当天完成登陆
要准确填写错误等级和再现率
错误等级
A类为严重影响系统运行（并且不可恢复）
B类为影响系统运行（可以恢复）
C类为不影响系统运行但必须修改
D类为所提建议
再现率
要求记录准确的测试和再现次数，尽量不要出现1/1的情况
再现时注意环境的正确，在已经出现缺陷的环境上继续再现的意义不大
再现前要尽量通过分析降低再现的难度和再现的步骤
集成测试和系统测试的执行－4
及时准确反馈产品缺陷
补充发现缺陷的相关信息（DEBUG信息，缺陷发生的图片，死机时的堆栈信息，发生缺陷的现场等）
集成测试和系统测试的执行－5
定期完成修改的确认
当发布新的版本到测试时，要得到该版本开发人员投入的已经修改的缺陷，进行确认
合理的分配测试时间，当测试工作量比较大时，首先完成变更点的测试，然后再进行确认测试
NotBug的及时确认
对于开发人员分配成NotBug的缺陷进行确认时，要以下面的顺序进行参考
仕样中是否有明确说明>>用户是否明确的文档说明>>其他模型的参考和自己正确的分析>>开发人员的分析
出现和开发人员无法达成一致时通过和测试负责人或者项目负责人沟通解决
对于开发人员判断错误的缺陷及时进行NG的处理，使开发人员尽快得到信息
集成测试和系统测试的执行－6
分析缺陷发生趋势，制定测试策略
集成测试和系统测试的执行－7
需求变更时，对应变更测试设计文档
对应产品开发过程中的需求变更方法，要和项目开始前的需求分析方法相同，对需求变更的部分及时修改或者填写测试设计文档
集成测试和系统测试的执行－8
收集测试数据，分析并使用
区分整个测试时间里，测试时间占用情况的分类
功能覆盖测试
脱离测试设计文档的自由测试
差分测试 （针对功能点变更进行的测试）
发现缺陷的再现测试
确认测试
开发人员调试
根据不同分类收集测试数据
根据测试时间占用情况的分类进行测试数据的收集
分析测试效率，发现问题
对于功能覆盖测试、自由测试和差分测试都是有效的测试时间，基本上90％以上的缺陷都是这个期间发现的，因此可以得到测试组以及每个测试人员的测试效率，然后再结合实际进行分析，就能得到测试组或者某个测试成员的测试状态如何
性能测试的测试执行
选择性能测试的对象，建立性能测试CheckList
收集评价用的性能数据，向CheckList进行补充
定期根据性能测试CheckList，对产品进行性能测试数据收集
提前进行性能数据的收集，以评估当前的产品是否能够达到性能要求
反馈性能数据
对提前收集的性能数据分析，评估当前的产品不能达到性能要求时立即向开发人员反馈性能数据
对性能测试阶段收集的性能数据，进行分析后提交开发人员
评估和预定的性能指标的差异
帮助开发人员分析造成性能指标差异的原因
例题
Myers问题: 读入三个整数值。这三个数值表示了一个三角形三条边的长度。程序将输出一条信息，说明该三角形是不等边三角形，等腰三角形，还是等边三角形。(并不要求写出程序)写出你认为能充分地测试这个问题的测试实例（即特定的数据集）。
（格式可写成：测试实例说明 测试实例值 期望输出）。
例题答案－1
*1 合法的不等边三角形 5 3 4 不等边三角形
*2 合法的等腰三角形 3 3 4 等腰三角形
*3 合法的等边三角形 3 3 3 等边三角形
*4 两个相同值边的互换（第一次） 50 50 25 等腰三角形
5 两个相同值边的互换（第二次） 25 50 50 等腰三角形
6 两个相同值边的互换（第三次） 50 25 50 等腰三角形
*7 一条边为0 1000 1000 0 非法
*8 一条边值为负 3 3 -4 非法
*9 两条相同边的第一次互换（非法） 5 5 10 非法
10 两条相同边的第二次互换（非法） 10 5 5 非法
11 两条相同边的第三次互换（非法） 5 10 5 非法
*12 两条较小的边长之和小于最大的边长 8 2 5 非法
13 上例的二条边第二次交换 2 8 5 非法
14 上例的二条边再次交换 2 5 8 非法
15 上例的二条边再次交换 8 5 2 非法
16 上例的二条边再次交换 5 8 2 非法
17 上例的二条边再次交换 5 2 8 非法
例题答案－2
*18 所有的边为0 0 0 0 非法
*19 第一个参数为非整数 # 3 7 非法
20 第二个参数为非整数 7 @ 8 非法
21 第三个参数为非整数 6 9 $ 非法
*22 缺少第一个参数的输入 4 5 非法
23 缺少第二个参数的输入 3 5 非法
24 缺少第三个参数的输入 3 4 非法
*25 三条边大于0，一边等于另两边之和 12 5 7 非法
26 上例的交换 12 7 5 非法
27 上例的再次交换 5 12 7 非法
28 上例的再次交换 5 7 12 非法
29 上例的再次交换 7 12 5 非法
30 上例的再次交换 7 5 12 非法
*31 三条边有最大的可能值 2147483647 2147483647 2147483647（32767） 等边
32 二条边有最大的可能值 2147483647 2147483647 1 等腰
33 一条边有最大的可能值 1 2147483647 1 非法
培训目的
什么是软件测试
如何做好软件测试
什么是软件测试
软件测试是以发现软件的缺陷为目的，使软件运行，将软件运行中所产生的危险性降低到允许的范围，是一个为发现错误而执行程序的过程
软件的缺陷是对软件产品预期属性的偏离现象。包括对产品规格说明书的偏离；对客户/用户的期望的偏离，客户/用户的要求没有纳入软件产品中（可能是产品规格说明书说明时的遗漏,也可能是软件实现的问题）。
软件测试的几个基本概念
单体测试：是指对单个模块或者是一个函数等更小单位的测试
集成测试：是指多个模块组合起来，或者一个子系统的所有模块都结合起来后进行的测试
系统测试：是指整个系统的所有子系统都结合起来以后进行的测试
回归测试：是指修复或调整好软件环境之后进行测试
差分测试：是指当测试时间较短时（不足以进行一遍系统测试时），而只对整个系统中新变更或者新追加功能的相关部分的测试
手动测试：是指测试人员，根据功能规格说明书、编写的测试大纲或者其他测试文档，直接运行程序而完成的测试
自动化测试：是指测试人员，使用自动测试工具、或者编写测试脚本，让程序自动运行而进行的测试
软件产品周期简介
根据需求文档进行分析制定测试策略和测试计划
分别根据需求分析、概要设计和详细设计的输出进行测试设计
使用测试设计文档，进行各个阶段的测试执行
产品Release之后进行测试工作的总结
当软件产品周期，需求文档变化时，将重新进行前三个工作
测试计划的制定
主要输入：需求文档和里程碑
主要输出：测试进度的制定和采取的测试策略
测试进度内容包括测试设计开始和结束的时间，测试执行的开始和结束时间，测试总结开始和结束时间，还包括测试设计、测试执行和测试总结所花费的工作量
测试策略内容包括采取测试方法、测试资源的分配和测试中风险的控制计划
测试设计
根据测试阶段的不同，测试设计包括以下几种
系统测试的测试设计
集成测试的测试设计
性能测试的测试设计
单体测试的测试设计
其中单体测试的测试设计由开发人员完成，其他一般情况下由测试人员完成
系统测试、集成测试的 测试设计
CheckList的编写
根据需求分析文档得到软件产品应该包括的功能点（包括大小功能点），组成CheckList的第一部分，要求CheckList必须覆盖软件产品应该包括的全部功能点
理解需求分析文档得到每个功能点的细化部分，组成CheckList的第二部分，要求覆盖需求文档中所有可测试的内容
根据测试经验和业务知识，进一步分析需求分析文档，得到需求分析文档上没有描述的内容，补充CheckList的第二部分
对每个功能点的细化部分，确定其测试方法（或者测试步骤）和预计的正确测试结果
测试用例的编写
需要特殊条件才能测试的功能点，编写测试用例以对应
编写一些测试用例，以覆盖主要的功能点，以供功能验证时使用
性能测试的测试设计
根据性能指标，选择测试用例
根据需求文档得到用户明确要求的性能指标
版本升级的项目，各功能的性能指标不得低于旧版本的性能指标
模型产品，新模型各功能的性能指标以不低于旧模型的性能为要求
根据收集的性能指标，建立性能测试的CheckList
单体测试的测试设计
白盒测试的测试设计
命令覆盖
分支覆盖
路径覆盖
单体测试_白盒测试设计1
单体测试_白盒测试设计2
单体测试_黑盒测试设计
黑盒测试的测试设计
等价类划分
边界值分析
测试执行
根据测试阶段的不同，测试执行分成
单体测试的测试执行
单集成测试的测试执行
集成测试和系统测试的测试执行
性能测试的测试执行
单体测试的测试执行
根据白盒测试设计和黑盒测试设计得到测试用例
编写对待测试代码进行输入和得到输出程序，或者找到能对待测试代码进行输入和得到输出的调试方法
使用测试用例逐一输入，收集输出结果，检查输出结果是否正确
单集成测试的测试执行-1
自顶向下法
单集成测试的测试执行-2
自底向上法
集成测试和系统测试的执行－1
判定需求，执行测试设计和测试用例，填写结果
及时准确反馈产品缺陷
定期完成修改的确认
分析缺陷发生趋势，制定测试策略
需求变更时，对应变更测试设计文档
收集测试数据，分析并使用
集成测试和系统测试的执行－2
判定需求，执行测试设计和测试用例，填写结果
获得测试版本的同时要获得版本对应的测试需求，根据需求选择相关的测试设计文档和测试用例文档
根据选择的文档进行测试，要求至少完成一遍的覆盖，覆盖测试后填写测试结果（OK和NG）
完成版本的测试时，把完成的文档测试结果和该版本发现的缺陷一起提交
注意：这里提到的需要提交文档测试结果的版本一般上是比较大的版本（项目负责人决定），普通的版本之提交发现的缺陷即可
集成测试和系统测试的执行－3
及时准确反馈产品缺陷
测试中发现缺陷（包括不确定的）时，首先要进行记录，其次在进行是否缺陷的分析
当天发现的缺陷要尽量在当天完成登陆
要准确填写错误等级和再现率
错误等级
A类为严重影响系统运行（并且不可恢复）
B类为影响系统运行（可以恢复）
C类为不影响系统运行但必须修改
D类为所提建议
再现率
要求记录准确的测试和再现次数，尽量不要出现1/1的情况
再现时注意环境的正确，在已经出现缺陷的环境上继续再现的意义不大
再现前要尽量通过分析降低再现的难度和再现的步骤
集成测试和系统测试的执行－4
及时准确反馈产品缺陷
补充发现缺陷的相关信息（DEBUG信息，缺陷发生的图片，死机时的堆栈信息，发生缺陷的现场等）
集成测试和系统测试的执行－5
定期完成修改的确认
当发布新的版本到测试时，要得到该版本开发人员投入的已经修改的缺陷，进行确认
合理的分配测试时间，当测试工作量比较大时，首先完成变更点的测试，然后再进行确认测试
NotBug的及时确认
对于开发人员分配成NotBug的缺陷进行确认时，要以下面的顺序进行参考
仕样中是否有明确说明>>用户是否明确的文档说明>>其他模型的参考和自己正确的分析>>开发人员的分析
出现和开发人员无法达成一致时通过和测试负责人或者项目负责人沟通解决
对于开发人员判断错误的缺陷及时进行NG的处理，使开发人员尽快得到信息
集成测试和系统测试的执行－6
分析缺陷发生趋势，制定测试策略
集成测试和系统测试的执行－7
需求变更时，对应变更测试设计文档
对应产品开发过程中的需求变更方法，要和项目开始前的需求分析方法相同，对需求变更的部分及时修改或者填写测试设计文档
集成测试和系统测试的执行－8
收集测试数据，分析并使用
区分整个测试时间里，测试时间占用情况的分类
功能覆盖测试
脱离测试设计文档的自由测试
差分测试 （针对功能点变更进行的测试）
发现缺陷的再现测试
确认测试
开发人员调试
根据不同分类收集测试数据
根据测试时间占用情况的分类进行测试数据的收集
分析测试效率，发现问题
对于功能覆盖测试、自由测试和差分测试都是有效的测试时间，基本上90％以上的缺陷都是这个期间发现的，因此可以得到测试组以及每个测试人员的测试效率，然后再结合实际进行分析，就能得到测试组或者某个测试成员的测试状态如何
性能测试的测试执行
选择性能测试的对象，建立性能测试CheckList
收集评价用的性能数据，向CheckList进行补充
定期根据性能测试CheckList，对产品进行性能测试数据收集
提前进行性能数据的收集，以评估当前的产品是否能够达到性能要求
反馈性能数据
对提前收集的性能数据分析，评估当前的产品不能达到性能要求时立即向开发人员反馈性能数据
对性能测试阶段收集的性能数据，进行分析后提交开发人员
评估和预定的性能指标的差异
帮助开发人员分析造成性能指标差异的原因
例题
Myers问题: 读入三个整数值。这三个数值表示了一个三角形三条边的长度。程序将输出一条信息，说明该三角形是不等边三角形，等腰三角形，还是等边三角形。(并不要求写出程序)写出你认为能充分地测试这个问题的测试实例（即特定的数据集）。
（格式可写成：测试实例说明 测试实例值 期望输出）。
例题答案－1
*1 合法的不等边三角形 5 3 4 不等边三角形
*2 合法的等腰三角形 3 3 4 等腰三角形
*3 合法的等边三角形 3 3 3 等边三角形
*4 两个相同值边的互换（第一次） 50 50 25 等腰三角形
5 两个相同值边的互换（第二次） 25 50 50 等腰三角形
6 两个相同值边的互换（第三次） 50 25 50 等腰三角形
*7 一条边为0 1000 1000 0 非法
*8 一条边值为负 3 3 -4 非法
*9 两条相同边的第一次互换（非法） 5 5 10 非法
10 两条相同边的第二次互换（非法） 10 5 5 非法
11 两条相同边的第三次互换（非法） 5 10 5 非法
*12 两条较小的边长之和小于最大的边长 8 2 5 非法
13 上例的二条边第二次交换 2 8 5 非法
14 上例的二条边再次交换 2 5 8 非法
15 上例的二条边再次交换 8 5 2 非法
16 上例的二条边再次交换 5 8 2 非法
17 上例的二条边再次交换 5 2 8 非法
例题答案－2
*18 所有的边为0 0 0 0 非法
*19 第一个参数为非整数 # 3 7 非法
20 第二个参数为非整数 7 @ 8 非法
21 第三个参数为非整数 6 9 $ 非法
*22 缺少第一个参数的输入 4 5 非法
23 缺少第二个参数的输入 3 5 非法
24 缺少第三个参数的输入 3 4 非法
*25 三条边大于0，一边等于另两边之和 12 5 7 非法
26 上例的交换 12 7 5 非法
27 上例的再次交换 5 12 7 非法
28 上例的再次交换 5 7 12 非法
29 上例的再次交换 7 12 5 非法
30 上例的再次交换 7 5 12 非法
*31 三条边有最大的可能值 2147483647 2147483647 2147483647（32767） 等边
32 二条边有最大的可能值 2147483647 2147483647 1 等腰
33 一条边有最大的可能值 1 2147483647 1 非法
2010年11月8日星期一
english word
Sporting house 妓院（不是体育室）
Dead president 美钞（不是死了的总统）
Lover 情人（不是爱人）
Busboy 餐馆勤杂工（不是公汽售票员）
Busybody 爱管闲事的人（不是大忙人）
Dry goods 纺织品 谷物（不是干货）
Heart man 换心人（不是有心人）
Mad doctor精神病科医生（不是发疯的医生）
Eleventh hour最后时刻（不是十一点）
Blind date（由第三者安排的）男女初次见面（并非盲目的约会或者是瞎约会）
Personal remark人身攻击（并非个人评论）
Sweet water淡水（不是糖水或者甜水）
Confidence man骗子（不是信得过的人）
Criminal lawyer 刑事律师（不是犯罪的律师）
Service station加油站（不是服务站）
Rest room厕所（不是休息室）
Dressing room化妆室（不是试衣间或者更衣室）
Horse sense常识（不是马的感觉）
Capital idea 好主意（不是资本主义思想）
Familiar talk 庸俗的交谈（不是熟悉的谈话）
Black tea红茶
Black art 妖术（不是黑色艺术）
Black stranger 完全陌生的人(不是陌生的黑人)
White coal （作动力来源用的）水
White man忠实可靠的人（不是皮肤白色的人）
Yellow book黄皮书（法国政府报告书，以黄纸为封，不是黄色书籍）
Red tape 官僚习气（不是红色带子）
Green hand 新手
Blue stocking 女学者，女才子（不是蓝色长筒袜）
China policy 对华政策（不是中华政策）
Chinese dragon 麒麟（不是中国龙）
American beauty 一种玫瑰，名叫美丽动人（不是美国美女）
English disease 软骨病（不是英国病）
Indian summer指的是秋天结束到冬天之前温暖的天气---》中国话 秋老虎 （谢谢ekin0906更正）
Greek gift 害人的礼品（不是希腊的礼物）
Spanish athlete 吹牛的人（不是西班牙的运动员）
French chalk 滑石粉（不是法国粉笔）
Pull ones leg 开玩笑（不是拉后腿）
In ones birthday suit 赤身裸体（不是穿着生日礼服）
Eat ones words 收回前言（不是食言）
An apple of love 西红柿（不是爱情之果）
Handwriting on the wall 不祥之兆（不是大字报）
Bring down the house 博得满堂喝彩（不是推倒房子）
Have a fit 勃然大怒（不是试穿）
Make ones hair stand on end 令人毛骨悚然，恐惧（不是令人发指，气愤）
Be taken in 受骗，上当（不是被接纳）
Think a great deal of oneself 高看或者看重自己（不是为自己想的很多）
Pull up ones socks 鼓起勇气（不是提上袜子）
Have the heart to do 用于否定句，忍心做（不是有心做或者有意做）
What a shame 多可惜，真遗憾（不是多可耻）
You don’t say 是吗？（不是你别说）
You can say that again 说的好（不是你别说）
I haven’t slept better 我睡得很好（不是我从未睡好过）
You can’t be too careful in your work 你工作越仔细越好（不是你工作不能太仔细）
It has been 4 years since I smoked 我戒烟4年了（不是我抽烟4年了）
All his friends did not turn up 他的朋友没全到（不是他的朋友全没到）
People will be long forgetting her 人们在很长时间内会记住她的（不是人们会永远忘记她）
He was only too pleased to let them go 他很乐意让他们走（不是他，不愿让他们走太高兴了）
It can’t be less interesting 它无聊极了（不是它不可能没有趣）
Dead president 美钞（不是死了的总统）
Lover 情人（不是爱人）
Busboy 餐馆勤杂工（不是公汽售票员）
Busybody 爱管闲事的人（不是大忙人）
Dry goods 纺织品 谷物（不是干货）
Heart man 换心人（不是有心人）
Mad doctor精神病科医生（不是发疯的医生）
Eleventh hour最后时刻（不是十一点）
Blind date（由第三者安排的）男女初次见面（并非盲目的约会或者是瞎约会）
Personal remark人身攻击（并非个人评论）
Sweet water淡水（不是糖水或者甜水）
Confidence man骗子（不是信得过的人）
Criminal lawyer 刑事律师（不是犯罪的律师）
Service station加油站（不是服务站）
Rest room厕所（不是休息室）
Dressing room化妆室（不是试衣间或者更衣室）
Horse sense常识（不是马的感觉）
Capital idea 好主意（不是资本主义思想）
Familiar talk 庸俗的交谈（不是熟悉的谈话）
Black tea红茶
Black art 妖术（不是黑色艺术）
Black stranger 完全陌生的人(不是陌生的黑人)
White coal （作动力来源用的）水
White man忠实可靠的人（不是皮肤白色的人）
Yellow book黄皮书（法国政府报告书，以黄纸为封，不是黄色书籍）
Red tape 官僚习气（不是红色带子）
Green hand 新手
Blue stocking 女学者，女才子（不是蓝色长筒袜）
China policy 对华政策（不是中华政策）
Chinese dragon 麒麟（不是中国龙）
American beauty 一种玫瑰，名叫美丽动人（不是美国美女）
English disease 软骨病（不是英国病）
Indian summer指的是秋天结束到冬天之前温暖的天气---》中国话 秋老虎 （谢谢ekin0906更正）
Greek gift 害人的礼品（不是希腊的礼物）
Spanish athlete 吹牛的人（不是西班牙的运动员）
French chalk 滑石粉（不是法国粉笔）
Pull ones leg 开玩笑（不是拉后腿）
In ones birthday suit 赤身裸体（不是穿着生日礼服）
Eat ones words 收回前言（不是食言）
An apple of love 西红柿（不是爱情之果）
Handwriting on the wall 不祥之兆（不是大字报）
Bring down the house 博得满堂喝彩（不是推倒房子）
Have a fit 勃然大怒（不是试穿）
Make ones hair stand on end 令人毛骨悚然，恐惧（不是令人发指，气愤）
Be taken in 受骗，上当（不是被接纳）
Think a great deal of oneself 高看或者看重自己（不是为自己想的很多）
Pull up ones socks 鼓起勇气（不是提上袜子）
Have the heart to do 用于否定句，忍心做（不是有心做或者有意做）
What a shame 多可惜，真遗憾（不是多可耻）
You don’t say 是吗？（不是你别说）
You can say that again 说的好（不是你别说）
I haven’t slept better 我睡得很好（不是我从未睡好过）
You can’t be too careful in your work 你工作越仔细越好（不是你工作不能太仔细）
It has been 4 years since I smoked 我戒烟4年了（不是我抽烟4年了）
All his friends did not turn up 他的朋友没全到（不是他的朋友全没到）
People will be long forgetting her 人们在很长时间内会记住她的（不是人们会永远忘记她）
He was only too pleased to let them go 他很乐意让他们走（不是他，不愿让他们走太高兴了）
It can’t be less interesting 它无聊极了（不是它不可能没有趣）
2010年5月3日星期一
分词技术
分词又叫,切词,划词等 我感觉是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在中文词典构建上比百度差些,还需要加把子力气才行,不过这也不是什么多难的事.
我有个实验站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..
订阅：
博文 (Atom)