kylebgorman
/ wagnerfischer.py
Created
July 14, 2011 04:41
Python implementation of the Wagner & Fischer dynamic programming approach to computing Levenshtein distance, with support for thresholding, arbitrary weights, and traceback to get individual insertion/deletion/substitution counts.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python | |
| # wagnerfischer.py: Dynamic programming Levensthein distance function | |
| # Kyle Gorman <gormanky@ohsu.edu> | |
| # | |
| # Based on: | |
| # | |
| # Robert A. Wagner and Michael J. Fischer (1974). The string-to-string | |
| # correction problem. Journal of the ACM 21(1):168-173. | |
| # | |
| # The thresholding function was inspired by BSD-licensed code from |