c++ हफमैन पेड़ को संग्रहित करने का कुशल तरीका




performance huffman-code (4)

मैं एक हफमैन एन्कोडिंग / डिकोडिंग टूल लिख रहा हूं और आउटपुट फ़ाइल के अंदर स्टोर करने के लिए बनाए गए हफमैन पेड़ को स्टोर करने के लिए एक कुशल तरीका ढूंढ रहा हूं।

वर्तमान में दो अलग-अलग संस्करण हैं जिन्हें मैं कार्यान्वित कर रहा हूं।

  1. यह पूरी फ़ाइल को चरित्र द्वारा मेमोरी कैरेक्टर में पढ़ता है और पूरे दस्तावेज़ के लिए आवृत्ति तालिका बनाता है। यह केवल एक बार पेड़ को आउटपुट करने की आवश्यकता होगी, और इस प्रकार दक्षता उस चिंता का बड़ा नहीं है, इनपुट इनपुट छोटा होने के अलावा।
  2. मैं जिस दूसरी विधि का उपयोग कर रहा हूं वह आंकड़ों का एक हिस्सा पढ़ने के लिए है, लगभग 64 किलोबाइट आकार में है और उस पर आवृत्ति विश्लेषण चलाएं, एक पेड़ बनाएं और इसे एन्कोड करें। हालांकि, इस मामले में प्रत्येक खंड से पहले मुझे अपने आवृत्ति पेड़ को आउटपुट करने की आवश्यकता होगी ताकि डीकोडर अपने पेड़ को फिर से बनाने में सक्षम हो और एन्कोडेड फ़ाइल को सही तरीके से डीकोड कर सके। यह वह जगह है जहां दक्षता आती है क्योंकि मैं जितना संभव हो उतना स्थान बचा सकता हूं।

मेरी खोजों में अब तक मुझे पेड़ को यथासंभव छोटी जगह में संग्रहित करने का एक अच्छा तरीका नहीं मिला है, मुझे आशा है कि स्टैक ओवरफ्लो समुदाय मुझे एक अच्छा समाधान खोजने में मदद कर सकता है!


चूंकि आपको पहले से ही अपने बाइट-संगठित स्ट्रीम / फ़ाइल के शीर्ष पर बिट-वार परत को संभालने के लिए कोड लागू करना है, तो मेरा प्रस्ताव यहां है।

वास्तविक आवृत्तियों को स्टोर न करें, उन्हें डिकोडिंग के लिए आवश्यक नहीं है। हालांकि, आपको वास्तविक पेड़ की आवश्यकता है।

तो प्रत्येक नोड के लिए, रूट से शुरू:

  1. यदि पत्ता-नोड: आउटपुट 1-बिट + एन-बिट चरित्र / बाइट
  2. यदि पत्ता-नोड नहीं, आउटपुट 0-बिट। फिर उसी तरह से दोनों बच्चे नोड्स (पहले दाएं बाएं) को एन्कोड करें

पढ़ने के लिए, यह करें:

  1. थोड़ा पढ़ें। यदि 1, तो एन-बिट चरित्र / बाइट पढ़ें, इसके बिना कोई नोड के साथ नया नोड वापस करें
  2. यदि बिट 0 था, तो बाएं और दाएं बच्चे-नोड्स को उसी तरह से डीकोड करें, और उन बच्चों के साथ उनके चारों ओर नया नोड वापस करें, लेकिन कोई मूल्य नहीं

एक पत्ता-नोड मूल रूप से कोई नोड होता है जिसमें बच्चे नहीं होते हैं।

इस दृष्टिकोण के साथ, आप इसे लिखने से पहले अपने आउटपुट के सटीक आकार की गणना कर सकते हैं, यह पता लगाने के लिए कि क्या लाभ प्रयास को उचित ठहराने के लिए पर्याप्त हैं। यह मानता है कि आपके पास कुंजी / मूल्य जोड़े का एक शब्दकोश है जिसमें प्रत्येक वर्ण की आवृत्ति होती है, जहां आवृत्ति घटनाओं की वास्तविक संख्या होती है।

गणना के लिए छद्म कोड:

Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))

वृक्ष-आकार की गणना पत्ती और गैर-पत्ती नोड्स को खाते में ले जाती है, और वहां वर्णों की तुलना में एक कम इनलाइन नोड होता है।

SIZE_OF_ONE_CHARACTER बिट्स की संख्या होगी, और वे दोनों आपको बिट्स की कुल संख्या देंगे जो पेड़ के लिए मेरा दृष्टिकोण + एन्कोडेड डेटा पर कब्जा करेगा।

पथ (सी) एक समारोह / सारणी है जो पेड़ में उस चरित्र से रूट तक बिट-पथ उत्पन्न करेगी।

ऐसा करने के लिए यहां एक सी # दिखने वाला छद्म कोड है, जो मानता है कि एक चरित्र सिर्फ एक साधारण बाइट है।

void EncodeNode(Node node, BitWriter writer)
{
    if (node.IsLeafNode)
    {
        writer.WriteBit(1);
        writer.WriteByte(node.Value);
    }
    else
    {
        writer.WriteBit(0);
        EncodeNode(node.LeftChild, writer);
        EncodeNode(node.Right, writer);
    }
}

इसे वापस पढ़ने के लिए:

Node ReadNode(BitReader reader)
{
    if (reader.ReadBit() == 1)
    {
        return new Node(reader.ReadByte(), null, null);
    }
    else
    {
        Node leftChild = ReadNode(reader);
        Node rightChild = ReadNode(reader);
        return new Node(0, leftChild, rightChild);
    }
}

एक उदाहरण (सरलीकृत, गुण गुण, आदि) नोड कार्यान्वयन:

public class Node
{
    public Byte Value;
    public Node LeftChild;
    public Node RightChild;

    public Node(Byte value, Node leftChild, Node rightChild)
    {
        Value = value;
        LeftChild = leftChild;
        RightChild = rightChild;
    }

    public Boolean IsLeafNode
    {
        get
        {
            return LeftChild == null;
        }
    }
}

यहां एक विशिष्ट उदाहरण से एक नमूना आउटपुट है।

इनपुट: AAAAAABCCCCCCDDEEEEE

आवृत्तियों:

  • ए: 6
  • बी: 1
  • सी: 6
  • डी: 2
  • ई: 5

प्रत्येक चरित्र केवल 8 बिट्स है, इसलिए पेड़ का आकार 10 * 5 - 1 = 49 बिट्स होगा।

पेड़ इस तरह दिख सकता है:

      20
  ----------
  |        8
  |     -------
 12     |     3
-----   |   -----
A   C   E   B   D
6   6   5   1   2

तो प्रत्येक चरित्र के पथ निम्नानुसार हैं (0 शेष है, 1 सही है):

  • ए: 00
  • बी: 110
  • सी: 01
  • डी: 111
  • ई: 10

तो आउटपुट आकार की गणना करने के लिए:

  • ए: 6 घटनाएं * 2 बिट्स = 12 बिट्स
  • बी: 1 घटना * 3 बिट्स = 3 बिट्स
  • सी: 6 घटनाएं * 2 बिट्स = 12 बिट्स
  • डी: 2 घटनाएं * 3 बिट्स = 6 बिट्स
  • ई: 5 घटनाएं * 2 बिट्स = 10 बिट्स

एन्कोडेड बाइट्स का योग 12 + 3 + 12 + 6 + 10 = 43 बिट्स है

पेड़ से 49 बिट्स में जोड़ें, और आउटपुट 92 बिट्स, या 12 बाइट्स होगा। मूल 20 वर्णों को अनएन्कोड करने के लिए आवश्यक 20 * 8 बाइट्स की तुलना करें, आप 8 बाइट्स बचाएंगे।

पेड़ सहित अंतिम आउटपुट, निम्नानुसार है। धारा (एई) में प्रत्येक चरित्र 8 बिट्स के रूप में एन्कोड किया गया है, जबकि 0 और 1 बस एक बिट है। धारा में जगह सिर्फ पेड़ को एन्कोड किए गए डेटा से अलग करने के लिए है और अंतिम आउटपुट में कोई जगह नहीं लेती है।

001A1C01E01B1D 0000000000001100101010101011111111010101010

कंक्रीट उदाहरण के लिए आपके पास टिप्पणियां हैं, एएबीसीडीईएफ, आपको यह मिल जाएगा:

इनपुट: एएबीसीडीईएफ

आवृत्तियों:

  • ए: 2
  • बी: 1
  • सी: 1
  • डी: 1
  • ई: 1
  • एफ: 1

ट्री:

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

पथ:

  • ए: 00
  • बी: 01
  • सी: 100
  • डी: 101
  • ई: 110
  • एफ: 111

वृक्ष: 001 ए 1 बी 001 सी 1 डी 01 ई 1 एफ = 59 बिट्स
डेटा: 000001100101110111 = 18 बिट्स
योग: 5 9 + 18 = 77 बिट्स = 10 बाइट्स

चूंकि मूल 8 बिट्स = 56 के 7 वर्ण थे, इसलिए आपके पास डेटा के ऐसे छोटे टुकड़ों के बहुत अधिक ओवरहेड होंगे।


एक बेहतर दृष्टिकोण

वृक्ष: 7 ------------- | 4 | --------- 3 2 2 ----- ----- ----- एबीसीडीईएफ 2 1 1 1 1 1: आवृत्तियों 2 2 3 3 3 3: वृक्ष गहराई (एन्कोडिंग बिट्स)

अब बस इस तालिका को प्राप्त करें: कोड की गहराई संख्या

 2   2 [A B]
 3   4 [C D E F]

आपको एक ही बाइनरी पेड़ का उपयोग करने की आवश्यकता नहीं है, केवल गणना की गई पेड़ गहराई यानी एन्कोडिंग बिट्स की संख्या रखें। तो बस पेड़ की गहराई द्वारा आदेशित असम्पीडित मूल्यों [एबीसीडीईएफ] के वेक्टर को रखें, इस अलग वेक्टर के बजाय सापेक्ष अनुक्रमणिका का उपयोग करें। अब प्रत्येक गहराई के लिए गठबंधन बिट पैटर्न को फिर से बनाएं:

कोड की गहराई संख्या

 2   2 [00x 01x]
 3   4 [100 101 110 111]

आप तुरंत क्या देखते हैं कि प्रत्येक पंक्ति में केवल पहला बिट पैटर्न महत्वपूर्ण है। आपको निम्न लुकअप टेबल मिलती है:

first pattern depth first index
------------- ----- -----------
000           2     0
100           3     2

इस एलयूटी का आकार बहुत छोटा है (भले ही आपका हफमैन कोड 32-बिट लंबा हो, इसमें केवल 32 पंक्तियां होंगी), और वास्तव में पहला पैटर्न हमेशा शून्य होता है, पैटर्न की बाइनरी खोज करते समय आप इसे पूरी तरह से अनदेखा कर सकते हैं इसमें (यहां केवल 1 पैटर्न की तुलना करने की आवश्यकता होगी, यह जानने के लिए कि क्या बिट गहराई 2 या 3 है और वे पहले इंडेक्स प्राप्त करें जिस पर वेक्टर में संबंधित डेटा संग्रहीत किया जाता है)। हमारे उदाहरण में आपको 31 मूल्यों की खोज स्थान में इनपुट पैटर्न की तेज़ बाइनरी खोज करने की आवश्यकता होगी, यानी अधिकतम 5 पूर्णांक तुलना। इन 31 तुलनात्मक दिनचर्या को 31 कोडों में अनुकूलित किया जा सकता है ताकि सभी लूपों से बचने के लिए और पूर्णांक बाइनरी लुकअप पेड़ उगते समय राज्यों का प्रबंधन किया जा सके। यह सभी तालिका छोटी निश्चित लंबाई में फिट बैठती है (एलयूटी को केवल 32 बिट्स से अधिक नहीं होने वाले हफमैन कोड के लिए 31 पंक्तियों की आवश्यकता होती है, और उपरोक्त 2 अन्य कॉलम अधिकतम 32 पंक्तियों को भर देंगे)।

दूसरे शब्दों में ऊपर दिए गए LUT को 32 बिट आकार के 31 इंच की आवश्यकता होती है, प्रत्येक बिट गहराई मानों को स्टोर करने के लिए 32 बाइट्स: लेकिन गहराई कॉलम (और गहराई 1 के लिए पहली पंक्ति) को लागू करके आप इसे से बच सकते हैं:

first pattern (depth) first index
------------- ------- -----------
(000)          (1)    (0)
 000           (2)     0
 100           (3)     2
 000           (4)     6
 000           (5)     6
 ...           ...     ...
 000           (32)    6

तो आपके LUT में [000, 100, 000 (30 टाइम्स)] शामिल है। इसमें खोज करने के लिए आपको उस स्थिति को ढूंढना चाहिए जहां इनपुट बिट्स पैटर्न दो पैटर्न के बीच हैं: यह इस LUT में अगली स्थिति में पैटर्न से कम होना चाहिए, लेकिन वर्तमान स्थिति में पैटर्न से अधिक या उसके बराबर होना चाहिए (यदि दोनों स्थितियां एक ही पैटर्न है, वर्तमान पंक्ति मेल नहीं खाएगी, इनपुट पैटर्न नीचे फिट बैठता है)। फिर आप विभाजित और जीत लेंगे, और अधिकतर 5 परीक्षणों का उपयोग करेंगे (द्विआधारी खोज के लिए एक कोड की आवश्यकता होती है जिसमें 5 एम्बेडेड होते हैं, फिर / फिर / नेस्टेड स्तर होते हैं, इसमें 32 शाखाएं होती हैं, शाखा पहुंचती है जो सीधे गहराई से संकेत देती है जो नहीं संग्रहीत करने की आवश्यकता है; आप पहली अनुक्रमणिका को वापस करने के लिए दूसरी तालिका में एक एकल सीधे अनुक्रमित लुकअप करते हैं; आप डीकोडेड मानों के वेक्टर में अंतिम सूचकांक को जोड़ते हैं)।

एक बार जब आप लुकअप टेबल (पहली कॉलम में खोज) में स्थिति प्राप्त कर लेते हैं, तो आपके पास तुरंत इनपुट से लेने के लिए बिट्स की संख्या होती है और फिर वेक्टर को स्टार्ट इंडेक्स होता है। पहली सूचकांक को घटाने के बाद मूल बिटमैस्किंग द्वारा, आपको प्राप्त की गई गहराई को सीधे समायोजित सूचकांक स्थिति प्राप्त करने के लिए उपयोग किया जा सकता है।

संक्षेप में: कभी भी बाइनरी पेड़ को स्टोर न करें, और आपको दृष्टिकोण को निष्पादित करने के लिए किसी भी लूप की आवश्यकता नहीं है, जिसमें 31 पैटर्न की एक तालिका में निश्चित पदों पर पैटर्न की तुलना करने के लिए केवल 5 घोंसले की आवश्यकता होती है, और 31 इंच की एक तालिका जिसमें प्रारंभ ऑफसेट होता है डीकोडेड मानों के वेक्टर (नेस्टेड की पहली शाखा में / फिर / अन्य परीक्षणों में, वेक्टर के लिए प्रारंभ ऑफसेट को इंगित किया जाता है, यह हमेशा शून्य होता है; यह भी सबसे लगातार शाखा है जिसे इसे सबसे कम कोड से मेल खाता है जो सबसे लगातार डीकोडेड मानों के लिए है)।


यदि आपके पेड़ की पीढ़ी पर पर्याप्त नियंत्रण है, तो आप इसे एक कैनोलिक पेड़ कर सकते हैं (वैसे ही DEFLATE करता है, उदाहरण के लिए), जिसका मूल रूप से मतलब है कि आप पेड़ के निर्माण के दौरान किसी अस्पष्ट परिस्थितियों को हल करने के लिए नियम बनाते हैं। फिर, डिफलेट की तरह, आपको वास्तव में स्टोर करना होगा, प्रत्येक चरित्र के लिए कोड की लंबाई है।

यही है, अगर आपके पास ऊपर वर्णित लास / कोड लास था:

  • ए: 00
  • बी: 110
  • सी: 01
  • डी: 111
  • ई: 10

फिर आप उन्हें स्टोर कर सकते हैं: 2, 3, 2, 3, 2

और यह वास्तव में हफमैन टेबल को पुन: उत्पन्न करने के लिए पर्याप्त जानकारी है, मानते हुए कि आप हमेशा एक ही चरित्र सेट का उपयोग कर रहे हैं - कहें, ASCII। (जिसका अर्थ है कि आप अक्षरों को छोड़ नहीं सकते - आपको प्रत्येक के लिए कोड की लंबाई सूचीबद्ध करनी होगी, भले ही यह शून्य हो।)

यदि आप बिट लम्बाई (कहते हैं, 7 बिट्स) पर भी सीमा डालते हैं, तो आप इन बाइनरी स्ट्रिंग्स का उपयोग करके इन नंबरों में से प्रत्येक को स्टोर कर सकते हैं। तो 2,3,2,3,2 010 011 010 011 010 बनता है - जो 2 बाइट्स में फिट बैठता है।

यदि आप वास्तव में पागल होना चाहते हैं, तो आप जो कर सकते हैं वह कर सकते हैं, और इन कोडों की लंबाई की एक और हफमैन तालिका बना सकते हैं, और इसकी कोड लंबाई पहले से स्टोर कर सकते हैं। खासकर जब से वे चीजों को कम करने के लिए "पंक्ति में शून्य बार बार डालें" के लिए अतिरिक्त कोड जोड़ते हैं।

डीएफएलएटी के लिए आरएफसी बहुत बुरा नहीं है, अगर आप पहले से ही हफमैन कोडिंग से परिचित हैं: http://www.ietf.org/rfc/rfc1951.txt


शाखाएं 0 पत्तियां हैं 1. अपने "आकार" को पाने के लिए पहले पेड़ की गहराई को पार करें

e.g. the shape for this tree

0 - 0 - 1 (A)
|    \- 1 (E)
  \
    0 - 1 (C)
     \- 0 - 1 (B)
         \- 1 (D)

would be 001101011

उसी गहराई में वर्णों के लिए बिट्स के साथ इसका पालन करें पहले ऑर्डर एईसीबीडी (जब आपको पढ़ना होगा तो पेड़ के आकार से कितने पात्र उम्मीद कर सकते हैं)। फिर संदेश के लिए कोड आउटपुट। फिर आपके पास बिट्स की एक लंबी श्रृंखला है जिसे आप आउटपुट के लिए वर्णों में विभाजित कर सकते हैं।

यदि आप इसे छेड़छाड़ कर रहे हैं, तो आप परीक्षण कर सकते हैं कि अगले चक के लिए पेड़ को संग्रहित करना उतना ही कुशल है जितना कि पिछले खंड के लिए पेड़ का पुन: उपयोग करना और पेड़ का आकार "1" होना चाहिए जो कि पिछले खंड से पेड़ का पुन: उपयोग करने के लिए सूचक है ।





huffman-code