in reply to Levenstein distance transcription

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 );

[download]

Or:

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

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

[download]

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'

[download]

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?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

Replies are listed 'Best First'.
Re^2: Levenstein distance transcription
by wollmers (Scribe) on Dec 05, 2014 at 21:07 UTC

    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'
          ]
        ];

    [download]

    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.</>

[reply]
[d/l]

In Section Seekers of Perl Wisdom