Unix spell chạy trên RAM 64kB

Cách Unix Spell chạy được trên RAM 64kB

Làm sao có thể nhét từ điển vào 64kB RAM?

• Các kỹ sư Unix đã giải quyết bài toán nhét một từ điển 250kB vào 64kB RAM bằng cách tận dụng cấu trúc dữ liệu và kỹ thuật nén.
• Vào thập niên 1970, Douglas McIlroy đã đối mặt với bài toán này khi triển khai trình kiểm tra chính tả Unix tại AT&T.
• Ông đã phát triển một thuật toán nén tận dụng đặc tính của dữ liệu để tiệm cận giới hạn nén về mặt lý thuyết.

TL;DR

• Trình kiểm tra chính tả Unix bắt đầu như một nguyên mẫu do Steve Johnson của AT&T tạo ra vào thập niên 1970.
• McIlroy đã phát triển một thuật toán stemming dựa trên ngôn ngữ để rút gọn từ điển xuống còn 25.000 từ.
• Bloom filter được sử dụng để tra cứu nhanh, với phần triển khai do Dennis Ritchie cung cấp.
• Khi từ điển tăng lên 30.000 từ, cách tiếp cận bằng Bloom filter trở nên kém hiệu quả và kỹ thuật nén băm được đưa vào.
• Bằng cách dùng mã băm 27 bit để giảm xác suất va chạm và mã Golomb, hệ thống đạt mức nén 13,60 bit/từ.

Nguồn gốc của lệnh kiểm tra chính tả Unix

• Unix được đề xuất cho bộ phận bằng sáng chế của AT&T như một hệ thống xử lý văn bản, và vì thế cần có trình kiểm tra chính tả.
• Phiên bản đầu tiên do Steve Johnson viết vào năm 1975 nhưng độ chính xác thấp.
• Douglas McIlroy đã viết lại dự án để cải thiện độ chính xác và hiệu năng.

Thuật toán loại bỏ tiền tố

• McIlroy đã phát triển một thuật toán loại bỏ các tiền tố và hậu tố phổ biến khỏi từ trước khi tra cứu từ điển.
• Phương pháp này không đạt độ chính xác 100%, nhưng vào thời điểm đó được xem là chấp nhận được.

Tra cứu dựa trên Bloom filter

• Bloom filter giúp tiết kiệm bộ nhớ và cho phép tra cứu nhanh.
• Nó được dùng để nạp một từ điển 25.000 từ vào 64kB RAM.
• Bloom filter được tinh chỉnh để duy trì tỷ lệ dương tính giả thấp.

Kỹ thuật băm nén để tra cứu từ điển

• Khi kích thước từ điển tăng lên 30.000 từ, cần một cấu trúc dữ liệu hiệu quả bộ nhớ hơn.
• McIlroy đã dùng phương pháp lưu trữ chênh lệch giữa các mã băm để tiết kiệm bộ nhớ.
• Mã Golomb được sử dụng để nén các chênh lệch mã băm này.

Kết luận

• Lệnh kiểm tra chính tả của Unix là một lát cắt lịch sử kỹ thuật thú vị xuất phát từ giới hạn bộ nhớ của PDP-11.
• Nó mang lại một lời giải thanh nhã bằng cách kết hợp Bloom filter, lý thuyết thông tin, lý thuyết xác suất và các thuật toán nén.
• Điều này cho thấy vẫn có thể giải quyết vấn đề một cách sâu sắc ngay cả khi tài nguyên bị giới hạn.

[GN⁺]

Ý kiến Hacker News

• Bloom filter ban đầu được gọi là "superimposed code scheme", và thực ra nó là một dạng superimposed code cụ thể

  • Calvin Mooers đã phát triển random superimposed coding tại MIT vào thập niên 1940, chịu ảnh hưởng từ nghiên cứu của Shannon
  • Cuốn sách năm 1963 của Bourne, "Methods of Information Handling", cung cấp các chi tiết toán học
  • Douglas rất có thể đã biết về kỹ thuật này

• Có thể triển khai trình kiểm tra chính tả dùng bộ nhớ ngoài với rất ít RAM

  • Cách làm là sắp xếp các từ trong tài liệu, loại bỏ từ trùng lặp, rồi trộn với từ điển để chỉ giữ lại các từ bị thiếu
  • Đã chạy được trên TRS-80 Color Computer với chưa tới 32k RAM
  • Turbo Lightning dùng từ điển nén để kiểm tra chính tả khi gõ trên PC

• Băng thông bộ nhớ và băng thông đĩa khi đó tương đương nhau, nên có thể xử lý bằng nhiều lượt quét

  • Dùng Bloom filter để làm việc này là một cách hay

• Từng có phần cứng kiểm tra chính tả cho IBM PC vào thập niên 1980

  • Nó được nối giữa bàn phím và PC, và phát tiếng bíp cảnh báo khi bạn gõ một từ mà nó không nhận ra

• Unix đã được đề xuất với AT&T như một hệ thống xử lý văn bản, nên cần có trình kiểm tra chính tả

  • UNIX chủ yếu được dùng cho xử lý văn bản

• Một bài viết trên Byte đầu thập niên 1980 đã giải thích cách tạo trình kiểm tra chính tả cho Unix

  • Trên PC 8-bit thì không có những khả năng như vậy

• Có thể có những lỗi gõ phổ biến bị bỏ sót do hashing

  • Có một cuộc thi về nén từ điển Wordle

• Vào giữa thập niên 1980, dữ liệu được xử lý với 640KB RAM cùng 64KB heap và stack

  • Việc trích xuất và kết hợp dữ liệu mất hàng giờ, và được thực hiện trên hệ thống đơn luồng

• Khoảng năm 1983 trên CP/M, Grammatik chạy với dưới 64k và bao gồm kiểm tra ngữ pháp cùng các quy tắc expert system

  • Nó được viết bằng Forth nên rất gọn nhẹ

• Phiên bản đầu tiên của UNIX cần 24kB, trong đó kernel chiếm một nửa