C# ile Türkçe Deasciification

Yazar: Muhammet Ali Köker

Türkçe karakter geri yükleme problemi, c harfini her gördüğünde ç ile değiştiren mekanik bir dönüşüm değildir. ASCII biçimindeki cocuk, cagri, saglik ve olcu dizilerinde hangi harfin Türkçe karşılığına çevrileceği, karakterin bulunduğu yerel bağlama göre belirlenmelidir. Aynı ASCII karakter bazı sözcüklerde korunurken bazılarında dönüştürülür.

Geliştirdiğim C# gerçeklenimi, Deniz Yüret'in Emacs Turkish Mode içinde kullandığı karar listesi yaklaşımını temel alıyordu. Yüret'in çalışması da Gökhan Tür'ün 2000 tarihli doktora tezindeki Türkçe deasciification probleminden esinlenmişti. Tür, ASCII karakterlerle yazılmış Türkçe metinlerde ü, ö, ç, ş, ğ ve ı harflerinin geri yüklenmesini istatistiksel doğal dil işleme görevlerinden biri olarak ele almıştı.

Yüret'in uygulaması, yaklaşık bir milyon sözcüklük Türkçe haber metninden öğrenilen karar listelerini kullanıyordu. Model, Yüret ve Michael de la Maza tarafından geliştirilen Greedy Prepend Algorithm ile üretilmişti. Emacs eklentisi, kullanıcı boşluk, sekme veya satır sonu tuşuna bastığında son sözcüğü bağlama göre düzeltiyordu.

Bu algoritmayı kendi dil işleme katmanıma aktarırken yalnız Lisp sözdizimini C#'a çevirmedim. Karakter tablolarını, model yükleme biçimini, bağlam üretimini ve karar önceliğini yeniden kurdum. En önemli hedefim, özgün algoritmanın ardışık karar davranışını korurken çalışma zamanındaki veri yapılarını .NET ortamına uygun hale getirmekti.

İkili sınıflandırma problemi

Algoritma altı karakter ailesi üzerinde çalışır:

c <-> ç
g <-> ğ
i <-> ı
o <-> ö
s <-> ş
u <-> ü

Büyük harfler de aynı ailelerin parçasıdır. Her aday konum için iki olası karar vardır:

0: ASCII biçimini koru 1: Türkçe karşılığı kullan

Algoritma harf eklemez, silmez veya sözcük sınırlarını değiştirmez. Yazım denetimi, kök bulma ve biçimbilimsel çözümleme yapmaz. Yalnızca mevcut karakterin aynı ailedeki diğer biçime çevrilip çevrilmeyeceğine karar verir.

Bu ayrım, yöntemin sınırını açıklar. cocuk girdisi çocuk olabilir. Ancak eksik harf içeren bir sözcük, yanlış yazılmış bir ek veya bitişik yazılması gereken iki sözcük bu algoritmanın problemi değildir.

Her karakter ailesi için ayrı bir desen sözlüğü tutulur:

c -> karar listesi
g -> karar listesi
i -> karar listesi
o -> karar listesi
s -> karar listesi
u -> karar listesi

Desen içindeki X, sınıflandırılan karakterin konumunu gösterir:

bu aXa na Xog birinX Xocuk

Desen bir sözcüğün tamamı olmak zorunda değildir. Hedefin solundan ve sağından alınmış kısa bir kesit olabilir. Önceki sözcüğün bir bölümü veya bir sınır karakteri de desene katılabilir.

Karar listesi bir olasılık puanları toplamı değildir. Paylaşılan kaynak içindeki eski açıklamalardan birinde alt desenlerin log-odds değerlerinin toplandığı belirtilmiş olsa da gerçek kod böyle çalışmaz. Kod, eşleşen kurallar arasından karar listesinde en yüksek önceliğe sahip tek kuralı seçer.

Bu davranış klasik karar listesi tanımıyla uyumludur. Kararlar sıralı kurallardan oluşur ve yeni örnek, ilk eşleşen kuralın sınıfını alır. Greedy Prepend Algorithm de bu tür listeleri üretmek için geliştirilmiştir.

Modelin bellekteki gösterimi

C# portunda desenler şu mantıksal yapıda saklanır:

Dictionary<char, Dictionary<string, short>>

Dış sözlük karakter ailesini, iç sözlük ise bağlam desenlerini tutar. short değer iki bilgiyi aynı anda taşır:

mutlak değer -> kural önceliği işaret -> sınıflandırma sonucu

Mutlak değeri küçük olan kural daha yüksek önceliklidir. Pozitif değer Türkçe biçimi, negatif değer ASCII biçimini temsil eder. Sıfır değeri de ASCII sınıfına aittir ve en yüksek öncelikli kural olarak kullanılabilir.

Bu kodlama ayrı bir kural nesnesine ihtiyaç bırakmaz. Her sözlük girdisi için desen, sıra ve sınıf bilgisi yeterlidir. Model yükleme tamamlandıktan sonra çıkarım yolu yalnız sözlük okumalarından oluşur.

Başlangıç değeri şu ifadeyle oluşturulmuştur:

rank = pattern.Count << 1

Amaç, gerçek kuralların bütün mutlak sıra değerlerinden daha büyük bir nötr değer elde etmektir. Tarihsel modelde her karakter ailesindeki kural sayısı short sınırının altında kaldığı için bu temsil yeterlidir. Model daha büyük bir derlemle yeniden eğitilirse short taşması ayrıca denetlenmelidir. Bir ailedeki kural sayısı 16.383 değerini aştığında ikiyle çarpılan değer işaretli 16 bit aralığını aşabilir.

Karakter işlemleri için dört yardımcı tablo kurulmuştur:

Türkçe karakteri ASCII karşılığına indiren tablo

Karakteri küçük ASCII biçimine dönüştüren tablo

Önceden düzeltilmiş karakteri bağlam işaretine dönüştüren tablo

ASCII ve Türkçe biçimler arasında geçiş yapan tablo

Bunların çalışma başında bir kez üretilmesi, her karakterde kültür çözümleme veya uzun koşul zinciri çalıştırılmasını önler. Model de statik başlatma sırasında oluşturulur. Daha sonra değiştirilmediği sürece aynı sözlükler bütün çağrılar arasında paylaşılabilir.

Asimetrik bağlam

Algoritmanın en belirleyici tarafı, hedef karakterin sol ve sağ bağlamını aynı biçimde işlememesidir.

Metin soldan sağa taranır. Hedefin solundaki karakterler daha önce sınıflandırılmıştır. Bu karakterlerin Türkçe biçimleri sonraki kararlara özellik olarak aktarılabilir. Sağdaki karakterler ise henüz işlenmemiştir. Bu nedenle sağ taraf yalnızca küçük ASCII biçimine indirgenir.

Sol bağlamda daha önce Türkçeleştirilmiş karakterler büyük temel harfle kodlanır:

ç -> C
ğ -> G
ı -> I
ö -> O
ş -> S
ü -> U

Buradaki büyük harf, özgün metindeki harf büyüklüğünü göstermek zorunda değildir. Önceki konumda Türkçe karakter bulunduğunu belirten bir özellik işaretidir.

Bu yapı algoritmayı bağımsız karakter sınıflandırıcılarının toplamı olmaktan çıkarır. Önceki tahmin sonraki tahminin girdisine dönüşür:

y_i = f(x_(i-K), ..., y_(i-1), x_i, x_(i+1), ..., x_(i+K))

x_i özgün karakteri, y_i ise düzeltilmiş karakteri gösterir. Sol tarafta tahmin edilmiş y değerleri, sağ tarafta henüz işlenmemiş x değerleri kullanılır.

Bu nedenle işlem yönü algoritmik sözleşmenin parçasıdır. Metni sağdan sola taramak veya bütün karakterleri bağımsız işleyip daha sonra birleştirmek aynı sonucu üretmez. Önceki bir yanlış kararın sonraki bağlamlara taşınması da mümkündür. Bu durum ardışık modelin sağladığı bilgiyi artırırken hata yayılımı riski oluşturur.

Pencere ve desen araması

Özgün Emacs yaklaşımı hedefin iki yanında 10 karakterlik bağlam kullanır. İncelediğim C# portunda ise sabitler şu şekildedir:

Current = 20 Size = 41

Hedef 20 indisinde tutulur. Böylece teorik pencere 20 sol karakter, X ve 20 sağ karakterden oluşur.

Bağlam oluşturulduktan sonra X içeren bütün kesintisiz alt diziler sınanır. Tek yöndeki genişlik K ise sol uzunluk 0..K, sağ uzunluk da 0..K aralığındadır:

aday desen sayısı = (K + 1)^2

Bu port için:

K = 20
(K + 1)^2 = 441

Bir aday karakter için en fazla 441 desen sözlükte aranır. Birden fazla desen eşleştiğinde en kısa veya en uzun desen seçilmez. Mutlak sıra değeri en küçük olan kural kazanır.

Bağlam toplama işlemi de yönlere göre farklıdır. Sağ taraf küçük ASCII biçimine çevrilir ve tanınmayan ilk sınır karakterinden sonra tarama sona erer. Sol taraf geriye doğru ilerler ve daha önce düzeltilmiş karakterleri işaretli biçimde kullanır. Bu asimetri, özellikle son yazılan sözcüğü önceki sözcük bağlamıyla düzeltmeye dayanan özgün kullanım biçimiyle uyumludur.

Türkçe i ailesi

i, ı, I ve İ karakterleri genel dönüşüm mantığına bırakılamaz:

i -> İ ı -> I

ASCII küçük i, Türkçe metinde i veya ı olabilir. ASCII büyük I ise I veya İ olabilir. Küçük harfte Türkçe biçime geçmek i -> ı dönüşümüdür. Büyük harfte aynı sınıf kararı I karakterini korumayı gerektirir.

Kod bu farkı açık bir özel durumla ele alır. Model noktasız aileyi seçtiğinde:

i -> ı I -> I

Model noktalı aileyi seçtiğinde:

i -> i I -> İ

Bu nedenle karar sonucunu yalnızca "aksan ekle" biçiminde yorumlamak doğru değildir. i ailesindeki pozitif sınıf noktasız biçimi temsil eder. Karakterin mevcut büyüklüğü, dönüşüm yönünü ayrıca belirler.

Standart ToUpperInvariant ve ToLowerInvariant çağrılarına güvenmek bu ilişkiyi doğru kurmaz. Port sırasında Türkçeye özgü eşlemeleri ayrı tablolarla korumamın nedeni buydu.

Gerçek çalışma maliyeti

Metin uzunluğu N, aday karakter sayısı A ve tek yöndeki bağlam genişliği K olsun. Metnin genel taraması Theta(N) maliyetindedir. Bağlam üretimi her aday için Theta(K) sürer.

Yalnız hash sorgularının sayısı dikkate alınırsa desen araması:

Theta(A * K^2)

görünür. Ancak mevcut kod her sorgu için şu biçimde yeni bir dize oluşturur:

new string(temp, start, length)

Her desenin oluşturulması ve hash değerinin hesaplanması desen uzunluğuyla orantılıdır. Bütün sol ve sağ uzunlukların toplamında üretilen karakter miktarı:

(K + 1)^3

değerine ulaşır.

K = 20 için bir aday konumda:

441 geçici dize 9261 karakterlik toplam geçici içerik

oluşturulabilir. Bu nedenle genelleştirilmiş çalışma zamanı daha doğru biçimde şöyle ifade edilir:

Theta(N + A * K^3)

K sabit kabul edildiğinde toplam süre yine Theta(N) olur. Ancak yüksek trafikli bir serviste asimptotik gösterimin gizlediği allocation ve hash maliyeti belirgin hale gelir.

Kalıcı bellek maliyeti, kural sayısı R ve ortalama desen uzunluğu L için yaklaşık olarak:

Theta(R * L)

değerindedir. Her çağrıda giriş metni char[] dizisine kopyalandığı için ek çalışma alanı Theta(N) olur. Bağlam tamponu sabit boyutludur.

Bu yapıyı daha sonra yeniden optimize etseydim, geçici dize üretimini kaldırırdım. Özel bir span anahtarı, çakışma denetimli kayan hash veya desen trie yapısı kullanılabilir. Böylece bütün kesitler için yeni string oluşturmak yerine aynı 41 karakterlik tampon üzerinde offset ve length değerleriyle çalışmak mümkün olur.

Optimizasyonun karar davranışını değiştirmemesi gerekir. Kural önceliği desen uzunluğundan bağımsızdır. Trie içinde ilk bulunan desenin seçilmesi yeterli değildir. Eşleşen bütün kurallar arasından en küçük mutlak rank yine korunmalıdır.

Üretim sınırları

Bu gerçeklenimin güçlü tarafı, çıkarım sırasında harici sözlük veya morfolojik çözümleyici gerektirmemesidir. Model yerel bellekte bulunur. Ağ erişimi ve kullanıcı metninin başka bir sisteme gönderilmesi gerekmez. Karar tablosu sabit olduğu için aynı giriş aynı çıktıyı üretir.

Kararların yeniden üretilebilmesi için şu unsurlar sabit kalmalıdır:

Karakter işleme yönü

Unicode normalizasyonu

Bağlam genişliği

Desen sırası

Ayırıcı davranışı

Türkçe büyük-küçük harf tabloları

Tekrarlanan desenlerde ilk kuralın korunması

I, İ, i ve ı özel durumu

Modelin haber metinlerinden öğrenilmiş olması alan bağımlılığı oluşturur. Özel adlar, teknik terimler, yabancı sözcükler, URL'ler, e-posta adresleri ve kaynak kod parçaları yanlış dönüştürülebilir. Bu bölgeler çekirdek algoritmadan önce işaretlenmeli veya ayrı bir koruma katmanından geçirilmelidir.

Paylaşılan inceleme nüshasında karar listelerinin ve doğrudan karakter lookup tablosunun tamamı bilinçli olarak bulunmuyor. Bu nedenle dosya, mevcut haliyle derlenebilir ve tarihsel doğruluk değerlerini yeniden üretebilir tam bir dağıtım paketi değildir. Algoritmik çekirdek, veri yapıları ve karar sırası ise açık biçimde incelenebilmektedir.

Bu portu geliştirirken edindiğim temel sonuç, küçük bir doğal dil işleme algoritmasında bile doğruluğun yalnız model tablosuna bağlı olmadığıydı. Bağlamın hangi yönde toplandığı, önceki kararların nasıl kodlandığı, kuralların nasıl sıralandığı ve dört farklı i karakterinin nasıl ele alındığı modelin parçasıdır.

Yöntemin başarısı karmaşık bir sinir ağı kullanmasından değil, problem için doğru özellikleri sıkıştırılmış bir karar listesinde tutmasından gelir. Eğitim çevrimdışı ve pahalı olabilir. Çalışma zamanı ise küçük, yerel ve deterministiktir. Bu yönüyle algoritma, doğal dil işleme tarihinde yorumlanabilir modeller ile düşük maliyetli üretim kodunun nasıl bir araya getirilebildiğini gösteren iyi bir örnektir.