I was inspired to tinker with partial string match algorithms by the eBird mobile app, which doesn't use one!
I created simple HTML pages to experiment with and compare algorithms in JavaScript.
More discussion of this work has been posted to my blog.
The search.html
page runs the final algorithm. It can be viewed here.
The compare.html
page compares results from the algorithms used in development. It can be viewed here.
I implemented the "iterative with full matrix" Levenshtein Distance algorithm from the pseudocode on Wikipedia.
For testing, I used eBird's "Printable Checklist" pages. After saving a page's HTML:
grep '<div class="subitem">' checklist.html | cut -d '>' -f 2 | cut -d '<' -f 1 | sort > checklist-birds.txt
MIT