I’m trying to make spell checker program that will compare words from a text file to a dictionary of words that are in alphabetical order. If the words don’t appear in the dictionary they should show up in a list as potentially incorrect. The list is named absent[] that will be outputted at the end. I need to use a binary search to iterate over the dictionary comparing them to the words from the text file. However the program is only getting the last word from the text file and comparing that in the dictionary. I have no idea why its doing that Here’s the code I have thus far:
def binarySearch():
firstLst=[]
fnameOne= input("enter file")
with open(fnameOne,"r") as file_dataOne:
for lineOne in file_dataOne:
for word in lineOne.split():
firstLst.append(word)
secondLst=[]
fnameTwo=input("enter dict")
with open(fnameTwo,"r") as file_dataTwo:
for lineTwo in file_dataTwo:
for wordTwo in lineTwo.split():
secondLst.append(wordTwo)
absent =[]
for word in firstLst:
lo,hi=0,len(secondLst)-1
found=False
while lo < hi:
mid = (lo +hi) //2
if secondLst[mid]== i:
found=True
elif secondLst[mid]<i :
lo=mid+1
else:
hi=mid-1
if not found:
absent.append(i)
print("Words not in dictionary : ", absent )
There’s an even better way to do it: Iterate over the dictionary of words once, and build up a Python set or dict object. (Yes, that’s called a dictionary too, have fun with the names there.) You can then directly ask the question “is this word in the dictionary” and let Python do the rest.
Also I think the while line and if not found block are wrongly indented. The final print line should be outside the for word in firstLst loop but the if not found should be inside the loop
from pathlib import Path
# read the word file in (one word per line)
valid_words = set(Path('words.txt').read_text().split('\n'))
def get_invalid_words(doc: Path) -> list[str]:
"""get a list of words in the doc that are not in the dictionary.
preserves order of appearance"""
return [
word
for word in doc.read_text().split()
if word not in valid_words
]
This seems like a homework problem, so switching from a binary search to a set() is probably out of scope.
As homework goes, it could either be that you wrote this code to solve the problem and need help, or were given this code to analyze. If the latter, giving the specific fix will not help you learn.
The problem in the code occurs in this section:
What you need to be looking at is indentations and how those define code blocks. Which blocks should be nested inside another, which should follow one after the next? The structure you have is:
# Iterate over words
for loop:
...
# Perform binary search
while loop:
...
if A: ...
elif B: ...
else: ...
# Report finding
if C:
...
Hopefully this can help you see why it only checks the last word. If you’re still having trouble, put print() statements inside your loops to see when each word is being looked at.
I moved the while loop inside the for loops and also the last print statement outside of the for word in firstLst loop but now after I type in the file names it’s not giving me any output. Technically the programs is still running but its not showing anything after I input the file names.
I’d check how much the overhead is for a spell checker.
I used a QSet class in Qt to do a little game (parolottero) a while ago and in the end the word list at runtime was taking up 40MiB of RAM while the file itself was roughly 10x smaller than that.
Also on my pinephone creating the set noticeably froze the UI for like half a second.
I ended up moving to a binary format and using mmap(), and binary search instead. It’s fast enough while playing, doesn’t freeze the UI while loading and uses way less RAM.
In conclusion, binary search for a large amount of data (such as a wordlist) might be the better approach.
I suspect that the performance isn’t nearly as important as the mastery gained by implementing this - it’s an excellent exercise for a programmer.
Have you considered a set or dict instead? I can load up a 7MB dictionary into about 43MB of total memory usage, without any extra hassles. No need to implement a binary search, no need to worry about whether it’s sorted.
>>> def memusage():
... with open("/proc/self/status") as f:
... for line in f:
... if line.startswith("VmPeak:"):
... return line[8:].strip()
...
>>> memusage()
'27232 kB'
>>> words = {word.strip() for word in open("/usr/share/dict/british-english-insane") if set(word) < set("qwertyuiopasdfghjklzxcvbnm\n")}
>>> memusage()
'70248 kB'
>>> 70248-27232
43016
>>> len(words)
429261
(The alphabet check is optional, but I tend to prefer to exclude words with uppercase letters in them and other such extraneous examples. You could keep the entire dictionary if you prefer. Also, I went for the largest English dictionary I have installed - usually I’d use a much more normal one and it’d be correspondingly smaller.)
In general, Python won’t punish you too badly for writing idiomatic code; yes, you might be able to do something a little faster in C, but you also might not, and every line of code you don’t have to write is one you don’t have to debug. It’s quite likely that a hashtable (as used in Python’s dictionaries) will be faster than anything you can do with a binary search anyway.