Wagner-Fischer Algorithm
Ekleme, silme ve değiştirme maliyetlerinden iki dizgi arasındaki minimum edit maliyetini dinamik programlamayla hesaplayan algoritma.
Wagner-Fischer, edit distance'in en anlaşılır referans implementasyonudur: tablo hücresi iki prefix arasındaki en düşük dönüşüm maliyetini tutar ve üç komşu durumdan güncellenir.
Standart süre O(m*n)'dir. Yalnız mesafe isteniyorsa iki satır veya kısa olan boyut üzerinden O(min(m,n)) bellek yeterlidir. Edit script de gerekiyorsa backpointer veya yeniden yapılandırma stratejisi gerekir.
Production Notu
Arama yalnız belirli bir eşik altındaki sonuçlarla ilgileniyorsa tüm matrisi doldurmak gereksiz olabilir. Banded/Ukkonen türü sınırlandırmalar ve erken kesme ciddi CPU kazancı sağlar. Unicode metinde "karakter" biriminin byte, code point veya grapheme cluster olarak seçilmesi de sonuç semantiğini değiştirir.
Kaynak
- https://dl.acm.org/doi/10.1145/321796.321811