Unix spell yang berjalan di RAM 64kB

Bagaimana Unix Spell berjalan di RAM 64kB

Bagaimana kamus bisa dimuat ke dalam RAM 64kB?

• Para insinyur Unix memecahkan masalah memuat kamus 250kB ke dalam RAM 64kB dengan memanfaatkan struktur data dan teknik kompresi.
• Pada 1970-an, Douglas McIlroy menghadapi masalah ini saat mengimplementasikan pemeriksa ejaan Unix di AT&T.
• Ia mengembangkan algoritme yang mendekati batas kompresi teoretis dengan memanfaatkan karakteristik data.

TL;DR

• Pemeriksa ejaan Unix dimulai sebagai prototipe yang dibuat Steve Johnson di AT&T pada 1970-an.
• McIlroy mengembangkan algoritme stemming berbasis bahasa untuk mengurangi kamus menjadi 25.000 kata.
• Bloom filter digunakan untuk pencarian cepat, dan Dennis Ritchie menyediakan implementasinya.
• Saat kamus bertambah menjadi 30.000 kata, pendekatan Bloom filter menjadi tidak efisien sehingga teknik kompresi hashing diadopsi.
• Dengan menggunakan hash code 27-bit untuk menurunkan probabilitas tabrakan dan kode Golomb, tercapai kompresi 13,60 bit/kata.

Asal-usul perintah spell di Unix

• Unix diusulkan ke divisi paten AT&T sebagai sistem pemrosesan teks, dan pemeriksa ejaan diperlukan.
• Versi awal ditulis oleh Steve Johnson pada 1975, tetapi akurasinya rendah.
• Douglas McIlroy menulis ulang proyek tersebut untuk meningkatkan akurasi dan kinerja.

Algoritme penghapusan prefiks

• McIlroy mengembangkan algoritme untuk menghapus prefiks dan sufiks umum dari kata sebelum melakukan pencarian kamus.
• Metode ini tidak 100% akurat, tetapi pada saat itu dianggap cukup dapat diterima.

Pencarian berbasis Bloom filter

• Bloom filter menghemat memori dan memungkinkan pencarian cepat.
• Digunakan untuk memuat kamus berisi 25.000 kata ke dalam RAM 64kB.
• Bloom filter disetel agar tetap mempertahankan tingkat false positive yang rendah.

Teknik hashing terkompresi untuk pencarian kamus

• Ketika ukuran kamus meningkat menjadi 30.000 kata, dibutuhkan struktur data yang lebih efisien secara memori.
• McIlroy menggunakan metode menyimpan selisih antar hash code untuk menghemat memori.
• Selisih hash dikompresi menggunakan kode Golomb.

Kesimpulan

• Perintah spell di Unix adalah bagian menarik dari sejarah rekayasa yang lahir dari keterbatasan memori PDP-11.
• Solusi ini memadukan Bloom filter, teori informasi, teori probabilitas, dan algoritme kompresi dengan elegan.
• Ini menunjukkan bahwa pemecahan masalah yang mendalam tetap mungkin dilakukan di bawah keterbatasan sumber daya.

[GN⁺]

Komentar Hacker News

• Filter Bloom awalnya disebut "superimposed code scheme", dan ini memang merupakan jenis tertentu dari superimposed code

  • Calvin Mooers mengembangkan random superimposed coding di MIT pada 1940-an, dipengaruhi oleh penelitian Shannon
  • Buku Bourne tahun 1963, "Methods of Information Handling", memberikan detail matematisnya
  • Douglas kemungkinan besar mengetahui teknik ini

• Pemeriksa ejaan dengan memori eksternal dapat diimplementasikan dengan RAM yang kecil

  • Caranya dengan mengurutkan kata-kata dalam dokumen, menghapus kata unik yang duplikat, lalu menggabungkannya dengan kamus sehingga hanya kata yang hilang yang dipertahankan
  • Ini pernah dijalankan di TRS-80 Color Computer dengan RAM kurang dari 32k
  • Turbo Lightning melakukan pemeriksaan ejaan saat mengetik di PC dengan menggunakan kamus terkompresi

• Bandwidth memori dan bandwidth disk dulu mirip, sehingga pekerjaan bisa diselesaikan lewat beberapa kali pass

  • Menggunakan filter Bloom adalah pendekatan yang baik untuk melakukan ini

• Pada 1980-an ada pemeriksa ejaan perangkat keras untuk IBM PC

  • Perangkat ini dihubungkan di antara keyboard dan PC, lalu berbunyi bip saat Anda mengetik kata yang tidak dikenali

• Unix diusulkan ke AT&T sebagai sistem pemrosesan teks, sehingga membutuhkan pemeriksa ejaan

  • UNIX terutama digunakan untuk pemrosesan teks

• Sebuah artikel Byte pada awal 1980-an menjelaskan cara membuat pemeriksa ejaan untuk Unix

  • PC 8-bit tidak memiliki kemampuan seperti ini

• Karena hashing, mungkin ada typo umum yang terlewat

  • Ada kompetisi tentang kompresi kamus Wordle

• Pada pertengahan 1980-an, data diproses dengan 640KB RAM serta heap dan stack sebesar 64KB

  • Butuh waktu berjam-jam untuk mengekstrak dan menggabungkan data, dan semuanya dilakukan pada sistem single-threaded

• Sekitar 1983 di CP/M, Grammatik berjalan dengan kurang dari 64k dan mencakup pemeriksaan tata bahasa serta aturan sistem pakar

  • Ditulis dalam Forth sehingga sangat ringkas

• Versi pertama UNIX membutuhkan 24kB, dan setengahnya dipakai oleh kernel