的Python 3：基本拼寫檢查

Question

#SPELL CHECK PROGRAM 
def SpellCheck(): 

    import difflib 
    import urllib.request 

    #Downloads 10000 most used english words as txt file 
    url = 'https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt' 
    response = urllib.request.urlopen(url) 
    data = response.read()  # 
    text = data.decode('utf-8') # 

    x = True 
    while x == True: 
     print("Enter your word: ") 
     word = input(">> ") 

     clr(2) 
     s(3) 

     if (word.lower()) in text: 
      print(word, " is spelt correctly") 

     else: 
      print("It doesn't seem like i know that word") 

      #closewords = difflib.get_close_matches(word, text) 
      wrongcount = 0 
      correctcount = 0 
      closewords = [] 

      ############ 

      for x in text: 
       wrongcount = 0 
       correctcount = 0 

       for let in x: 
        for letter in word: 
         if let == letter: 
          correctcount += 1 
         else: 
          wrongcount +=1 

        if correctcount > len(word) - 4: 
         closewords.append(x) 

        else: 
         x = 0 

      ############# 

      print("Perhaps you meant one of these: ") 
      print(closewords) 

     print("Would you like to try again?") 
     again = input(">> ") 

     if again == 'Y' or again == 'y' or again == 'yes' or again == 'Yes': 
      x = True 
     else: 
      print("Okay") 
      x = False 

它應該採取的10,000個最常用的英語單詞列表，並把它們變成一個列表。 如果用戶的單詞與列表中的某個單詞不匹配，它應該： 對於每個單詞中的每個字母，請檢查該單詞是否與用戶單詞中的單詞相匹配。 使用此來查看這兩個單詞中是否有任何/許多字母匹配。如果他們這樣做，將其打印在建議列表中。

如果輸入的單詞拼寫正確;它會打印拼寫正確

如果輸入的單詞拼寫錯誤;它會打印出拼寫錯誤，但它不會給出任何建議，即使例如; （我輸入「pooison」，它不會拿出任何東西，即使「毒藥」是字典）

應該在這種情況下，打印出「毒藥」

Answer 1

您的建議 - 不要」不要使用你的方法。建議密切詞的潛在更嚴格的方式是使用smith waterman type alignment algorithm。

其基本思想是您聲明對字母不匹配和插入其中一個單詞的處罰。然後，您可以選擇字典中匹配得分大於特定閾值的作品。對於長度爲n和m的單詞的算法是O（mn），所以對於10k短的單詞應該是相當合理的。

從實施角度看，這種算法主要用於基因序列近似匹配，所以大部分python實現都是針對這一點的。如果你找不到一個通用的實現，那麼寫你自己的學習練習可能是值得的。如果你願意，我可以給你一些指示嗎？

例

import numpy as np 
 
from collections import defaultdict 
 

 
def sub_function(letter1, letter2): 
 
    
 
    if letter1 == letter2: 
 
     return 1 #increase score if letter match 
 
    else: 
 
     return -1 # decrease score if letter mismatch 
 

 
     
 
#######################################################   
 

 

 
def needleman_wunsch(si,sj,d=-2): 
 
    #dimensions 
 
    I =len(si)+1 ; J = len(sj)+1 
 
     
 
    #define a dynamic programming matrix+backpointer matrix as a numpy array 
 
    DP=np.zeros([len(si)+1,len(sj)+1]); PTR = DP.copy() 
 

 
    #initialise top and left edges with the ga[ penalties 
 
    for i in range(0,DP.shape[0]): 
 
     DP[i,0]=d*(i) 
 
    for i in range(0,DP.shape[1]): 
 
     DP[0,i]=d*(i) 
 
    
 
    #iterations over DP matrix, generate PTR matrix to all reconstruction 
 
    for i in range(1,I): 
 
     for j in range(1,J): 
 
      F_ij =[DP[i,j-1]+d,DP[i-1,j]+d,DP[i-1,j-1]+sub_function(si[i-1],sj[j-1])] 
 
      DP[i,j]=max(F_ij) 
 
      PTR[i,j]=F_ij.index(DP[i,j]) 
 
    
 
    #reconstructed strings 
 
    sI='';sJ='' 
 
    l_c = [I-1,J-1]; p_c=PTR[l_c[0],l_c[1]] 
 
    
 
    #main loop 
 
    while l_c[0] >0 and l_c[1] >0: 
 
     i=l_c[0]-1; j=l_c[1]-1 # character indices 
 
     if PTR[l_c[0],l_c[1]] ==2: 
 
      sI+=si[i]; sJ+=sj[j]; 
 
      l_c=[l_c[0]-1,l_c[1]-1] 
 
     elif PTR[l_c[0],l_c[1]] ==1: 
 
      l_c=[l_c[0]-1,l_c[1]] 
 
      sI+=si[i]; sJ+='-'; 
 
     elif PTR[l_c[0],l_c[1]] ==0: 
 
      l_c=[l_c[0],l_c[1]-1] 
 
      sI+='-'; sJ+=sj[j]; 
 
     
 
    #reversing strings as loop builds them backwards 
 
    sI=sI[::-1]; sJ=sJ[::-1] 
 
    
 
    return (sI,sJ,DP[-1,-1]) # a tuple of the two string+ score 
 
    
 
def display(nw_tuple): 
 
    print nw_tuple[0] 
 
    print nw_tuple[1] 
 
    print 'score: '+str(nw_tuple[2]) 
 
    
 

 
match= needleman_wunsch('acknowledgment','acknowlefdgment') 
 
display(match)