BlockSu'da iki blok cevabının ne kadar benzediğini sayıya çevirmek faydalı. Ancak metinler yakın diye programlar aynı işi yapıyor diyemem. Levenshtein mesafesini bu yüzden bir doğruluk hakemi olarak değil, ekleme, silme ve değiştirme farklarını ölçen bir araç olarak kullanırım. Arşivdeki Compute ve GetSimilarityRatio akışı cevap karşılaştırmasına bu fikri taşıyor; aşağıdaki karakter tabanlı örnek bütün puanlama sisteminin kopyası değil.
Mesafe hangi soruya cevap veriyor?
kitten metnini sitting yapmak için k→s, e→i değişimleri ve sona g eklemesi yeterli. Üç işlemden daha kısa bir yol olmadığı için mesafe 3. Birim maliyetli klasik modelde her ekleme, silme ve değiştirme bir puan tutar. Birbirinin yerini değiştirmiş iki karakter için ayrıca “tek işlemde takas” kuralı yok; bu başka bir varyanttır.
static int Distance(string left,string right)
{
ArgumentNullException.ThrowIfNull(left);
ArgumentNullException.ThrowIfNull(right);
var costs=new int[left.Length+1,right.Length+1];
for(int i=0;i<=left.Length;i++)costs[i,0]=i;
for(int j=0;j<=right.Length;j++)costs[0,j]=j;
for(int i=1;i<=left.Length;i++)
for(int j=1;j<=right.Length;j++)
{
int replace=costs[i-1,j-1]+(left[i-1]==right[j-1]?0:1);
costs[i,j]=Math.Min(replace,Math.Min(costs[i-1,j]+1,costs[i,j-1]+1));
}
return costs[left.Length,right.Length];
}
static double Similarity(string a,string b) =>
a.Length==0&&b.Length==0?1:1d-(double)Distance(a,b)/Math.Max(a.Length,b.Length);
Console.WriteLine(Distance("kitten","sitting"));
Console.WriteLine(Similarity("",""));
Console.WriteLine(Distance("<move/>","<turn/>"));Örneği .NET 10 konsolunda çalıştırınca mesafe için 3, iki boş metnin benzerliği için 1 ve son XML benzeri çift için 4 elde edilir. Null girdi mesafe yordamında reddediliyor. Similarity yardımcı metodunda da null kabul edilmek istenmiyorsa aynı ön koşul çağrı sınırında korunmalı; kod her kullanıcı girdisini kendi başına doğrulayan bir endpoint değildir.
Matris hücresi bir önekin cevabıdır
costs[i,j], soldaki metnin ilk i birimini sağdakinin ilk j birimine dönüştürmenin en küçük maliyetini tutar. Boş metinden j birim üretmek j ekleme, i birimi boşaltmak i silme gerektirir; ilk satır ve kolon bu yüzden sayılarla başlatılır.
Her yeni hücre üç olasılığı karşılaştırır: üst komşuya bir silme eklemek, sol komşuya bir ekleme eklemek veya çapraz komşudan eşleşme/değiştirme ile gelmek. Karakterler aynıysa çapraz geçiş bedelsizdir. Math.Min daha önce çözülmüş küçük problemleri bir araya getirir; aynı önekleri tekrar tekrar hesaplamayız. Dinamik programlama burada soyut bir ad değil, matrisin doğrudan yaptığı iştir.
Benzerlik oranı algoritmanın zorunlu parçası değil
Örnekte oran 1 − distance / maxLength. kitten/sitting için 1 − 3/7, yaklaşık 0.571. Bu normalizasyonu uygulama seçiyor; Levenshtein mesafesinin kendisi yüzde puanı üretmez. Kısa bir metinde bir karakter değişmesiyle uzun bir metinde aynı değişiklik farklı oranlar verir. Eşik seçerken yalnız birkaç başarılı örneğe bakmak yeterli olmaz.
İki boş metne 1 vermek matematiksel bir özel durum seçimi. “Cevap boş bırakıldı” durumunu eğitim uygulamasında tam puan saymak zorunda değiliz. Girdi kabulü ve cevap tamlığı kuralları, benzerlik hesabından önce çalışmalı. Aynı şekilde yüksek benzerlik tek başına doğru çözüm kanıtı değildir.
Blockly XML'ini doğrudan karşılaştırmanın gürültüsü
Rastgele blok kimlikleri, metadata veya önemsiz boşluklar metin mesafesini artırabilir. Buna karşılık bir sayının veya operatörün küçük değişimi program davranışını tamamen değiştirebilir. “XML'in boşluklarına puan verdik” durumuna düşmemek için hangi farkların önemsiz olduğuna iş alanı karar vermeli.
Normalize etme de dikkat ister: değişken referanslarında kullanılan kimlikleri rastgele silmek ilişkileri bozabilir; blok veya argüman sırasını sıralamak program anlamını değiştirebilir. Yapısal karşılaştırma, tutarlı kimlik eşleme ve davranışsal test ayrı araçlardır. Arşivdeki kelime bazlı karşılaştırmayı bu karakter örneğiyle aynı şeymiş gibi sunmam.
Maliyet ve Unicode sınırı
m ve n uzunluklarında süre O(mn), bu tam matrisin belleği de O(mn). Yalnız son mesafe gerekiyorsa iki satırla bellek azaltılabilir; düzenleme yolunu göstermek için ek bilgi gerekir. İstemciden gelen büyük XML'e boyut sınırı koyarım. Eşik altını arayan bir senaryoda hesaplama stratejisini de o ihtiyaca göre daraltmak mümkün olabilir.
C# char karşılaştırması UTF-16 birimleri üzerindedir; görünen her karakterin tek birim olduğunu varsaymaz. Unicode normalizasyonu ve dil duyarlı büyük/küçük harf kuralları ayrıca düşünülür. XML'i gelişigüzel küçük harfe dönüştürmek ise doğru çözüm değildir; adların ve değerlerin anlamı kaybolabilir.
Test kümesinde eşit metin, tek ekleme, tek silme, iki boş metin, bir tarafın boş olması ve anlamsal olarak farklı ama yazı olarak yakın bloklar bulunmalı. Elde edilen sayıdan hangi kararın çıkarılacağını bu örneklerle birlikte açıklarım.
