Re: Levenstein distance transcription

[BrowserUk]

I've got to wonder why you want this?

I normally try to resist asking this question, because I personally dislike having to explain my reasoning to others... but.

There are so many different possibilities for each pair of strings, to want any given one seems nonsensical.

For example: Given the length (in words) of any two strings, you can generate an "edit transcript" thus:

my $shorter = min( $lenString1, $lenString2 );
my $longer  = max( $lenString1, $lenString2 );

## longer to shorter
my $et = 'DI' x $shorter . 'D' x ( $longer - $shorter );

## or shorter to longer
my $et = 'DI' x $shorter . 'I' x ( $longer - $shorter );

Or:

## longer to shorter
my $et = 'D' x $longer . 'I' x $shorter;

## shorter to longer
my $et = 'D' x $shorter . 'I' x $longer;

As best I can tell, the only actually useful information you might glean from this, (done the full, laborious Levenstein way), is where the two sentences happen to contain the same word in the same position.

But given that if you had two identical sentences with the exception that one of the had an extra word at the start, eg:

'the quick brown fox'
'before the quick brown fox'

The Levenstein algorithm would fail to detect any 'same word in same place' and produce a "edit transcript" of (something like) 'DIDIDIDII'; I'm failing to see a good use?

[wollmers]

The Levenshtein algorithm finds the shortest edit script. In your example this would be:

use Algorithm::Diff qw(sdiff);
use Data::Dumper;
my $a=sdiff(
  [split(/\W+/,"the quick brown fox")],
  [split(/\W+/,"before the quick brown fox")]
);
print Dumper($a);

$VAR1 = [
          [
            '+',
            '',
            'before'
          ],
          [
            'u',
            'the',
            'the'
          ],
          [
            'u',
            'quick',
            'quick'
          ],
          [
            'u',
            'brown',
            'brown'
          ],
          [
            'u',
            'fox',
            'fox'
          ]
        ];

Algorithm::Diff (aka A::D) uses the Hunt-Szymansky-Algorithm which is an improved Levenshtein-Algorithm. The nice thing of A::D is the use of arrays as input, thus A::D can be used for everything, which can be represented as array of strings. Result can be edit-distance, edit-script, length of longest common substring (LLCS), longest common substring (LCS), and (global) alignment.

A::D is reasonable fast, A::DXS is a lot faster, but my private versions of them have approximately double speed. Of course, String::Similarity, purely string based, only determining LLCS, implementing Meyer's algorithm in C is ten times faster.</>