# 64kb RAM에서 실행된 Unix spell

> Clean Markdown view of GeekNews topic #18810. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=18810](https://news.hada.io/topic?id=18810)
- GeekNews Markdown: [https://news.hada.io/topic/18810.md](https://news.hada.io/topic/18810.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-01-20T09:49:15+09:00
- Updated: 2025-01-20T09:49:15+09:00
- Original source: [blog.codingconfessions.com](https://blog.codingconfessions.com/p/how-unix-spell-ran-in-64kb-ram)
- Points: 3
- Comments: 1

## Topic Body

##### Unix Spell이 64kB RAM에서 실행된 방법

###### 64kB RAM에 사전을 어떻게 맞출 수 있을까?
- Unix 엔지니어들은 데이터 구조와 압축 기법을 활용하여 64kB RAM에 250kB 사전을 맞추는 문제를 해결함.
- 1970년대에 Douglas McIlroy는 AT&T의 Unix 철자 검사기를 구현하면서 이 문제에 직면함.
- 그는 데이터의 특성을 활용하여 이론적 압축 한계에 근접한 압축 알고리듬을 개발함.

##### TL;DR
- Unix 철자 검사기는 1970년대에 AT&T의 Steve Johnson이 프로토타입으로 시작함.
- McIlroy는 언어 기반의 어간 추출 알고리듬을 개발하여 사전을 25,000 단어로 줄임.
- 빠른 조회를 위해 Bloom 필터를 사용하였으며, Dennis Ritchie가 구현을 제공함.
- 사전이 30,000 단어로 증가하면서 Bloom 필터 접근법이 비효율적이 되어 해시 압축 기법을 도입함.
- 27비트 해시 코드를 사용하여 충돌 확률을 낮추고, Golomb의 코드를 사용하여 13.60 비트/단어의 압축을 달성함.

##### Unix 철자 명령의 기원
- Unix는 AT&T의 특허 부서에 텍스트 처리 시스템으로 제안되었고, 철자 검사기가 필요했음.
- 초기 버전은 Steve Johnson이 1975년에 작성하였으나 정확도가 낮았음.
- Douglas McIlroy는 정확도와 성능을 개선하기 위해 프로젝트를 다시 작성함.

##### 접두사 제거 알고리듬
- McIlroy는 단어에서 공통 접두사와 접미사를 제거하여 사전을 조회하는 알고리듬을 개발함.
- 이 방법은 100% 정확하지 않았지만 당시에는 수용 가능한 수준이었음.

##### Bloom 필터 기반 조회
- Bloom 필터는 메모리를 절약하고 빠른 조회를 가능하게 함.
- 25,000 단어의 사전을 64kB RAM에 적재하기 위해 사용됨.
- Bloom 필터는 낮은 오탐률을 유지하도록 조정됨.

##### 사전 조회를 위한 압축 해싱 기법
- 사전 크기가 30,000 단어로 증가하면서 더 메모리 효율적인 데이터 구조가 필요해짐.
- McIlroy는 해시 코드의 차이를 저장하여 메모리를 절약하는 방법을 사용함.
- Golomb의 코드를 사용하여 해시 차이를 압축함.

##### 결론
- Unix 철자 명령은 PDP-11의 메모리 제약에서 비롯된 흥미로운 엔지니어링 역사임.
- Bloom 필터, 정보 이론, 확률 이론, 압축 알고리듬을 결합한 우아한 솔루션을 제공함.
- 자원 제약이 있을 때 깊이 있는 문제 해결이 가능하다는 것을 보여줌.

## Comments



### Comment 33608

- Author: neo
- Created: 2025-01-20T09:49:15+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=42752604) 
- Bloom 필터는 원래 "superimposed code scheme"으로 불렸으며, 이는 특정 유형의 superimposed code임
  - Calvin Mooers는 1940년대 MIT에서 Shannon의 연구에 영향을 받아 무작위 superimposed coding을 개발함
  - Bourne의 1963년 책 "Methods of Information Handling"에서 수학적 세부 사항을 제공함
  - Douglas는 이 기술을 알고 있었을 가능성이 높음

- 외부 메모리 철자 검사기를 적은 RAM으로 구현할 수 있음
  - 문서의 단어를 정렬하고 고유한 단어를 제거한 후 사전과 병합하여 누락된 단어만 유지하는 방식임
  - TRS-80 Color Computer에서 32k 미만의 RAM으로 작동시킴
  - Turbo Lightning은 압축된 사전을 사용하여 PC에서 입력할 때 철자 검사를 수행함

- 메모리 대역폭과 디스크 대역폭이 비슷했으며, 여러 번의 패스를 통해 작업을 수행할 수 있었음
  - Bloom 필터를 사용하여 작업을 수행하는 것이 좋음

- 1980년대 IBM PC용 하드웨어 철자 검사기가 있었음
  - 키보드와 PC 사이에 연결되어 인식하지 못하는 단어를 입력하면 경고음을 냄

- Unix는 텍스트 처리 시스템으로 AT&T에 제안되었으며, 철자 검사기가 필요했음
  - UNIX는 주로 텍스트 처리에 사용됨

- 1980년대 초 Byte 기사에서 Unix의 철자 검사기를 만드는 방법을 설명함
  - 8비트 PC에서는 이러한 기능이 없었음

- 해싱으로 인해 놓치는 일반적인 오타가 있을 수 있음
  - Wordle 사전 압축에 관한 대회가 있음

- 1980년대 중반, 640KB RAM과 64KB의 힙 및 스택을 사용하여 데이터를 처리함
  - 데이터를 추출하고 결합하는 데 몇 시간이 걸렸으며, 단일 스레드 시스템에서 수행됨

- 1983년경 CP/M에서 Grammatik은 64k 미만으로 실행되었으며, 문법 검사와 전문가 시스템 규칙을 포함함
  - Forth로 작성되어 매우 컴팩트했음

- UNIX의 첫 번째 버전은 24kB가 필요했으며, 그 중 절반은 커널이 차지함