Edit distances

Edit distance is a way of comparing two strings with each other. One common use is just to calculate the distance between the two strings, where the distance is the sum of all the replacement, insertions and deletions needed to transform the first string to the other.

This program compares two strings using two edit distance algorithms: Hirschberg and Levenshtein. It not only shows the number of edit distance operations, but also shows the needed operations in a couple of ways. The mapping (conversion) from the first word to the second is not unique, and shows the specific conversion for the algoritm.

Tip: To see another mapping, it may be useful to insert spaces in front of, or after, either of the word.

This program was presented in my (swedish) weblogg hakank.blogg, in the post Ordavstånd (edit distances): Levenshtein och Hirschberg med lite extra finesser, and may contain some further comments.

Please note: This program is written in Perl but is heavily relying on the Javascript code contained in web pages referenced above. Credit to LAllison comp sci monash uni au for the Javascript coding. (This program should be at least bug compatible with the Javascript code.)

Please type in the two strings to compare

String 1:
String 2:


Hirschberg algorithm

Comparing and using Hirschberg algorithm.

Operations (graphical):




Explanation:
'-': insert or delete
'|': keep
' ': replace

Long description (string position in parenthesis):


Short description (k: keep, i: insert, d: delete, r: replace):

It was 0 edit operations:
('keep' is not counted as an operation)

Levenshtein algorithm

Comparing and using Levenshtein algorithm.

Operations (graphical):




Explanation:
'-': insert or delete
'|': keep
' ': replace

Long description (string position in parenthesis):


Short description (k: keep, i: insert, d: delete, r: replace):

It was 0 edit operations:
('keep' is not counted as an operation)

Back to my other useless programs
Back to my homepage
Created by Hakan Kjellerstrand hakank@bonetmail.com