▲

GN⁺: 64kb RAM에서 실행된 Unix spell

 (blog.codingconfessions.com)
3P by neo 1달전 | ★ favorite | 댓글 1개

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 필터, 정보 이론, 확률 이론, 압축 알고리듬을 결합한 우아한 솔루션을 제공함.
  • 자원 제약이 있을 때 깊이 있는 문제 해결이 가능하다는 것을 보여줌.
▲
neo 1달전  [-]
Hacker News 의견

  • 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가 필요했으며, 그 중 절반은 커널이 차지함

답변달기