Spell checker

[nathanael]

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 to the words in the dictionary. I have no idea why its doing that Here’s the code and output 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]== word:
found=True

elif secondLst[mid]<word :

lo=mid+1
else:

hi=mid-1
if not found:

absent.append(word)
print("Words not in dictionary : ", absent )

Output: Words not in dictionary : ['items', 'items', 'items', 'items', 'items', 'items', 'items', 'items', 'items', 'items', 'items', 'items']

 

[WhiteCube]

I dig a good binary search.

For a start, remove the binary search from the program. Just load and print the words. Test it until you're absolutely sure that the words are being loaded correctly.

There's a couple of logic problems with the search.

searching for 9

   L       H
...3 4 6 7 9...

mid points at 6, so lo = mid + 1

         L H
...3 4 6 7 9...

mid points at 7, so lo = mid + 1
           L
           H
...3 4 6 7 9...

The while exits, because lo is not less than hi. 9 is unfound.

The second problem is that when a word is found, the while gets stuck in an infinite loop, lo and hi are unchanged. The found needs to be in the while condition. (This is why I suspect your load isn't working correctly.)

When I do it, my indexes point just outside the search area. lo points to an element I know is less than the key, and hi points to an element I know is above it.

initialise: lo = -1, hi = length

if word at mid < key: lo = mid
if word at mid > key: hi = mid

mid = (lo + hi)//2 is the same as yours

when (lo+1 == hi) the search failed

 

[WhiteCube]

The interesting thing about lo=mid hi=mid is that it doesn't matter what order the list is in.

If the initial hi and lo are arguments, and the while exit condition checks that lo and hi are adjacent (absolute(lo-hi)==1) then the exact same code can be used for ascending order lists, and decending.

ascending
=bsearch(list,-1,length(list),key)

decending
=bsearch(list,length(list),-1,key)

On the other hand, I may have a warped sense of "interesting".

 

[WhiteCube]

If I was going to write a spell checker, I wouldn't load the whole dictionary into memory.

I would sort the text file, then sequentially read the text file, and the dictionary, one word at a time.

To find all the misspelled words, only needs one pass through the dictionary.

Instead of searching for a dictionary file on the internet (futile, been there), I would make one by downloading a dozen novels from Project Gutenberg and making a program to list all the unique words. Good enough.