- 1970 के दशक में AT&T का Unix spell, PDP-11 की 64KB RAM के भीतर 250KB dictionary को तेज़ी से lookup करना चाहता था, और Douglas McIlroy ने general-purpose compression के बजाय डेटा की विशेषताओं का उपयोग करके इसे हल किया
- Steve Johnson का शुरुआती prototype disk-based था, इसलिए धीमा था और accuracy कम थी, लेकिन McIlroy ने stemming के ज़रिए dictionary को करीब 25,000 शब्दों तक घटाकर performance और accuracy बेहतर की
- पहली in-memory structure Dennis Ritchie द्वारा implement किया गया Bloom filter था, जिसमें 400,000-bit table और 11 hash functions के साथ लगभग 1/2000 false-positive rate हासिल किया गया और अलग dictionary lookup छोड़ दिया गया
- जब dictionary 30,000 शब्दों तक बढ़ गई, तो सिर्फ Bloom filter से memory constraints पूरा करना कठिन हो गया; इसलिए 27-bit hashes को sort करके hash differences को Golomb code से compress किया गया
- अंतिम implementation ने compressed difference table को कई bins में बाँटकर lookup speed बढ़ाई, और प्रति शब्द लगभग 14 bits storage के साथ 64KB के भीतर तेज़ spell checking संभव बनाई
Unix spell के सामने आई memory constraint
- मुख्य समस्या 250KB dictionary को 64KB RAM environment में तेज़ी से lookup करना था
gzip -9 जैसी आधुनिक compression लगाने पर भी यह file 85KB से कम नहीं होती- 1970 के दशक के PDP-11 पर पूरी dictionary को memory में load नहीं किया जा सकता था, और disk-based lookup धीमा था
- McIlroy ने general-purpose compression के बजाय dictionary data की structure और probability distribution का उपयोग करने वाला specialized data structure design किया
शुरुआती Unix spell और stem-based dictionary reduction
- AT&T ने Unix को patent department के लिए text processing system के रूप में propose किया, जिससे spell checker की ज़रूरत पड़ी
- Steve Johnson ने 1975 में पहला Unix spell prototype लिखा, और Jon Bentley के अनुसार यह काम एक दोपहर में बना था
- शुरुआती version input file को word stream में बाँटता था, फिर numbers और special characters हटाना, lowercase conversion, sorting, duplicate removal करके disk dictionary में word existence check करता था
- साधारण disk lookup method धीमा था और accuracy भी कम थी
- McIlroy ने performance और accuracy बढ़ाने के लिए दो हिस्सों को फिर से design किया
- prefixes और suffixes हटाकर शब्दों को stem में घटाने वाला algorithm
- dictionary को memory में रखकर तेज़ lookup करने वाला compressed data structure
prefix/suffix removal algorithm
- McIlroy की stemming method किसी word से common prefixes और suffixes को बार-बार हटाती थी, फिर check करती थी कि reduced word dictionary में है या नहीं
- उदाहरण के लिए
misrepresented से prefix mis, re और suffix ed हटाकर यह present बनता है
- अगर
present dictionary में है, तो original word को typo के रूप में mark नहीं किया जाता
- यह method 100% accurate नहीं था और कुछ typos को pass कर सकता था, लेकिन उस समय इसे acceptable level माना गया
- common errors से बचने के लिए exception rules भी साथ में implement किए गए
- अंतिम dictionary 25,000 words तक घट गई, और well-designed data structure होने पर इसे memory में load किया जा सकने वाला आकार मिल गया
Bloom filter आधारित lookup
- McIlroy ने सबसे पहले जिस in-memory structure का उपयोग किया, उसे उस समय के paper में “superimposed code scheme” कहा गया था; वही Bloom filter था
- Bloom filter paper 1970 में प्रकाशित हुआ था, और Unix spell 1970 के दशक के मध्य में विकसित हुआ
- यह implementation Dennis Ritchie ने दिया था
- Bloom filter bit table को 0 से initialize करता है, फिर प्रत्येक item पर कई hash functions apply करके corresponding bits को 1 set करता है
- lookup के समय भी वही hash functions apply किए जाते हैं
- अगर कोई भी bit 0 हो, तो वह item मौजूद नहीं है
- अगर सभी bits 1 हों, तो item मौजूद हो सकता है, लेकिन false positive की संभावना बची रहती है
- सामान्य Bloom filter में false positives handle करने के लिए actual dictionary lookup की ज़रूरत होती है, लेकिन spell checker में ज़्यादातर words dictionary में मौजूद होते हैं, इसलिए full dictionary lookup बार-बार हो सकता था
- McIlroy ने false-positive rate इतना कम कर दिया कि actual dictionary lookup को छोड़ दिया गया
- accepted false-positive rate 1/2000 था
- dictionary word count 25,000 था
- bit table size 400,000 bits था
- hash functions 11 थे
- इस combination से false-positive rate लगभग 1/2000 के स्तर पर रखा गया
Bloom filter की सीमाएँ और compressed hash method
- Bloom filter method कुछ समय तक इस्तेमाल हुआ, लेकिन नए words लगातार add होते गए और dictionary 25,000 से बढ़कर 30,000 words हो गई
- वही false-positive rate बनाए रखने के लिए बड़े bit table की ज़रूरत थी, लेकिन memory constraints के कारण यह मुश्किल था
- McIlroy ने पूरी hash table के बजाय केवल words के hash values store करने की method अपनाई
- lookup input word का hash calculate करके stored hash list में existence check करने की तरह काम करता था
- hash collisions की संभावना कम करने के लिए पर्याप्त बड़े hash code की ज़रूरत थी
- dictionary size
v लगभग 30,000, यानी करीब 2^15 था
- accepted collision probability
1 / 2^12 थी
- आवश्यक hash size 27 bits था
- 30,000 27-bit hashes store करने पर PDP-11 की 64KB RAM में fit नहीं होता, इसलिए compression अनिवार्य था
theoretical compression limit
- McIlroy ने पहले hash code set को store करने के लिए ज़रूरी theoretical minimum bit count calculate किया
- अगर hash code size
b bits है, तो possible hash codes 2^b हैं, और उनमें से v unique hash codes चुनने के number of cases को information quantity में बदला गया
- calculation में Stirling approximation और
v « 2^b की simplifying assumption का उपयोग किया गया
v=30,000, b=27 रखने पर single hash code store करने के लिए minimum value 13.57 bits निकलती है- यह original 27-bit hash से करीब 50% छोटा है, और PDP-11 memory capacity के भीतर आ सकने वाला level है
hash differences storage और lookup
- McIlroy ने original hash codes को सीधे compress नहीं किया; उन्होंने sorted hash codes के बीच के differences store किए
- उदाहरण इस प्रकार है
sorted hash codes: 5, 14, 21, 32, 55, 67
hash differences: 5, 9, 7, 11, 23, 12
- differences store करने के दो फायदे थे
- difference values original hash code से छोटी होती हैं
- कई hash code pairs में same difference value repeat हो सकती है
- lookup input word का hash calculate करने के बाद differences को शुरुआत से accumulate करता है
- अगर cumulative sum input hash के बराबर हो, तो वह मौजूद है
- अगर cumulative sum input hash से आगे निकल जाए, तो वह मौजूद नहीं है
- storage space घटता है, लेकिन compressed values को शुरुआत से decode और accumulate करना पड़ता है, इसलिए lookup धीमा हो सकता है
hash differences का geometric distribution modeling
- lossless compression तब efficient होती है जब frequently occurring values को short codes और rare values को long codes दिए जाते हैं
- सामान्य probability distribution table-based compression McIlroy की constraints के अनुकूल नहीं थी
- करीब 30,000 symbols की probability distribution table memory में रखने पर compression gains खत्म हो जाते
- difference values की frequency और probability calculate करने के लिए costly disk-based structure की ज़रूरत पड़ती
- McIlroy ने इस बात का उपयोग किया कि hash differences geometric distribution follow करते हैं
- hash space में
2^b points हैं, और उनमें v hash codes distributed हैं
- किसी point पर hash होने की probability
q = v / 2^b है
- खाली होने की probability
p = 1 - v / 2^b है
- difference
k तब होता है जब किसी hash के बाद k-1 positions खाली हों और k-th position पर अगला hash हो
- इसलिए difference
k की probability p^(k-1)q होती है, जो geometric distribution form से match करती है
Golomb code से differences compression
- McIlroy ने geometric distribution integers के लिए उपयुक्त Golomb code से hash differences compress किए
- Golomb के 1965 paper ने geometric distribution values के लिए simple run-length coding method दी
- geometric distribution में probability exponentially decrease होती है, इसलिए values को size
m blocks में group करके, अगले block पर जाने के साथ code length को 1 bit बढ़ाने वाली structure बनाई जा सकती है
- Unix spell implementation ने Golomb paper की method से अलग, थोड़ा अधिक complex लेकिन efficient encoding/decoding algorithm इस्तेमाल किया
- original SVR4 implementation निम्न स्थानों पर देखा जा सकता है
- Golomb code hash differences को प्रति शब्द 13.60 bits की expected code length तक compress करता है
- यह theoretical minimum 13.57 bits के बहुत करीब है
lookup speed के लिए bin partitioning
- सिर्फ compressed difference table का उपयोग करने पर lookup के दौरान शुरुआत से decode और accumulate करना पड़ता, इसलिए यह धीमा था
- अंतिम Unix spell implementation ने difference table को
M bins में बाँटा
- lookup के समय पहले संबंधित bin खोजा जाता है, और केवल उसी के भीतर scan किया जाता है
- यह method search speed को
M गुना बढ़ाती है
- बदले में bin pointers store करने पड़ते हैं, इसलिए प्रति शब्द
log₂M bits का extra storage space चाहिए
- कुल storage प्रति शब्द लगभग 14 bits तक बढ़ी, लेकिन यह memory budget के भीतर कहीं तेज़ lookup देने वाला trade-off बना
Unix spell ने दिखाया constraint-based design
- Unix spell Bloom filter, information theory, probability theory और Golomb compression को जोड़ने वाला design example है
- development process का flow इस तरह रहा
- Bloom filter से low false-positive rate हासिल किया गया
- dictionary बड़ी होने पर compressed hash method पर switch किया गया
- hash storage के theoretical minimum bit count की calculation की गई
- hash differences के distribution को पहचाना गया
- Golomb code से लगभग optimal compression हासिल की गई
- bin partitioning से थोड़ा space overhead जोड़कर lookup तेज़ बनाया गया
- आधुनिक spell checkers edit distance या language models जैसी अन्य techniques का उपयोग करते हैं, लेकिन Unix spell theoretical understanding और practical constraints को मिलाकर efficient system बनाने का उदाहरण बना हुआ है
1 टिप्पणियां
Hacker News की राय
बहुत कम RAM में भी external-memory spell checker बनाया जा सकता है: डॉक्यूमेंट के शब्दों को sort करें, unique शब्द हटाएँ, फिर sorted dictionary के साथ merge करके सिर्फ वे शब्द छोड़ दें जो मौजूद नहीं हैं।
मैंने यह तरीका Creative Computing के BASIC example में देखा था, और इसे TRS-80 Color Computer पर चलाया था, जहाँ उपलब्ध RAM 32KB से भी काफी कम थी, इसलिए title देखते ही सबसे पहले वही याद आया।
उस समय Turbo Lightning ने लोगों को चौंका दिया था; इसकी compressed dictionary PC पर चल रहे दूसरे programs के साथ fit हो जाती थी और typing के दौरान spell check करती थी।
PC में 640KB की सीमा थी, लेकिन दूसरे programs को disturb न करने के लिए उसका सिर्फ एक हिस्सा ही इस्तेमाल करना पड़ता था, और PC के शुरुआती दौर में उस memory को पूरा भरना भी लागत के लिहाज से आसान नहीं था।
Working copy को पहले disk पर save करना, sort करना, compare करना और फिर वापस load करना भी संभव रहा होगा, लेकिन C=64 developers ने शायद disk interface बहुत slow होने के कारण ऐसी strategy से बचा होगा।
एक हिस्सा कहता है कि उस समय Bloom filter को अभी Bloom filter नहीं कहा जाता था और Douglas ने paper में इसे “superimposed code scheme” कहा था, लेकिन Bloom filter superimposed code का एक specific type है।
Calvin Mooers ने 1940s में अपनी MIT master’s thesis में Shannon से सीधे प्रभावित होकर random superimposed coding विकसित की थी।
Bourne की शानदार 1963 की किताब “Methods of Information Handling” में mathematical details दी गई हैं।
मुझे यकीन है कि Douglas व्यापक technique से परिचित रहे होंगे। उदाहरण के लिए, “The Large Data Base File Structure Dilemma” (1975) के लेखक ने भी http://dx.doi.org/10.1021/ci60001a005 में इसे “super-imposed coding नाम की पुरानी technique” कहा था।
यहाँ “random” qualifier महत्वपूर्ण है, क्योंकि Mooers से पहले भी superimposed code मौजूद थे, लेकिन वे न तो mathematically बहुत interesting थे और न practically important।
“worse is better” के हिसाब से यह बहुत ज्यादा smart है। और खराब दिशा में सोचना चाहिए।
Main memory bandwidth और disk bandwidth लगभग बराबर थे, दोनों ही 1MB/s से थोड़ा ऊपर।
मैं होता तो शायद multiple-pass तरीका अपनाता, लेकिन फिर भी Bloom filter cool है, इसलिए शायद उसे ही इस्तेमाल करता।
https://github.com/arnoldrobbins/v10spell
https://code.google.com/archive/p/unix-spell/
Original paper भी शानदार है: https://www.semanticscholar.org/paper/Development-of-a-Spelling-List-McIlroy/e08c8a4c17f23c41616649ca73a908d06828d67f
यह उनकी webpage पर भी मौजूद है: https://www.cs.dartmouth.edu/~doug/
https://en.wikipedia.org/wiki/Douglas_McIlroy
अगर आप शब्दों के शौकीन हैं, तो “obovate” खोजते-खोजते यह leaf shape chart भी देख लेंगे।
https://upload.wikimedia.org/wikipedia/commons/e/e8/Leaf_morphology.svg
product name याद नहीं, लेकिन 80s में IBM PC के लिए एक hardware spell checker था। यह keyboard और PC के बीच जुड़ने वाला box था, और अगर आप ऐसा string type करते जिसे यह dictionary word के तौर पर पहचान नहीं पाता, तो beep करके बता देता था।
https://vintageapple.org/pcworld/pdf/PC_World_8711_November_1987.pdf के page 237 पर review है। बड़ा PDF है, ध्यान रखें।
Unix में मेरी रुचि जगाने वाली चीजों में से एक 1980s की शुरुआत के आसपास Byte का article था। उसमें split/sort/comm pipeline से spell checker बनाने की प्रक्रिया दिखाई गई थी, करीब 7 commands जितनी।
8-bit PC में ऐसा कुछ भी नहीं था, लेकिन देखने पर लगता था कि इतनी ज्यादा complexity की जरूरत भी नहीं है।
https://youtu.be/tc4ROCJYbm0?t=4m56s
अब जाकर पूरा लेख पढ़ा, और मुझे इसका सार यह लगता है: अगर आपके पास 30,000 शब्दों का “dictionary” है, और आप लगभग 1/4000 की false positive rate स्वीकार कर लें, तो हर शब्द को 27-bit string, यानी integer में hash करके dictionary को छोड़ देने और 30,000 27-bit strings के set को store करने की समस्या में बदल सकते हैं
थोड़ी हैरानी की बात है कि information theory के अनुसार 30,000 27-bit strings को प्रति शब्द 27 bits नहीं, बल्कि लगभग 13.57 bits में store किया जा सकता है। गणित समझ आता है (https://www.wolframalpha.com/input?i=log_2%282%5E27+choose+30000%29%2F30000), लेकिन 30,000, 2^27 यानी लगभग 13.4 करोड़ की तुलना में इतना छोटा है कि फायदा कहाँ से आ रहा है, इसे सहज रूप से समझने में शायद समय लगेगा
इन 30,000 27-bit hashes के subset को encode करने के लिए hash differences इस्तेमाल किए गए, और चूँकि ये differences geometric distribution follow करते हैं, इसलिए geometric-distribution input के लिए tuned Golomb coding से वास्तव में प्रति शब्द लगभग 13.6 bits हासिल हुए
मैंने सोचा कि क्या “perfect hashing” जैसी दिशा में सिद्धांततः इससे बेहतर किया जा सकता है। शायद कोई ऐसा function हो जो alphabetic word लेकर किसी transformation से गुजारे और फिर आसानी से verify करे कि resulting hash किसी अच्छे set में आता है या नहीं
लेकिन दोबारा सोचने पर, क्योंकि false positive rate चाहिए, इसलिए dictionary में न होने वाले word को “अच्छे” set में map होने से रोकने के लिए hash में कम से कम 27 bits चाहिए। यह तरीका मूलतः theoretical optimum जैसा लगता है। या फिर क्या कोई ऐसा तरीका मौजूद हो सकता है जिसमें हर word को 27-bit integer में map किया जाए, लेकिन अच्छे strings वे हों जिनकी value, मान लें, 30000 से कम हो?
संदर्भ के लिए, लगभग 1983 में CP/M का Grammatik 64KB से कम में चलता था, और 8-bit systems पर “grammar checking” करता था। असल में यह spell checking में expert-system rules जोड़ने जैसा था
याद रह जाने की वजह यह है कि मैंने इसके दिलचस्प हिस्से में झाँका था: यह इतना छोटा इसलिए हो पाया क्योंकि इसे Forth में लिखा गया था, और product के अंदर इतना external interpreter मौजूद था कि थोड़ी-सी hex editing करके इसे specialized functions preloaded वाले Forth interpreter की तरह इस्तेमाल किया जा सकता था
यह कैसे काम करता है देखने के लिए मैंने decompile नहीं किया, लेकिन यह छोटा, तेज़ और अच्छे से काम करता है
Hashing की वजह से कौन-सी आम typos छूट जाती होंगी, यह जानने की उत्सुकता है
इससे जुड़ी Wordle dictionary compression प्रतियोगिता भी है: http://golf.horse/wordle/
80 के दशक के मध्य में कुछ ऐसा ही अनुभव हुआ था। तेज़ होना relative बात है
Data बहुत था, और RAM 640KB, heap 64KB, stack 64KB था। सैकड़ों MB में से data search करके extract करना था और उसके कुछ हिस्सों को combine करना था
Data को ternary tree जैसी index structure में बनाने का प्रयोग किया। Conceptually बात बनती थी, लेकिन implement करने पर सिर्फ relationships और path information ही 64KB में फिट करने के लिए बहुत बड़ी निकली
Compression के बजाय swapping चुना। TSR, आज के हिसाब से service जैसा code लिखा, जो data chunk को process करता, result extract करके stack में store करता, फिर original data छोड़ देता और TSR को interrupt call भेजता। तब TSR heap साफ कर देता, storage से अगला chunk पढ़ता और control program को लौटा देता; program उसे process करता, stack data के साथ combine करता, और पूरा काम खत्म होने तक यह दोहराता
मूल रूप से इस काम के लिए data entry करने वाले 3 लोगों को लगभग एक सप्ताह और जानकारी combine करने वाला एक expert चाहिए था। लगभग बारह 3-inch ring binders जितनी tables सोच लीजिए। Program ने इसे कुछ घंटों में पूरा कर दिया और यह हैरान करने वाली तरह से “तेज़” था
यह single-threaded system पर किया गया काम था
https://en.wikipedia.org/wiki/Terminate-and-stay-resident_program
याद है कि UNIX spell में British spelling इस्तेमाल करने के लिए
-boption इस्तेमाल किया था। Language options सिर्फ दो थे, और अब सोचता हूँ कि ऐसा फैसला क्यों लिया गया, code इसे कैसे handle करता था, और अलग-अलग dictionaries कहाँ से आई थींAustralia और New Zealand के लोग British spelling लिखते थे या American spelling?
UNIX spell, spelling के क्षेत्र में ZX81 1K chess जैसा था, और home computers पर Windows 3.1 के लिए MS Word आने तक spell checking बहुत ज़्यादा नहीं थी। उससे पहले offices में secretaries WordPerfect पर type करती थीं और हर manager व team के लिए human spell checker का काम करती थीं
उधर घर पर dot matrix printer और flickering screen के साथ early computing दौर में मैं paper dictionary पर निर्भर रहकर जैसे-तैसे काम चला लेता था। उस समय सबको spelling आती थी, इसलिए याद नहीं कि spell checking इतनी महत्वपूर्ण थी। हजार students वाले school में dyslexia का दावा करने वाला बस एक बच्चा था, और spelling न आ पाने का वह एक plausible excuse बन गया था
शायद 1980s literacy का golden age था, और spelling ability के decline की साफ शुरुआत की तारीख वही दिन थी जब UNIX spell लिखा गया
Scrabble पसंद है। यह spell checking से बहुत अलग समस्या है, लेकिन processing में UNIX spell के साथ कुछ steps साझा करता है। Common word prefixes और suffixes खोजकर उन्हें rack या board पर दूसरे components से जोड़ता है
Scrabble dictionary भी UNIX spell से थोड़ी मिलती-जुलती है, क्योंकि वह meanings दिए बिना बस एक बड़ी word list होती है। मायने सिर्फ यह रखता है कि दिया गया word book में है या नहीं। 102 two-letter words जैसी कुछ special lookup tables भी होती हैं
Dictionary को disk से पढ़ते हुए check करता था, इसलिए कुछ मिनट लगते थे, और बाद में non-matching words को देखा जा सकता था