8
An implementation of the Levenshtein distance algorithm in LUA.
source link: https://gist.github.com/Badgerati/3261142
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Instantly share code, notes, and snippets.
An implementation of the Levenshtein distance algorithm in LUA.
Thanks for this!
Oustanding!
This is great, thanks. :)
who came here from that one devforum
quick note: because in line 35 you only ever refer to matrix[i] and matrix[i-1], you can get away with just storing the two most recent lines of the matrix, rather than computing the whole thing. This gets you down to O(2n) space (while still taking O(n^2) time)
You can use a modified version of this algorithm to search for substrings that closely match another string.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK