nrg3

nrg3 / Editdistance / 0.1.1

README.md
This algorithm finds editing distance of two given strings, which is based on insertions, deletions and substitutions.
The algorithm takes 5 arguments:
- first string;
- second string;
- price of insertion;
- price of deletion;
- price of substitution;
The algorithm returns one integer, which corresponds to minimal editing distance price using given prices for operations from input.

Time complexity O(n*m), space complexity O(n), where n and m are minimal and maximal sizes of input strings respectively.

If all prices are set to 1, then the algorithm calculates Levenshtein distance, i.e. merely number of required editing operations in order to convert first string into second one.

More details:
http://en.wikipedia.org/wiki/Edit_distance
http://en.wikipedia.org/wiki/Levenshtein_distance

Usage: natural language processing, bioinformatics...