So here I am programming for my class in 107. I'm pretty behind on the assignment due to a long weekend helping out with the job fair and doing my duties to it. The job fair approximately took about 20 working hours out of my weekend, setting me way too far behind. I'm coming up to the deadline, and I need to finish my assignment.
This whole assignment deals with find misspellings in text files and finding the most likely correction. The main algorithm of this program deals with finding the levenshtein distance between two words. This is basically the number of edits it takes to get from one word to the other. My edit_distance function at the moment was running perfectly, except for the huge amount of recursive calls it was using.
I've fixed several errors that were pretty small and simple. A bad find_min function and a missing ++i and it seems to be all working pretty well. What is not working well is my recursive find_edit_distance function. I can't get the recursive statement to quit early. Without going into too much detail on this assignment here, due to Stanford legality.
I knew that I needed a function that could quit out early because I was only looking for the top five misspellings. There was no need to keep recursing if the number of edits was more then the "weakest" function in the top five misspellings. I decided to pass in a max, to try and help with this.
I couldn't figure out how to quit early, though. I should've trusted my instinct and passed in a fourth variable. The thing that bothered me was that this ruined the magic of recursion. There was no need to return a distance then. It was unneeded. Midnight was rolling around, but I still held my head high that there must be some way to cancel out early.
Sadly, midnight passed and I realized that I did need a fourth variable. I turned in the assignment an aggravating 8 mins late, but it was working perfectly and it was as fast as the solution. I felt good, accomplished, but pretty peeved because I had something that I was using this fourth variable. I felt dumb.
This could've been solved by using dynamic programming with a matrix that would allow for me to quit early when I was already computing edit distances that were too big. Sadly, though, I had to butcher recursion. I committed a most high foul crime in Computer Science that I'm not sure I will ever forgive myself about.
This whole assignment deals with find misspellings in text files and finding the most likely correction. The main algorithm of this program deals with finding the levenshtein distance between two words. This is basically the number of edits it takes to get from one word to the other. My edit_distance function at the moment was running perfectly, except for the huge amount of recursive calls it was using.
 |
| This works on levenshtein distance |
I've fixed several errors that were pretty small and simple. A bad find_min function and a missing ++i and it seems to be all working pretty well. What is not working well is my recursive find_edit_distance function. I can't get the recursive statement to quit early. Without going into too much detail on this assignment here, due to Stanford legality.
I knew that I needed a function that could quit out early because I was only looking for the top five misspellings. There was no need to keep recursing if the number of edits was more then the "weakest" function in the top five misspellings. I decided to pass in a max, to try and help with this.
I couldn't figure out how to quit early, though. I should've trusted my instinct and passed in a fourth variable. The thing that bothered me was that this ruined the magic of recursion. There was no need to return a distance then. It was unneeded. Midnight was rolling around, but I still held my head high that there must be some way to cancel out early.
Sadly, midnight passed and I realized that I did need a fourth variable. I turned in the assignment an aggravating 8 mins late, but it was working perfectly and it was as fast as the solution. I felt good, accomplished, but pretty peeved because I had something that I was using this fourth variable. I felt dumb.This could've been solved by using dynamic programming with a matrix that would allow for me to quit early when I was already computing edit distances that were too big. Sadly, though, I had to butcher recursion. I committed a most high foul crime in Computer Science that I'm not sure I will ever forgive myself about.
No comments:
Post a Comment