二分搜索 Python 拼写检查

Question

我正在尝试导入一个文本文件（里面全是小写字母的单词，没有标点符号），然后把这些单词和一个字典列表里的单词进行比较。如果某个单词在字典列表中找不到，就把它打印出来，标记为可能是错误的。如果某个单词在字典列表中找到了，就什么都不做。我们这里应该使用二分查找的方法。我觉得我的二分查找方法是对的，只是不知道在哪里或者怎么把那些不在字典列表中的单词返回出来，并标记它们为可能错误。

谢谢！

我的输入文件句子是：the quick red fox jumps over the lzy brn dog

def spellcheck(inputfile):

filebeingchecked=open(inputfile,'r')
spellcheckfile=open("words.txt",'r')

dictionary=spellcheckfile.read().split()
checkedwords=filebeingchecked.read().split()

for word in checkedwords:

    low = 0
    high=len(dictionary)-1

    while low <= high:

        mid=(low+high)//2
        item=dictionary[mid]

        if word == item:
            return word

        elif word < item:
            high=mid-1

        else:
            low=mid+1

    return word

def main():

    print("This program accepts a file as an input file and uses a spell check function to \nidentify any problematic words that are not found in a common dictionary.")
    inputfile=input("Enter the name of the desired .txt file you wish to spellcheck: ")

main()

Answer 1

二分查找在你要查找的数组为空时就“结束”了。在你的情况中，你用 low 和 high 来记录数组的起始和结束位置，你说得对，应该在 low <= high 的条件下继续查找。

但是，当 (low <= high) == False 的时候，说明了什么呢？这意味着你还没有找到匹配的单词。

这就表示这个单词不在你的字典里，你应该采取相应的措施（把它加入“错误单词”的列表）。

当然，你只有在检查完所有应该查找的单词后，才会输出错误单词的列表。

Answer 2

当 word == item 时，你不想返回这个单词。你想要跳出这个循环。不过，跳出一个循环有两个条件：

1. 当这个单词在字典里时，你就跳出循环，或者
2. 当这个单词不在字典里时，最终循环也会结束

那么，我们怎么区分这两种情况呢？其实在Python中，while 和 for 循环都有一个 else 子句：这个 else 里的代码只有在循环自然结束时才会执行，而不是因为遇到 break 语句。所以我就用这个方法。

另外，如果想返回多个单词，我可以把它们收集到一个列表里，然后再返回这个列表，或者我可以使用 yield 关键字。下面看看它是怎么工作的。

def spellcheck(inputfile):

    filebeingchecked=open(inputfile,'r')
    spellcheckfile=open("words.txt",'r')

    dictionary=spellcheckfile.read().split()
    checkedwords=filebeingchecked.read().split()

    for word in checkedwords:

        low = 0
        high=len(dictionary)-1

        while low <= high:

            mid=(low+high)//2
            item=dictionary[mid]

            if word == item:
                break

            elif word < item:
                high=mid-1

            else:
                low=mid+1
        else:
            yield word

def main():

    print("This program accepts a file as an input file and uses a spell check function to \nidentify any problematic words that are not found in a common dictionary.")
    inputfile=input("Enter the name of the desired .txt file you wish to spellcheck: ")
    for word in spellcheck(inputfile):
        print(word)

main()