Haskell से Huffman code आधारित compression utility बनाना

 (lazamar.github.io)
1 पॉइंट द्वारा GN⁺ 2024-07-06 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • लगभग 150 लाइनों के Haskell में Huffman coding compressor लागू करते हुए, arbitrary binary files की encoding·decoding को constant memory में संभालने वाला structure दिखाता है
  • Huffman code अक्सर आने वाली values को छोटी bit sequences देता है, और prefix-free code condition से decoder bit sequence को बिना ambiguity के interpret कर पाता है
  • Implementation FreqMap, HTree, CodeMap के जरिए frequency table से tree बनाता है, और concatMap व recursive decoder की lazy evaluation से result को incremental रूप से generate करता है
  • Binary files के लिए Data.ByteString.Char8 से bytes को Char की तरह handle किया जाता है; compressed result के आगे frequency table serialize की जाती है और bit sequence को byte units में padding करके store किया जाता है
  • Tests में War and Peace 3.2M से 1.9M हो गया, 106M ghcup binary 84M तक घटा, और maximum resident set size 300KB से कम observe हुआ

Huffman code compression का basic idea

  • लक्ष्य Huffman coding का इस्तेमाल करके लगभग 150 लाइनों के Haskell में data compression utility implement करना है
  • पूरा code GitHub repository पर public है
  • Huffman code हर character या value को एक unique bit sequence assign करता है
    • अक्सर आने वाली values छोटी bit sequence use करती हैं
    • कम आने वाली values लंबी bit sequence use करती हैं
    • common values original representation से कम bits में represent होती हैं, जिससे compression effect मिलता है
  • Example aaab में a = 1, b = 0 रखने पर result 1110 बनता है
    • यह UTF-8 में 4 bytes लगने वाली string को आधे byte में represent करने का example है

Prefix-free code और Huffman tree

  • Decoding ambiguity-free होनी चाहिए, तो कोई भी codeword किसी दूसरे codeword का prefix नहीं होना चाहिए
    • उदाहरण के लिए aaabc में a = 1, b = 10, c = 01 assign करने पर 101 के ac या ba होने में ambiguity हो सकती है
  • Prefix-free code को full binary tree के रूप में बनाया जा सकता है
    • सभी values को leaves पर रखा जाता है
    • left edge को 1, right edge को 0 label किया जाता है
    • root से leaf तक का path उस value का codeword बनता है
  • Huffman tree कम frequency वाली values को नीचे से group करते हुए ऊपर की ओर बनाने के तरीके से generate किया जाता है
    • हर character को उसके occurrence count यानी weight के साथ node बनाया जाता है
    • सबसे छोटे weight वाले दो nodes को tree में जोड़ा जाता है
    • नए tree का weight दोनों nodes के weights का sum होता है
    • यह तब तक repeat होता है जब तक सिर्फ एक tree न बच जाए
  • इस process से ज्यादा frequent values root के करीब आ जाती हैं और उनके codewords छोटे हो जाते हैं

Haskell encoder structure

  • Implementation के main types Bit, Code, FreqMap, CodeMap, Weight, HTree हैं
    • Bit One या Zero है
    • Code [Bit] है
    • FreqMap Map Char Int है, जो हर character की occurrence count store करता है
    • CodeMap Map Char Code है, जो हर character का codeword store करता है
    • HTree Leaf Weight Char या Fork Weight HTree HTree है
  • HTree को weight के आधार पर comparable बनाया गया है ताकि tree generation process में sorting और insertion simple रहे
  • countFrequency string में हर character की occurrence count calculate करता है
  • buildTree FreqMap को leaf list में बदलकर sort करता है, फिर सबसे छोटे दो nodes को repeatedly combine करके Huffman tree बनाता है
  • buildCodes tree traverse करते हुए left में One, right में Zero जोड़कर हर character का codeword generate करता है
  • encode :: FreqMap -> String -> [Bit] FreqMap से tree और code map बनाता है, और input string के हर character को codeword से replace करके bit list बनाता है

Lazy evaluation से incremental processing

  • Encoding का core transformation concatMap codeFor str है
    • Conceptually यह [Char] को [[Bit]] में बदलकर फिर [Bit] में flatten करने की process है
    • Haskell की lazy evaluation की वजह से यह पहले पूरे input को encode करके फिर combine करने जैसा operate नहीं करता
  • छोटी lists left से right की ओर process होती हैं और बड़ी result list में flatten होती हैं
    • Result list का tail अभी evaluate नहीं हुआ thunk बना रहता है
    • जब कोई needed value request होती है, तभी next part calculate होता है
  • Decoder भी इसी तरह result incremental रूप से generate करता है
    • decode :: FreqMap -> [Bit] -> String bits के अनुसार tree में left या right जाता है
    • Leaf पर पहुंचने पर character output करता है और root से फिर शुरू करता है
    • यह तब तक repeat होता है जब तक decoded characters की total count Huffman tree के weight के बराबर न हो जाए
  • Decoder input bit list के end से नहीं, बल्कि character count के आधार पर रुकता है
    • क्योंकि serialization stage में byte alignment के लिए आखिर में padding bits add किए जाते हैं
  • go function leaf पर पहुंचने पर known head वाली list और tail recursive call return करता है, इसलिए पूरी recursion खत्म होने से पहले result evaluate किया जा सकता है

Binary file handling और serialization

  • Binary data को 256 possible bytes में से किसी एक के repeat होने वाले form के रूप में देखा जा सकता है
  • Data.ByteString.Char8 ByteString को Char operations से handle करने देता है, और सभी Char 8-bit में truncate हो जाते हैं
    • इस property की वजह से text coder को ज्यादा बदले बिना binary data पर भी apply किया जा सकता है
  • Compressed file में decoding के लिए जरूरी FreqMap पहले आता है, उसके बाद encoded bit sequence आती है
  • serializeFreqMap frequency table को निम्न format में record करता है
    • Map length को Word8 के रूप में store करता है, लेकिन representable range adjustment के लिए 1 घटाकर store करता है
    • हर item में key को Word8 और frequency value को 64-bit big-endian integer के रूप में store किया जाता है
  • serialize binary package के Put monad से ByteString generate करता है
    • Bits को एक-एक करके पढ़कर एक byte fill करता है
    • 8 bits भरने पर putWord8 से record करता है
    • Last byte में बची जगह Zero से pad की जाती है

Deserialization और constant-memory strategy

  • deserializeFreqMap Data.Binary.Get से serialized frequency table पढ़ता है
    • पहले length पढ़कर उसमें 1 जोड़कर actual item count calculate करता है
    • हर item से Word8 key और 64-bit frequency value पढ़कर FreqMap restore करता है
  • बाकी पूरा input Get से process नहीं किया जाता; इसके बजाय ByteString में offset के बाद वाला हिस्सा निकालकर bit list में बदला जाता है
  • deserialize (FreqMap, [Bit]) return करता है, और [Bit] एक lazy list है जो तुरंत पूरी calculate नहीं होती
    • अगर इस list की length मांगी जाए तो पूरी list evaluate करनी पड़ेगी, इसलिए इससे बचना चाहिए
  • पूरे input पर Get use न करने की वजह यह है कि monad का bind order force करता है
    • इससे ऐसी structure बनती है जिसमें पूरी input processing खत्म होने के बाद ही list return हो सकती है
  • Constant-memory strategy यह है कि output bits लिखते समय input का सिर्फ next छोटा हिस्सा evaluate किया जाए
    • कुछ ByteString evaluate होता है और file का वह piece पढ़ा जाता है
    • Processed output file में record होता है
    • जिन input pieces और bit lists का अब reference नहीं रहता उन्हें garbage collector reclaim कर सकता है
  • FreqMap byte basis पर maximum 256 items वाला होता है, इसलिए constant-size overhead में रहता है

File compression·decompression CLI

  • compress input file को दो बार पढ़ता है
    • First pass में FreqMap बनाता है
    • Second pass में उसी FreqMap से data encode करता है
  • अगर file को सिर्फ एक बार पढ़कर वही reference encode को दें, तो frequency table बनने के बाद भी पूरे input file reference को बनाए रखना पड़ेगा, इसलिए पूरी file memory में रखनी पड़ेगी
  • दो बार पढ़ने वाला तरीका frequency table generation और encoding दोनों में processed memory को process के दौरान free होने देता है
  • decompress compressed file पढ़कर deserialize से FreqMap और bit list लेता है, फिर decode result को file में save करता है
  • CLI ये arguments लेता है
    • compress FILE FILE
    • decompress FILE FILE
  • चूंकि यह केवल GHC में included packages use करता है, इसलिए cabal के बिना ghc -O2 Main.hs -o main से compile किया जा सकता है

Execution results और memory usage

  • Tolstoy की War and Peace text file test में compression और decompression के बाद diff result identical है
    • Original WarAndPeace.txt: 3.2M
    • Compressed file: 1.9M
    • Decompressed file: 3.2M
    • Size लगभग 40% घट गया
  • बड़े binary file ghcup पर भी compression और decompression काम करता है
    • Original ghcup: 106M
    • Compressed file: 84M
    • Decompressed file: 106M
    • Compression time लगभग 15.173 seconds, decompression time लगभग 14.555 seconds है
  • +RTS -s के हिसाब से ghcup processing के दौरान maximum resident set size 300KB से कम है
  • दोनों processes execution में 10MB से कम memory use करते हैं
  • Time कहां spend हुआ, यह अलग profile में देखा जा सकता है

आगे सुधार की संभावनाएं

  • Implementation goal जितना हो सके उतनी simple और clear compression utility बनाना था; efficiency बढ़ाने के लिए ज्यादा complex implementation चाहिए
  • Possible improvements ये हैं
    • Multithreading: file sections को parallel decode करना, लेकिन arbitrary position पर codeword boundary पता नहीं चल सकती, इसलिए compressed file की शुरुआत में section boundaries और expected decoded size table add करनी होगी
    • Single-pass encoding: सभी bytes की frequency 1 वाली initial frequency table से शुरू करना, और हर byte देखते समय पहले encode करना फिर frequency table update करना
    • Canonical Huffman codes: decoding में tree को O(log n) में traverse करने के बजाय code को vector index की तरह use करके O(1) access target किया जा सकता है; related details Canonical Huffman code में हैं
    • Faster code generation: single-pass encoding में CodeMap generation को काफी faster करना होगा, और tree बनाए बिना codewords generate करने का faster तरीका मौजूद है
  • भविष्य में adaptive dictionary method LZ77 का इस्तेमाल करने पर Huffman code के साथ gzip implement किया जा सकता है

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

1 टिप्पणियां

 
GN⁺ 2024-07-06
Hacker News की राय

  • इस काम के लिए एक array-based in-place algorithm है, जो trees allocate करने और pointers follow करने का काम कम करता है
    कॉलेज में जब tree-based approach सीखी थी, तब मुझे पता नहीं था कि कोई दूसरा तरीका भी है, और सोचता हूँ क्या दूसरों के साथ भी ऐसा ही था
    tree वाला तरीका intuitive है और समझने में मदद करता है, लेकिन जहाँ compression सबसे ज़्यादा मायने रखता है, वहाँ आमतौर पर data बहुत होता है और उसे तेज़ चलाना होता है, इसलिए in-place array के रूप में संभालना ज़्यादा logical हो सकता है
    In-Place Calculation of Minimum-Redundancy Codes, Moffat, Katajainen, 1995
    http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

    • सामान्य तौर पर Moffat और Turpin का On the Implementation of Minimum Redundancy Prefix Codes भी देखने लायक है
      Charles Bloom ने इसकी ज़ोरदार सिफारिश की थी और बाद में इस पर explanation भी जोड़ा था
      https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
    • JPEG standard ITU T.81(1992) में यह algorithm flowchart के रूप में समझाया गया है, इसलिए लगता है कि array-based Huffman के बारे में जानकारी 80s में भी कुछ हद तक पहले से ज्ञात थी
    • लेख के अंत में इसका ज़िक्र है, और इसे reader exercise के रूप में छोड़ दिया गया है
    • “सोचता हूँ कि क्या आपमें से कुछ लोगों पर भी यह लागू होता है” वाला वाक्य list comprehension जैसा सुनाई देता है

  • “कोई भी code word किसी दूसरे code word का prefix नहीं होना चाहिए, तभी ambiguity नहीं होगी” — यह बात strictly accurate नहीं है
    तथाकथित uniquely decodable codes ambiguous नहीं होते, और वे prefix codes का superset हैं
    एक आसान उदाहरण है prefix code को उलट देना. लेख के उदाहरण में यह a 1, b 00, c 10 होगा
    a का code, c code का prefix है, लेकिन code sequence को उल्टे क्रम में process करें तो फिर भी बिना ambiguity के decode कर सकते हैं. ऐसा uniquely decodable code देखना दिलचस्प होगा जो न prefix code हो और न उसका reverse

    • prefix code और suffix code को compose करें तो बिना अनावश्यक inefficiency के ऐसा code बनाया जा सकता है
      A 0, B 01, C 11 रखें, और फिर a A 0, b BA 010, c BB 0101, d BC 0111, e C 11 रखें, तो {a=0,b=010,c=0101,d=0111,e=11} मिलता है
      पीछे से 0->A जैसी uniquely decoding करने के बाद, आगे से A->a जैसी uniquely decoding दोबारा कर सकते हैं, इसलिए यह साफ़ तौर पर uniquely decodable है
      length के लिहाज़ से यह optimal prefix code {a=0,b=110,c=1110,d=1111,e=10} जैसा ही है, इसलिए समान probability distribution के लिए यह कई optimal codes में से एक है
      साथ ही a=0, b=010 की वजह से यह न prefix code है, न suffix code. दरअसल सामान्य तौर पर किसी भी दिशा में incremental decoding संभव नहीं होती, और cee...ee? और bee...ee?, ?cc...cca और ?cc...ccb में अंतर करने के लिए एक symbol पहचानने में भी असीमित lookahead की ज़रूरत पड़ सकती है
      स्वतंत्र रूप से optimal prefix code और स्वतंत्र रूप से optimal suffix code को compose करने पर optimality हमेशा बनी रहती है या नहीं, यह मुझे नहीं पता, लेकिन degenerate 1:1 codes को छोड़कर मेरे दिमाग में आए सबसे सरल cases में यह ठीक काम करता है
    • यह समस्या उम्मीद से ज़्यादा दिलचस्प है. पहले तो adversarial जवाब के रूप में a 101, b 1 जैसा उदाहरण दिया जा सकता है
      लेकिन यह खराब code है, क्योंकि हमेशा a=1, b=0 रखना बेहतर होगा
      Kraft inequality बताती है कि code lengths के कौन-से sets uniquely decodable बनाए जा सकते हैं, और Huffman coding से ऐसे सारे sets हासिल किए जा सकते हैं. इसलिए अगर आप symbol coding कर रहे हैं, तो ANS या arithmetic coding जैसे किसी दूसरे तरीके पर जाने के अलावा non-prefix code इस्तेमाल करने की कोई वजह नहीं है
      हालांकि यह नहीं पता कि optimal Huffman code जैसे length set वाला, लेकिन न prefix code और न उसका reverse यानी suffix code, ऐसा कोई uniquely decodable code मौजूद है या नहीं
      समय लगाऊँ तो शायद https://en.wikipedia.org/wiki/Sardinas-Patterson_algorithm देखकर brute force से counterexample खोजूँगा, या algorithm के काम करने के तरीके से proof सोचूँगा
    • अजीब उदाहरण है, लेकिन a 1, b 101 कैसा रहेगा, यह सोचता हूँ
      यह न prefix-free है, न suffix-free, लेकिन जब भी 0 आता है, वह b के आने से correspond करता है
      बेशक यह साफ़ तौर पर inefficient है, इसलिए आखिर सवाल यह है कि क्या ऐसा optimal code है जो न prefix-free हो न suffix-free
      खोजने पर https://blog.plover.com/CS/udcodes.html में a 0011, b 011, c 11, d 1110 वाला uniquely decodable code example मिलता है
      इसमें एकमात्र prefix relation बस इतना है कि c, d का prefix है, इसलिए यह “लगभग” prefix-free जैसा है. अगर message 1 से शुरू होता है, तो पहला 0 खोजकर उसके पहले कितने 1 हैं—odd या even—यह देखकर शायद समझा जा सकता है कि यह uniquely decodable है
      हालांकि यह किस probability distribution के लिए optimal है, यह दिखाने का तरीका याद नहीं, क्योंकि cryptography का ज्ञान काफ़ी rust हो चुका है
    • दिलचस्प है, लेकिन शायद इसे आमतौर पर इस्तेमाल न करने की वजह यह है कि ambiguity resolve करने वाला bit आने तक बहुत लंबी bit sequence पढ़नी पड़ सकती है
      उदाहरण के लिए 100000000000000001 में पहला code a है या c, यह जानने के लिए सभी 0s खत्म होने वाली जगह तक पूरा पढ़ना पड़ेगा

  • इस लेख की तरह Haskell program बनाते हुए आगे बढ़ने वाले similar tutorials में, क्या monad transformers या lenses जैसी ज्यादा advanced features को cover करने वाली कोई material है?

    • Haskell in Depth किताब recommend करता हूँ. monad transformers chapter 6 में हैं, lenses chapters 3 और 14 में cover किए गए हैं
      Template Haskell, concurrency जैसी दूसरी advanced features भी cover होती हैं, और Haskell में SQL databases handle करने वाला chapter भी है
    • https://github.com/turion/rhine-koans देखने लायक है
      यह FRP library Rhine का tutorial है, और comments व tests अच्छी तरह लिखे गए हैं

  • Coursera के Scala-आधारित functional programming course में भी काफी मिलता-जुलता Huffman coding assignment है, और उसमें automatic grader भी है, इसलिए जो लोग खुद हल करके देखना चाहते हैं उनके लिए अच्छा है
    https://www.coursera.org/learn/scala-functional-programming?...

  • आख़िरी बार मैंने Huffman code का इस्तेमाल MICMAC processor के macroprogram, यानी assembly text को न्यूनतम microcycles और न्यूनतम microinstructions में चलाने के लिए किया था
    मैंने executed macroinstruction histogram से शुरुआत की थी, और जहाँ तक याद है, पहले C में interpreter लिखकर गिना था कि हर instruction कितनी बार execute होती है
    उसके बाद मैंने एक incremental decoding microcode program बनाया, जो ज़रूरी ISA macro operations सभी को implement करता था। लगता है कि बनाया गया macroinstruction ISA byte-oriented नहीं, बल्कि bit-level था
    असल दुनिया में यह धीमा और असुविधाजनक रहा होगा, लेकिन Huffman code का फायदा यह है कि value distribution के हिसाब से prefix depth adjust की जा सकती है, इसलिए 1-bit prefix की वजह से एक तरफ़ झुका हुआ code बनाने की ज़रूरत नहीं पड़ती
    साथ ही, microprogram एक non-superscalar pipelined processor model था, इसलिए branch prediction भी संभालनी पड़ती थी। branch को गलत predict करने पर, सही branch के आगे propagate होने तक pipeline stall की वजह से cycles बर्बाद हो जाते हैं

  • https://rosettacode.org/wiki/Huffman_coding

  • लगता है Haskell प्रोग्रामर यहाँ इकट्ठा होंगे, इसलिए पूछना चाहता हूँ: आजकल Haskell, अगर कोई programmer optimization पर ध्यान देकर लिखे, तो कितना तेज़ है?
    खासकर matrix operations जैसे numeric computing और SIMD से फायदा लेने वाले workloads की performance जानना चाहता हूँ

    • Haskell की speed system languages से मुकाबला कर सकती है, लेकिन यह ध्यान में रखना चाहिए कि इसका मुख्य फायदा abstraction की आसानी है
      कई हिस्सों को एक consistent और अच्छी तरह organized program में जोड़ना आसान होना ही core बात है। यह सिर्फ tight loops के लिए नहीं, बल्कि पूरे program के लिए अहम है
      Haskell का FFI अच्छा है, इसलिए जिन हिस्सों में मूल रूप से imperative optimization की ज़रूरत होती है, उन्हें garbage collection वाली language के बाहर ले जाया जा सकता है। अगर ऐसे हिस्सों को अच्छे types वाली library में wrap कर दें, तो type-match करने वाले Haskell code में कहीं भी उस raw performance का इस्तेमाल किया जा सकता है
      Meta में high-performance Haskell applications बनाते समय हमने ऐसा ही किया था। सुंदर, बड़े और तेज़ Haskell programs लिखे, लेकिन कुछ specialized हिस्सों में C++ components लगाए। 99% समय Haskell side पर उन्हें ज्यादा उपयोगी applications में compose करने में लगा
    • रोज़मर्रा के backend, web, CLI कामों में Haskell की performance मुझे पसंद है। लेकिन performance-centric code लिखते समय मैं Rust पर उतर जाता हूँ
      फिर भी Haskell धीमी नहीं है। file में 1-bit की संख्या गिनने वाला छोटा program इसका उदाहरण हो सकता है
      -msse4.2 से compile करने पर यह hardware popcount instruction का सही इस्तेमाल करता है, और 1GB input file को 0m0,090s में process करता है। MB में round करने पर heap usage 0 है
      -msse4.2 के बिना compile करने पर 0m0,293s लगता है
      matrix computation खुद नहीं आज़माया, लेकिन शुरुआत के लिए शायद repa, accelerate, massiv देखूँगा
      https://hackage.haskell.org/package/repa
      https://hackage.haskell.org/package/accelerate
      https://hackage.haskell.org/package/massiv
    • ZuriHac में Sam Derbyshire से मिला था, और सुना कि SIMD support के लिए मुश्किल architecture work पूरा हो चुका है
      https://gitlab.haskell.org/ghc/ghc/-/issues/7741
      यह GHC 9.12 में आ सकता है। हालांकि target केवल 128-bit vectors होंगे, और जब तक दूसरे लोग contribute नहीं करते, यह मुख्यतः floating-point operations पर केंद्रित रहेगा
      patch यहाँ है
      https://gitlab.haskell.org/ghc/ghc/-/merge_requests/12860
    • व्यावहारिक रूप से, C समेत किसी भी language में compiler-optimized code, BLAS जैसी libraries के hand-optimized code जितना तेज़ नहीं हो सकता
      एक स्तर पर host language का चुनाव बहुत मायने नहीं रखता। अगर आप सच में speed को लेकर serious हैं, तो computation वैसे भी बाहर offload कर देंगे
      इसी वजह से AI code—जो दुनिया में सबसे ज्यादा compute resources इस्तेमाल करने वालों में हो सकता है—low-level compute libraries को छोड़कर Python में लिखा जा सकता है
      सीधे जवाब दें तो GHC compiler बहुत अच्छा है। high-level code काफी अच्छा चलता है, और ज्यादातर real-world applications में performance bottleneck single-width operations vs SIMD जैसी चीज़ नहीं, बल्कि architecture की समस्या होती है। Haskell की “architectural asymptotics” काफी फायदेमंद हैं
      मुझे लगता है GHC में SIMD support है या आ रहा है, लेकिन performance evaluate करते समय मैं उसी पर focus नहीं करूँगा
      Haskell में matrix multiplication algorithm खुद नहीं लिखूँगा, लेकिन अगर speed को लेकर serious हूँ तो Rust या C में भी खुद नहीं लिखूँगा
      numeric computing को अक्सर performance metric माना जाता है, लेकिन असल में बहुत कम लोगों का bottleneck वहीं होता है; और अगर bottleneck वहीं है, तो आप कौन-सी high-level language इस्तेमाल कर रहे हैं, यह ज्यादा मायने नहीं रखता
    • Haskell तब सच में चमकता है जब आप high-level declarative code लिखना चाहते हैं
      इस style की performance आम तौर पर CLI या web backend tasks के लिए पर्याप्त होती है। काफी तेज़ low-level code लिखने के tools भी हैं, लेकिन वे थोड़े rough हैं, इसलिए अगर आप सिर्फ वही करना चाहते हैं तो शायद यह best tool नहीं है
      हालांकि जब optimize करने के लिए कुछ concentrated hotspots हों, तो यह काफी ठीक है
      CPU profiling tools अच्छे हैं, इसलिए CPU hotspots ढूँढना और optimize करना अपेक्षाकृत pleasant है। दूसरी ओर lazy evaluation की वजह से ज्यादा आसानी से बनने वाले अजीब memory leaks को trace करना बहुत frustrating हो सकता है
      benchmarks game के results देखें तो सबसे तेज़ Haskell implementations आम तौर पर सबसे तेज़ C versions से 2–5 गुना धीमे हैं, और काफी imperative style में लिखे गए हैं
      https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

  • “Creating prefix-free codes” section की table में typo लगता है। D 0110 नहीं, 0010 होना चाहिए

    • इसलिए मैं काफी देर तक सोचता रहा कि 0110 ambiguous कैसे नहीं हो सकता, अब समझ आया

  • image में महिला की shirt पर क्या है, यह जानना चाहता हूँ
    direct link: https://lazamar.github.io/images/data-compressor.svg