- 1970'lerde AT&T'nin Unix
spell aracı, PDP-11'in 64KB RAM'i içinde 250KB'lık bir sözlüğü hızlıca sorgulamak zorundaydı ve Douglas McIlroy bunu genel amaçlı sıkıştırma yerine verinin özelliklerinden yararlanarak çözdü
- Steve Johnson'ın ilk prototipi disk tabanlı olduğu için yavaştı ve doğruluğu düşüktü; McIlroy ise kök bulma ile sözlüğü 25.000 kelime düzeyine indirerek performans ve doğruluğu iyileştirdi
- İlk bellek içi yapı, Dennis Ritchie'nin uyguladığı bir Bloom filter idi; 400.000 bitlik tablo ve 11 hash fonksiyonuyla yaklaşık 1/2000 yanlış pozitif oranı sağlanarak ayrı bir sözlük sorgusu atlandı
- Sözlük 30.000 kelimeye büyüyünce yalnızca Bloom filter ile bellek kısıtlarını karşılamak zorlaştı; bunun üzerine 27 bitlik hash'ler sıralanıp hash farkları Golomb code ile sıkıştırıldı
- Son uygulama, sıkıştırılmış fark tablosunu birden çok bin'e bölerek sorgu hızını artırdı ve kelime başına yaklaşık 14 bit depolamayla 64KB içinde hızlı yazım denetimini mümkün kıldı
Unix spellin karşılaştığı bellek kısıtı
- Temel sorun, 250KB'lık bir sözlüğü 64KB RAM ortamında hızlıca sorgulamaktı
gzip -9 gibi modern sıkıştırma uygulansa bile bu dosya 85KB'ın altına inmiyor- 1970'lerin PDP-11 sistemlerinde tüm sözlüğü belleğe almak mümkün değildi ve disk tabanlı sorgular yavaştı
- McIlroy, genel amaçlı sıkıştırma yerine sözlük verisinin yapısını ve olasılık dağılımını kullanan özel bir veri yapısı tasarladı
İlk Unix spell ve kök tabanlı sözlük küçültme
- AT&T, Unix'i patent departmanı için bir metin işleme sistemi olarak önerince bir yazım denetleyicisine ihtiyaç doğdu
- Steve Johnson, 1975'te ilk Unix
spell prototipini yazdı; Jon Bentley ise bu çalışmanın bir öğleden sonra ortaya çıktığını aktardı
- İlk sürüm, girdi dosyasını bir kelime akışına ayırıyor; sayı ve özel karakterleri kaldırıyor, küçük harfe çeviriyor, sıralıyor, tekrarları siliyor ve ardından disk üzerindeki sözlükte kelimenin varlığını kontrol ediyordu
- Bu basit disk sorgulama yöntemi hem yavaştı hem de doğruluğu düşüktü
- McIlroy, performansı ve doğruluğu artırmak için iki bölümü yeniden tasarladı
- Önek ve sonekleri kaldırarak kelimeyi köküne indiren bir algoritma
- Sözlüğü bellekte tutup hızlı sorgulama sağlayan sıkıştırılmış bir veri yapısı
Önek ve sonek kaldırma algoritması
- McIlroy'un kök bulma yaklaşımı, kelimedeki yaygın önek ve sonekleri tekrar tekrar kaldırıp ardından küçültülmüş kelimenin sözlükte olup olmadığını kontrol ediyordu
- Örneğin
misrepresented, mis, re önekleri ve ed soneki çıkarılarak present biçimine indirgeniyordu
present sözlükte varsa özgün kelime yazım hatası olarak işaretlenmiyordu- Bu yöntem %100 doğru değildi; bazı yazım hatalarının gözden kaçmasına yol açabiliyordu, ancak o dönemde kabul edilebilir görülüyordu
- Yaygın hatalardan kaçınmak için istisna kuralları da uygulanmıştı
- Son sözlük 25.000 kelimeye kadar küçüldü ve iyi tasarlanmış bir veri yapısıyla belleğe sığabilecek bir boyuta geldi
Bloom filter tabanlı sorgulama
- McIlroy'un ilk kullandığı bellek içi yapı, o dönem makalelerde “superimposed code scheme” diye anılan bir Bloom filter idi
- Bloom filter makalesi 1970'te yayımlandı, Unix
spell ise 1970'lerin ortasında geliştirildi
- Bu uygulama Dennis Ritchie tarafından sağlandı
- Bloom filter, bit tablosunu önce 0'larla başlatıp her öğe için birden fazla hash fonksiyonu uygulayarak karşılık gelen bitleri 1 yapar
- Sorgulama sırasında da aynı hash fonksiyonları uygulanır
- Bitlerden biri bile 0 ise ilgili öğe yoktur
- Tüm bitler 1 ise öğe var olabilir, ancak yanlış pozitif (false positive) olasılığı sürer
- Normalde Bloom filter'da yanlış pozitifleri elemek için gerçek sözlük sorgusu gerekir, ancak yazım denetleyicisinde kelimelerin büyük kısmı sözlükte bulunduğundan bu, sık sık tüm sözlüğe başvurmayı gerektirebilirdi
- McIlroy, yanlış pozitif oranını yeterince düşürerek gerçek sözlük sorgusunu atladı
- Kabul edilen yanlış pozitif oranı 1/2000
- Sözlükteki kelime sayısı 25.000
- Bit tablosu boyutu 400.000 bit
- Hash fonksiyonu sayısı 11
- Bu kombinasyonla yanlış pozitif oranı yaklaşık 1/2000 düzeyine indirildi
Bloom filter'ın sınırları ve sıkıştırılmış hash yaklaşımı
- Bloom filter yaklaşımı bir süre kullanıldı, ancak yeni kelimeler eklendikçe sözlük 25.000'den 30.000 kelimeye çıktı
- Aynı yanlış pozitif oranını korumak için daha büyük bir bit tablosu gerekiyordu, fakat bellek kısıtı buna izin vermiyordu
- McIlroy bunun yerine, tüm hash tablosu yerine yalnızca kelimelerin hash değerlerini depolayan bir yönteme geçti
- Sorgulama, giriş kelimesinin hash'ini hesaplayıp kayıtlı hash listesinde bunun var olup olmadığına bakarak çalışıyordu
- Hash çakışması olasılığını düşük tutmak için yeterince büyük bir hash kodu gerekiyordu
- Sözlük boyutu
v yaklaşık 30.000, yani yaklaşık 2^15
- İzin verilen çakışma olasılığı
1 / 2^12
- Gerekli hash boyutu 27 bit
- 30.000 adet 27 bitlik hash depolamak PDP-11'in 64KB RAM'ine sığmadığı için sıkıştırma zorunluydu
Kuramsal sıkıştırma sınırı
- McIlroy önce hash kodu kümesini depolamak için gereken kuramsal en düşük bit sayısını hesapladı
- Hash kodu boyutu
b bit ise olası hash kodu sayısı 2^b olur; bunların içinden v adet benzersiz hash kodu seçmenin sayısı bilgi miktarına çevrilerek değerlendirildi
- Hesaplamada Stirling yaklaşımı ve
v « 2^b basitleştirme varsayımı kullanıldı
v=30.000, b=27 yerine konduğunda, tek bir hash kodunu depolamak için gereken en düşük değer 13,57 bit çıkıyordu- Bu, özgün 27 bitlik hash'ten yaklaşık %50 daha kısa ve PDP-11 bellek kapasitesine sığabilecek bir düzeydi
Hash farklarını depolama ve sorgulama
- McIlroy, özgün hash kodlarını doğrudan sıkıştırmak yerine sıralanmış hash kodları arasındaki farkları depoladı
- Örnek şöyleydi
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
- Farkları depolamanın iki avantajı vardı
- Fark değerleri, özgün hash kodlarından daha küçüktü
- Birçok hash kodu çifti arasında aynı fark değeri tekrar edebiliyordu
- Sorgulama, giriş kelimesinin hash'ini hesapladıktan sonra farkları baştan itibaren biriktirerek yapılıyordu
- Kümülatif toplam giriş hash'iyle eşleşirse öğe vardır
- Kümülatif toplam giriş hash'ini aşarsa öğe yoktur
- Depolama alanı azalıyor, ancak sıkıştırılmış değerlerin baştan itibaren çözümlenip biriktirilmesi gerektiği için sorgulama yavaşlayabiliyordu
Hash farklarının geometrik dağılımla modellenmesi
- Kayıpsız sıkıştırma, sık görülen değerlere kısa kodlar ve nadir görülen değerlere uzun kodlar verildiğinde daha verimli olur
- Genel amaçlı olasılık dağılım tablosu tabanlı sıkıştırma, McIlroy'un kısıtlarına uymuyordu
- Yaklaşık 30.000 sembolün olasılık dağılım tablosunu bellekte tutmak, sıkıştırma kazancını ortadan kaldıracaktı
- Fark değerlerinin sıklık ve olasılıklarını hesaplamak, pahalı disk tabanlı yapılar gerektiriyordu
- McIlroy, hash farklarının geometrik dağılımı izlediğinden yararlandı
- Hash uzayı
2^b noktadan oluşur ve bunun içine v adet hash kodu dağılmıştır
- Bir noktada hash bulunma olasılığı
q = v / 2^b
- Boş olma olasılığı
p = 1 - v / 2^b
k farkı, bir hash'ten sonraki k-1 konum boşken k'ncı konumda sonraki hash bulunduğunda ortaya çıkar- Dolayısıyla
k farkının olasılığı p^(k-1)q olur ve bu da geometrik dağılım biçimiyle örtüşür
Golomb code ile fark sıkıştırma
- McIlroy, hash farklarını geometrik dağılımlı tamsayılar için uygun olan Golomb code ile sıkıştırdı
- Golomb'un 1965 tarihli makalesi, geometrik dağılımlı değerler için basit bir run-length kodlama yöntemi sunuyordu
- Geometrik dağılımda olasılık üstel olarak azaldığı için değerler
m boyutlu bloklar hâlinde gruplanabilir ve her sonraki blokta kod uzunluğu 1 bit artırılabilir
- Unix
spell uygulaması, Golomb makalesindekinden farklı; biraz daha karmaşık ama daha verimli bir kodlama/çözme algoritması kullanıyordu
- Özgün SVR4 uygulaması şu konumlarda görülebilir
- Golomb code, hash farklarını kelime başına 13,60 bit beklenen kod uzunluğuyla sıkıştırdı
- Bu, 13,57 bitlik kuramsal minimuma çok yakın bir sonuçtu
Sorgu hızını artırmak için bin'lere bölme
- Yalnızca sıkıştırılmış fark tablosu kullanıldığında, sorgu sırasında baştan başlayıp çözmek ve biriktirmek gerektiğinden işlem yavaş kalıyordu
- Son Unix
spell uygulaması fark tablosunu M adet bin'e böldü
- Sorgu sırasında önce ilgili bin bulunuyor, sonra yalnızca onun içinde tarama yapılıyordu
- Bu yöntem arama hızını
M kat artırdı
- Bunun karşılığında bin işaretçilerini saklamak gerektiği için kelime başına
log₂M bit ek depolama gerekiyordu
- Toplam depolama miktarı kelime başına yaklaşık 14 bite çıksa da, bu bellek bütçesi içinde çok daha hızlı sorgu sağlayan bir ödünleşim oldu
Unix spellin gösterdiği kısıt odaklı tasarım
- Unix
spell, Bloom filter, bilgi kuramı, olasılık kuramı ve Golomb sıkıştırmasını birleştiren bir tasarım örneği
- Geliştirme süreci şu akışla ilerledi
- Bloom filter ile düşük yanlış pozitif oranı sağlandı
- Sözlük büyüyünce sıkıştırılmış hash yaklaşımına geçildi
- Hash depolamanın kuramsal minimum bit sayısı hesaplandı
- Hash farklarının dağılımı fark edildi
- Golomb code ile neredeyse en uygun sıkıştırma elde edildi
- Bin'lere bölme ile küçük bir alan ek yükü karşılığında sorgu hızlandırıldı
- Modern yazım denetleyicileri edit distance veya dil modeli gibi başka teknikler kullanıyor olsa da, Unix
spell; kuramsal anlayışla gerçek kısıtları birleştirip verimli bir sistem kurmanın kalıcı örneklerinden biri olarak öne çıkıyor
1 yorum
Hacker News yorumları
Çok az RAM ile de harici bellekli bir yazım denetleyicisi yapılabilir: belgedeki sözcükleri sıralayıp, benzersiz sözcükleri çıkardıktan sonra, sıralanmış sözlükle birleştirerek yalnızca olmayan sözcükleri geride bırakmak gibi.
Bu yöntemi Creative Computing’deki bir BASIC örneğinde görmüştüm ve kullanılabilir RAM’i 32 KB’tan çok daha az olan TRS-80 Color Computer’da çalışır hâle getirdiğim için başlığı görür görmez aklıma ilk bu geldi.
O dönemde Turbo Lightning insanları şaşırtmıştı; sıkıştırılmış sözlüğü, PC’de çalışan diğer programlarla birlikte belleğe sığıyor ve yazarken yazım denetimi yapıyordu.
PC’de 640 KB sınırı vardı ama diğer programları engellememek için bunun yalnızca bir kısmını kullanmak gerekiyordu; PC’nin ilk dönemlerinde o belleği tamamen doldurmak bile maliyet açısından kolay değildi.
Çalışma kopyasını önce diske kaydetmek, sıralamak, karşılaştırmak ve sonra yeniden yüklemek de mümkün olurdu; ama C=64 geliştiricileri disk arayüzü çok yavaş olduğu için muhtemelen böyle bir stratejiden kaçınırdı.
O dönemde Bloom filtresine henüz Bloom filtresi denmediği ve Douglas’ın makalede buna “superimposed code scheme” dediği bir bölüm var; Bloom filtresi, superimposed code’un belirli bir türüdür.
Calvin Mooers, 1940’lardaki MIT yüksek lisans tezinde Shannon’dan doğrudan etkilenerek rastgele superimposed coding’i geliştirdi.
Bourne’un mükemmel 1963 tarihli “Methods of Information Handling” kitabında matematiksel ayrıntılar yer alır.
Douglas’ın daha geniş tekniği bildiğinden eminim. Örneğin “The Large Data Base File Structure Dilemma” (1975) makalesinin yazarı da http://dx.doi.org/10.1021/ci60001a005 adresinde bunu “super-imposed coding adlı eski bir teknik” diye ifade etmişti.
Burada “rastgele” nitelemesi önemli; çünkü Mooers’tan önce de superimposed code vardı ama matematiksel açıdan ilginç ya da pratik açıdan önemli değildi.
“worse is better” için fazla akıllıca. Daha kötü taraftan düşünmek lazım.
Ana bellek bant genişliği ile disk bant genişliği neredeyse aynıydı; ikisi de 1 MB/s’nin biraz üzerindeydi.
Ben olsam muhtemelen çok geçişli bir yöntem kullanırdım ama yine de Bloom filtresi havalı olduğu için onu seçerdim.
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
Orijinal makale de harika: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
Kendi web sayfasında da var: https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
Sözcük meraklısıysanız “obovate” sözcüğüne bakarken bu yaprak biçimi şemasını da görürsünüz.
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg
Ürün adını hatırlamıyorum ama 80’lerde IBM PC için bir donanımsal yazım denetleyicisi vardı. Klavye ile PC arasına bağlanan bir kutuydu; sözlük sözcüğü olarak tanımadığı bir karakter dizisi yazdığınızda bip sesiyle uyarıyordu.
https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf sayfa 237’de incelemesi var. Büyük PDF, dikkat.
Unix’e ilgi duymama yol açan şeylerden biri, 1980’lerin başları civarında Byte’ta çıkan bir yazıydı. split/sort/comm pipeline ile bir yazım denetleyicisi yapma sürecini gösteriyordu; yaklaşık 7 komut kadardı.
8 bit PC’lerde böyle bir şey hiç yoktu ama görünce de sanki o kadar büyük bir karmaşıklık gerekmiyormuş gibi geliyordu.
https://youtu.be/tc4ROCJYbm0?t=4m56s
Yazıyı ancak şimdi tamamen okudum ve özünün şu olduğunu düşünüyorum: 30.000 kelimelik bir “sözlük” var; yaklaşık 1/4000’lik bir yanlış pozitif oranını kabul ederseniz, her kelimeyi 27 bitlik bir dizeye, yani bir tam sayıya hash’leyip sözlüğü atarak problemi 30.000 adet 27 bitlik dizeden oluşan bir kümeyi saklama problemine dönüştürebilirsiniz
Biraz şaşırtıcı biçimde, bilgi teorisine göre 30.000 adet 27 bitlik dize, kelime başına 27 bit değil, yalnızca yaklaşık 13,57 bit ile saklanabiliyor. Matematiği anlıyorum (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), ama 30.000, 2^27’ye, yani yaklaşık 134 milyona kıyasla o kadar küçük ki kazancın nereden geldiğini sezgisel olarak kabullenmem biraz zaman alacak gibi
Bu 30.000 öğelik 27 bit hash alt kümesini kodlamak için hash farkları kullanılmış; bu farklar geometrik dağılım izlediğinden, geometrik dağılımlı girdilere göre ayarlanmış Golomb kodlaması ile pratikte kelime başına yaklaşık 13,6 bit elde edilmiş
“Mükemmel hashing” gibi yönlerle ilkesel olarak daha iyisinin yapılıp yapılamayacağını düşündüm. Alfabetik bir kelimeyi alıp bir dönüşümden geçirdikten sonra, ortaya çıkan hash’in iyi bir kümeye ait olup olmadığını kolayca doğrulayan bir fonksiyon olabilir mi diye aklımdan geçti
Ama tekrar düşününce, yanlış pozitif oranı gerektiği için sözlükte olmayan bir kelimenin “iyi” kümeye eşlenmemesini istiyorsanız hash’te en az 27 bit gerekiyor. Bu yöntem temelde teorik olarak optimal görünüyor. Ya da her kelimeyi 27 bitlik bir tam sayıya eşleyip, iyi dizeleri örneğin değeri 30000’den küçük olanlar yapmanın bir yolu var mıdır?
Bu arada 1983 civarında CP/M’deki Grammatik 64KB’tan az bellekle çalışıyordu ve 8 bit sistemlerde “dilbilgisi denetimi” yapıyordu. Aslında yazım denetimine uzman sistem kuralları eklenmiş bir biçimdi
Aklımda kalmasının nedeni ilginç taraflarını kurcalamış olmamdı: bu kadar küçük olabilmesinin nedeni Forth ile yazılmış olmasıydı; ürünün içinde yeterince harici yorumlayıcı vardı, öyle ki biraz hex düzenlemeyle, özel fonksiyonları önceden yüklenmiş bir Forth yorumlayıcısı gibi kullanılabiliyordu
Nasıl çalıştığını görmek için tersine derlemedim, ama küçük, hızlı ve iyi çalışıyor
Hashing yüzünden hangi yaygın yazım hatalarının kaçırıldığını merak ediyorum
Bununla ilgili bir Wordle sözlüğü sıkıştırma yarışması da var: http://golf.horse/wordle/
80’lerin ortasında benzer bir şey yaşamıştım. Hızlı olmak göreceli bir şey
Çok veri vardı; RAM 640KB, heap 64KB, stack 64KB idi. Yüzlerce MB içinden veri arayıp çıkarmamız ve bir kısmını birleştirmemiz gerekiyordu
Veriyi ternary tree biçiminde bir indeks yapısına dönüştürmeyi denedik. Kavramsal olarak mantıklıydı, ama uygulayınca yalnızca ilişkiler ve yol bilgisi bile 64KB’a sığmayacak kadar büyüktü
Sıkıştırma yerine swapping’i seçtik. TSR, bugünün terimleriyle hizmet gibi bir kod yazdık; veri parçalarını işliyor, sonucu çıkarıp stack’e kaydediyor, sonra kaynak veriyi atıyor ve TSR’ye interrupt çağrısı gönderiyordu. Bunun üzerine TSR heap’i temizliyor, depolamadan bir sonraki parçayı okuyup denetimi programa geri veriyordu; program da işleyip stack verisiyle birleştiriyor ve tüm işlem bitene kadar bunu tekrarlıyordu
Normalde bu iş, veri girişiyle ilgilenen 3 kişinin yaklaşık bir haftasını ve bilgileri birleştirecek bir uzmanı gerektiriyordu. Yaklaşık on iki adet 3 inçlik halkalı klasör dolusu tablo düşünün. Program birkaç saatte bitirdi ve şaşırtıcı derecede “hızlıydı”
Bu, tek iş parçacıklı bir sistemde yapılmıştı
https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program
UNIX spell’de Britanya yazımını kullanmak için
-bseçeneğini kullandığımı hatırlıyorum. Yalnızca iki dil seçeneği vardı; bunun neden böyle kararlaştırıldığını, kodun bunu nasıl ele aldığını ve her bir sözlüğün nereden geldiğini merak ediyorumAvustralyalılar ve Yeni Zelandalılar Britanya yazımını mı kullanıyordu, Amerikan yazımını mı?
UNIX spell, yazım denetimi alanının ZX81 1K satrancı gibiydi; ev bilgisayarlarında Windows 3.1 için MS Word çıkana kadar yazım denetimi pek yaygın değildi. Ondan önce ofiste sekreterler WordPerfect ile yazıyor, her yönetici ve ekibin insan yazım denetleyicisi rolünü üstleniyordu
Öte yandan evde nokta vuruşlu yazıcı ve titrek ekranla, erken bilgisayar dönemim boyunca kâğıt sözlüklere dayanarak bir şekilde idare ettim. O zamanlar herkes yazım biliyordu, bu yüzden yazım denetiminin o kadar önemli olduğunu hatırlamıyorum. Bin öğrencili bir okulda disleksisi olduğunu iddia eden yalnızca bir çocuk vardı; yazımının kötü olmasına makul bir bahane oluyordu
Belki de 1980’ler okuryazarlığın altın çağıydı ve yazım becerisindeki düşüşün net başlangıç tarihi UNIX spell’in yazıldığı gündü
Scrabble’ı severim. Yazım denetiminden çok farklı bir problem, ama işleme süreci UNIX spell ile birkaç adımı paylaşıyor. Yaygın kelime önekleri ve sonekleri bulunup raftaki ya da tahtadaki diğer bileşenlerle birleştiriliyor
Scrabble sözlüğü de anlam vermeyen büyük bir kelime listesi olması bakımından UNIX spell’e biraz benzer. Önemli olan, verilen kelimenin kitapta olup olmadığıdır. 102 adet iki harfli kelime gibi birkaç özel arama tablosu da vardır
Sözlüğü diskten okuyarak denetlediği için birkaç dakika sürüyordu; ardından eşleşmeyen kelimeleri gözden geçirebiliyordunuz