编辑距离：忽略开始/结束[关闭]

Question

我正在寻找一种算法，它可以编辑距离，但会忽略一个字符串和空白中的开始和结束：

edit("four","foor") = 1
edit("four","noise fo or blur") = 1

有没有现成的算法？甚至可能是Perl或Python库？

Answer 1

这里有一个Perl6解决方案。我使用的语法知道如何抓住四个有趣的字符，尽管中间有一些东西。更复杂的需求需要不同的语法，但这并不难。

每次有匹配时，NString:：Actions类对象都会得到一个更改来检查匹配。它和我以前做的一样高水位。这看起来需要做更多的工作，这就是这个小例子。对于更复杂的例子，情况不会更糟。我的Perl5版本需要做大量的工具来确定保留什么或不保留什么。

use Text::Levenshtein;

my $string = 'The quixotic purple and jasmine butterfly flew over the quick zany dog';

grammar NString {
    regex n-chars      { [<.ignore-chars>* \w]**4 }
    regex ignore-chars { \s }
    }

class NString::Actions {
    # See 
    my subset IntInf where Int:D | Inf;

    has        $.target;
    has Str    $.closest          is rw = '';
    has IntInf $.closest-distance is rw = Inf;

    method n-chars ($/) {
        my $string = $/.subst: /\s+/, '', :g;

        my $distance = distance( $string,  self.target );
        # say "Matched <$/>. Distance for $string is $distance";
        if $distance < self.closest-distance {
            self.closest = $string;
            self.closest-distance = $distance;
            }
        }
    }

my $action =  NString::Actions.new: target => 'Perl';

loop {
    state $from = 0;
    my $match = NString.subparse(
        $string,
        :rule('n-chars'),
        :actions($action),
        :c($from)
        );
    last unless ?$match;

    $from++;
    }

say "Shortest is { $action.closest } with { $action.closest-distance }";

（我从Perl 5做了一个直接的端口，我将在这里离开）

我在Perl 6中尝试了同样的方法，但我确信这有点冗长。我想知道是否有一种聪明的方法来抓取N个字符组进行比较。也许我以后会有一些进步。

use Text::Levenshtein;

put edit( "four", "foar" );
put edit( "four", "noise fo or blur" );

sub edit ( Str:D $start, Str:D $target --> Int:D ) {
    my $target-modified = $target.subst: rx/\s+/, '',  :g;

    my $last-position-to-check = [-] map { .chars }, $target-modified, $start;

    my $closest = Any;
    my $closest-distance = $start.chars + 1;
    for 0..$last-position-to-check -> $starting-pos {
        my $substr = $target-modified.substr: $starting-pos, $start.chars;
        my $this-distance = distance( $start, $substr );
        put "So far: $substr -> $this-distance";
        if $this-distance < $closest-distance {
            $closest          = $substr;
            $closest-distance = $this-distance;
            }
        last if $this-distance = 0;
        }

    return $closest-distance // -1;
    }

Answer 2

实现这一点的代码在概念上很简单。您可以自己添加您想要忽略的内容：

#!perl
use v5.22;
use feature qw(signatures);
no warnings qw(experimental::signatures);

use Text::Levenshtein qw(distance);

say edit( "four", "foor" );
say edit( "four", "noise fo or blur" );

sub edit ( $start, $target ) {
    # transform strings to ignore what you want
    # ...
    distance( $start, $target )
    }

可能要检查相同长度的所有子字符串：

use v5.22;
use feature qw(signatures);
no warnings qw(experimental::signatures);

use Text::Levenshtein qw(distance);

say edit( "four", "foar" );
say edit( "four", "noise fo or blur" );

sub edit ( $start, $target ) {
    my $start_length = length $start;
    $target =~ s/\s+//g;
    my @all_n_chars = map {
        substr $target, $_, 4
        } 0 .. ( length($target) - $start_length );

    my $closest;
    my $closest_distance = $start_length + 1;
    foreach ( @all_n_chars ) {
        my $distance = distance( $start, $_ );
        if( $distance < $closest_distance ) {
            $closest = $_;
            $closest_distance = $distance;
            say "closest: $closest Distance: $distance";
            last if $distance == 0;
            }
        }

    return $closest_distance;
    }

这个非常简单的实现可以找到您想要的。但是，请注意，其他随机字符串可能会意外地具有较低的编辑距离。

closest: foar Distance: 1
1
closest: nois Distance: 3
closest: foor Distance: 1
1

您可以扩展它来记住每个字符串的真实起始位置，这样您就可以在原始字符串中再次找到它，但这应该足以让您继续前进。如果你想使用Python，我认为这个程序看起来可能非常相似。