第9講 拼寫(xiě)檢查(2012)

1、第第9講講 自然語(yǔ)言處理應(yīng)用之一自然語(yǔ)言處理應(yīng)用之一拼寫(xiě)檢查拼寫(xiě)檢查spelling collection廣東外語(yǔ)外貿(mào)大學(xué)信息學(xué)院廣東外語(yǔ)外貿(mào)大學(xué)信息學(xué)院 李霞李霞 2012內(nèi)容內(nèi)容n1 正則表達(dá)式正則表達(dá)式n2 編輯距離及基于權(quán)重的編輯距離編輯距離及基于權(quán)重的編輯距離n3 拼寫(xiě)檢查拼寫(xiě)檢查1. 正則表達(dá)式正則表達(dá)式regular expression正則表達(dá)式正則表達(dá)式n正則表達(dá)式在基于文本的編輯器和搜索工具中占據(jù)非正則表達(dá)式在基于文本的編輯器和搜索工具中占據(jù)非常重要的地位，對(duì)常重要的地位，對(duì)NLP也有許多應(yīng)用也有許多應(yīng)用如拼寫(xiě)檢查、機(jī)器翻譯等如拼寫(xiě)檢查、機(jī)器翻譯等主要功能：主要功能：正則表

2、達(dá)式正則表達(dá)式n各語(yǔ)言有所支持的正則表達(dá)式庫(kù)各語(yǔ)言有所支持的正則表達(dá)式庫(kù)n如：如：python, java 等等n這里以支持這里以支持VC+的的boost.regex進(jìn)行講解進(jìn)行講解正則表達(dá)式概念正則表達(dá)式概念n正則表達(dá)式是由正則表達(dá)式是由普通字符普通字符(如如A-Z)和和特殊字符特殊字符(稱稱為元字符為元字符)組成的文字模式組成的文字模式(pattern)。n正則表達(dá)式作為一個(gè)模板，將某個(gè)字符模式與正則表達(dá)式作為一個(gè)模板，將某個(gè)字符模式與所搜索的字符串進(jìn)行匹配。所搜索的字符串進(jìn)行匹配。普通字符普通字符 LiteralsnAll characters are literals except:

3、n., | , * , ? , + , ( , ) , , , , , , $ and These characters are literals when preceded by a . A literal is a character that matches itself, or matches the result of traits_type:translate(), where traits_type is the traits template parameter to class basic_regex.通配符通配符 Wildcardn. nThe dot character

4、. matches any single character 限定符限定符nA repeat is an expression that is repeated an arbitrary number of times.n有有 “*” “+” “?” “n” “n,” “n,m”共共6種。種。All repeat expressions refer to the shortest possible previous sub-expression: a single character; a character set, or a sub-expression grouped with ()限定

5、符說(shuō)明限定符說(shuō)明n* 匹配前面的子表達(dá)式零次或多次。匹配前面的子表達(dá)式零次或多次。例如，例如，zo* 能匹配能匹配z 以及以及 zoo。* 等價(jià)于等價(jià)于0,。 n+ 匹配前面的子表達(dá)式一次或多次。匹配前面的子表達(dá)式一次或多次。例如，例如，zo+ 能匹配能匹配 zo 以及以及 zoo，但不能匹配，但不能匹配 z。+ 等價(jià)于等價(jià)于 1,。 n? 匹配前面的子表達(dá)式零次或一次。匹配前面的子表達(dá)式零次或一次。例如，例如，do(es)? 可以匹配可以匹配 do 或或 does 中的中的do 。? 等價(jià)于等價(jià)于 0,1。 限定符說(shuō)明限定符說(shuō)明nn n 是一個(gè)非負(fù)整數(shù)。匹配確定的是一個(gè)非負(fù)整數(shù)。匹配確定的

6、n 次。次。例如，例如，o2 不能匹配不能匹配 Bob 中的中的 o，但是能匹配，但是能匹配 food 中的兩個(gè)中的兩個(gè) o。 nn, n 是一個(gè)非負(fù)整數(shù)。至少匹配是一個(gè)非負(fù)整數(shù)。至少匹配n 次。次。例如，例如，o2, 不能匹配不能匹配 Bob 中的中的o，但能匹配，但能匹配 foooood 中的所有中的所有 o。o1, 等價(jià)于等價(jià)于 o+。o0, 則等價(jià)于則等價(jià)于 o*。 nn,m m 和和 n 均為非負(fù)整數(shù)，其中均為非負(fù)整數(shù)，其中n = m。最少匹配。最少匹配 n 次且最多匹配次且最多匹配 m 次。次。例如，例如，o1,3 將匹配將匹配 fooooood 中的前三個(gè)中的前三個(gè) o。o0,1

7、 等等價(jià)于價(jià)于 o?。請(qǐng)注意在逗號(hào)和兩個(gè)數(shù)之間不能有空格。請(qǐng)注意在逗號(hào)和兩個(gè)數(shù)之間不能有空格。 例例n“ba*” will match：all of b, ba, baaa etc. n“ba+” will match： ba or baaaa for example but not b. n“ba?” will match： b or ba. n“ba2,4” will match： baa, baaa and baaaa. ( ) Parenthesisn圓括號(hào)可以充當(dāng)圓括號(hào)可以充當(dāng)2個(gè)功能：個(gè)功能：將括號(hào)內(nèi)的字符組成一個(gè)子串來(lái)進(jìn)行匹配將括號(hào)內(nèi)的字符組成一個(gè)子串來(lái)進(jìn)行匹配例如：例如：“(a

8、b)*”可以匹配可以匹配 ababab. Non-Marking Parenthesis n有時(shí)需要將字符組合在一塊，但又不想作為一有時(shí)需要將字符組合在一塊，但又不想作為一個(gè)子表達(dá)式與其他標(biāo)記子表達(dá)式分開(kāi)，可以使個(gè)子表達(dá)式與其他標(biāo)記子表達(dá)式分開(kāi)，可以使用非標(biāo)記圓括號(hào)：用非標(biāo)記圓括號(hào)： (?:expression) 例如：例如： (?:abc)*Alternatives nAlternatives occur when the expression can match either one sub-expression or another, each alternative is separa

9、ted by a | Examples: a(b|c) could match ab or ac. abc|def could match abc or def. Setsn集是指可以匹配集中字符串任意字符的一組字集是指可以匹配集中字符串任意字符的一組字符符n集以集以“” and “” 作為界定符，可能包含：作為界定符，可能包含：普通字符普通字符Character literals 字符范圍字符范圍Character ranges字符類字符類Character classes等價(jià)類等價(jià)類Equivalence classes n以符號(hào)以符號(hào) “” 打頭聲明的集包含的是補(bǔ)集打頭聲明的集包含的是補(bǔ)

10、集SetsnExamples: nCharacter literals: abc will match either of a, b, or c. abc will match any character other than a, b, or c. nCharacter ranges: a-z will match any character in the range a to z. A-Z will match any character other than those in the range A to Z. SetsnCharacter classes 以以“:classname:”

11、 表示表示n如：如：:word: 表示任何單詞字母，可以以表示任何單詞字母，可以以w代替代替:space:表示任何空格字符，可以以表示任何空格字符，可以以s代替代替 :digit: 表示任何表示任何09之間的數(shù)字，可以之間的數(shù)字，可以d代替代替:lower:表示任意小寫(xiě)字母，可以表示任意小寫(xiě)字母，可以 l代替代替 :upper:表示任意大寫(xiě)字母，可以表示任意大寫(xiě)字母，可以 u代替代替Line anchorsnAn anchor is something that matches the null string at the start or end of a line: n matches t

12、he null string at the start of a line $ matches the null string at the end of a line. Word operatorsnw matches any single character that is a member of the word character class, this is identical to the expression :word:. nW matches any single character that is not a member of the word character cla

13、ss, this is identical to the expression :word:. n matches the null string at the end of the word. nb matches the null string at either the start or the end of a word. nB matches a null string within a word. Buffer operatorsnThe following operators are provided for compatibility with the GNU regular

14、expression library, and Perl regular expressions: n matches the start of a buffer. nA matches the start of the buffer. n matches the end of a buffer. nz matches the end of a buffer. nZ matches the end of a buffer, or possibly one or more new line characters followed by the end of the buffer. nA buff

15、er is considered to consist of the whole sequence passed to the matching algorithms, unless the flags match_not_bob or match_not_eob are set. The escape charactern轉(zhuǎn)義字符：轉(zhuǎn)義字符： “”：在集內(nèi)定義的轉(zhuǎn)義字符是一個(gè)普通字符在集內(nèi)定義的轉(zhuǎn)義字符是一個(gè)普通字符將元字符轉(zhuǎn)為普通字符將元字符轉(zhuǎn)為普通字符例如：例如： * represents a literal * rather than the repeat operator. The

16、escape charactern特殊含義：特殊含義： a Bell character. f Form feed. n Newline character. r Carriage return. t Tab character. v Vertical tab. e ASCII Escape character. The escape charactern特殊含義：特殊含義：0dd 八進(jìn)制字符碼八進(jìn)制字符碼, dd是一個(gè)活多個(gè)八進(jìn)制數(shù)字是一個(gè)活多個(gè)八進(jìn)制數(shù)字xXX 十六進(jìn)制字符碼十六進(jìn)制字符碼, XX是一個(gè)或多個(gè)十六進(jìn)制數(shù)是一個(gè)或多個(gè)十六進(jìn)制數(shù)xXX 一個(gè)十六進(jìn)制字符碼一個(gè)十六進(jìn)制字符碼, X

17、X是一個(gè)或多個(gè)十六是一個(gè)或多個(gè)十六進(jìn)制數(shù)進(jìn)制數(shù)cZ 一個(gè)一個(gè)ASCII轉(zhuǎn)義序列控制符轉(zhuǎn)義序列控制符, Z是任意大于或等是任意大于或等于于 碼的字符碼的字符. 其它兼容轉(zhuǎn)義序列其它兼容轉(zhuǎn)義序列nw Equivalent to :word:. nW Equivalent to :word:. ns Equivalent to :space:. nS Equivalent to :space:. nd Equivalent to :digit:. nD Equivalent to :digit:. nl Equivalent to :lower:. 其它兼容轉(zhuǎn)義序列其它兼容轉(zhuǎn)義序列nL Equiva

18、lent to :lower:. nu Equivalent to :upper:. nU Equivalent to :upper:. nC Any single character, equivalent to . nX Match any Unicode combining character sequence, for example ax 0301 (a letter a with an acute). nQ The begin quote operator, everything that follows is treated as a literal character unti

19、l a E end quote operator is found. nE The end quote operator, terminates a sequence begun with Q. 構(gòu)造正則表達(dá)式的方法和創(chuàng)建數(shù)學(xué)表達(dá)式的構(gòu)造正則表達(dá)式的方法和創(chuàng)建數(shù)學(xué)表達(dá)式的方法一樣。也就是用多種元字符與操作符將小的方法一樣。也就是用多種元字符與操作符將小的表達(dá)式結(jié)合在一起來(lái)創(chuàng)建更大的表達(dá)式。正則表表達(dá)式結(jié)合在一起來(lái)創(chuàng)建更大的表達(dá)式。正則表達(dá)式的組件可以是單個(gè)的字符、字符集合、字符達(dá)式的組件可以是單個(gè)的字符、字符集合、字符范圍、字符間的選擇或者所有這些組件的任意組范圍、字符間的選擇或者所有這些組件

20、的任意組合。合?？偨Y(jié)總結(jié)總結(jié)總結(jié)總結(jié)總結(jié)總結(jié)總結(jié)例例nvoid main()/定義一個(gè)正則表達(dá)式對(duì)象的匹配模版，要求匹配定義一個(gè)正則表達(dá)式對(duì)象的匹配模版，要求匹配3個(gè)數(shù)字個(gè)數(shù)字.boost:regex reg(d3);/定義源串定義源串std:string src1=123;std:string src2=Hello;/匹配測(cè)試匹配測(cè)試if ( boost:regex_match(src1, reg) )cout匹配！匹配！endl;elsecout“不匹配不匹配!endl;演示例例2nvoid EmailTest()/定義一個(gè)正則表達(dá)式對(duì)象的匹配模版定義一個(gè)正則表達(dá)式對(duì)象的匹配模版,要求匹配

21、合法郵箱要求匹配合法郵箱boost:regex reg(w2,15a-z0-93,.l3,);/定義原串定義原串std:string src=shelly163.cm;/匹配測(cè)試匹配測(cè)試if (boost:regex_match(src, reg) )cout合法郵箱！合法郵箱！endl;elsecout不合法郵箱不合法郵箱!endl;演示練習(xí)練習(xí)1n假定信用卡號(hào)碼為：假定信用卡號(hào)碼為：16位數(shù)字，格式為：位數(shù)字，格式為： xxxx xxxx xxxx xxxx請(qǐng)寫(xiě)一個(gè)正則表達(dá)式匹配正確的信用卡請(qǐng)寫(xiě)一個(gè)正則表達(dá)式匹配正確的信用卡演示演示nhttp:/ We looked!Then we saw

22、 him step in on the mat.We looked!And we saw him!The Cat in the Hat!2. 編輯距離編輯距離edited distance編輯距離編輯距離n編輯距離由俄羅斯科學(xué)家編輯距離由俄羅斯科學(xué)家Vladimir Levenshtein在在1965年提出，所以也叫年提出，所以也叫Levenshtein距離。距離。n應(yīng)用：應(yīng)用：DNA分析分析拼字檢查拼字檢查語(yǔ)音辨識(shí)語(yǔ)音辨識(shí)抄襲偵測(cè)抄襲偵測(cè)最小編輯距離的應(yīng)用最小編輯距離的應(yīng)用n拼寫(xiě)檢查拼寫(xiě)檢查spelling collection當(dāng)用戶拼寫(xiě)當(dāng)用戶拼寫(xiě) “graffe”哪個(gè)是最接近的單詞呢？哪個(gè)

23、是最接近的單詞呢？lgraflgraft lgraillgiraffe概念概念n編輯距離，是指兩個(gè)編輯距離，是指兩個(gè)字串字串之間，由一個(gè)轉(zhuǎn)成另之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的一個(gè)所需的最少編輯操作次數(shù)最少編輯操作次數(shù)。n許可的編輯操作包括：許可的編輯操作包括：將一個(gè)字符替換成另一個(gè)字符將一個(gè)字符替換成另一個(gè)字符 substitution；插入一個(gè)字符插入一個(gè)字符 insert；刪除一個(gè)字符刪除一個(gè)字符 delete;例如例如l將將kitten轉(zhuǎn)成轉(zhuǎn)成sitting需要需要3個(gè)操作次數(shù)個(gè)操作次數(shù)lsitten （ks） sittin （ei）sitting （g）例如例如n兩個(gè)字符串的編輯距離：兩個(gè)

24、字符串的編輯距離：如何尋找最小編輯距離如何尋找最小編輯距離如何尋找最小編輯距離如何尋找最小編輯距離最小編輯距離的定義最小編輯距離的定義n對(duì)兩個(gè)字符串對(duì)兩個(gè)字符串str1, str2，假定：，假定：串串str1的長(zhǎng)度為的長(zhǎng)度為n串串str2的長(zhǎng)度為的長(zhǎng)度為mn我們定義我們定義D(i,j)為：為：str1(1i)和和str2(1j)之間的編輯距離之間的編輯距離n這樣串這樣串str1和串和串str2的編輯距離為：的編輯距離為：D(n,m)最小編輯距離的計(jì)算最小編輯距離的計(jì)算最小編輯距離最小編輯距離(Levenshtein)的定義的定義在str2上j位置刪除字符 在str2上j-1位置插入字符 替換操

25、作 cost 偽代碼偽代碼n查看查看txt圖示講解圖示講解編輯距離表編輯距離表練習(xí)練習(xí)n請(qǐng)利用該方法計(jì)算單詞請(qǐng)利用該方法計(jì)算單詞 actualy 與單詞與單詞 actual, actually, actuary，hello 的最小編輯距離，并按的最小編輯距離，并按升序排列。升序排列。 3. 基于權(quán)重的編輯距離基于權(quán)重的編輯距離weighted edited distanceweighted edited distance拼寫(xiě)錯(cuò)誤中的混淆矩陣拼寫(xiě)錯(cuò)誤中的混淆矩陣weighted edited distancen由于由于鍵盤(pán)中字母位置鍵盤(pán)中字母位置人們習(xí)慣人們習(xí)慣n等問(wèn)題，導(dǎo)致某些字符更容易混淆或

26、出錯(cuò)等問(wèn)題，導(dǎo)致某些字符更容易混淆或出錯(cuò)n因此：對(duì)某些刪除，插入或替換等操作增加權(quán)因此：對(duì)某些刪除，插入或替換等操作增加權(quán)重重weighted edited distance4. 拼寫(xiě)檢查拼寫(xiě)檢查spelling collection拼寫(xiě)檢查拼寫(xiě)檢查 n常見(jiàn)的英文文本中單詞錯(cuò)誤的檢測(cè)主要分為兩常見(jiàn)的英文文本中單詞錯(cuò)誤的檢測(cè)主要分為兩大類大類:非詞檢錯(cuò)非詞檢錯(cuò)真詞檢錯(cuò)真詞檢錯(cuò)n拼寫(xiě)檢查的拼寫(xiě)檢查的2個(gè)問(wèn)題：個(gè)問(wèn)題：檢錯(cuò)檢錯(cuò)糾錯(cuò)糾錯(cuò)非詞非詞檢錯(cuò)檢錯(cuò) n非詞檢錯(cuò)目前主要有兩種方法非詞檢錯(cuò)目前主要有兩種方法:N-gram分析法分析法查詞典法查詞典法N-gram非詞非詞檢錯(cuò)檢錯(cuò)nN-gram錯(cuò)誤檢測(cè)技術(shù)

27、對(duì)輸入串中的每一個(gè)錯(cuò)誤檢測(cè)技術(shù)對(duì)輸入串中的每一個(gè)n元元串串( n一般取一般取2或或3)在事先編輯好的一個(gè)在事先編輯好的一個(gè)N-gram表表中進(jìn)行查找中進(jìn)行查找,看它是否在表中存在或它的出現(xiàn)頻看它是否在表中存在或它的出現(xiàn)頻次次,那些不存在或出現(xiàn)頻次非常低的那些不存在或出現(xiàn)頻次非常低的n元串被認(rèn)為元串被認(rèn)為是可能的拼寫(xiě)錯(cuò)誤是可能的拼寫(xiě)錯(cuò)誤如如“shj”或或“het”就是錯(cuò)誤的三元串。就是錯(cuò)誤的三元串。N-gram分析法通常需要一個(gè)詞典或大規(guī)模的文本語(yǔ)分析法通常需要一個(gè)詞典或大規(guī)模的文本語(yǔ)料以便事先編輯料以便事先編輯N-gram表。表。查字典法非詞查字典法非詞檢錯(cuò)檢錯(cuò)n查字典法主要是檢查所輸入的查字

28、典法主要是檢查所輸入的n元串是否在字典元串是否在字典或可接受的詞表中或可接受的詞表中,如果不在字典中如果不在字典中,則將該輸入則將該輸入串標(biāo)志為一個(gè)拼寫(xiě)錯(cuò)誤的詞。串標(biāo)志為一個(gè)拼寫(xiě)錯(cuò)誤的詞。n由于基于查字典法的校對(duì)系統(tǒng)查錯(cuò)精度高由于基于查字典法的校對(duì)系統(tǒng)查錯(cuò)精度高,因此因此,是目前較為流行的錯(cuò)誤檢測(cè)技術(shù)?？紤]到存取是目前較為流行的錯(cuò)誤檢測(cè)技術(shù)?？紤]到存取速度速度,當(dāng)詞典規(guī)模較大時(shí)當(dāng)詞典規(guī)模較大時(shí),為了提高查錯(cuò)速度為了提高查錯(cuò)速度,有效有效的詞典查找算法也是人們研究的重點(diǎn)。的詞典查找算法也是人們研究的重點(diǎn)。真詞真詞檢錯(cuò)檢錯(cuò) n真詞錯(cuò)誤通常稱為真詞錯(cuò)誤通常稱為“上下文相關(guān)的錯(cuò)誤上下文相關(guān)的錯(cuò)誤”?，F(xiàn)

29、?，F(xiàn)有的基于上下文的文本錯(cuò)誤校對(duì)方法有三類有的基于上下文的文本錯(cuò)誤校對(duì)方法有三類:用文本的特征用文本的特征,如字形特征、詞性特征或上下文特征如字形特征、詞性特征或上下文特征利用概率統(tǒng)計(jì)特性進(jìn)行上下文接續(xù)關(guān)系的分析利用概率統(tǒng)計(jì)特性進(jìn)行上下文接續(xù)關(guān)系的分析利用規(guī)則或語(yǔ)言學(xué)知識(shí)利用規(guī)則或語(yǔ)言學(xué)知識(shí),如語(yǔ)法規(guī)則、詞搭配規(guī)則等如語(yǔ)法規(guī)則、詞搭配規(guī)則等 拼寫(xiě)拼寫(xiě)糾錯(cuò)糾錯(cuò)n國(guó)際拼寫(xiě)校正研究，尤其是英文文本拼寫(xiě)校正國(guó)際拼寫(xiě)校正研究，尤其是英文文本拼寫(xiě)校正研究，可以分為三個(gè)依次深入的基本問(wèn)題研究，可以分為三個(gè)依次深入的基本問(wèn)題:1、非詞錯(cuò)誤識(shí)別；、非詞錯(cuò)誤識(shí)別；2、單個(gè)詞拼寫(xiě)校正；、單個(gè)詞拼寫(xiě)校正；3、上下文相

30、關(guān)拼寫(xiě)校正。、上下文相關(guān)拼寫(xiě)校正。單詞糾錯(cuò)常用的方法單詞糾錯(cuò)常用的方法 n單詞錯(cuò)誤的拼寫(xiě)校正方法已經(jīng)有很多研究單詞錯(cuò)誤的拼寫(xiě)校正方法已經(jīng)有很多研究,常見(jiàn)常見(jiàn)的英文單詞糾錯(cuò)法，主要有以下幾種：的英文單詞糾錯(cuò)法，主要有以下幾種：誤拼詞典法誤拼詞典法詞干法詞干法N-gram法法基于規(guī)則的技術(shù)基于規(guī)則的技術(shù)最小編輯距離法最小編輯距離法相似鍵相似鍵誤拼字典法誤拼字典法這種方法可以理解成窮舉法，通過(guò)收集大規(guī)模真實(shí)文本中拼寫(xiě)出錯(cuò)這種方法可以理解成窮舉法，通過(guò)收集大規(guī)模真實(shí)文本中拼寫(xiě)出錯(cuò)的英文單詞并給出相應(yīng)的正確拼寫(xiě)，建造一個(gè)無(wú)歧義的誤拼字典。的英文單詞并給出相應(yīng)的正確拼寫(xiě)，建造一個(gè)無(wú)歧義的誤拼字典。在進(jìn)行英

31、文單詞拼寫(xiě)檢查時(shí)，查找誤拼字典，如命中，則說(shuō)明該單在進(jìn)行英文單詞拼寫(xiě)檢查時(shí)，查找誤拼字典，如命中，則說(shuō)明該單詞拼寫(xiě)有誤，該詞的正確拼寫(xiě)字段為糾錯(cuò)建議。比如在搜索引擎的詞拼寫(xiě)有誤，該詞的正確拼寫(xiě)字段為糾錯(cuò)建議。比如在搜索引擎的實(shí)現(xiàn)中，通過(guò)記錄日志的形式，把所有用戶的輸入都記錄下來(lái)，提實(shí)現(xiàn)中，通過(guò)記錄日志的形式，把所有用戶的輸入都記錄下來(lái)，提取有拼寫(xiě)錯(cuò)誤的輸入，形成誤拼詞典。該方法的特點(diǎn)是算法簡(jiǎn)單，取有拼寫(xiě)錯(cuò)誤的輸入，形成誤拼詞典。該方法的特點(diǎn)是算法簡(jiǎn)單，效率高。但英文拼寫(xiě)錯(cuò)誤具有隨機(jī)性，很難保證誤拼字典的無(wú)歧義效率高。但英文拼寫(xiě)錯(cuò)誤具有隨機(jī)性，很難保證誤拼字典的無(wú)歧義性和全面性，因此查準(zhǔn)率低、校

32、對(duì)效果差；而且，對(duì)于搜索引擎用性和全面性，因此查準(zhǔn)率低、校對(duì)效果差；而且，對(duì)于搜索引擎用戶海量的誤拼輸入，空間復(fù)雜度也是需要考慮的問(wèn)題。戶海量的誤拼輸入，空間復(fù)雜度也是需要考慮的問(wèn)題。詞干法詞干法詞干法又稱作骨架鍵法。通過(guò)構(gòu)建詞干詞典，在詞干法又稱作骨架鍵法。通過(guò)構(gòu)建詞干詞典，在英文單詞出現(xiàn)錯(cuò)誤時(shí)，先抽取出該錯(cuò)誤單詞的詞英文單詞出現(xiàn)錯(cuò)誤時(shí)，先抽取出該錯(cuò)誤單詞的詞干，然后再去查詞干詞典，將詞典中與該單詞具干，然后再去查詞干詞典，將詞典中與該單詞具有相同詞干的正確單詞作為該單詞的糾錯(cuò)建議。有相同詞干的正確單詞作為該單詞的糾錯(cuò)建議。這種方法主要的難度在于構(gòu)建詞干詞典上，需要這種方法主要的難度在于構(gòu)建

33、詞干詞典上，需要對(duì)幾乎所有的英文單詞都進(jìn)行分析，提取出每個(gè)對(duì)幾乎所有的英文單詞都進(jìn)行分析，提取出每個(gè)單詞的詞干，或者稱為骨架詞；這種實(shí)現(xiàn)的工作單詞的詞干，或者稱為骨架詞；這種實(shí)現(xiàn)的工作量是巨大的，而且詞干的選擇非常重要，每個(gè)詞量是巨大的，而且詞干的選擇非常重要，每個(gè)詞干要有很好的區(qū)分度，才能給用戶給出良好的糾干要有很好的區(qū)分度，才能給用戶給出良好的糾錯(cuò)建議。錯(cuò)建議?；诨趎元文法元文法n基于基于n元文法，通過(guò)對(duì)大規(guī)模英文文本的統(tǒng)計(jì)得元文法，通過(guò)對(duì)大規(guī)模英文文本的統(tǒng)計(jì)得到單詞與單詞間的轉(zhuǎn)移概率矩陣。當(dāng)檢測(cè)到某到單詞與單詞間的轉(zhuǎn)移概率矩陣。當(dāng)檢測(cè)到某英文單詞不在詞典中時(shí)。查轉(zhuǎn)移概率矩陣，取英文單

34、詞不在詞典中時(shí)。查轉(zhuǎn)移概率矩陣，取轉(zhuǎn)移概率大于某給定閾值的單詞為糾錯(cuò)建議。轉(zhuǎn)移概率大于某給定閾值的單詞為糾錯(cuò)建議。詞形距離法詞形距離法n這是一種基于最大相似度和最小串間距離的英這是一種基于最大相似度和最小串間距離的英文校對(duì)法。其核心思想是構(gòu)造單詞的似然性函文校對(duì)法。其核心思想是構(gòu)造單詞的似然性函數(shù)，如該單詞在詞典中，則單詞拼寫(xiě)正確；否數(shù)，如該單詞在詞典中，則單詞拼寫(xiě)正確；否則，按照似然性函數(shù)，在詞典中找到一個(gè)與誤則，按照似然性函數(shù)，在詞典中找到一個(gè)與誤拼單詞最相似的詞作為糾錯(cuò)候選詞。該方法的拼單詞最相似的詞作為糾錯(cuò)候選詞。該方法的特點(diǎn)是節(jié)省存儲(chǔ)空間，能反映一定的常見(jiàn)拼寫(xiě)特點(diǎn)是節(jié)省存儲(chǔ)空間，能反

35、映一定的常見(jiàn)拼寫(xiě)錯(cuò)誤統(tǒng)計(jì)規(guī)律，是一種模糊校對(duì)法。錯(cuò)誤統(tǒng)計(jì)規(guī)律，是一種模糊校對(duì)法。利用規(guī)則的形式利用規(guī)則的形式n利用規(guī)則的形式將通常的拼寫(xiě)錯(cuò)誤模式進(jìn)行表利用規(guī)則的形式將通常的拼寫(xiě)錯(cuò)誤模式進(jìn)行表示，這些規(guī)則可用來(lái)將拼寫(xiě)錯(cuò)誤的單詞轉(zhuǎn)換為示，這些規(guī)則可用來(lái)將拼寫(xiě)錯(cuò)誤的單詞轉(zhuǎn)換為正確有效的單詞。對(duì)于一個(gè)誤拼字符串，應(yīng)用正確有效的單詞。對(duì)于一個(gè)誤拼字符串，應(yīng)用所有合適的規(guī)則從詞典中找到一些與之對(duì)應(yīng)的所有合適的規(guī)則從詞典中找到一些與之對(duì)應(yīng)的單詞作為候選結(jié)果；然后，對(duì)每個(gè)結(jié)果根據(jù)事單詞作為候選結(jié)果；然后，對(duì)每個(gè)結(jié)果根據(jù)事先賦予生成它的規(guī)則的概率估計(jì)計(jì)算一個(gè)數(shù)值，先賦予生成它的規(guī)則的概率估計(jì)計(jì)算一個(gè)數(shù)值，依據(jù)這

36、個(gè)數(shù)值對(duì)所有候選結(jié)果進(jìn)行排序，把將依據(jù)這個(gè)數(shù)值對(duì)所有候選結(jié)果進(jìn)行排序，把將排序靠前的結(jié)果當(dāng)成糾錯(cuò)結(jié)果返回給用戶。排序靠前的結(jié)果當(dāng)成糾錯(cuò)結(jié)果返回給用戶。最小編輯距離方法最小編輯距離方法n通過(guò)計(jì)算誤拼字符串與詞典中某個(gè)詞間的通過(guò)計(jì)算誤拼字符串與詞典中某個(gè)詞間的最小編最小編輯距離來(lái)確定糾錯(cuò)候選詞輯距離來(lái)確定糾錯(cuò)候選詞?？紤]到在實(shí)際計(jì)算機(jī)輸入過(guò)程中，字符的顛倒異位考慮到在實(shí)際計(jì)算機(jī)輸入過(guò)程中，字符的顛倒異位也是常見(jiàn)的錯(cuò)誤，我們將顛倒異位也算作一種編輯也是常見(jiàn)的錯(cuò)誤，我們將顛倒異位也算作一種編輯動(dòng)作。動(dòng)作。還有人提出了反向最小編輯距離法，這種方法首先還有人提出了反向最小編輯距離法，這種方法首先對(duì)每個(gè)可能

37、的單個(gè)錯(cuò)誤按照編輯距離進(jìn)行搜索，生對(duì)每個(gè)可能的單個(gè)錯(cuò)誤按照編輯距離進(jìn)行搜索，生成一個(gè)候選集，然后，通過(guò)查詞典看哪些是有效的成一個(gè)候選集，然后，通過(guò)查詞典看哪些是有效的單詞，并將這些有效的單詞作為誤拼字符串的糾錯(cuò)單詞，并將這些有效的單詞作為誤拼字符串的糾錯(cuò)建議。建議?；诮y(tǒng)計(jì)的方法基于統(tǒng)計(jì)的方法n英語(yǔ)單詞拼寫(xiě)檢查之統(tǒng)計(jì)方法，主要是針對(duì)英語(yǔ)單詞拼寫(xiě)檢查之統(tǒng)計(jì)方法，主要是針對(duì)“真真詞錯(cuò)誤詞錯(cuò)誤”來(lái)實(shí)現(xiàn)的。來(lái)實(shí)現(xiàn)的。真詞錯(cuò)誤的拼寫(xiě)校對(duì)不僅要修正那些真詞錯(cuò)誤的拼寫(xiě)校對(duì)不僅要修正那些“經(jīng)典經(jīng)典”的拼的拼寫(xiě)錯(cuò)誤類型寫(xiě)錯(cuò)誤類型,比如同音詞錯(cuò)誤比如同音詞錯(cuò)誤(如如peace與與piece)和字母和字母排序錯(cuò)誤排序錯(cuò)誤(如如form與與from),而且還要修正那些常見(jiàn)的而且還要修正那些常見(jiàn)的語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤(如如among與與between)和詞邊界混淆的錯(cuò)誤和詞邊界混淆的錯(cuò)誤(如如maybe與與maybe)。因?yàn)檎嬖~錯(cuò)誤的出錯(cuò)字符串是詞典中的正確詞因