> bwt | ट्रांसफॉर्म | कंप्रेस <
// Burrows-Wheeler Transform - संपीड़न को बेहतर बनाने के लिए रिवर्सिबल टेक्स्ट ट्रांसफॉर्मेशन
>> विशेषताएँ
पूरी तरह रिवर्सिबल
लॉसलेस ट्रांसफॉर्म जो मूल टेक्स्ट को बिल्कुल पुनर्निर्मित कर सकता है.
करेक्टर क्लस्टरिंग
मिलते-जुलते अक्षरों को एक साथ लाकर बाद की एन्कोडिंग स्टेज में बेहतर संपीड़न देता है.
bzip2 का आधार
bzip2 शैली के कई कम्प्रेशन एल्गोरिदम में इस्तेमाल होने वाला मूल ट्रांसफॉर्म.
>> तकनीकी जानकारी
BWT कैसे काम करता है
Burrows-Wheeler Transform इनपुट स्ट्रिंग की सभी साइक्लिक रोटेशन बनाता है, उन्हें लेक्सिकोग्राफिक रूप से सॉर्ट करता है और सॉर्ट की हुई मैट्रिक्स का आखिरी कॉलम तथा मूल स्ट्रिंग का इंडेक्स लौटाता है. इससे समान अक्षर एक साथ जुड़ जाते हैं और आउटपुट को RLE, Move-to-Front या अन्य एंट्रॉपी कोडर से बहुत अच्छी तरह कंप्रेस किया जा सकता है.
BWT उदाहरण
Input: "banana$" Rotations: 0: banana$ 1: anana$b 2: nana$ba 3: ana$ban 4: na$bana 5: a$banan 6: $banana Sorted: 0: $banana 1: a$banan 2: ana$ban 3: anana$b 4: banana$ 5: na$bana 6: nana$ba Last column: annb$aa Original index: 4 Output: annb$aa|4
BWT क्यों उपयोग करें
- डेटा की कम्प्रेसिबिलिटी बढ़ाता है
- पूरी तरह रिवर्सिबल और लॉसलेस
- मिलते-जुलते कॉन्टेक्स्ट को समूह में रखता है
- bzip2 कम्प्रेशन एल्गोरिदम की नींव
- अन्य एन्कोडिंग स्टेप से पहले प्रभावी प्री-प्रोसेसिंग
>> अक्सर पूछे जाने वाले प्रश्न
Burrows-Wheeler Transform क्या है?
Burrows-Wheeler Transform (BWT) एक रिवर्सिबल एल्गोरिदम है जो कैरेक्टर स्ट्रिंग को इस तरह पुनर्व्यवस्थित करता है कि समान प्रतीक लंबे रन में आ जाएँ. इसे 1994 में Michael Burrows और David Wheeler ने प्रस्तावित किया था और यह bzip2 जैसे कम्प्रेसर में बेहतर कम्प्रेशन रेशियो पाने के लिए प्री-प्रोसेसिंग स्टेप के रूप में उपयोग होता है.
BWT कम्प्रेशन को कैसे बेहतर बनाता है?
BWT उन अक्षरों को समूहित करता है जो समान संदर्भों में आते हैं, जिससे आउटपुट में एक ही प्रतीक की कई आवृत्तियाँ पास-पास आ जाती हैं. ऐसी श्रृंखलाएँ रन-लेंथ एन्कोडिंग, Move-to-Front और Huffman जैसे एंट्रॉपी कोडर के साथ बहुत अच्छी तरह से कंप्रेस होती हैं.
EOF मार्कर क्या होता है?
EOF (End Of File) मार्कर, आमतौर पर '$' या कोई विशिष्ट कैरेक्टर, यह सुनिश्चित करता है कि सभी रोटेशन अलग-अलग हों और मूल स्ट्रिंग की स्थिति पहचानी जा सके. इसके बिना कुछ स्ट्रिंग्स की यूनिक प्रस्तुति संभव नहीं होती. इनवर्स ट्रांसफॉर्म के दौरान EOF मार्कर हटा दिया जाता है.
क्या BWT खुद एक पूरा कम्प्रेशन एल्गोरिदम है?
नहीं. BWT स्वयं में कम्प्रेशन एल्गोरिदम नहीं है बल्कि एक ट्रांसफॉर्म है जो डेटा को अधिक कम्प्रेसिबल बनाता है. इसे आम तौर पर Move-to-Front, RLE और Huffman कोडिंग के साथ bzip2 जैसे स्कीम में प्रयोग किया जाता है.