Unix spell yang berjalan di RAM 64KB

 (blog.codingconfessions.com)
3 poin oleh GN⁺ 2025-01-20 | 1 komentar | Bagikan ke WhatsApp
  • Pada 1970-an, spell di Unix milik AT&T harus melakukan lookup cepat terhadap kamus 250KB di dalam RAM PDP-11 yang hanya 64KB, dan Douglas McIlroy menyelesaikannya dengan memanfaatkan karakteristik data alih-alih kompresi umum
  • Prototipe awal Steve Johnson berbasis disk sehingga lambat dan kurang akurat, tetapi McIlroy meningkatkan performa dan akurasi dengan stemming yang mengecilkan kamus menjadi sekitar 25.000 kata
  • Struktur in-memory pertama adalah Bloom filter yang diimplementasikan Dennis Ritchie, dengan tabel 400.000 bit dan 11 fungsi hash untuk mencapai tingkat positive palsu sekitar 1/2000 sehingga lookup kamus terpisah bisa dihilangkan
  • Saat kamus membesar menjadi 30.000 kata, Bloom filter saja makin sulit memenuhi batas memori, sehingga hash 27 bit diurutkan lalu selisih hash-nya dikompresi dengan kode Golomb
  • Implementasi akhirnya membagi tabel selisih terkompresi ke beberapa bin untuk mempercepat lookup, dan dengan penyimpanan sekitar 14 bit per kata memungkinkan pemeriksa ejaan cepat tetap berjalan dalam 64KB

Batasan memori yang dihadapi Unix spell

  • Masalah utamanya adalah melakukan lookup cepat terhadap kamus 250KB dalam lingkungan RAM 64KB
  • Bahkan jika dikompresi dengan kompresi modern seperti gzip -9, file ini tetap tidak bisa diperkecil hingga di bawah 85KB
  • Pada PDP-11 era 1970-an, seluruh kamus tidak bisa dimuat ke memori, dan lookup berbasis disk terlalu lambat
  • McIlroy merancang struktur data khusus yang memanfaatkan struktur dan distribusi probabilitas data kamus, bukan kompresi umum

Unix spell awal dan penyusutan kamus berbasis stem

  • Ketika AT&T mengusulkan Unix sebagai sistem pemrosesan teks untuk departemen paten, pemeriksa ejaan menjadi kebutuhan
  • Steve Johnson menulis prototipe spell Unix pertama pada 1975, dan Jon Bentley menyebut pekerjaan itu selesai hanya dalam satu sore
  • Versi awal memecah berkas input menjadi aliran kata, lalu menghapus angka dan karakter khusus, mengubahnya menjadi huruf kecil, mengurutkannya, menghapus duplikasi, dan memeriksa keberadaan kata dalam kamus di disk
  • Pendekatan lookup disk yang sederhana ini lambat dan akurasinya juga rendah
  • Untuk meningkatkan performa dan akurasi, McIlroy merancang ulang dua bagian
    • algoritme yang menghapus prefiks dan sufiks untuk mereduksi kata menjadi stem
    • struktur data terkompresi untuk memuat kamus di memori dan melakukan lookup cepat

Algoritme penghapusan prefiks dan sufiks

  • Metode stemming McIlroy berulang kali menghapus prefiks dan sufiks umum dari kata, lalu memeriksa apakah kata yang sudah diperkecil ada di kamus
  • Misalnya, misrepresented diperkecil menjadi present dengan menghapus prefiks mis, re, dan sufiks ed
  • Jika present ada di kamus, kata aslinya tidak ditandai sebagai salah eja
  • Metode ini tidak 100% akurat dan bisa meloloskan sebagian salah eja, tetapi saat itu dianggap masih dapat diterima
  • Aturan pengecualian juga diimplementasikan untuk menghindari kesalahan yang umum
  • Kamus akhir menyusut menjadi 25.000 kata, ukuran yang bisa dimuat ke memori dengan struktur data yang dirancang baik

Lookup berbasis Bloom filter

  • Struktur in-memory pertama yang digunakan McIlroy adalah Bloom filter, yang dalam makalah saat itu disebut “superimposed code scheme”
  • Makalah Bloom filter terbit pada 1970, dan spell Unix dikembangkan pada pertengahan 1970-an
  • Implementasi ini disediakan oleh Dennis Ritchie
  • Bloom filter menginisialisasi tabel bit ke 0, lalu untuk setiap item menerapkan beberapa fungsi hash dan mengatur bit yang sesuai menjadi 1
  • Saat lookup, fungsi hash yang sama diterapkan lagi
    • jika ada satu saja bit bernilai 0, item itu tidak ada
    • jika semua bit bernilai 1, item itu mungkin ada, tetapi masih ada kemungkinan positive palsu (false positive)
  • Bloom filter pada umumnya memerlukan lookup kamus asli untuk menangani positive palsu, tetapi pada pemeriksa ejaan sebagian besar kata memang ada dalam kamus sehingga lookup kamus penuh bisa terlalu sering terjadi
  • McIlroy menurunkan tingkat positive palsu cukup rendah sehingga lookup kamus asli bisa dihilangkan
    • tingkat positive palsu yang diizinkan: 1/2000
    • jumlah kata kamus: 25.000
    • ukuran tabel bit: 400.000 bit
    • jumlah fungsi hash: 11
  • Kombinasi ini menghasilkan tingkat positive palsu sekitar 1/2000

Keterbatasan Bloom filter dan pendekatan hash terkompresi

  • Pendekatan Bloom filter dipakai untuk sementara waktu, tetapi kamus terus bertambah dari 25.000 menjadi 30.000 kata
  • Untuk mempertahankan tingkat positive palsu yang sama dibutuhkan tabel bit yang lebih besar, tetapi ini sulit karena keterbatasan memori
  • McIlroy beralih ke metode yang menyimpan hanya nilai hash kata, bukan seluruh tabel hash
  • Lookup bekerja dengan menghitung hash kata input lalu memeriksa keberadaannya dalam daftar hash yang disimpan
  • Untuk menurunkan kemungkinan collision hash, dibutuhkan kode hash yang cukup besar
    • ukuran kamus v sekitar 30.000, yaitu kira-kira 2^15
    • probabilitas collision yang diizinkan adalah 1 / 2^12
    • ukuran hash yang diperlukan adalah 27 bit
  • Menyimpan 30.000 hash 27 bit tidak muat dalam RAM 64KB PDP-11, sehingga kompresi menjadi wajib

Batas kompresi teoretis

  • McIlroy mula-mula menghitung jumlah bit minimum teoretis yang dibutuhkan untuk menyimpan himpunan kode hash
  • Jika ukuran hash adalah b bit, maka ada 2^b kemungkinan kode hash, dan jumlah cara memilih v kode hash unik di antaranya dapat diubah menjadi besaran informasi
  • Perhitungan ini menggunakan pendekatan Stirling dan asumsi penyederhanaan v « 2^b
  • Dengan memasukkan v=30.000 dan b=27, nilai minimum untuk menyimpan satu kode hash adalah 13,57 bit
  • Ini sekitar 50% lebih pendek daripada hash 27 bit asli, dan cukup kecil untuk muat dalam memori PDP-11

Penyimpanan selisih hash dan lookup

  • McIlroy tidak langsung mengompresi kode hash asli, melainkan menyimpan selisih antara kode hash yang telah diurutkan
  • Contohnya sebagai berikut
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
  • Menyimpan selisih memiliki dua keuntungan
    • nilai selisih lebih kecil daripada kode hash aslinya
    • nilai selisih yang sama bisa berulang pada banyak pasangan hash
  • Lookup dilakukan dengan menghitung hash kata input lalu mengakumulasikan selisih dari depan
    • jika jumlah kumulatif sama dengan hash input, berarti ada
    • jika jumlah kumulatif melewati hash input, berarti tidak ada
  • Ruang penyimpanan memang berkurang, tetapi lookup bisa melambat karena nilai terkompresi harus didekode dari awal dan diakumulasikan

Pemodelan distribusi geometrik untuk selisih hash

  • Kompresi lossless paling efisien ketika kode pendek diberikan pada nilai yang sering muncul dan kode panjang pada nilai yang jarang
  • Kompresi umum berbasis tabel distribusi probabilitas tidak cocok dengan batasan McIlroy
    • jika tabel distribusi probabilitas untuk sekitar 30.000 simbol disimpan di memori, keuntungan kompresinya hilang
    • menghitung frekuensi dan probabilitas nilai selisih memerlukan struktur berbasis disk yang mahal
  • McIlroy memanfaatkan fakta bahwa selisih hash mengikuti distribusi geometrik
  • Ruang hash memiliki 2^b titik, dan v kode hash tersebar di dalamnya
    • probabilitas sebuah titik berisi hash adalah q = v / 2^b
    • probabilitas sebuah titik kosong adalah p = 1 - v / 2^b
  • Selisih k terjadi ketika k-1 posisi setelah suatu hash kosong, dan posisi ke-k berisi hash berikutnya
  • Karena itu, probabilitas selisih k menjadi p^(k-1)q, yang sesuai dengan bentuk distribusi geometrik

Mengompresi selisih dengan Golomb code

  • McIlroy mengompresi selisih hash dengan Golomb code, yang cocok untuk bilangan bulat berdistribusi geometrik
  • Makalah Golomb tahun 1965 menyediakan skema run-length coding sederhana untuk nilai berdistribusi geometrik
  • Dalam distribusi geometrik, probabilitas menurun secara eksponensial, sehingga nilai bisa dikelompokkan ke dalam blok berukuran m dan panjang kode bertambah 1 bit setiap pindah ke blok berikutnya
  • Implementasi spell Unix menggunakan algoritme encoding dan decoding yang berbeda dari metode dalam makalah Golomb, sedikit lebih kompleks tetapi lebih efisien
  • Implementasi SVR4 asli dapat dilihat di lokasi berikut
  • Golomb code mengompresi selisih hash hingga panjang kode ekspektasian 13,60 bit per kata
  • Hasil ini sangat dekat dengan nilai minimum teoretis 13,57 bit

Pemecahan bin untuk kecepatan lookup

  • Jika hanya memakai tabel selisih terkompresi, lookup akan lambat karena harus mendekode dan mengakumulasi dari awal setiap kali
  • Implementasi akhir spell Unix membagi tabel selisih menjadi M bin
  • Saat lookup, sistem lebih dulu menemukan bin yang sesuai lalu hanya memindai bagian itu
  • Pendekatan ini meningkatkan kecepatan pencarian sebanyak M kali
  • Sebagai gantinya, pointer bin harus disimpan sehingga perlu ruang tambahan log₂M bit per kata
  • Total kebutuhan penyimpanan naik menjadi sekitar 14 bit per kata, tetapi ini menjadi kompromi yang memberi lookup jauh lebih cepat sambil tetap berada dalam anggaran memori

Desain berbasis keterbatasan yang ditunjukkan Unix spell

  • spell Unix adalah contoh desain yang menggabungkan Bloom filter, teori informasi, teori probabilitas, dan kompresi Golomb
  • Proses pengembangannya mengikuti alur berikut
    • mencapai tingkat positive palsu rendah dengan Bloom filter
    • beralih ke pendekatan hash terkompresi saat kamus membesar
    • menghitung jumlah bit minimum teoretis untuk penyimpanan hash
    • mengenali distribusi selisih hash
    • mencapai kompresi yang nyaris optimal dengan Golomb code
    • mempercepat lookup lewat pemecahan bin dengan tambahan overhead ruang yang kecil
  • Pemeriksa ejaan modern memakai teknik lain seperti edit distance atau language model, tetapi spell Unix tetap menjadi contoh sistem efisien yang lahir dari perpaduan pemahaman teoretis dan keterbatasan praktis

Bacaan terkait

1 komentar

 
GN⁺ 2025-01-20
Opini Hacker News

  • Bahkan dengan RAM yang sangat sedikit, kita bisa membuat pemeriksa ejaan berbasis memori eksternal: urutkan kata-kata dalam dokumen, hapus kata-kata unik, lalu gabungkan dengan kamus yang sudah diurutkan sehingga hanya tersisa kata-kata yang tidak ada
    Saya pernah melihat pendekatan ini sebagai contoh BASIC di Creative Computing, dan karena saya membuatnya berjalan di TRS-80 Color Computer yang RAM tersedianya jauh di bawah 32KB, hal itulah yang langsung terlintas begitu melihat judulnya
    Saat itu Turbo Lightning membuat orang terkesan, karena kamus terkompresinya bisa muat bersama program lain yang sedang berjalan di PC dan memeriksa ejaan saat pengguna mengetik
    PC memang memiliki batas 640KB, tetapi agar tidak mengganggu program lain, hanya sebagian dari itu yang bisa dipakai, dan pada masa awal PC pun mengisi penuh memori sebesar itu tidak mudah dari sisi biaya

    • Artikelnya juga membahas alternatif ini sebagai pembuktian konsep pertama dan menunjukkan kekurangannya: “karena implementasinya sederhana, akurasinya tidak tinggi, dan lambat karena harus melakukan pencarian kamus dari disk”
    • Sepertinya mereka memanfaatkan banyaknya kata yang berulang untuk menekan jumlah byte. Di C=64 dulu, jika tulisan melebihi 1–2 halaman, teks dokumen saja sudah bisa membuat memori jebol, jadi mempertahankan salinan kedua yang sudah diurutkan terasa cukup mewah
      Mungkin saja salinan kerja disimpan dulu ke disk, diurutkan, dibandingkan, lalu dimuat kembali, tetapi saya rasa para pengembang C=64 menghindari strategi seperti itu karena antarmuka disknya terlalu lambat

  • Ada bagian yang menyebut bahwa pada masa itu Bloom filter belum disebut Bloom filter dan Douglas menyebutnya “superimposed code scheme” dalam makalahnya; Bloom filter adalah tipe tertentu dari superimposed code
    Calvin Mooers mengembangkan random superimposed coding dalam tesis masternya di MIT pada 1940-an, dengan pengaruh langsung dari Shannon
    Buku bagus Bourne tahun 1963, “Methods of Information Handling”, memuat rincian matematisnya
    Saya yakin Douglas mengetahui teknik yang lebih luas ini. Misalnya, penulis “The Large Data Base File Structure Dilemma” (1975) juga menyebutnya sebagai “teknik lama yang disebut super-imposed coding” di http://dx.doi.org/10.1021/ci60001a005
    Di sini, kualifikasi “acak” itu penting, karena superimposed code sudah ada sebelum Mooers, tetapi belum menarik secara matematis atau penting secara praktis

  • Untuk ukuran “worse is better”, ini terlalu pintar. Kita harus berpikir ke arah yang lebih buruk
    Bandwidth memori utama dan bandwidth disk hampir sama, keduanya sedikit di atas 1MB/s
    Kalau saya mungkin akan memakai pendekatan beberapa kali lintasan, tetapi Bloom filter tetap keren, jadi mungkin tetap akan saya gunakan
    https://github.com/arnoldrobbins/v10spell
    https://code.google.com/archive/p/unix-spell/
    Makalah aslinya juga bagus: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
    Ada juga di halaman webnya: https://www.cs.dartmouth.edu/~doug/
    https://en.wikipedia.org/wiki/Douglas_McIlroy
    Jika Anda penggemar kata, saat mencari “obovate” Anda mungkin juga akan menemukan bagan bentuk daun ini
    https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg

  • Saya tidak ingat nama produknya, tetapi pada 1980-an ada pemeriksa ejaan perangkat keras untuk IBM PC. Bentuknya kotak yang dipasang di antara keyboard dan PC, lalu akan berbunyi bip jika Anda mengetik string yang tidak dikenali sebagai kata dalam kamus

  • Salah satu hal yang membuat saya tertarik pada Unix adalah artikel Byte sekitar awal 1980-an. Artikel itu menunjukkan cara membuat pemeriksa ejaan dengan pipeline split/sort/comm, kira-kira sekitar 7 perintah
    Di PC 8-bit sama sekali tidak ada hal seperti itu, tetapi setelah melihatnya, rasanya tidak perlu kompleksitas yang begitu luar biasa

  • Saya baru selesai membaca tulisannya, dan menurut saya intinya begini: ada “kamus” berisi 30.000 kata, dan jika kita bisa menerima tingkat positif palsu sekitar 1/4000, tiap kata dapat di-hash menjadi string 27-bit, alias integer, sehingga masalahnya berubah menjadi membuang kamus dan menyimpan himpunan 30.000 string 27-bit
    Agak mengejutkan, menurut teori informasi, 30.000 string 27-bit dapat disimpan bukan dengan 27 bit per kata, melainkan hanya sekitar 13,57 bit. Matematikanya bisa saya pahami (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), tetapi karena 30.000 sangat kecil dibandingkan 2^27, yaitu sekitar 134 juta, sepertinya butuh waktu untuk menerimanya secara intuitif dari mana keuntungan itu muncul
    Untuk mengodekan subset hash 27-bit berisi 30.000 item ini, digunakan selisih antar-hash; karena selisih ini mengikuti distribusi geometrik, pengodean Golomb yang disesuaikan untuk input berdistribusi geometrik berhasil mencapai sekitar 13,6 bit per kata dalam praktiknya
    Saya sempat memikirkan apakah secara prinsip bisa lebih baik dengan arah seperti “perfect hashing”. Mungkin ada fungsi yang menerima kata alfabetis, menjalani suatu transformasi, lalu mudah memverifikasi apakah hash hasilnya termasuk dalam himpunan yang baik
    Namun kalau dipikir lagi, karena perlu ada tingkat positif palsu, untuk mencegah kata yang tidak ada di kamus terpetakan ke himpunan “baik”, hash minimal harus 27 bit. Pendekatan ini pada dasarnya tampak optimal secara teoretis. Atau mungkinkah ada cara memetakan tiap kata ke integer 27-bit, tetapi membuat string yang baik, misalnya, hanya yang nilainya kurang dari 30000?

  • Sebagai referensi, sekitar 1983 Grammatik di CP/M berjalan di bawah 64KB dan melakukan “pemeriksaan tata bahasa” pada sistem 8-bit. Dalam praktiknya, itu lebih berupa pemeriksa ejaan yang ditambah aturan sistem pakar
    Yang saya ingat adalah karena saya mengulik bagian menariknya: alasan ukurannya bisa sekecil itu adalah karena ditulis dalam Forth, dan di dalam produknya ada interpreter eksternal yang cukup lengkap, sehingga hanya dengan sedikit penyuntingan heksadesimal, ia bisa dipakai seperti interpreter Forth dengan fungsi-fungsi khusus yang sudah dimuat sebelumnya

    • Di editor WordStar yang berjalan di sistem CP/M saya dengan RAM 64KB, ada pemeriksa ejaan SPELL.COM sepanjang 2023 byte
      Saya tidak pernah mendekompilasinya untuk melihat cara kerjanya, tetapi kecil, cepat, dan berfungsi dengan baik

  • Saya penasaran salah ketik umum apa saja yang lolos karena hashing
    Terkait ini, ada juga kompetisi kompresi kamus Wordle: http://golf.horse/wordle/

  • Saya pernah mengalami hal serupa pada pertengahan 80-an. “Cepat” itu istilah relatif
    Datanya banyak, RAM 640KB, heap 64KB, stack 64KB. Saya harus mencari dan mengekstrak data dari ratusan MB, lalu menggabungkan sebagian di antaranya
    Saya bereksperimen membuat data menjadi struktur indeks berbentuk ternary tree. Secara konsep masuk akal, tetapi setelah diimplementasikan, relasi dan informasi jalurnya saja sudah terlalu besar untuk dimasukkan ke dalam 64KB
    Alih-alih kompresi, saya memilih swapping. Saya menulis TSR, kode yang dalam istilah sekarang mirip service, untuk memproses bongkahan data, mengekstrak hasilnya, menyimpannya di stack, lalu membuang data asli, kemudian mengirim panggilan interrupt ke TSR. TSR lalu menghapus heap, membaca bongkahan berikutnya dari media penyimpanan, dan mengembalikan kontrol ke program; program memprosesnya, menggabungkannya dengan data di stack, dan mengulang sampai semuanya selesai
    Aslinya pekerjaan ini membutuhkan tiga petugas entri data sekitar seminggu, plus seorang pakar untuk menggabungkan informasinya. Bayangkan sekitar selusin binder ring 3 inci berisi tabel. Program menyelesaikannya dalam beberapa jam dan terasa luar biasa “cepat”
    Itu dikerjakan pada sistem single-thread
    https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program

  • Saya ingat pernah memakai opsi -b di UNIX spell untuk menggunakan ejaan Britania. Opsi bahasanya hanya ada dua, jadi saya jadi penasaran mengapa keputusan itu diambil, bagaimana kode menanganinya, dan dari mana masing-masing kamus berasal
    Apakah orang Australia dan Selandia Baru memakai ejaan Britania, atau ejaan Amerika?
    UNIX spell adalah semacam catur ZX81 1K di bidang ejaan, dan di komputer rumahan pemeriksa ejaan tidak terlalu banyak sampai MS Word untuk Windows 3.1 hadir. Sebelumnya di kantor, para sekretaris mengetik dengan WordPerfect dan berperan sebagai pemeriksa ejaan manusia bagi tiap manajer dan tim
    Sementara itu di rumah, dengan printer dot matrix dan layar berkedip-kedip, saya bertahan seadanya sepanjang era komputasi awal dengan mengandalkan kamus kertas. Saya tidak ingat pemeriksa ejaan terasa begitu penting saat itu, karena semua orang bisa mengeja. Di sekolah berisi seribu siswa, hanya ada satu anak yang mengaku disleksia, dan itu menjadi alasan yang terdengar masuk akal untuk tidak bisa mengeja
    Mungkin saja 1980-an adalah masa keemasan literasi, dan tanggal jelas dimulainya kemunduran kemampuan mengeja adalah hari ketika UNIX spell ditulis
    Saya suka Scrabble. Itu masalah yang sangat berbeda dari pemeriksaan ejaan, tetapi prosesnya berbagi beberapa tahap dengan UNIX spell. Ia mencari prefiks dan sufiks kata yang umum, lalu menempelkannya ke komponen lain di rack atau papan
    Kamus Scrabble juga agak mirip dengan UNIX spell karena hanyalah daftar kata besar tanpa definisi. Yang penting hanya apakah kata tertentu ada di buku. Ada juga beberapa tabel pencarian khusus, seperti 102 kata dua huruf

    • Saya ingat pada 1984 memeriksa ejaan esai SMA dengan Paperclip 64 di Commodore 64. Itu sebelum Microsoft Windows hadir
      Karena kamus dibaca dari disk saat pemeriksaan, prosesnya memakan beberapa menit, lalu setelah itu kita bisa meninjau kata-kata yang tidak cocok