使用二分搜索进行拼写检查

Question

我正在尝试使用二分查找来检查文件中单词的拼写，并打印出那些不在字典里的单词。但是现在，大部分拼写正确的单词却被错误地打印成拼写错误（也就是在字典里找不到的单词）。字典文件也是一个文本文件，内容大概是这样的：

abactinally
abaction
abactor
abaculi
abaculus
abacus
abacuses
Abad
abada
Abadan
Abaddon
abaddon
abadejo
abadengo
abadia

代码：

def binSearch(x, nums):
    low = 0
    high = len(nums)-1
    while low <= high:          
        mid = (low + high)//2   
        item = nums[mid]
        if x == item :
            print(nums[mid])
            return mid
        elif x < item:         
            high = mid - 1      
        else:                  
            low = mid + 1       
    return -1                  



def main():

    print("This program performs a spell-check in a file")
    print("and prints a report of the possibly misspelled words.\n")

    # get the sequence of words from the file
    fname = input("File to analyze: ")
    text = open(fname,'r').read()
    for ch in '!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~':
        text = text.replace(ch, ' ')
    words = text.split()

    #import dictionary from file
    fname2 =input("File of dictionary: ")
    dic = open(fname2,'r').read()
    dic = dic.split()

    #perform binary search for misspelled words
    misw = []
    for w in words:
        m = binSearch(w,dic)
        if m == -1:
            misw.append(w)

Answer 1

你的二分查找功能运行得很好！不过，你似乎没有完全去掉所有的特殊字符。

我用自己的句子测试了一下你的代码：

def main():

   print("This program performs a spell-check in a file")
   print("and prints a report of the possibly misspelled words.\n")

   text = 'An old mann gathreed his abacus, and ran a mile.  His abacus\n ran two miles!'
   for ch in '!"#$%&()*+,-./:;<=>?@[\\]^_`{|}~':
       text = text.replace(ch, ' ')
   words = text.lower().split(' ')

   dic = ['a','abacus','an','and','arranged', 'gathered', 'his', 'man','mile','miles','old','ran','two']

   #perform binary search for misspelled words
   misw = []
   for w in words:
       m = binSearch(w,dic)
       if m == -1:
           misw.append(w)
   print misw

输出结果是 ['mann', 'gathreed', '', '', 'abacus\n', '']

那些多出来的空字符串 '' 是因为你把标点符号替换成了空格，结果留下了多余的空格。\n（换行符）就有点麻烦了，因为它在外部文本文件中确实会出现，但处理起来不太直观。你应该做的，不是像这样 for ch in '!"#$%&()*+,-./:;<=>?@[\\]^_``{|}~':，而是检查每个字符是否是字母 .isalpha()。试试这个：

def main():

   ...

   text = 'An old mann gathreed his abacus, and ran a mile. His abacus\n ran two miles!'
   for ch in text:
       if not ch.isalpha() and not ch == ' ': 
           #we want to keep spaces or else we'd only have one word in our entire text
           text = text.replace(ch, '') #replace with empty string (basically, remove)
   words = text.lower().split(' ')

   #import dictionary
   dic = ['a','abacus','an','and','arranged', 'gathered', 'his', 'man','mile','miles','old','ran','two']

   #perform binary search for misspelled words
   misw = []
   for w in words:
       m = binSearch(w,dic)
       if m == -1:
           misw.append(w)
   print misw

输出：

This program performs a spell-check in a file
and prints a report of the possibly misspelled words.

['mann', 'gathreed']

希望这对你有帮助！如果你需要进一步解释或者有什么不明白的地方，随时可以留言。