64kb RAM में चला Unix spell

 (blog.codingconfessions.com)
3 पॉइंट द्वारा GN⁺ 2025-01-20 | 1 टिप्पणियां | WhatsApp पर शेयर करें

Unix Spell को 64kB RAM में कैसे चलाया गया

64kB RAM में dictionary को कैसे फिट किया जा सकता है?
  • Unix इंजीनियरों ने data structure और compression techniques का उपयोग करके 64kB RAM में 250kB dictionary फिट करने की समस्या हल की।
  • 1970 के दशक में Douglas McIlroy को AT&T के Unix spell checker को implement करते समय इस समस्या का सामना करना पड़ा।
  • उन्होंने data की विशेषताओं का उपयोग करके ऐसा compression algorithm विकसित किया जो सैद्धांतिक compression limit के काफ़ी करीब था।

TL;DR

  • Unix spell checker की शुरुआत 1970 के दशक में AT&T के Steve Johnson के prototype से हुई।
  • McIlroy ने language-based stemming algorithm विकसित किया, जिससे dictionary 25,000 शब्दों तक घट गई।
  • तेज़ lookup के लिए Bloom filter का उपयोग किया गया, और Dennis Ritchie ने इसका implementation दिया।
  • जब dictionary 30,000 शब्दों तक बढ़ी, तो Bloom filter approach अप्रभावी हो गई और hash compression technique अपनाई गई।
  • 27-bit hash code का उपयोग करके collision की संभावना कम की गई, और Golomb code की मदद से 13.60 bits/word का compression हासिल किया गया।

Unix spell command की उत्पत्ति

  • Unix को AT&T के patent department में text processing system के रूप में प्रस्तावित किया गया था, और spell checker की आवश्यकता थी।
  • शुरुआती version Steve Johnson ने 1975 में लिखा था, लेकिन उसकी accuracy कम थी।
  • Douglas McIlroy ने accuracy और performance बेहतर करने के लिए project को फिर से लिखा।

prefix removal algorithm

  • McIlroy ने ऐसा algorithm विकसित किया जो शब्दों से common prefix और suffix हटाकर dictionary lookup करता था।
  • यह तरीका 100% accurate नहीं था, लेकिन उस समय के लिए स्वीकार्य था।

Bloom filter आधारित lookup

  • Bloom filter ने memory बचाने और तेज़ lookup संभव करने में मदद की।
  • 25,000 शब्दों की dictionary को 64kB RAM में लोड करने के लिए इसका उपयोग किया गया।
  • Bloom filter को low false positive rate बनाए रखने के लिए tune किया गया।

dictionary lookup के लिए compressed hashing technique

  • जब dictionary का आकार 30,000 शब्दों तक बढ़ा, तो अधिक memory-efficient data structure की ज़रूरत पड़ी।
  • McIlroy ने memory बचाने के लिए hash code के differences को store करने का तरीका अपनाया।
  • hash differences को compress करने के लिए Golomb code का उपयोग किया गया।

निष्कर्ष

  • Unix spell command, PDP-11 की memory limitations से जन्मी एक दिलचस्प engineering history है।
  • इसने Bloom filter, information theory, probability theory, और compression algorithm को जोड़कर एक elegant solution दिया।
  • यह दिखाता है कि resource constraints होने पर भी गहराई से problem-solving की जा सकती है।

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-01-20
Hacker News राय

  • Bloom फ़िल्टर को मूल रूप से "superimposed code scheme" कहा जाता था, और यह एक खास प्रकार का superimposed code है

    • Calvin Mooers ने 1940 के दशक में MIT में Shannon के काम से प्रभावित होकर random superimposed coding विकसित की
    • Bourne की 1963 की किताब "Methods of Information Handling" में इसके गणितीय विवरण दिए गए हैं
    • संभव है कि Douglas इस तकनीक को जानते थे

  • बाहरी मेमोरी spell checker को कम RAM में लागू किया जा सकता है

    • तरीका यह है कि दस्तावेज़ के शब्दों को sort किया जाए, unique शब्दों को अलग किया जाए, फिर उन्हें dictionary के साथ merge किया जाए ताकि केवल missing शब्द बचे रहें
    • इसे TRS-80 Color Computer पर 32k से कम RAM में चलाया गया था
    • Turbo Lightning compressed dictionary का उपयोग करके PC पर टाइप करते समय spell checking करता था

  • मेमोरी bandwidth और disk bandwidth लगभग समान थे, इसलिए कई passes के ज़रिए काम किया जा सकता था

    • इसके लिए Bloom फ़िल्टर का उपयोग करना अच्छा रहता

  • 1980 के दशक में IBM PC के लिए hardware spell checker मौजूद था

    • यह keyboard और PC के बीच जोड़ा जाता था, और कोई अपरिचित शब्द टाइप करने पर beep करता था

  • Unix को AT&T के सामने एक text processing system के रूप में प्रस्तावित किया गया था, इसलिए spell checker की ज़रूरत थी

    • UNIX का उपयोग मुख्य रूप से text processing के लिए होता था

  • 1980 के शुरुआती दौर के Byte लेख में Unix का spell checker बनाने का तरीका बताया गया था

    • 8-bit PC में ऐसी क्षमताएँ नहीं थीं

  • hashing की वजह से कुछ आम typos छूट सकते हैं

    • Wordle dictionary compression पर एक प्रतियोगिता है

  • 1980 के मध्य दशक में 640KB RAM और 64KB heap तथा stack के साथ data process किया जाता था

    • data को extract और combine करने में कई घंटे लगते थे, और यह single-threaded system पर किया जाता था

  • लगभग 1983 में CP/M पर Grammatik 64k से कम में चलता था, और इसमें grammar checking तथा expert system rules शामिल थे

    • यह Forth में लिखा गया था, इसलिए बहुत compact था

  • UNIX के पहले संस्करण को 24kB की आवश्यकता थी, जिसमें से आधा kernel ले लेता था