Sayısal Soundex ile Türkçe Fonetik Eşleme

Bir Soundex anahtarının string olarak tutulması zorunlu değildir. Klasik biçimde S530 gibi bir harf ve üç rakamla gösterilen fonetik kod, ilk karakter ile üç basamaklı sayısal bölüm çakışmasız biçimde bir int içinde paketlenebilir. Geliştirdiğim gerçeklenimde bu seçimi bilinçli olarak yaptım. Amaç yalnızca daha kısa bir dönüş değeri üretmek değildi. Kodun HashSet<int> gibi yapılarda doğrudan kullanılabilmesi, değer karşılaştırmasının ucuz kalması ve fonetik anahtarın bir nesnenin GetHashCode() davranışına temel oluşturabilmesi de tasarımın parçasıydı.

Kod, klasik Soundex mantığını Türkçe karakterleri tanıyacak biçimde genişleten hafif bir fonetik eşleme katmanıdır. Her sözcük en fazla üç fonetik rakama indirgenir. İlk harf ise ASCII büyük harf biçiminde korunur. Dönüşüm tek geçişte tamamlanır, sonuç için yeni bir dize oluşturulmaz ve sözcük uzun olsa bile üçüncü fonetik rakam bulunduğunda tarama sona erer.

Bu gerçeklenimi AI destekli kod üretim araçlarının yaygınlaşmasından önce geliştirdim. Kodun ilgi çekici tarafı, Soundex kurallarını uygulamasından çok, klasik dört karakterli çıktıyı sabit boyutlu sayısal bir anahtara dönüştürmesi ve bunu çok sözcüklü eşleme işlemleriyle birleştirmesidir.

Soundex algoritmasının sınırı

Soundex'in kökeni, Robert C. Russell'ın 1918 ve 1922 yıllarında aldığı fonetik indeks patentlerine dayanır. Daha sonraki tarihsel anlatımlarda Margaret K. Odell ile birlikte anılan yöntem, farklı yazılan fakat İngilizce telaffuzları birbirine benzeyen soyadlarını aynı indeks altında toplamak için geliştirilmiştir.

Klasik Amerikan Soundex kodu ilk harfi korur ve ardından üç rakam üretir. Sessiz harfler şu sınıflara ayrılır:

1 = B, F, P, V
2 = C, G, J, K, Q, S, X, Z
3 = D, T
4 = L
5 = M, N
6 = R

Sesli harfler ile bazı ayırıcı harfler rakam üretmez. Kod üç rakamdan kısa kalırsa sıfırla tamamlanır. Üç rakama ulaşıldığında sözcüğün geri kalanı sonucu değiştirmez.

Soundex, fonetik benzerliği kesin olarak ölçen bir model değildir. Birçok farklı sözcüğü aynı sınıfa indirger. Aynı telaffuza sahip iki sözcüğün aynı kodu üretmesi de her dil ve yazım biçimi için garanti edilmez. Bu nedenle yöntem bir kimlik doğrulama algoritması değil, aday kümesini daraltan bir fonetik indeks olarak ele alınmalıdır.

Türkçeye uyarlanan kodda klasik ikinci sınıf genişletilmiştir:

2 = C, Ç, G, Ğ, J, K, Q, S, Ş, X, Z

Ö, Ü ve I/İ/ı/i ailesi dahil olmak üzere rakam üretmeyen karakterler 0 sınıfına düşer. Bu genişletme Türkçe karakterlerin kaybolmasını önler, ancak başlı başına Türkçe ses bilgisi modeli oluşturmaz. Örneğin g, ğ, k, s ve ş aynı sayısal sınıfta yer alır. Bu karar fonetik ayrıntıyı korumaktan çok geniş aday eşleşmesi üretmeyi hedefler.

Karakter sınıflandırması

Algoritmanın en alt katmanı, tek bir karakteri 0 ile 6 arasında bir değere eşleyen sabit bir fonksiyondur:

f(c) -> {0, 1, 2, 3, 4, 5, 6}

Karakter sınıflandırması bir switch yapısıyla gerçekleştirilir. Türkçe karakterlerin büyük ve küçük biçimleri doğrudan aynı dallara yazılmıştır. Kültüre bağlı ToUpper() veya ToLower() işlemi sınıflandırma yolunda kullanılmaz.

Tek karakter için işlem maliyeti sabittir:

T(c) = Theta(1)
S(c) = Theta(1)

Bu yaklaşımda sözlük, düzenli ifade veya dinamik eşleme tablosu bulunmaz. Karakter kümesi küçük ve değişmez olduğu için doğrudan dallanma, hem kodun davranışını görünür tutar hem de çalışma anında herhangi bir hazırlık gerektirmez.

Fonksiyonun 0 döndürmesi iki farklı anlamı aynı değerde birleştirir:

Sesli harf veya kodlanmayan ayırıcı

Desteklenmeyen herhangi bir karakter

Bu sadeleştirme hızlıdır, ancak noktalama işareti, boşluk, H, W, Y ve Türkçe sesli harfler sonraki karar açısından aynı etkiyi üretir. Klasik Soundex'in bazı varyantlarında bu karakterlerin tamamı aynı davranışı göstermez.

İlk karakter rakamsal sınıflandırmaya dahil edilmez. Ayrı bir ASCII büyük harf dönüşümünden geçirilir. Böylece çelik ve celik aynı başlangıç harfine, şahin ve sahin aynı S değerine indirgenebilir. Bu karar Türkçe karakter içermeyen aramalar için tolerans sağlar. Bedeli ise özgün ilk harf ayrımının kaybolmasıdır.

Sayısal fonetik anahtar

Klasik Soundex çıktısı kavramsal olarak iki parçadan oluşur:

ilk harf + üç rakam

Kodda bu iki parça şu formülle tek bir int değerine paketlenir:

K = 1000 x U(c0) + d

Burada U(c0) ilk karakterin ASCII büyük harf kodunu, d ise 000 ile 666 arasındaki üç basamaklı Soundex bölümünü gösterir.

Örneğin klasik gösterimi S530 olan bir sonuç için:

U('S') = 83

K = 83 x 1000 + 530 K = 83530

Sayısal anahtardan kavramsal Soundex gösterimi tekrar çıkarılabilir:

ilk harf kodu = K / 1000 rakam bölümü = K % 1000

Rakam bölümü görüntülenirken üç haneye sıfırla tamamlanmalıdır. L000 kodunun sayısal karşılığı bu nedenle 76000 olur.

Bu paketleme, ilk karakter kodu ile üç basamaklı bölüm arasında çakışma üretmez. Son bölüm her zaman 0..999 aralığında kaldığı için farklı iki çift aynı int değerine dönüşmez:

1000a + x = 1000b + y
0 <= x,y < 1000

ise a = b ve x = y

Bu özellik Soundex'in kendi fonetik çakışmalarını ortadan kaldırmaz. Smith ve Smyth bilinçli olarak aynı anahtarı üretir. Çakışmasız olan yalnızca harf ve rakam çiftinin int içinde paketlenmesidir.

Sayısal çıktı, dört karakterli yeni bir sonuç dizesinin oluşturulmasını önler. Int32 değer türü olduğu için dizi ve jenerik koleksiyonlarda ek bir nesne gerektirmez. Fonetik anahtarı yoğun biçimde saklayan yapılarda bu tercih, dize nesnesi ve karakter tamponu maliyetini azaltır.

Bu kodu geliştirirken int seçmemin önemli nedenlerinden biri de fonetik anahtarın hash tabanlı yapılara doğal biçimde taşınabilmesiydi. Yine de Soundex değeri benzersiz kimlik veya kriptografik özet değildir. Bir nesnenin GetHashCode() metodunda kullanıldığında çok sayıda farklı adın aynı hash değerini üretmesi beklenen davranıştır. Equals() sözleşmesi buna göre kurulmalı, Soundex eşitliği ile gerçek nesne eşitliği birbirine karıştırılmamalıdır.

Tek geçişli kod üretimi

Sözcük dönüşümü ikinci karakterden başlar. Algoritma şu durumu taşır:

current  = mevcut karakterin fonetik sınıfı
prev     = önceki karakterin fonetik sınıfı
b        = üretilen rakam sayısı
r        = biriken üç basamaklı bölüm

Her karakter için önce yeni sınıf hesaplanır. Sınıf sıfır değilse ve önceki sınıftan farklıysa sonuç bölümüne eklenir:

r = r x 10 + current

Üç rakam üretildiğinde döngü sona erer. Daha az rakam elde edilmişse sonuç sağdan sıfırlarla tamamlanır:

r = r x 10

Bu yöntem StringBuilder, geçici karakter dizisi veya ara metin oluşturmaz. Sözcük uzunluğu n olduğunda en kötü durum maliyeti doğrusaldır:

T(n) = Theta(n)
S(n) = Theta(1)

Üç farklı sınıf erken bulunursa sözcüğün kalanı okunmaz. Bu nedenle gerçek işlem sayısı şu konumla sınırlıdır:

T(n) = O(min(n, üçüncü üretilen kodun konumu))

Asimptotik en kötü durum yine Theta(n) değerindedir. Tamamı sesli harflerden veya aynı fonetik sınıftan oluşan uzun bir sözcük sonuna kadar taranır.

Algoritmanın bu bölümünde SoundexSize sabiti üçtür. Kod tabanı da 10^3 olarak hesaplanır. Değer yalnız bir kez statik başlatmada üretildiği için Math.Pow() çağrısının çalışma zamanı etkisi ihmal edilebilir. Yine de 1000 değerinin doğrudan sabit olarak tanımlanması, sayısal paketleme sözleşmesini daha açık hale getirirdi.

Klasik kurallarla ayrılan davranış

Kaynak dosyanın açıklama bölümünde klasik Soundex'in H/W ayırıcı kuralı ve ilk harfe bağlı yinelenen sınıf kuralı anlatılmıştır. Gerçek kod ise bu iki kuralı aynı biçimde uygulamaz. Bu fark sessizce göz ardı edilmemelidir.

Klasik kurala göre ilk harf, rakam olarak yazılmasa da kendi fonetik sınıfını sonraki karakter üzerinde etkili kılar. Pfister örneğinde P ve F aynı 1 sınıfındadır. Bu nedenle F yeniden kodlanmaz ve standart sonuç P236 olur. ABD Ulusal Arşivleri de bu örneği aynı biçimde verir.

İncelenen gerçeklenimde önceki sınıf -1 ile başlatılır ve ilk harfin sınıfı hesaba katılmaz. Bu nedenle:

Pfister -> P123

üretilir. F ilk işlenen karakter olduğu için 1 değeri sonuç bölümüne eklenir.

İkinci fark H ve W karakterleriyle ilgilidir. Klasik Amerikan Soundex'te aynı sınıftaki iki sessiz harf yalnız H veya W ile ayrılmışsa ikinci rakam bastırılır. Ashcraft bu nedenle A261 kodunu üretir. Sesli harf ise sınıf tekrarını ayırır ve ikinci rakamın yazılmasına izin verir.

Kodda H, W, sesli harfler ve diğer kodlanmayan karakterler aynı 0 değerine dönüşür. Sıfır değeri önceki sınıfı sıfırladığı için S-H-C dizisinde ikinci 2 yeniden yazılır:

Ashcraft -> A226

Bu davranış kodun kendi içinde tutarlıdır. Ancak açıklama bölümündeki klasik kuralla aynı değildir. Gerçeklenimin standart Soundex uyumluluğu hedefleniyorsa iki ayrı durum korunmalıdır:

Sesli harf ve Y, önceki sınıfı ayırır

H ve W, rakam üretmez fakat önceki sınıfı korur

Ayrıca ilk harfin fonetik sınıfı başlangıç durumu olarak atanmalıdır.

Mevcut davranış bilinçli bir sadeleştirme olarak kullanılacaksa algoritma klasik Soundex değil, ona dayalı Türkçe karakter uyumlu bir varyant olarak belgelenmelidir. Bu ayrım başka sistemlerin Soundex fonksiyonlarıyla anahtar karşılaştırılırken önem kazanır.

Çok sözcüklü karşılaştırma

Tek sözcük eşleştirmesinde önce tam dize eşitliği kontrol edilir. Dizeler aynıysa Soundex hesaplanmadan true döner. Aksi halde iki sayısal anahtar karşılaştırılır.

Çok sözcüklü sürüm, metni yalnız boşluk karakterinden böler ve her parça için bir int anahtar üretir. Ardından iki anahtar dizisinin kesişip kesişmediğini iç içe döngüyle sınar.

Sol tarafta p, sağ tarafta q sözcük varsa karşılaştırma maliyeti:

T(p,q) = Theta(pq)
S(p,q) = Theta(p + q)

olur. Alan maliyetine Split() tarafından oluşturulan parça dizileri ve Soundex dizileri dahildir.

Bu tasarım kısa kişi adlarında düşük sabit maliyetlidir. İki veya üç parçalı adlarda ek bir HashSet oluşturmak, iç içe birkaç tamsayı karşılaştırmasından daha pahalı olabilir. Sözcük sayısı büyüdüğünde küçük tarafın kodlarını HashSet<int> içine almak, beklenen karşılaştırma maliyetini O(p+q) düzeyine indirebilir. Sayısal anahtar seçimi bu değişime uygundur.

Eşleme koşulu oldukça geniştir. İki metindeki herhangi bir sözcüğün fonetik kodunun aynı olması yeterlidir. Sözcük sırası, tekrar sayısı ve diğer parçaların uyuşup uyuşmadığı dikkate alınmaz. Bu davranış aday bulma aşamasında yüksek geri çağırım sağlayabilir. Kesin kişi eşleştirmesinde tek başına kullanılması çok sayıda yanlış pozitif üretir.

Split(' ') çağrısı varsayılan olarak boş parçaları korur. Ardışık iki ayırıcı arasında boş dize oluşur. .NET belgeleri, StringSplitOptions.None davranışında bitişik ayırıcıların boş öğe ürettiğini açıkça belirtir.

Boş dizenin Soundex değeri 0 olduğundan, iki farklı metinde boş parça bulunması çok sözcüklü karşılaştırmayı yanlışlıkla başarılı hale getirebilir:

"ali veli" "mehmet can"

Her iki dizede de çift boşluktan doğan 0 anahtarı bulunduğu için ortak kod tespit edilir. Üretim kullanımında boş parçalar çıkarılmalı veya 0 karşılaştırmaya dahil edilmemelidir.

Benzer biçimde tek sözcüklü API, null ve boş dize için 0 döndürür. Bu nedenle null ile boş dize fonetik olarak eşit kabul edilir. Bu bir API politikası olabilir, ancak veri yokluğu ile boş metin ayrımı önemliyse ayrı ele alınmalıdır.

Fonetik indeksin kullanım biçimi

Bu gerçeklenimin asıl gücü, küçük ve deterministik bir aday anahtarı üretmesidir. Her karakter en fazla bir kez incelenir. Tek sözcüklü sıcak yol ek bellek ayırmaz. Sonuç, doğrudan tamsayı dizilerinde ve hash tabanlı yapılarda tutulabilir.

Türkçe karakterlerin ASCII karşılıklarıyla aynı ilk harfe ve aynı fonetik sınıfa indirilmesi, diakritiksiz yazılmış adların bulunmasını kolaylaştırır:

çelik -> C420 celik -> C420

Aynı genişletme yanlış eşleşmeleri de artırır. Soundex kodu şu verilerle birlikte kullanıldığında daha güvenilir hale gelir:

Normalize edilmiş tam metin

Sözcük sayısı

Ad ve soyad konumu

Düzenleme uzaklığı

Doğum tarihi veya başka doğrulayıcı alanlar

Dil ve karakter kümesi bilgisi

Koddan çıkarılabilen sonuç, genel bir Türkçe fonetik model geliştirildiği değildir. Ortaya çıkan yapı, klasik Soundex sınıflarını Türkçe karakterleri kaybetmeden uygulayan, sayısal çıktı için optimize edilmiş bir aday eşleme algoritmasıdır. Doğruluk iddiası için kişi adlarından oluşan etiketli bir veri kümesinde precision, recall ve yanlış eşleşme dağılımı ölçülmelidir.

Bu geliştirme deneyiminde belirleyici karar, bilinen algoritmayı doğrudan kopyalamak yerine kullanım katmanına göre yeniden biçimlendirmekti. Dört karakterli metin anahtarı bir int değerine dönüştürüldü. Türkçe harfler sınıflara eklendi. Tek sözcük ve çok sözcüklü karşılaştırma aynı temsil üzerinde birleştirildi.

Kaynak kodun ayrıntılı incelenmesi, iyi optimizasyon ile standart uyumluluğun ayrı konular olduğunu da gösterir. Sayısal paketleme ve sabit alanlı tek geçiş verimli bir tasarımdır. İlk harf sınıfı ile H/W davranışı ise klasik algoritmadan ayrılır. Üretim kalitesi, bu farkın yanlışlıkla mı oluştuğunun yoksa bilinçli bir varyant mı olduğunun açıkça tanımlanmasına bağlıdır.