Mikrooptymalizacja do obliczania odległości edycji: czy jest poprawna?

W Wikipedii podano implementację oddolnego schematu programowania dynamicznego dla odległości edycji. Nie jest całkowicie zgodny z definicją; komórki wewnętrzne są obliczane w następujący sposób:

if s[i] = t[j] then  
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

Jak widać, algorytm zawsze wybiera wartość od lewego górnego sąsiada, jeśli istnieje dopasowanie, oszczędzając dostęp do pamięci, operacje ALU i porównania.

Jednak usunięcie (lub wstawienie) może skutkować mniejszą wartością, dlatego algorytm jest lokalnie niepoprawny, tzn. Łamie kryterium optymalności. Ale może błąd nie zmienia wyniku końcowego - może zostać anulowany.

Czy ta mikrooptymalizacja jest ważna i dlaczego (nie)?

Nie sądzę, że algorytm jest wadliwy. Jeśli dwa ciągi są dopasowane, najpierw porównujemy jego ostatnie dwa znaki (a następnie powtarzamy). Jeśli są takie same, możemy je dopasować, aby uzyskać optymalne wyrównanie. Rozważmy na przykład ciągi testi testat. Jeśli nie pasujesz do dwóch ostatnich ts, jeden z nich tpozostaje niedopasowany, ponieważ w przeciwnym razie dopasowanie wyglądałoby tak:

Jest to niemożliwe, ponieważ strzałki nie mogą się „krzyżować”. Dopasowanie tpowoduje kilka wstawek (zielone pola na rysunku), jak pokazano po lewej stronie:

Ale wtedy możesz po prostu znaleźć równie dobre wyrównanie, przedstawione po prawej stronie. W obu przypadkach pasujesz do a ti masz dwie wstawki.

Argument za zastąpieniem jednego z ostatnich ts jest taki sam. Więc jeśli zastąpisz jedno z ostatnich ts, możesz zamiast tego dopasować dwa ostatnie t i uzyskać lepsze wyrównanie (patrz obrazek).