से 16 बाइट्स

Question

में कम्प्रेस 21 अक्षरांकीय अक्षर मैं डेटा के 21 बाइट्स जो विशिष्ट रूप से एक व्यापार की पहचान करता है लेने के लिए और एक 16 बाइट char सरणी में संग्रहीत करने की कोशिश कर रहा हूँ। मुझे इसके लिए सही एल्गोरिदम के साथ आने में परेशानी हो रही है।

व्यापार आईडी जो मैं संपीड़ित करने के लिए कोशिश कर रहा हूँ 2 क्षेत्रों के होते हैं:

1. 18 अक्षरांकीय अक्षर ASCII वर्ण 0x20 0x7E को, समावेशी से मिलकर। (32-126)
2. एक 3-चरित्र सांख्यिक स्ट्रिंग "000" को "999"

तो एक सी ++ वर्ग है कि इस डेटा धरना होगा इस तरह दिखता है:

class ID 
{ 
public: 
    char trade_num_[18]; 
    char broker_[3]; 
}; 

इस डेटा की जरूरत है एक 16- char डेटा संरचना है, जो इस तरह दिखता में संग्रहीत करने के लिए:

class Compressed 
{ 
public: 
    char sku_[16];  
}; 

मैं इस तथ्य का लाभ लेने की कोशिश की है कि +०१२३१११७२५२८ में पात्रों के बाद सेकेवल 0-127 हैं प्रत्येक चरित्र में 1 अप्रयुक्त बिट था। इसी प्रकार, बाइनरी में 99 9 1111100111 है, जो केवल 10 बिट्स है - 2 बिट बाइट शब्द से कम 6 बिट्स। लेकिन जब मैं यह काम करता हूं कि मैं इसे कितना निचोड़ सकता हूं, सबसे छोटा मैं इसे 17 बाइट बना सकता हूं; एक बाइट बहुत बड़ा है।

कोई भी विचार?

वैसे, trade_num_ एक मिथ्या नाम है। इसमें अक्षरों और अन्य पात्र हो सकते हैं। यही कहता है कि स्पेक कहता है।

संपादित करें: भ्रम के लिए खेद है। trade_num_ फ़ील्ड वास्तव में 18 बाइट्स है और नहीं 16. 16. इस धागे को पोस्ट करने के बाद मेरा इंटरनेट कनेक्शन मर गया और मैं अभी तक इस धागे पर वापस नहीं जा सका।

EDIT2: मुझे लगता है कि यह डाटासेट के बारे में एक धारणा बनाने के लिए सुरक्षित है। Trade_num_ फ़ील्ड के लिए, हम मान सकते हैं कि गैर-प्रिंट करने योग्य ASCII वर्ण 0-31 मौजूद नहीं होंगे। ASCII कोड 127 या 126 (~) नहीं होगा। अन्य सभी उपस्थित हो सकते हैं, ऊपरी और निचले केस अक्षरों, संख्याओं और विराम चिह्नों सहित। यह सेट में कुल 94 वर्ण छोड़ देता है जो trade_num_ शामिल होंगे, ASCII कोड 32 से 125, समावेशी।

Answer 1

आप रेंज 0 18 कैरेक्टर है - 127 और सीमा 0 में एक नंबर - 999 और कॉम्पैक्ट इस जितना संभव हो उतना तो यह 17 बाइट्स की आवश्यकता होगी।

>>> math.log(128**18 * 1000, 256) 
16.995723035582763 

आप इस तथ्य का लाभ उठाने में सक्षम हो सकते हैं कि कुछ पात्रों का अधिकतर उपयोग नहीं किया जाता है। विशेष रूप से यह असंभव है कि मूल्य 32 के नीचे कोई भी वर्ण हैं, और 127 का शायद उपयोग नहीं किया जाता है। यदि आप एक और अप्रयुक्त चरित्र पा सकते हैं ताकि आप पहले वर्णों को बेस 94 में परिवर्तित कर सकें और फिर उन्हें जितना संभव हो सके बाइट्स में पैक कर सकें।

>>> math.log(94**18 * 1000, 256) 
15.993547951857446 

यह सिर्फ 16 बाइट्स में फिट बैठता है!

---

उदाहरण कोड

यहां कुछ उदाहरण पायथन में लिखा है (लेकिन एक बहुत ही जरूरी शैली में लिखा इतना है कि यह आसानी से गैर अजगर प्रोग्रामर द्वारा समझा जा सकता है) कोड है। मुझे लगता है कि इनपुट में कोई tildes (~) नहीं हैं। यदि स्ट्रिंग को एन्कोड करने से पहले आपको उन्हें किसी अन्य चरित्र के साथ प्रतिस्थापित करना चाहिए।

def encodeChar(c): 
    return ord(c) - 32 

def encode(s, n): 
    t = 0 
    for c in s: 
     t = t * 94 + encodeChar(c) 
    t = t * 1000 + n 

    r = [] 
    for i in range(16): 
     r.append(int(t % 256)) 
     t /= 256 

    return r 

print encode('     ', 0) # smallest possible value 
print encode('abcdefghijklmnopqr', 123) 
print encode('}}}}}}}}}}}}}}}}}}', 999) # largest possible value 

आउटपुट:

[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] 
[ 59, 118, 192, 166, 108, 50, 131, 135, 174, 93, 87, 215, 177, 56, 170, 172] 
[255, 255, 159, 243, 182, 100, 36, 102, 214, 109, 171, 77, 211, 183, 0, 247] 

इस एल्गोरिथ्म पायथन के बहुत बड़ी संख्या को संभालने की क्षमता का उपयोग करता है। इस कोड को सी ++ में बदलने के लिए आप एक बड़ी पूर्णांक लाइब्रेरी का उपयोग कर सकते हैं।

आपको निश्चित रूप से समकक्ष डिकोडिंग फ़ंक्शन की आवश्यकता होगी, सिद्धांत समान है - संचालन रिवर्स ऑर्डर में किया जाता है।

Answer 2

जो बनाता है (18 * 7 + 10) = 136 बिट्स, या 17 बाइट्स। आपने लिखा trade_num अल्फान्यूमेरिक है? यदि इसका मतलब सामान्य [ए-जेए-जेड -9_] वर्णों का सेट है, तो आपके पास प्रति चरित्र केवल 6 बिट होंगे, पूरी चीज के लिए (18 * 6 + 10) = 118 बिट = 15 बाइट की आवश्यकता होगी।

मान लिया जाये कि 8 बिट = 1 बाइट

या, दूसरी दिशा से आ रही: 118 देखते हैं आप भंडारण के लिए 128 बिट है, तो आप की जरूरत है ~ संख्या भाग के लिए 10 बिट, तो trade_num के लिए छोड़ दिया है। 18 अक्षरों का अर्थ है 118/18 = 6.555 बिट्स प्रति वर्ण, इसका मतलब है कि आपके पास केवल 2 6.555 = 94 विभिन्न वर्णों को एन्कोड करने की जगह हो सकती है ** जब तक ट्रेड_नम में एक छिपी संरचना नहीं है जिसे हम अधिक बिट्स बचाने के लिए शोषण कर सकते हैं।

Answer 3

यदि इसमें केवल अक्षर हो सकते हैं, तो आपके पास प्रति चरित्र 64 से कम संभावनाएं हैं (26 ऊपरी मामला, 26 निचला मामला, आपको स्पेस, टर्मिनेटर, अंडरस्कोर आदि के लिए 12 छोड़कर)। प्रति चरित्र 6 बिट्स के साथ, आपको वहां जाना चाहिए - 15 वर्णों में। मान लीजिए कि आप विशेष पात्रों का समर्थन नहीं करते हैं।

Answer 4

आप इसे ~~ 15bytes (14 बाइट्स और 6 बिट्स) में कर सकते हैं।

trace_num_ से प्रत्येक वर्ण के लिए यदि आप 7 बिट्स में एएससीआई को सहेजना चाहते हैं तो आप 1 बिट बचा सकते हैं।

• तो फिर तुम 2 नि: शुल्क बाइट्स और 2 बिट्स है, तो आप होना आवश्यक है 5.

संख्या में जानकारी प्राप्त करते हैं, प्रत्येक चार दस मूल्यों (0 से 9 तक) से एक हो सकता है। फिर आपके पास इस चरित्र को सहेजने के लिए 4 बिट्स होनी चाहिए, ताकि आपके पास 1 बाइट और 4 बिट्स हो सकें, तो आप इसका आधा हिस्सा बचा सकते हैं।

• अब आप 3 मुक्त बाइट्स और 6 बिट, है आप होना आवश्यक है 5.

आप उपयोग करना केवल qwertyuioplkjhgfdsazxcvbnmQWERTYUIOPLKJHGFDSAZXCVBNM1234567890[] आप 6 बिट में प्रत्येक चार को बचा सकता है चाहते हैं। फिर आपके पास अगले 2 बाइट्स और 2 बिट्स हैं।

• अब आप 6 बाइट्स छोड़ दिया है, और अपने स्ट्रिंग 15 बाइट्स + nulltermination = 16bytes में बचा सकता है।

और यदि आप अपना नंबर 10 बाइट्स पर पूर्णांक में सहेजते हैं। आप इसे 14 बाइट्स और 6 बिट्स में फिट कर सकते हैं।

Answer 5

कुंजी प्रश्न हैं:

वहाँ अपनी पोस्ट में कुछ विरोधाभास व्यापार संख्या 16 या 18 वर्ण है कि क्या दिखाई देता है। आपको इसे साफ़ करने की ज़रूरत है। आप कहते हैं कि कुल 21 में से 16 + 3 है। :-(

आप कहते हैं कि व्यापार संख्या वर्ण 0x00-0x7f श्रेणी में हैं। क्या वे वास्तव में टैब, नई लाइन, नियंत्रण-सी, आदि सहित उस श्रेणी में कोई चरित्र हो सकते हैं? या वे प्रिंट करने योग्य पात्रों तक सीमित हैं ?, या शायद करने के लिए अक्षर या अंक

, उत्पादन 16 बाइट्स मुद्रण योग्य पात्रों होना जरूरी है या यह मूल रूप से एक द्विआधारी संख्या है

संपादित करें, मूल पोस्ट के अपडेट के बाद:

उस मामले में, अगर आउटपुट चरित्र सेट में कोई भी चरित्र हो सकता है, तो यह संभव है। अगर यह केवल प्रिंट करने योग्य वर्ण हो सकता है, तो यह नहीं है।

गणितीय संभावना का प्रदर्शन सरल है। 18 वर्णों में से प्रत्येक के लिए 94 संभावित मान हैं, और प्रत्येक 3 के लिए 10 संभावित मान हैं। संभावित संयोजनों की कुल संख्या = 94^18 * 10^3 ~ = 3.28E35। इसके लिए 128 बिट्स की आवश्यकता है। 2^127 ~ = 1.70e38, जो बहुत छोटा है, जबकि 2^128 ~ = 3.40e38, जो काफी बड़ा है। 128 बिट्स 16 बाइट्स हैं, इसलिए अगर हम हर संभव बिट संयोजन का उपयोग कर सकते हैं तो यह मुश्किल से फिट होगा।

तंग फिट को देखते हुए, मुझे लगता है कि सबसे व्यावहारिक तरीका मूल्य उत्पन्न करने के लिए एक डबल लंबे संख्या के रूप में यह के बारे में सोच, और उसके बाद हर संभव इनपुट के लिए एक अनूठा पूर्णांक उत्पन्न करने के लिए एक एल्गोरिथ्म के माध्यम से इनपुट को चलाने के लिए है।

संकल्पनात्मक रूप से, तो आइए कल्पना करें कि हमारे पास "विशाल पूर्णांक" डेटा प्रकार था जो 16 बाइट लंबा है।

huge out; 
for (int p=0;p<18;++p) 
{ 
    out=out*94+tradenum[p]-32; 
} 
for (int p=0;p<3;++p) 
{ 
    out=out*10+broker[p]-'0'; 
} 

// Convert output to char[16] 
unsigned char[16] out16; 
for (int p=15;p>=0;--p) 
{ 
    out16[p]=huge&0xff; 
    huge=huge>>8; 
} 

return out16; 

बेशक

हम सी में एक "बड़ा" डेटा प्रकार आप शुद्ध सी या सी ++ का उपयोग कर रहे नहीं है: एल्गोरिथ्म कुछ इस तरह हो सकता है? सी ++ में कोई बड़ी संख्या में बड़ी संख्या नहीं है? क्षमा करें, मैंने थोड़ी देर में सी ++ नहीं किया है। यदि नहीं, तो हम एक विशाल लागू करने के लिए आसानी से एक छोटी पुस्तकालय बना सकते हैं।

Answer 6

3-वर्ण संख्यात्मक स्ट्रिंग के लिए पहले 10 बिट्स का उपयोग करें (बिट्स को एन्कोड करें जैसे कि वे एक संख्या का प्रतिनिधित्व करते हैं और फिर डीकोडिंग के दौरान उपयुक्त शून्य के साथ पैड)।

ठीक है, यह आपको स्टोर करने के लिए 118 बिट्स और 16 अल्फान्यूमेरिक वर्णों के साथ छोड़ देता है।

0x00 से 0x7F (यदि आप समावेशी हैं) में प्रतिनिधित्व करने के लिए 128 संभावित वर्ण शामिल हैं। इसका मतलब है कि प्रत्येक चरित्र को 7 बिट्स के संयोजन से पहचाना जा सकता है। प्रत्येक संख्या मैपिंग इंडेक्स के साथ आओ जो उन 7 बिट्स वास्तविक चरित्र को प्रदर्शित कर सकते हैं। इस तरह से अपने 16 "अल्फान्यूमेरिक" वर्णों का प्रतिनिधित्व करने के लिए, आपको कुल 112 बिट्स की आवश्यकता है।

अब हमारे पास 122 बिट्स (या 15.25 बाइट्स) हैं जो हमारे डेटा का प्रतिनिधित्व करते हैं। शेष अप्रयुक्त बिट्स को भरने के लिए एक ईस्टर अंडे जोड़ें और आपके पास 16 वर्ण सरणी है।

Answer 7

यह ऐसा कुछ है जो काम करना चाहिए, मान लीजिए कि आपको केवल allowedchars से वर्णों की आवश्यकता है, और वहां लगभग 94 वर्ण हैं। यह अजगर है, लेकिन यह फैंसी शॉर्टकट्स का उपयोग न करने की कोशिश कर रहा है - ताकि आप इसे अपनी गंतव्य भाषा में आसानी से अनुवाद कर सकें। यह मानता है कि number चर में 2 ** 128 तक पूर्णांक हो सकते हैं - सी ++ में आपको किसी प्रकार की बड़ी संख्या कक्षा का उपयोग करना चाहिए।

allowedchars=' !"#$%&\'()*+,-./:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}' 
alphabase = len(allowedchars) 

def compress(code): 
    alphanumeric = code[0:18] 
    number = int(code[18:21]) 

    for character in alphanumeric: 
     # find returns index of character on the allowedchars list 
     number = alphabase*number + allowedchars.find(character) 

    compressed = '' 
    for i in xrange(16): 
     compressed += chr(number % 256) 
     number = number/256 

    return compressed 

def decompress(compressed): 
    number = 0 

    for byte in reversed(compressed): 
     number = 256*number + ord(byte) 

    alphanumeric = '' 
    for i in xrange(18): 
     alphanumeric = allowedchars[number % alphabase] + alphanumeric 
     number = number/alphabase 

    # make a string padded with zeros 
    number = '%03d' % number 

    return alphanumeric + number 

Answer 8

अंतरिक्ष (0x20) और टिल्ड (0x7E) के बीच वर्ण हैं। (अन्य उत्तरों में 9 4 ऑफ-बाय-1 त्रुटि से पीड़ित हैं)।

इसलिए अलग आईडी की संख्या 95 × 1000 है = 3,97 ।

लेकिन उस संकुचित संरचना केवल पकड़ कर सकते हैं (2) = 3,40 विशिष्ट मान।

इसलिए यह, कि संरचना से सभी आईडी प्रतिनिधित्व करने के लिए असंभव है जब तक:

• वहाँ trade_num_ की ≥15 अंकों में 1 अप्रयुक्त चरित्र, या है
• का 1 अंकों में ≥14 अप्रयुक्त वर्ण हैं trade_num_, या
• केवल ≤856 दलालों, या
• आप का उपयोग कर रहे हैं एक पीडीपी -10 जो एक 9-bit char है।