64 KB RAM’de çalışan Unix spell

Unix Spell'in 64 kB RAM'de nasıl çalıştırıldığı

64 kB RAM'e bir sözlük nasıl sığdırılır?

• Unix mühendisleri, veri yapıları ve sıkıştırma tekniklerinden yararlanarak 250 kB'lık bir sözlüğü 64 kB RAM'e sığdırma sorununu çözdü.
• 1970'lerde Douglas McIlroy, AT&T'nin Unix yazım denetleyicisini uygularken bu sorunla karşılaştı.
• Verinin özelliklerinden yararlanarak, teorik sıkıştırma sınırına yaklaşan bir sıkıştırma algoritması geliştirdi.

TL;DR

• Unix yazım denetleyicisi, 1970'lerde AT&T'de Steve Johnson'ın bir prototipiyle başladı.
• McIlroy, sözlüğü 25.000 kelimeye indiren, dil temelli bir kök bulma algoritması geliştirdi.
• Hızlı arama için Bloom filtresi kullanıldı ve uygulamayı Dennis Ritchie sağladı.
• Sözlük 30.000 kelimeye çıkınca Bloom filtresi yaklaşımı verimsiz hale geldi ve sıkıştırılmış hash tekniği benimsendi.
• 27 bitlik hash kodları çakışma olasılığını düşürmek için kullanıldı ve Golomb kodu ile kelime başına 13,60 bitlik sıkıştırma elde edildi.

Unix yazım denetimi komutunun kökeni

• Unix, AT&T'nin patent bölümüne bir metin işleme sistemi olarak önerildi ve bir yazım denetleyicisine ihtiyaç vardı.
• İlk sürüm Steve Johnson tarafından 1975'te yazıldı, ancak doğruluğu düşüktü.
• Douglas McIlroy, doğruluğu ve performansı artırmak için projeyi yeniden yazdı.

Önek kaldırma algoritması

• McIlroy, sözlüğe bakmadan önce kelimelerden ortak önek ve sonekleri çıkaran bir algoritma geliştirdi.
• Bu yöntem %100 doğru değildi, ancak o dönemde kabul edilebilir bir düzeydeydi.

Bloom filtresi tabanlı arama

• Bloom filtresi, bellek tasarrufu sağladı ve hızlı aramayı mümkün kıldı.
• 25.000 kelimelik sözlüğü 64 kB RAM'e yüklemek için kullanıldı.
• Bloom filtresi, düşük yanlış pozitif oranını koruyacak şekilde ayarlandı.

Sözlük araması için sıkıştırılmış hashing tekniği

• Sözlük boyutu 30.000 kelimeye çıkınca daha bellek verimli bir veri yapısına ihtiyaç duyuldu.
• McIlroy, bellekten tasarruf etmek için hash kodları arasındaki farkları saklayan bir yöntem kullandı.
• Bu hash farklarını sıkıştırmak için Golomb kodu kullanıldı.

Sonuç

• Unix yazım denetimi komutu, PDP-11'in bellek kısıtlarından doğan ilginç bir mühendislik tarihi sunuyor.
• Bloom filtresi, bilgi kuramı, olasılık kuramı ve sıkıştırma algoritmalarını birleştiren zarif bir çözüm sağladı.
• Kaynakların kısıtlı olduğu durumlarda derinlemesine problem çözmenin mümkün olduğunu gösteriyor.

[GN⁺]

Hacker News yorumu

• Bloom filtresi başlangıçta "superimposed code scheme" olarak adlandırılıyordu; bu da belirli bir superimposed code türüdür

  • Calvin Mooers, 1940'larda MIT'de Shannon'ın çalışmalarından etkilenerek rastgele superimposed coding geliştirdi
  • Bourne'un 1963 tarihli "Methods of Information Handling" kitabı matematiksel ayrıntıları verir
  • Douglas muhtemelen bu tekniği biliyordu

• Harici bellek kullanan bir yazım denetleyicisi az RAM ile uygulanabilir

  • Yöntem; belgedeki sözcükleri sıralamak, benzersiz sözcükleri ayıklamak ve ardından sözlükle birleştirerek yalnızca eksik sözcükleri tutmaktır
  • TRS-80 Color Computer'da 32k'den az RAM ile çalıştırıldı
  • Turbo Lightning, sıkıştırılmış bir sözlük kullanarak PC'de yazarken yazım denetimi yapıyordu

• Bellek bant genişliği ile disk bant genişliği benzerdi ve iş birden fazla geçişle yapılabiliyordu

  • Bunun için Bloom filtresi kullanmak iyi olurdu

• 1980'lerde IBM PC için donanım tabanlı bir yazım denetleyicisi vardı

  • Klavye ile PC arasına bağlanıyor ve tanımadığı bir sözcük yazıldığında bip sesi çıkarıyordu

• Unix, AT&T'ye bir metin işleme sistemi olarak önerildi ve bir yazım denetleyicisine ihtiyaç vardı

  • UNIX çoğunlukla metin işleme için kullanılıyordu

• 1980'lerin başındaki bir Byte makalesi, Unix'in yazım denetleyicisinin nasıl yapılacağını açıklıyordu

  • 8 bit PC'lerde böyle yetenekler yoktu

• Hashing nedeniyle kaçırılan yaygın yazım hataları olabilir

  • Wordle sözlüğü sıkıştırmasıyla ilgili bir yarışma var

• 1980'lerin ortalarında veriler, 640KB RAM ile 64KB heap ve stack kullanılarak işleniyordu

  • Verileri çıkarmak ve birleştirmek saatler alıyordu ve bu, tek iş parçacıklı bir sistemde yapılıyordu

• 1983 civarında CP/M üzerinde Grammatik 64k'den az bellekle çalışıyordu; dilbilgisi denetimi ve uzman sistem kuralları içeriyordu

  • Forth ile yazılmıştı ve çok kompaktı

• UNIX'in ilk sürümü 24kB gerektiriyordu ve bunun yarısını çekirdek kaplıyordu