編集距離：無視開始/終了

Question

私は編集距離を行うアルゴリズムを探していますが、1つの文字列と空白で終わる+スタート無視れる：

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

は、そのための既存のアルゴリズムがあります？たぶんPerlやPythonライブラリですか？

Answer 1

これを行うコードは概念的に単純です。それはあなたが自分で追加できることを無視したいもののアイデアです：

#!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; 
    } 

この非常にsimpleminded実装が見つかりますあなたが欲しいもの。しかし、他のランダムな文字列が間違って編集距離が狭くなっている可能性があることを認識してください。

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

あなたが元に再びそれを見つけることができるようにするには、各文字列の真の開始位置を覚えて、これを拡張することができ、これはあなたの方法であなたを送るのに十分でなければなりません。 Pythonを使いたければ、プログラムは非常によく似ているかもしれません。

Answer 2

ここにPerl 6のソリューションがあります。インタースティシャルのものにも関わらず、4人の面白いキャラクターをつかむ方法を知っている文法を使っています。より複雑な要件は異なる文法を必要とするが、それほど難しくない。

一致するたびに、NString :: Actionsクラスオブジェクトが一致を調べるための変更を取得します。それは私が以前やっていたものと同じ最高水準点のことをします。これは束の間の仕事のように見えますが、これは簡単な例です。より複雑な例については、それほど悪くはないでしょう。私のPerl 5バージョンは、何を保持するかどうかを理解するために多くのツールを必要とします。

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