<wbr id="juant"></wbr>
  • <wbr id="juant"></wbr>
    更多課程 選擇中心


    Python培訓

    400-111-8989

    Python 如何編寫一個拼寫糾錯器?

    • 發布:Python培訓
    • 來源:Python常見問題
    • 時間:2017-07-12 16:26

    2007年的某個星期,我的兩個朋友(Dean和Bill)分別向我傳達了他們對Google的拼寫自動糾錯能力的贊嘆。例如輸入"speling",Google會立即顯示"spelling"的檢索結果。我原以為這兩位才智卓越的工程師、數學家,會對其工作原理有準確的推測,事實上他們沒有。后來我意識到,他們怎么會對離自身專業領域如此遠的東西認知清晰呢?

    我覺得他們還有其他人,也許能從拼寫糾錯原理的解釋中獲益。工業級的完整拼寫糾錯相當復雜(詳細參見1和2),在橫貫大陸的航空旅途中,我用約半頁代碼寫了一個迷你拼寫糾錯器,其性能已經達到對句子以10詞/秒的速度處理,且糾錯準確率達到80%~90%。

    代碼如下:

    #coding:utf-8
    importre
    fromcollectionsimportCounter
    defwords(text):
    returnre.findall(r'w',text.lower())
    #統計詞頻
    WORDS=Counter(words(open('big.txt').read()))
    defP(word,N=sum(WORDS.values())):
    """詞'word'的概率"""
    returnfloat(WORDS[word])/N
    defcorrection(word):
    """最有可能的糾正候選詞"""
    returnmax(candidates(word),key=P)
    defcandidates(word):
    """生成拼寫糾正詞的候選集合"""
    return(known([word])orknown(edits1(word))orknown(edits2(word))or[word])
    defknown(words):
    """'words'中出現在WORDS集合的元素子集"""
    returnset(wforwinwordsifwinWORDS)
    defedits1(word):
    """與'word'的編輯距離為1的全部結果"""
    letters='abcdefghijklmnopqrstuvwxyz'
    splits=[(word[:i],word[i:])foriinrange(len(word)1)]
    deletes=[LR[1:]forL,RinsplitsifR]
    transposes=[LR[1]R[0]R[2:]forL,Rinsplitsiflen(R)>1]
    replaces=[LcR[1:]forL,Rinsplitsforcinletters]
    inserts=[LcRforL,Rinsplitsforcinletters]
    returnset(deletestransposesreplacesinserts)
    defedits2(word):
    """與'word'的編輯距離為2的全部結果"""
    return(e2fore1inedits1(word)fore2inedits1(e1))
    函數correction(word)返回一個最有可能的糾錯還原單詞:

    >>>correction('speling')
    'spelling'
    >>>correction('korrectud')
    'corrected'
    它是如何工作的:概率理論

    調用correction(w)函數將試圖選出對于詞w最有可能的拼寫糾正單詞,概率學上我們是無法預知應該選擇哪一個的(例如,"lates"應該被糾正為"late"還是"latest"或"latters"...?)。對于給定的原始詞w,我們試圖在所有可能的候選集合中,找出一個概率最大的修正結果c。

    $$argmax_cincandidatesP(c|w)$

    根據貝葉斯原理,它等價于:

    argmaxcincandidatesfracP(c)P(w|c)P(w)

    由于對w的每個候選單詞c,其P(w)均相等,因此剔除后公式如下:

    argmaxcincandidatesP(c)P(w|c)

    該式分為4個部分:
    1.選擇機制:argmax
    選擇候選集中概率最高的單詞。
    2.候選模型:cincandidates
    有哪些候選單詞可供考慮。
    3.語言模型:P(c)
    c在英語文本中出現的概率。例如:在英語文本出現的單詞中,約7%是"the",那么P(the)=0.07
    4.錯誤模型:P(w|c)
    當作者本意是c結果打成w的概率。例如:概率P(the|the)相當高,而P(theeexyz|the)將非常低。

    一個顯而易見的問題是:為什么將簡單的表達P(c|w)引入兩個模型使得其變得更復雜?答案是P(c|w)本身就是兩個部分的合并,將二者分開能更明確地進行處理。考慮對錯誤拼寫"thew"進行還原,兩個候選單詞分別是"the"和"thaw",二者誰的P(c|w)更高呢?"thaw"的優點在于它只對原詞做了細小的改變:將'e'換成'a'。而另一方面,"the"似乎是一個更常見的詞,盡管增加'w'似乎變化更大,可能性更小,也許是打字者在敲'e'后手滑呢?問題的核心在于:為了計算P(c|w)我們必須同時考慮c出現的概率,以及從c變成w的可能性。因此顯式地分為兩部分,思路上會更清晰。

    它是如何工作的:Python部分

    該程序的4個部分:
    1.選擇機制:在Python中,帶key的max()函數即可實現argmax的功能。
    2.候選模型:先介紹一個新概念:對一個單詞的簡單編輯是指:刪除(移除一個字母)、置換(單詞內兩字母互換)、替換(單詞內一個字母改變)、插入(增加一個字母)。函數edits1(word)返回一個單詞的所有簡單編輯(譯者:稱其編輯距離為1)的集合,不考慮編輯后是否是合法單詞:

    defedits1(word):
    """與'word'的編輯距離為1的全部結果"""
    letters='abcdefghijklmnopqrstuvwxyz'
    splits=[(word[:i],word[i:])foriinrange(len(word)1)]
    deletes=[LR[1:]forL,RinsplitsifR]
    transposes=[LR[1]R[0]R[2:]forL,Rinsplitsiflen(R)>1]
    replaces=[LcR[1:]forL,Rinsplitsforcinletters]
    inserts=[LcRforL,Rinsplitsforcinletters]
    returnset(deletestransposesreplacesinserts)
    這個集合可能非常大。一個長度為n的單詞,有n個刪除編輯,n?1個置換編輯,26n個替換編輯,26(n1)的插入編輯,總共54n25個簡單編輯(其中存在重復)。例如:

    >>>len(edits1('something'))
    442
    然而,如果我們限制單詞為已知(known,譯者:即存在于WORDS字典中的單詞),那么這個單詞集合將顯著縮小:

    defknown(words):
    """'words'中出現在WORDS集合的元素子集"""
    returnset(wforwinwordsifwinWORDS)
    >>>known(edits1('something'))
    ['something','soothing']
    我們也需要考慮經過二次編輯得到的單詞(譯者:"二次編輯"即編輯距離為2,此處作者巧妙運用遞歸思想,將函數edits1返回集合里的每個元素再次經過edits1處理即可得到),這個集合更大,但仍然只有很少一部分是已知單詞:

    defedits2(word):
    """與'word'的編輯距離為2的全部結果"""
    return(e2fore1inedits1(word)fore2inedits1(e1))
    >>>len(set(edits2('something'))
    90902
    >>>known(edits2('something'))
    {'seething','smoothing','something','soothing'}
    >>>known(edits2('somthing'))
    {'loathing','nothing','scathing','seething','smoothing','something','soothing','sorting'}
    我們稱edits2(w)結果中的每個單詞與w的距離為2。

    3.語言模型:我們通過統計一個百萬級詞條的文本big.txt中各單詞出現的頻率來估計P(w),它的數據來源于古騰堡項目中公共領域的書摘,以及維基詞典中頻率最高的詞匯,還有英國國家語料庫,函數words(text)將文本分割為詞組,并統計每個詞出現的頻率保存在變量WORDS中,P基于該統計評估每個詞的概率:

    defwords(text):
    returnre.findall(r'w',text.lower())
    #統計詞頻
    WORDS=Counter(words(open('big.txt').read()))
    defP(word,N=sum(WORDS.values())):
    """詞'word'的概率"""
    returnfloat(WORDS[word])/N
    可以看到,去重后有32,192個單詞,它們一共出現1,115,504次,"the"是出現頻率最高的單詞,共出現79,808次(約占7%),其他詞概率低一些。

    >>>len(WORDS)
    32192
    >>>sum(WORDS.values())
    1115504
    >>>WORDS.most_common(10)
    [('the',79808),
    ('of',40024),
    ('and',38311),
    ('to',28765),
    ('in',22020),
    ('a',21124),
    ('that',12512),
    ('he',12401),
    ('was',11410),
    ('it',10681),
    ('his',10034),
    ('is',9773),
    ('with',9739),
    ('as',8064),
    ('i',7679),
    ('had',7383),
    ('for',6938),
    ('at',6789),
    ('by',6735),
    ('on',6639)]
    >>>max(WORDS,key=P)
    'the'
    >>>P('the')
    0.07154434228832886
    >>>P('outrivaled')
    8.9645577245801e-07
    >>>P('unmentioned')
    0.0
    4.錯誤模型:2007年坐在機艙內寫這個程序時,我沒有拼寫錯誤的相關數據,也沒有網絡連接(我知道這在今天可能難以想象)。沒有數據就不能構建拼寫錯誤模型,因此我采用了一個捷徑,定義了這么一個簡單的、有缺陷的模型:認定對所有已知詞距離為1的編輯必定比距離為2的編輯概率更高,且概率一定低于距離為0的單詞(即原單詞)。因此函數candidates(word)的優先級如下:
    1.原始單詞(如果已知),否則到2。
    2.所有距離為1的單詞,如果為空到3。
    3.所有距離為2的單詞,如果為空到4。
    4.原始單詞,即使它不是已知單詞。

    效果評估

    現在我們看看程序效果如何。下飛機后,我從牛津文本檔案庫下載了RogerMitton的伯克貝克拼寫錯誤語料庫,從中抽取了兩個錯誤修正測試集,前者在開發中作為參考,調整程序以適應其結果;后者用于最終測試,因此我不能偷看,也無法在評估時修改程序。取兩個集合分別用于開發和測試是個好習慣,它讓我不至于自欺欺人地調整程序以適應結果,然后覺得程序效果有提升。我還寫了單元測試:

    defunit_tests():
    """開發的單元測試"""
    assertcorrection('speling')=='spelling'#insert
    assertcorrection('korrectud')=='corrected'#replace2
    assertcorrection('bycycle')=='bicycle'#replace
    assertcorrection('inconvient')=='inconvenient'#insert2
    assertcorrection('arrainged')=='arranged'#delete
    assertcorrection('peotry')=='poetry'#transpose
    assertcorrection('peotryy')=='poetry'#transposedelete
    assertcorrection('word')=='word'#known
    assertcorrection('quintessential')=='quintessential'#unknown
    assertwords('ThisisaTEST.')==['this','is','a','test']
    assertCounter(words('Thisisatest.123;ATESTthisis.'))==(
    Counter({'123':1,'a':2,'is':2,'test':2,'this':2}))
    assertlen(WORDS)==32192
    assertsum(WORDS.values())==1115504
    assertWORDS.most_common(10)==[
    ('the',79808),
    ('of',40024),
    ('and',38311),
    ('to',28765),
    ('in',22020),
    ('a',21124),
    ('that',12512),
    ('he',12401),
    ('was',11410),
    ('it',10681)]
    assertWORDS['the']==79808
    assertP('quintessential')==0
    assert0.07<P('the')<0.08
    return'unit_testspass'
    defspelltest(tests,verbose=False):
    """對測試集合1中的(right,wrong)詞條,運行correction(wrong)并統計結果的正確性"""
    importtime
    start=time.clock()
    good,unknown=0,0
    =len(tests)
    forright,wrongintests:
    w=correction(wrong)
    good=(w==right)
    ifw!=right:
    unknown=(rightnotinWORDS)
    ifverbose:
    print('correction({})=>{}({});expected{}({})'
    .format(wrong,w,WORDS[w],right,WORDS[right]))
    dt=time.clock()-start
    print('{:.0%}of{}correct({:.0%}unknown)at{:.0f}wordspersecond'
    .format(good/n,n,unknown/n,n/dt))
    defTestset(lines):
    """對測試集合2中的錯誤樣本,將'wrong1wrong2'修正為[('right','wrong1'),('right','wrong2')]"""
    return[(right,wrong)
    for(right,wrongs)in(line.split(':')forlineinlines)
    forwronginwrongs.split()]
    print(unit_tests())
    spelltest(Testset(open('spell-testset1.txt')))#Developmentset
    spelltest(Testset(open('spell-testset2.txt')))#Finaltestset
    結果如下:

    unit_testspass
    75%of270correctat41wordspersecond
    68%of400correctat35wordspersecond
    None
    可以看到,開發部分的集合準確率達到了74%(處理速度是41詞/秒),而在最終的測試集中準確率是68%(31詞/秒)。結論是:我達到了簡潔,開發時間短,運行速度快這3個目的,但準確性不太高。也許是我的測試集太復雜,又或是模型太簡單因故而不能達到80%~90%的準確率。

    后續工作

    考慮一下我們如何做的更好。
    1.語言模型P(c)。在語言模型中我們能區分兩種類型的錯誤(譯者:known詞和unknown詞,前者2次編輯詞集合存在元素inWORDS,后者不存在),更為嚴重的是unknow詞,程序會直接返回該詞的原始結果。在開發集合中,有15個unknown詞,約占5%,而測試集中有43個(11%)。以下我們給出部分spelltest的運行結果:

    correction('transportibility')=>'transportibility'(0);expected'transportability'(0)
    correction('addresable')=>'addresable'(0);expected'addressable'(0)
    correction('auxillary')=>'axillary'(31);expected'auxiliary'(0)
    我將期望輸出與實際輸出分別打印出來,計數'0'表示目標詞匯不在詞庫字典內,因此我們無法糾錯。如果能收集更多數據,包括使用一些語法(例如在單詞后加入"ility"或是"able"),我們能構建一個更好的語言模型。

    處理unknown詞匯的另一種辦法是,允許correction結果中出現我們沒見過的詞匯。例如,如果輸入是"electroencephalographicallz",較好的一種修正是將末尾的'z'替換成'y',盡管"electroencephalographically"并不在詞庫里,我們可以基于詞成分,例如發音或后綴來實現此效果。一種更簡單的方法是基于字母序列:統計常見2、3、4個字母序列。

    2.錯誤模型P(w|c)。目前為止我們的錯誤模型相當簡陋:認定編輯距離越短錯誤越小。這導致了許多問題,許多例子中應該返回編輯距離為2的結果而不是距離為1。如下所示:

    correction('reciet')=>'recite'(5);expected'receipt'(14)
    correction('adres')=>'acres'(37);expected'address'(77)
    correction('rember')=>'member'(51);expected'remember'(162)
    correction('juse')=>'just'(768);expected'juice'(6)
    correction('accesing')=>'acceding'(2);expected'assessing'(1)
    為何"adres"應該被修正為"address"而非"acres"呢?直覺是從'd'到"dd"和從's'到"ss"的二次編輯很常見,應該擁有更高的概率,而從'd'到'c'的簡單編輯概率很低。

    顯然我們可以根據編輯開銷來改進模型:根據直覺將疊詞的編輯開銷降低,或是改變元音字母。一種更好的做法是收集數據:收集拼寫錯誤的語料,并對照正確單詞統計增刪、替換操作的概率。想做好這些需要大量數據:例如給定窗口大小為2的兩個單詞,如果你想得到兩者間的全部修正概率,其可能的轉換有266種,超過3000萬詞匯。因此如果你想獲取每個單詞的幾個轉換實例,大約需10億條修正數據,如要保證質量,大概需要100億之多。

    注意到語言模型和錯誤模型存在聯系:目前如此簡陋(編輯距離為1的詞必定優于編輯距離為2的詞)的錯誤模型給語言模型造成阻礙:我們不愿將相對冷僻的詞放入模型內,因為如果這類詞恰好與輸入單詞的編輯距離為1,它將被選中,即使存在一個編輯距離為2但很常見的詞。好的錯誤模型在添加冷僻詞時更富有侵略性,以下例子展示了冷僻詞出現在字典里的危害:

    correction('wonted')=>'wonted'(2);expected'wanted'(214)
    correction('planed')=>'planed'(2);expected'planned'(16)
    correction('forth')=>'forth'(83);expected'fourth'(79)
    correction('et')=>'et'(20);expected'set'(325)
    3.修正集合argmaxc。本程序會枚舉某單詞所有編劇距離2以內的修正,在開發集的270個修正詞中只有3個編輯距離超過2,然而在測試集合中,23/400個編輯距離超過2,它們是:

    purpleperpul
    curtainscourtens
    minutesmuinets
    successfulsucssuful
    hierarchyheiarky
    professionpreffeson
    weightedwagted
    inefficientineffiect
    availabilityavaiblity
    thermawearthermawhere
    aturenatior
    dissensiondesention
    unnecessarilyunessasarily
    disappointingdissapoiting
    acquaintancesaquantences
    thoughtsthorts
    criticismcitisum
    immediatelyimidatly
    ecessarynecasery
    ecessarynessasary
    ecessarynessisary
    unnecessaryunessessay
    ightnite
    minutesmuiuets
    assessingaccesing
    ecessitatesnessisitates
    我們可以考慮擴展一下模型,允許一些編輯距離為3的詞進入修正集合。例如,允許元音之后插入元音,或元音間的替換,又或'c'和's'之間的替換。

    4.第四種(也可能是最佳)改進方案為:將correction的文本窗口調大一些。當前的correction只檢測單個詞,然而在許多情形下僅靠一個單詞很難做出判決。而假若這個單詞恰好出現在字典里,這種糾錯手段就更顯無力。例如:

    correction('where')=>'where'(123);expected'were'(452)
    correction('latter')=>'latter'(11);expected'later'(116)
    correction('advice')=>'advice'(64);expected'advise'(20)
    我們幾乎不可能知道correction('where')在某個語句內應該返回"were",而在另一句返回"where"。但如果輸入語句是correction('Theywheregoing'),我們很容易判定此處"where"應該被糾錯為"were"。

    要構建一個能同時處理詞和上下文的模型需要大量數據。幸運的是,Google已經公開了最長5個詞的全部序列詞庫,該數據源于上千億的語料集。我相信要使拼寫糾錯準確率達到90%,必須依賴上下文輔助決策,關于這個以后我們再討論。

    我們也可以決定以哪種方言進行訓練。以下糾正時產生的錯誤均源于英式和美式拼寫間的差異:

    correction('humor')=>'humor'(17);expected'humour'(5)
    correction('oranisation')=>'organisation'(8);expected'organization'(43)
    correction('oranised')=>'organised'(11);expected'organized'(70)
    5.最后,我們可以改進實現方法,使程序在不改變結果的情況下運行速度更快。例如:將實現該程序的語言從解釋型語言換成編譯型語言;緩存糾錯結果從而不必重復糾錯。一句話:在進行任何速度優化前,先大致看看時間消耗情況再決定優化方向。

    閱讀材料

    RogerMitton關于拼寫檢測的調研文章
    Jurafsky和Martin的教材中拼寫檢測部分。
    Manning和Schutze在他們編撰的FoundationsofStatisticalNaturalLanguageProcessing中很好的講述了統計語言模型,但似乎沒有(至少目錄中沒有)提及拼寫檢查。
    aspell項目中有大量有趣的材料,其中的一些測試數據似乎比我使用的更好。
    LinPipe項目有一個拼寫檢測教程

    預約申請免費試聽課

    填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

    上一篇:iOS程序員如何使用Python寫網路爬蟲
    下一篇:如何用Python分析用戶消費行為?Python分析用戶消費行為教程

    Python培訓班線上線下哪種靠譜

    python線上培訓班學費一般多少

    Python線下培訓班有哪些

    一篇文章帶你了解python和c語言的區別

    • 掃碼領取資料

      回復關鍵字:視頻資料

      免費領取 達內課程視頻學習資料

    • 視頻學習QQ群

      添加QQ群:1143617948

      免費領取達內課程視頻學習資料

    Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

    選擇城市和中心
    黑龍江省

    吉林省

    河北省

    湖南省

    貴州省

    云南省

    廣西省

    海南省

    天天日天天射天天干天天伊|奇米电影|奇米网_奇米首页|奇米首页 百度 好搜 搜狗
    <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>