दुसरी बाईक: आम्ही युनिकोड स्ट्रिंग्स UTF-30 पेक्षा 60-8% अधिक कॉम्पॅक्ट संग्रहित करतो

जर तुम्ही विकसक असाल आणि तुम्हाला एन्कोडिंग निवडण्याचे काम येत असेल, तर युनिकोड हा नेहमीच योग्य उपाय असेल. विशिष्ट प्रतिनिधित्व पद्धत संदर्भावर अवलंबून असते, परंतु बहुतेकदा येथे एक सार्वत्रिक उत्तर देखील असते - UTF-8. यात चांगली गोष्ट अशी आहे की ते तुम्हाला खर्च न करता सर्व युनिकोड वर्ण वापरण्याची परवानगी देते खूप बहुतेक प्रकरणांमध्ये बरेच बाइट्स. खरे आहे, ज्या भाषा फक्त लॅटिन वर्णमाला पेक्षा जास्त वापरतात त्यांच्यासाठी, "जास्त नाही" किमान प्रति वर्ण दोन बाइट. प्रागैतिहासिक एन्कोडिंगकडे परत न जाता आम्ही अधिक चांगले करू शकतो जे आम्हाला फक्त 256 उपलब्ध वर्णांपर्यंत मर्यादित करते?

खाली मी या प्रश्नाचे उत्तर देण्याचा आणि तुलनेने सोपा अल्गोरिदम अंमलात आणण्याच्या माझ्या प्रयत्नाशी परिचित होण्याचा प्रस्ताव देतो जो तुम्हाला UTF-8 मधील रिडंडंसी न जोडता जगातील बहुतेक भाषांमध्ये ओळी संग्रहित करू देतो.

अस्वीकरण. मी ताबडतोब काही महत्त्वपूर्ण आरक्षणे करेन: वर्णन केलेले समाधान UTF-8 साठी सार्वत्रिक बदल म्हणून दिले जात नाही, हे केवळ प्रकरणांच्या संकुचित सूचीमध्ये योग्य आहे (खालील त्यावरील अधिक), आणि कोणत्याही परिस्थितीत ते तृतीय-पक्ष API (ज्यांना याबद्दल माहित नाही) सह संवाद साधण्यासाठी वापरले जाऊ नये. बर्‍याचदा, सामान्य उद्देश कॉम्प्रेशन अल्गोरिदम (उदाहरणार्थ, डिफ्लेट) मोठ्या प्रमाणात मजकूर डेटाच्या संक्षिप्त संचयनासाठी योग्य असतात. याव्यतिरिक्त, माझे सोल्यूशन तयार करण्याच्या प्रक्रियेत, मला युनिकोडमध्येच एक विद्यमान मानक सापडला, जो समान समस्येचे निराकरण करतो - हे काहीसे अधिक क्लिष्ट (आणि बरेचदा वाईट) आहे, परंतु तरीही ते स्वीकारलेले मानक आहे, आणि फक्त ठेवले नाही. गुडघ्यावर एकत्र. मी तुम्हाला त्याच्याबद्दलही सांगेन.

युनिकोड आणि UTF-8 बद्दल

सुरुवातीला, ते काय आहे याबद्दल काही शब्द युनिकोड и यूटीएफ-एक्सNUMएक्स.

तुम्हाला माहिती आहे की, 8-बिट एन्कोडिंग लोकप्रिय होते. त्यांच्यासह, सर्वकाही सोपे होते: 256 ते 0 पर्यंतच्या संख्येसह 255 वर्णांची संख्या केली जाऊ शकते आणि 0 ते 255 पर्यंतची संख्या स्पष्टपणे एक बाइट म्हणून दर्शविली जाऊ शकते. जर आपण अगदी सुरुवातीस परत गेलो तर, ASCII एन्कोडिंग पूर्णपणे 7 बिट्सपर्यंत मर्यादित आहे, त्यामुळे त्याच्या बाइट प्रतिनिधित्वातील सर्वात लक्षणीय बिट शून्य आहे आणि बहुतेक 8-बिट एन्कोडिंग त्याच्याशी सुसंगत आहेत (ते फक्त "वरच्या" मध्ये भिन्न आहेत. भाग, जिथे सर्वात लक्षणीय बिट एक आहे).

युनिकोड त्या एन्कोडिंगपेक्षा वेगळे कसे आहे आणि त्याच्याशी अनेक विशिष्ट प्रतिनिधित्व का आहेत - UTF-8, UTF-16 (BE आणि LE), UTF-32? चला क्रमाने क्रमवारी लावू.

मूलभूत युनिकोड मानक केवळ वर्ण (आणि काही प्रकरणांमध्ये, वर्णांचे वैयक्तिक घटक) आणि त्यांची संख्या यांच्यातील पत्रव्यवहाराचे वर्णन करते. आणि या मानकामध्ये बरेच संभाव्य संख्या आहेत - पासून 0x00 ते 0x10FFFF (1 तुकडे). जर आम्हाला अशा श्रेणीतील संख्या व्हेरिएबलमध्ये ठेवायची असेल तर आमच्यासाठी 114 किंवा 112 बाइट्स पुरेसे नाहीत. आणि आमचे प्रोसेसर तीन-बाइट नंबरसह काम करण्यासाठी फारसे डिझाइन केलेले नसल्यामुळे, आम्हाला प्रति वर्ण 1 बाइट्स वापरण्याची सक्ती केली जाईल! हे UTF-2 आहे, परंतु या "फालतूपणा" मुळे हे स्वरूप लोकप्रिय नाही.

सुदैवाने, युनिकोडमधील वर्णांचा क्रम यादृच्छिक नाही. त्यांचा संपूर्ण संच 17 मध्ये विभागलेला आहे "विमाने", त्यातील प्रत्येकामध्ये 65536 (0x10000) "कोड पॉइंट्स" येथे "कोड पॉइंट" ची संकल्पना सोपी आहे वर्ण संख्या, त्यास युनिकोडद्वारे नियुक्त केले आहे. परंतु, वर नमूद केल्याप्रमाणे, युनिकोडमध्ये केवळ वैयक्तिक वर्णच नाही तर त्यांचे घटक आणि सेवा चिन्ह देखील दिले जातात (आणि काहीवेळा काहीही संख्याशी संबंधित नसते - कदाचित काही काळासाठी, परंतु आमच्यासाठी हे इतके महत्त्वाचे नाही), म्हणून हे अधिक बरोबर आहे नेहमी विशेषत: स्वतः संख्यांच्या संख्येबद्दल बोला, चिन्हांबद्दल नाही. तथापि, खालील मध्ये, संक्षिप्ततेसाठी, मी "कोड पॉइंट" या शब्दाचा अर्थ लावत "प्रतीक" हा शब्द वापरेन.

युनिकोड विमाने. तुम्ही बघू शकता, त्यातील बहुतेक (विमान 4 ते 13) अद्याप न वापरलेले आहेत.

सर्वात उल्लेखनीय गोष्ट म्हणजे सर्व मुख्य "लगदा" शून्य समतल आहे, त्याला "म्हणतात.मूलभूत बहुभाषिक विमान". जर एखाद्या ओळीत आधुनिक भाषेतील (चिनीसह) मजकूर असेल तर, तुम्ही या विमानाच्या पलीकडे जाणार नाही. परंतु तुम्ही उर्वरित युनिकोड देखील कापून टाकू शकत नाही - उदाहरणार्थ, इमोजी मुख्यतः शेवटच्या टोकाला असतात. पुढचे विमान"पूरक बहुभाषिक समतल"(ते पासून विस्तारते 0x10000 ते 0x1FFFF). म्हणून UTF-16 असे करते: सर्व वर्ण आत येतात मूलभूत बहुभाषिक विमान, संबंधित दोन-बाइट क्रमांकासह "जसे आहे तसे" एन्कोड केलेले आहेत. तथापि, या श्रेणीतील काही संख्या विशिष्ट वर्ण दर्शवत नाहीत, परंतु असे सूचित करतात की बाइट्सच्या या जोडीनंतर आपल्याला दुसर्याचा विचार करणे आवश्यक आहे - या चार बाइट्सची मूल्ये एकत्र करून, आपल्याला एक संख्या मिळते जी कव्हर करते संपूर्ण वैध युनिकोड श्रेणी. या कल्पनेला "सरोगेट जोडपे" म्हणतात—तुम्ही कदाचित त्यांच्याबद्दल ऐकले असेल.

म्हणून UTF-16 ला दोन किंवा (अत्यंत दुर्मिळ प्रकरणांमध्ये) प्रति "कोड पॉइंट" चार बाइट्स आवश्यक आहेत. हे सर्व वेळ चार बाइट वापरण्यापेक्षा चांगले आहे, परंतु लॅटिन (आणि इतर ASCII अक्षरे) अशा प्रकारे एन्कोड केल्यावर शून्यावरील अर्धी जागा वाया घालवते. UTF-8 हे दुरुस्त करण्यासाठी डिझाइन केले आहे: ASCII पूर्वीप्रमाणे, फक्त एक बाइट व्यापते; पासून कोड 0x80 ते 0x7FF - दोन बाइट्स; पासून 0x800 ते 0xFFFF - तीन, आणि पासून 0x10000 ते 0x10FFFF - चार. एकीकडे, लॅटिन वर्णमाला चांगली झाली आहे: ASCII सह सुसंगतता परत आली आहे आणि वितरण अधिक समान रीतीने 1 ते 4 बाइट्स पर्यंत पसरले आहे. परंतु लॅटिन व्यतिरिक्त इतर वर्णमाला UTF-16 च्या तुलनेत कोणत्याही प्रकारे फायदेशीर नाहीत आणि अनेकांना आता दोन ऐवजी तीन बाइट्सची आवश्यकता आहे - दोन-बाइट रेकॉर्डद्वारे व्यापलेली श्रेणी 32 पटीने कमी झाली आहे. 0xFFFF ते 0x7FF, आणि चिनी किंवा, उदाहरणार्थ, जॉर्जियनचा त्यात समावेश नाही. सिरिलिक आणि इतर पाच अक्षरे - हुरे - भाग्यवान, प्रति वर्ण 2 बाइट.

असे का घडते? UTF-8 कॅरेक्टर कोडचे प्रतिनिधित्व कसे करते ते पाहू या:

थेट संख्या दर्शवण्यासाठी, चिन्हासह चिन्हांकित बिट येथे वापरले जातात x. हे पाहिले जाऊ शकते की दोन-बाइट रेकॉर्डमध्ये असे फक्त 11 बिट आहेत (16 पैकी). येथे अग्रगण्य बिट्समध्ये फक्त एक सहायक कार्य आहे. चार-बाइट रेकॉर्डच्या बाबतीत, 21 पैकी 32 बिट्स कोड पॉइंट नंबरसाठी वाटप केले जातात - असे दिसते की तीन बाइट्स (जे एकूण 24 बिट्स देतात) पुरेसे असतील, परंतु सर्व्हिस मार्कर खूप जास्त खातात.

हे वाईट आहे का? खरंच नाही. एकीकडे, जर आपल्याला जागेची खूप काळजी असेल, तर आमच्याकडे कॉम्प्रेशन अल्गोरिदम आहेत जे सर्व अतिरिक्त एन्ट्रॉपी आणि रिडंडंसी सहजपणे काढून टाकू शकतात. दुसरीकडे, युनिकोडचे ध्येय शक्य तितके सार्वत्रिक कोडिंग प्रदान करणे हे होते. उदाहरणार्थ, आम्ही UTF-8 मध्ये एन्कोड केलेली एक ओळ या कोडवर सोपवू शकतो जी पूर्वी फक्त ASCII सोबत काम करत होती आणि घाबरू नका की ASCII श्रेणीतील एक वर्ण दिसेल जो प्रत्यक्षात नाही (तरीही, UTF-8 मध्ये सर्व शून्य बिट पासून सुरू होणारे बाइट्स - हेच ASCII आहे). आणि जर आम्हाला एका मोठ्या स्ट्रिंगमधून एक लहान शेपूट अगदी सुरुवातीपासूनच डीकोड न करता कापायची असेल (किंवा खराब झालेल्या विभागानंतर माहितीचा काही भाग पुनर्संचयित करा), तर अक्षर कोठे सुरू होते ते ऑफसेट शोधणे आमच्यासाठी सोपे आहे (ते पुरेसे आहे. थोडा उपसर्ग असलेले बाइट्स वगळण्यासाठी 10).

मग काहीतरी नवीन शोध का?

त्याच वेळी, अधूनमधून अशी परिस्थिती असते जेव्हा डिफ्लेट सारख्या कॉम्प्रेशन अल्गोरिदम खराबपणे लागू होतात, परंतु तुम्हाला स्ट्रिंगचे कॉम्पॅक्ट स्टोरेज साध्य करायचे आहे. वैयक्तिकरित्या, इमारतीबद्दल विचार करताना मला ही समस्या आली संकुचित उपसर्ग वृक्ष अनियंत्रित भाषांमधील शब्दांसह मोठ्या शब्दकोशासाठी. एकीकडे, प्रत्येक शब्द खूपच लहान आहे, म्हणून तो संकुचित करणे अप्रभावी होईल. दुसरीकडे, मी विचारात घेतलेल्या ट्री अंमलबजावणीची रचना अशी केली गेली होती की संग्रहित स्ट्रिंगच्या प्रत्येक बाइटने एक स्वतंत्र ट्री व्हर्टेक्स तयार केला, त्यामुळे त्यांची संख्या कमी करणे खूप उपयुक्त होते. माझ्या लायब्ररीत Az.js (म्हणून pymorphy2, ज्यावर ते आधारित आहे) एक समान समस्या सहजपणे सोडविली जाऊ शकते - मध्ये पॅक केलेले स्ट्रिंग डीएडब्ल्यूजी-शब्दकोश, तेथे संग्रहित चांगले जुने CP1251. परंतु, समजण्यास सोप्याप्रमाणे, हे केवळ मर्यादित वर्णमालासाठी चांगले कार्य करते - अशा शब्दकोशात चीनी भाषेतील एक ओळ जोडली जाऊ शकत नाही.

स्वतंत्रपणे, मी अशा डेटा स्ट्रक्चरमध्ये UTF-8 वापरताना उद्भवणारी आणखी एक अप्रिय सूक्ष्मता लक्षात घेऊ इच्छितो. वरील चित्रात असे दिसून येते की जेव्हा एखादे अक्षर दोन बाइट्स म्हणून लिहिले जाते तेव्हा त्याच्या संख्येशी संबंधित बिट्स एका ओळीत येत नाहीत, परंतु बिट्सच्या जोडीने वेगळे केले जातात. 10 मध्ये: 110xxxxx 10xxxxxx. यामुळे, जेव्हा कॅरेक्टर कोडमध्ये दुसऱ्या बाइटचे खालचे 6 बिट्स ओव्हरफ्लो होतात (म्हणजे, एक संक्रमण होते 10111111 → 10000000), नंतर पहिला बाइट देखील बदलतो. असे दिसून आले की "p" अक्षर बाइट्सद्वारे दर्शविले जाते 0xD0 0xBF, आणि पुढील "r" आधीच आहे 0xD1 0x80. उपसर्ग वृक्षात, यामुळे मूळ नोडचे दोन भाग होतात - उपसर्गासाठी एक 0xD0, आणि दुसरा साठी 0xD1 (जरी संपूर्ण सिरिलिक वर्णमाला फक्त दुसऱ्या बाइटद्वारे एन्कोड केली जाऊ शकते).

मला काय मिळाले

या समस्येचा सामना करताना, मी बिट्ससह गेम खेळण्याचा सराव करण्याचा निर्णय घेतला आणि त्याच वेळी संपूर्ण युनिकोडच्या संरचनेची थोडीशी चांगली ओळख करून घ्या. परिणाम UTF-C एन्कोडिंग स्वरूप ("C" साठी संक्षिप्त), जे प्रति कोड पॉइंट 3 बाइट्सपेक्षा जास्त खर्च करत नाही आणि बर्‍याचदा तुम्हाला फक्त खर्च करण्याची परवानगी देते संपूर्ण एन्कोड केलेल्या ओळीसाठी एक अतिरिक्त बाइट. यामुळे अनेक गैर-ASCII अक्षरांवर असे एन्कोडिंग होते UTF-30 पेक्षा 60-8% अधिक कॉम्पॅक्ट.

मी फॉर्ममध्ये एन्कोडिंग आणि डीकोडिंग अल्गोरिदमच्या अंमलबजावणीची उदाहरणे सादर केली आहेत JavaScript आणि Go लायब्ररी, तुम्ही ते तुमच्या कोडमध्ये मुक्तपणे वापरू शकता. परंतु तरीही मी यावर जोर देईन की एका अर्थाने हे स्वरूप "सायकल" राहते आणि मी ते वापरण्याची शिफारस करत नाही आपल्याला त्याची गरज का आहे हे लक्षात न घेता. गंभीर "UTF-8 च्या सुधारणे" पेक्षा हा अजून एक प्रयोग आहे. तरीसुद्धा, तेथे कोड सुबकपणे, संक्षिप्तपणे, मोठ्या संख्येने टिप्पण्या आणि चाचणी कव्हरेजसह लिहिलेला आहे.

चाचणी परिणाम आणि UTF-8 सह तुलना

मी पण केले डेमो पृष्ठ, जिथे तुम्ही अल्गोरिदमच्या कार्यक्षमतेचे मूल्यांकन करू शकता आणि नंतर मी तुम्हाला त्याची तत्त्वे आणि विकास प्रक्रियेबद्दल अधिक सांगेन.

अनावश्यक बिट्स काढून टाकणे

मी अर्थातच आधार म्हणून UTF-8 घेतला. त्यात बदल करता येणारी पहिली आणि सर्वात स्पष्ट गोष्ट म्हणजे प्रत्येक बाइटमधील सर्व्हिस बिट्सची संख्या कमी करणे. उदाहरणार्थ, UTF-8 मधील पहिला बाइट नेहमी दोन्हीपैकी एकाने सुरू होतो 0, किंवा सह 11 - एक उपसर्ग 10 फक्त खालील बाइट्समध्ये आहेत. चला उपसर्ग बदलू 11 वर 1, आणि पुढील बाइट्ससाठी आम्ही उपसर्ग पूर्णपणे काढून टाकू. काय होईल?

0xxxxxxx - 1 बाइट
10xxxxxx xxxxxxxx - 2 बाइट्स
110xxxxx xxxxxxxx xxxxxxxx - 3 बाइट्स

थांबा, चार बाइट रेकॉर्ड कुठे आहे? परंतु यापुढे त्याची आवश्यकता नाही - तीन बाइट्समध्ये लिहिताना, आमच्याकडे आता 21 बिट उपलब्ध आहेत आणि हे सर्व संख्यांसाठी पुरेसे आहे. 0x10FFFF.

आम्ही येथे काय बलिदान दिले? सर्वात महत्वाची गोष्ट म्हणजे बफरमधील अनियंत्रित स्थानावरून वर्ण सीमा शोधणे. आपण एका अनियंत्रित बाइटकडे निर्देश करू शकत नाही आणि त्यातून पुढील वर्णाची सुरुवात शोधू शकत नाही. ही आमच्या स्वरूपाची मर्यादा आहे, परंतु व्यवहारात हे क्वचितच आवश्यक आहे. आम्ही सहसा अगदी सुरुवातीपासूनच बफरमधून धावू शकतो (विशेषत: जेव्हा लहान ओळींचा विचार केला जातो).

2 बाइट्ससह भाषा कव्हर करण्याची परिस्थिती देखील चांगली झाली आहे: आता दोन-बाइट स्वरूप 14 बिट्सची श्रेणी देते आणि हे कोड आहेत 0x3FFF. चिनी लोक अशुभ आहेत (त्यांची वर्ण मुख्यतः पासून 0x4E00 ते 0x9FFF), परंतु जॉर्जियन आणि इतर बर्‍याच लोकांना अधिक मजा येते - त्यांच्या भाषा देखील प्रति वर्ण 2 बाइट्समध्ये बसतात.

एन्कोडर स्थिती प्रविष्ट करा

आता स्वतःच रेषांच्या गुणधर्मांबद्दल विचार करूया. शब्दकोशात बहुतेक वेळा समान वर्णमालेतील अक्षरांमध्ये लिहिलेले शब्द असतात आणि हे इतर अनेक ग्रंथांसाठी देखील खरे आहे. हे वर्णमाला एकदा सूचित करणे चांगले होईल आणि नंतर त्यातील अक्षरांची संख्या दर्शवा. युनिकोड सारणीतील वर्णांची मांडणी आपल्याला मदत करेल का ते पाहू.

वर नमूद केल्याप्रमाणे, युनिकोडची विभागणी केली आहे विमान प्रत्येकी 65536 कोड. परंतु हा फारसा उपयुक्त विभाग नाही (आधीच म्हटल्याप्रमाणे, बहुतेकदा आपण शून्य विमानात असतो). द्वारे विभागणी अधिक मनोरंजक आहे अवरोध या श्रेणींची यापुढे निश्चित लांबी नाही आणि ती अधिक अर्थपूर्ण आहेत - नियम म्हणून, प्रत्येक समान वर्णमालातील वर्ण एकत्र करते.

बंगाली वर्णमालेतील वर्ण असलेला ब्लॉक. दुर्दैवाने, ऐतिहासिक कारणास्तव, हे फार दाट पॅकेजिंगचे उदाहरण नाही - 96 ब्लॉक कोड पॉइंट्समध्ये 128 वर्ण अव्यवस्थितपणे विखुरलेले आहेत.

ब्लॉक्सची सुरुवात आणि त्यांचे आकार नेहमी 16 च्या पटीत असतात - हे फक्त सोयीसाठी केले जाते. याव्यतिरिक्त, अनेक ब्लॉक्स 128 किंवा अगदी 256 च्या पटीत असलेल्या मूल्यांवर सुरू होतात आणि समाप्त होतात - उदाहरणार्थ, मूलभूत सिरिलिक वर्णमाला 256 बाइट्स घेते 0x0400 ते 0x04FF. हे अगदी सोयीचे आहे: जर आपण उपसर्ग एकदा सेव्ह केला 0x04, नंतर कोणतेही सिरिलिक वर्ण एका बाइटमध्ये लिहिले जाऊ शकते. खरे आहे, अशा प्रकारे आम्ही ASCII (आणि सर्वसाधारणपणे इतर कोणत्याही वर्णांकडे) परत येण्याची संधी गमावू. म्हणून आम्ही हे करतो:

1. दोन बाइट्स 10yyyyyy yxxxxxxx केवळ संख्या असलेले चिन्ह दर्शवत नाही yyyyyy yxxxxxxx, पण बदला वर्तमान वर्णमाला वर yyyyyy y0000000 (म्हणजेच कमीत कमी महत्त्वाचे वगळता सर्व बिट्स आम्हाला आठवतात 7 बिट्स);
2. एक बाइट 0xxxxxxx हे वर्तमान वर्णमाला वर्ण आहे. ते फक्त ऑफसेटमध्ये जोडणे आवश्यक आहे जे आम्हाला चरण 1 मध्ये लक्षात ठेवले होते. आम्ही वर्णमाला बदलली नसली तरी ऑफसेट शून्य आहे, म्हणून आम्ही ASCII सह सुसंगतता राखली.

त्याचप्रमाणे 3 बाइट्स आवश्यक असलेल्या कोडसाठी:

1. तीन बाइट्स 110yyyyy yxxxxxxx xxxxxxxx संख्येसह चिन्ह दर्शवा yyyyyy yxxxxxxx xxxxxxxx, बदल वर्तमान वर्णमाला वर yyyyyy y0000000 00000000 (लहान मुले सोडून सर्व काही आठवले 15 बिट्स), आणि आम्ही आता ज्या बॉक्समध्ये आहोत तो चेक करा लांब मोड (वर्णमाला परत दुहेरी-बाइटमध्ये बदलताना, आम्ही हा ध्वज रीसेट करू);
2. दोन बाइट्स 0xxxxxxx xxxxxxxx लांब मोडमध्ये हे वर्तमान वर्णमालाचे वर्ण आहे. त्याचप्रमाणे, आम्ही ते चरण 1 मधील ऑफसेटसह जोडतो. फरक एवढाच आहे की आता आम्ही दोन बाइट्स वाचतो (कारण आम्ही या मोडवर स्विच केले आहे).

छान वाटतं: आता आपल्याला त्याच 7-बिट युनिकोड श्रेणीतील वर्ण एन्कोड करण्याची आवश्यकता असताना, आम्ही सुरुवातीला 1 अतिरिक्त बाइट आणि प्रति वर्ण एकूण एक बाइट खर्च करतो.

आधीच्या आवृत्त्यांपैकी एकावर काम करत आहे. हे आधीच अनेकदा UTF-8 ला हरवते, परंतु सुधारण्यासाठी अजूनही जागा आहे.

काय वाईट आहे? प्रथम, आमच्याकडे एक अट आहे, म्हणजे वर्तमान वर्णमाला ऑफसेट आणि चेकबॉक्स लांब मोड. हे आम्हाला आणखी मर्यादित करते: आता समान वर्ण वेगवेगळ्या संदर्भांमध्ये वेगळ्या प्रकारे एन्कोड केले जाऊ शकतात. सबस्ट्रिंग्स शोधणे, उदाहरणार्थ, हे लक्षात घेऊन केले पाहिजे, आणि केवळ बाइट्सची तुलना करून नाही. दुसरे म्हणजे, आम्ही वर्णमाला बदलताच, ते ASCII वर्णांच्या एन्कोडिंगसह खराब झाले (आणि हे केवळ लॅटिन वर्णमालाच नाही तर रिक्त स्थानांसह मूलभूत विरामचिन्हे देखील आहेत) - त्यांना वर्णमाला पुन्हा 0 वर बदलणे आवश्यक आहे, म्हणजे, पुन्हा एक अतिरिक्त बाइट (आणि नंतर आमच्या मुख्य मुद्द्यावर परत जाण्यासाठी दुसरा).

एक वर्णमाला चांगली आहे, दोन चांगली आहे

वर वर्णन केलेल्या तीनपैकी आणखी एक पिळून आमचे बिट उपसर्ग थोडेसे बदलण्याचा प्रयत्न करूया:

0xxxxxxx — सामान्य मोडमध्ये 1 बाइट, 2 लांब मोडमध्ये
11xxxxxx - 1 बाइट
100xxxxx xxxxxxxx - 2 बाइट्स
101xxxxx xxxxxxxx xxxxxxxx - 3 बाइट्स

आता दोन-बाइट रेकॉर्डमध्ये एक कमी उपलब्ध बिट आहे - कोड पॉइंट पर्यंत 0x1FFFपण नाही 0x3FFF. तथापि, ते अद्याप डबल-बाइट UTF-8 कोडपेक्षा लक्षणीय मोठे आहे, बहुतेक सामान्य भाषा अजूनही बसतात, सर्वात लक्षणीय तोटा बाहेर पडला आहे हिरागाना и काटाकाना, जपानी दुःखी आहेत.

हा नवीन कोड काय आहे? 11xxxxxx? हा 64 वर्णांचा एक छोटासा "स्टॅश" आहे, तो आमच्या मुख्य वर्णमालाला पूरक आहे, म्हणून मी त्याला सहायक म्हटले (सहाय्यक) वर्णमाला. जेव्हा आपण वर्तमान वर्णमाला बदलतो, तेव्हा जुन्या वर्णमालाचा एक भाग सहायक बनतो. उदाहरणार्थ, आम्ही ASCII वरून सिरिलिकवर स्विच केले - स्टॅशमध्ये आता 64 वर्ण आहेत लॅटिन वर्णमाला, संख्या, जागा आणि स्वल्पविराम (एएससीआयआय नसलेल्या मजकुरात सर्वाधिक वारंवार अंतर्भूत करणे). ASCII वर परत जा - आणि सिरिलिक वर्णमालाचा मुख्य भाग सहायक वर्णमाला बनेल.

दोन अक्षरांमध्ये प्रवेश केल्याबद्दल धन्यवाद, आम्ही अक्षरे बदलण्यासाठी कमीतकमी खर्चासह मोठ्या संख्येने मजकूर हाताळू शकतो (विरामचिन्हे बहुतेकदा ASCII वर परत जातील, परंतु त्यानंतर आम्हाला अतिरिक्त वर्णमालामधून अनेक गैर-ASCII वर्ण मिळतील, त्याशिवाय पुन्हा स्विच करत आहे).

बोनस: उप-वर्णमाला उपसर्ग लावणे 11xxxxxx आणि त्याचा प्रारंभिक ऑफसेट असणे निवडणे 0xC0, आम्हाला CP1252 सह आंशिक सुसंगतता मिळते. दुसऱ्या शब्दांत, CP1252 मध्ये एन्कोड केलेले अनेक (परंतु सर्वच नाही) पाश्चात्य युरोपियन मजकूर UTF-C मध्ये समान दिसतील.

येथे, तथापि, एक अडचण उद्भवते: मुख्य वर्णमालामधून सहायक कसे मिळवायचे? आपण समान ऑफसेट सोडू शकता, परंतु - अरेरे - येथे युनिकोड संरचना आधीच आमच्या विरूद्ध खेळत आहे. बर्‍याचदा वर्णमालाचा मुख्य भाग ब्लॉकच्या सुरूवातीस नसतो (उदाहरणार्थ, रशियन कॅपिटल “ए” मध्ये कोड असतो 0x0410, जरी सिरिलिक ब्लॉक पासून सुरू होते 0x0400). अशा प्रकारे, स्टॅशमध्ये पहिले 64 वर्ण घेतल्याने, आम्ही वर्णमालाच्या शेपटीच्या भागाचा प्रवेश गमावू शकतो.

या समस्येचे निराकरण करण्यासाठी, मी व्यक्तिचलितपणे भिन्न भाषांशी संबंधित काही ब्लॉक्समधून गेलो आणि त्यांच्यासाठी मुख्य एकामध्ये सहायक वर्णमालाचा ऑफसेट निर्दिष्ट केला. लॅटिन वर्णमाला, अपवाद म्हणून, सामान्यतः बेस64 प्रमाणे पुनर्क्रमित केली गेली.

अंतिम स्पर्श

शेवटी आपण काहीतरी सुधारू शकतो याचा विचार करूया.

लक्षात ठेवा की स्वरूप 101xxxxx xxxxxxxx xxxxxxxx पर्यंत क्रमांक एन्कोड करण्याची परवानगी देते 0x1FFFFF, आणि युनिकोड आधी, वाजता संपेल 0x10FFFF. दुसऱ्या शब्दांत, शेवटचा कोड पॉइंट म्हणून दर्शविला जाईल 10110000 11111111 11111111. म्हणून, आपण असे म्हणू शकतो की जर पहिला बाइट फॉर्मचा असेल 1011xxxx (कुठे xxxx 0 पेक्षा जास्त), तर याचा अर्थ काहीतरी वेगळा आहे. उदाहरणार्थ, आपण तेथे आणखी 15 वर्ण जोडू शकता जे एका बाइटमध्ये एन्कोडिंगसाठी सतत उपलब्ध असतात, परंतु मी ते वेगळ्या पद्धतीने करण्याचा निर्णय घेतला.

आता ते युनिकोड ब्लॉक्स पाहू ज्यांना तीन बाइट्स आवश्यक आहेत. मूलभूतपणे, आधीच नमूद केल्याप्रमाणे, ही चीनी वर्ण आहेत - परंतु त्यांच्याशी काहीही करणे कठीण आहे, त्यापैकी 21 हजार आहेत. परंतु हिरागाना आणि काटाकाना देखील तेथे उड्डाण केले - आणि आता त्यापैकी बरेच नाहीत, दोनशेपेक्षा कमी. आणि, आम्हाला जपानी आठवत असल्याने, तेथे इमोजी देखील आहेत (खरं तर, ते युनिकोडमध्ये अनेक ठिकाणी विखुरलेले आहेत, परंतु मुख्य ब्लॉक श्रेणीत आहेत. 0x1F300 - 0x1FBFF). जर तुम्ही या वस्तुस्थितीबद्दल विचार केला तर आता इमोजी आहेत जे एकाच वेळी अनेक कोड पॉइंट्समधून एकत्र केले जातात (उदाहरणार्थ, इमोजी ‍‍‍ जास्तीत जास्त 7 कोड असतात!), नंतर प्रत्येकावर तीन बाइट्स (एका चिन्हासाठी 7×3 = 21 बाइट्स, एक भयानक स्वप्न) खर्च करणे पूर्णपणे लाजिरवाणे आहे.

म्हणून, आम्ही इमोजी, हिरागाना आणि काटाकाना यांच्याशी संबंधित काही निवडक श्रेणी निवडतो, त्यांना एका सततच्या सूचीमध्ये पुन्हा क्रमांकित करतो आणि त्यांना तीन ऐवजी दोन बाइट्स म्हणून एन्कोड करतो:

1011xxxx xxxxxxxx

उत्तम: वर नमूद केलेले इमोजी, 7 कोड पॉइंट्सचा समावेश असलेला, UTF-8 मध्ये 25 बाइट्स घेतो आणि आम्ही त्यात बसतो 14 (प्रत्येक कोड पॉइंटसाठी नेमके दोन बाइट्स). तसे, Habr ने ते पचवण्यास नकार दिला (जुन्या आणि नवीन संपादकात दोन्ही), म्हणून मला ते चित्रासह घालावे लागले.

चला आणखी एक समस्या सोडवण्याचा प्रयत्न करूया. जसे आपण लक्षात ठेवतो, मूलभूत वर्णमाला मूलत: आहे उच्च 6 बिट, जे आपण लक्षात ठेवतो आणि प्रत्येक पुढील डीकोड केलेल्या चिन्हाच्या कोडला चिकटवतो. ब्लॉकमध्ये असलेल्या चीनी वर्णांच्या बाबतीत 0x4E00 - 0x9FFF, हे एकतर बिट 0 किंवा 1 आहे. हे फार सोयीचे नाही: आम्हाला या दोन मूल्यांमधील वर्णमाला सतत बदलण्याची आवश्यकता असेल (म्हणजे तीन बाइट खर्च करा). परंतु लक्षात ठेवा की लाँग मोडमध्ये, कोडमधूनच आपण शॉर्ट मोड वापरून एन्कोड केलेल्या वर्णांची संख्या वजा करू शकतो (वर वर्णन केलेल्या सर्व युक्त्यांनंतर, हे 10240 आहे) - नंतर हायरोग्लिफ्सची श्रेणी येथे बदलेल 0x2600 - 0x77FF, आणि या प्रकरणात, या संपूर्ण श्रेणीमध्ये, सर्वात महत्त्वपूर्ण 6 बिट्स (21 पैकी) 0 च्या बरोबरीचे असतील. अशा प्रकारे, हायरोग्लिफचे अनुक्रम प्रति हायरोग्लिफ दोन बाइट्स वापरतील (जे इतक्या मोठ्या श्रेणीसाठी इष्टतम आहे), त्याशिवाय वर्णमाला स्विचेस कारणीभूत.

पर्यायी उपाय: SCSU, BOCU-1

युनिकोड तज्ञ, लेखाचे शीर्षक नुकतेच वाचल्यानंतर, बहुधा तुम्हाला याची आठवण करून देण्याची घाई करतील की थेट युनिकोड मानकांमध्ये आहे. युनिकोडसाठी मानक कॉम्प्रेशन योजना (SCSU), जे लेखात वर्णन केलेल्या एन्कोडिंग पद्धतीचे वर्णन करते.

मी प्रामाणिकपणे कबूल करतो: मी माझा निर्णय लिहिण्यात खूप मग्न झाल्यानंतरच मला त्याच्या अस्तित्वाबद्दल कळले. मला त्याबद्दल सुरवातीपासून माहिती असते तर कदाचित मी माझा स्वतःचा दृष्टिकोन न मांडता अंमलबजावणी लिहिण्याचा प्रयत्न केला असता.

मनोरंजक गोष्ट अशी आहे की SCSU माझ्या स्वतःच्या कल्पनांशी मिळत्याजुळत्या कल्पना वापरते (“वर्णमाला” या संकल्पनेऐवजी ते “विंडोज” वापरतात, आणि माझ्यापेक्षा बरेच काही उपलब्ध आहेत). त्याच वेळी, या स्वरूपाचे तोटे देखील आहेत: ते एन्कोडिंगपेक्षा कॉम्प्रेशन अल्गोरिदमच्या थोडे जवळ आहे. विशेषतः, मानक अनेक प्रतिनिधित्व पद्धती देते, परंतु इष्टतम कसे निवडायचे ते सांगत नाही - यासाठी, एन्कोडरने काही प्रकारचे हेरिस्टिक्स वापरणे आवश्यक आहे. अशा प्रकारे, चांगले पॅकेजिंग तयार करणारा SCSU एन्कोडर माझ्या अल्गोरिदमपेक्षा अधिक जटिल आणि अधिक अवजड असेल.

तुलनेसाठी, मी SCSU ची तुलनेने सोपी अंमलबजावणी JavaScript वर हस्तांतरित केली - कोड व्हॉल्यूमच्या बाबतीत ते माझ्या UTF-C शी तुलना करता येण्यासारखे होते, परंतु काही प्रकरणांमध्ये परिणाम दहापट टक्के वाईट होता (कधीकधी ते त्यापेक्षा जास्त असू शकते, परंतु जास्त नाही). उदाहरणार्थ, हिब्रू आणि ग्रीकमधील मजकूर UTF-C द्वारे एन्कोड केलेले होते SCSU पेक्षा 60% चांगले (कदाचित त्यांच्या संक्षिप्त अक्षरांमुळे).

स्वतंत्रपणे, मी जोडेन की SCSU व्यतिरिक्त युनिकोडचे संक्षिप्त प्रतिनिधित्व करण्याचा दुसरा मार्ग देखील आहे - BOCU-1, परंतु हे MIME सुसंगततेसाठी (ज्याची मला गरज नव्हती) उद्देश आहे आणि एन्कोडिंगसाठी थोडा वेगळा दृष्टीकोन घेते. मी त्याच्या प्रभावीतेचे मूल्यांकन केले नाही, परंतु मला असे दिसते की ते SCSU पेक्षा जास्त असण्याची शक्यता नाही.

संभाव्य सुधारणा

मी सादर केलेला अल्गोरिदम डिझाइननुसार सार्वत्रिक नाही (कदाचित माझी उद्दिष्टे युनिकोड कन्सोर्टियमच्या उद्दिष्टांपेक्षा जास्त वेगळी आहेत). मी आधीच नमूद केले आहे की हे प्रामुख्याने एका कार्यासाठी विकसित केले गेले आहे (उपसर्गाच्या झाडामध्ये बहुभाषिक शब्दकोश संग्रहित करणे), आणि त्यातील काही वैशिष्ट्ये इतर कार्यांसाठी योग्य नसतील. परंतु हे मानक नाही हे एक प्लस असू शकते - तुमच्या गरजेनुसार तुम्ही त्यात सहज बदल करू शकता.

उदाहरणार्थ, स्पष्टपणे तुम्ही राज्याच्या उपस्थितीपासून मुक्त होऊ शकता, स्टेटलेस कोडिंग बनवू शकता - फक्त व्हेरिएबल्स अपडेट करू नका offs, auxOffs и is21Bit एन्कोडर आणि डीकोडरमध्ये. या प्रकरणात, समान वर्णमालेतील वर्णांचे अनुक्रम प्रभावीपणे पॅक करणे शक्य होणार नाही, परंतु संदर्भाकडे दुर्लक्ष करून, समान वर्ण नेहमी समान बाइट्ससह एन्कोड केला जाईल याची हमी दिली जाईल.

याव्यतिरिक्त, आपण डीफॉल्ट स्थिती बदलून विशिष्ट भाषेत एन्कोडर तयार करू शकता - उदाहरणार्थ, रशियन मजकूरांवर लक्ष केंद्रित करून, एन्कोडर आणि डीकोडर सुरुवातीला सेट करा offs = 0x0400 и auxOffs = 0. हे विशेषतः स्टेटलेस मोडच्या बाबतीत अर्थपूर्ण आहे. सर्वसाधारणपणे, हे जुने आठ-बिट एन्कोडिंग वापरण्यासारखे असेल, परंतु आवश्यकतेनुसार सर्व युनिकोडमधून वर्ण घालण्याची क्षमता काढून टाकल्याशिवाय.

आधी उल्लेख केलेला आणखी एक दोष म्हणजे UTF-C मध्ये एन्कोड केलेल्या मोठ्या मजकुरात अनियंत्रित बाइटच्या सर्वात जवळ असलेल्या वर्ण सीमा शोधण्याचा कोणताही द्रुत मार्ग नाही. जर तुम्ही एन्कोड केलेल्या बफरमधून शेवटचे, 100 बाइट्स कापले तर, तुम्हाला कचरा मिळण्याचा धोका आहे ज्यासह तुम्ही काहीही करू शकत नाही. एन्कोडिंग मल्टी-गीगाबाइट लॉग संचयित करण्यासाठी डिझाइन केलेले नाही, परंतु सर्वसाधारणपणे हे दुरुस्त केले जाऊ शकते. बाइट 0xBF प्रथम बाइट म्हणून कधीही दिसू नये (परंतु दुसरा किंवा तिसरा असू शकतो). म्हणून, एन्कोडिंग करताना, आपण अनुक्रम घालू शकता 0xBF 0xBF 0xBF प्रत्येक, म्हणा, 10 KB - मग, जर तुम्हाला सीमा शोधायची असेल, तर समान मार्कर सापडेपर्यंत निवडलेला तुकडा स्कॅन करणे पुरेसे असेल. शेवटचे अनुसरण 0xBF पात्राची सुरुवात असल्याची हमी दिली जाते. (डीकोडिंग करताना, तीन बाइट्सचा हा क्रम अर्थातच दुर्लक्षित करणे आवश्यक आहे.)

संक्षिप्त करण्यासाठी

आपण आतापर्यंत वाचले असल्यास, अभिनंदन! मला आशा आहे की तुम्ही, माझ्याप्रमाणेच, युनिकोडच्या संरचनेबद्दल काहीतरी नवीन (किंवा तुमची स्मृती ताजी) शिकली असेल.

डेमो पृष्ठ. हिब्रूचे उदाहरण UTF-8 आणि SCSU या दोन्हींवरील फायदे दर्शविते.

वर वर्णन केलेले संशोधन हे मानकांचे अतिक्रमण मानले जाऊ नये. तथापि, मी सामान्यतः माझ्या कामाच्या परिणामांबद्दल समाधानी आहे, म्हणून मी त्यांच्याशी आनंदी आहे सामायिक करा: उदाहरणार्थ, मिनिफाइड JS लायब्ररीचे वजन फक्त 1710 बाइट्स असते (आणि अर्थातच कोणतेही अवलंबित्व नसते). मी वर नमूद केल्याप्रमाणे, तिचे कार्य येथे आढळू शकते डेमो पृष्ठ (तेथे मजकूरांचा एक संच देखील आहे ज्यावर त्याची UTF-8 आणि SCSU शी तुलना केली जाऊ शकते).

शेवटी, मी पुन्हा एकदा UTF-C वापरलेल्या प्रकरणांकडे लक्ष वेधून घेईन तो योग्य नाही:

• जर तुमच्या ओळी पुरेशा लांब असतील (100-200 वर्णांपर्यंत). या प्रकरणात, आपण डिफ्लेट सारख्या कॉम्प्रेशन अल्गोरिदम वापरण्याचा विचार केला पाहिजे.
• जर तुला गरज असेल ASCII पारदर्शकता, म्हणजे, तुमच्यासाठी हे महत्त्वाचे आहे की एन्कोड केलेल्या अनुक्रमांमध्ये मूळ स्ट्रिंगमध्ये नसलेले ASCII कोड नसतात. जर, तृतीय-पक्ष API सह संवाद साधताना (उदाहरणार्थ, डेटाबेससह कार्य करताना) आपण एन्कोडिंग परिणाम बाइट्सच्या अमूर्त संचाच्या रूपात पास केल्यास, स्ट्रिंग म्हणून नाही तर याची आवश्यकता टाळली जाऊ शकते. अन्यथा, तुम्हाला अनपेक्षित असुरक्षा मिळण्याचा धोका आहे.
• आपण अनियंत्रित ऑफसेटवर वर्ण सीमा द्रुतपणे शोधण्यात सक्षम होऊ इच्छित असल्यास (उदाहरणार्थ, जेव्हा ओळीचा भाग खराब होतो). हे केले जाऊ शकते, परंतु केवळ सुरुवातीपासूनच ओळ स्कॅन करून (किंवा मागील विभागात वर्णन केलेले बदल लागू करून).
• जर तुम्हाला स्ट्रिंग्सच्या सामग्रीवर त्वरीत ऑपरेशन्स करण्याची आवश्यकता असेल (त्यांची क्रमवारी लावा, त्यातील सबस्ट्रिंग शोधा, एकत्र करा). यासाठी प्रथम स्ट्रिंग्स डीकोड करणे आवश्यक आहे, त्यामुळे या प्रकरणांमध्ये UTF-C UTF-8 पेक्षा हळू असेल (परंतु कॉम्प्रेशन अल्गोरिदमपेक्षा वेगवान). समान स्ट्रिंग नेहमी त्याच प्रकारे एन्कोड केलेली असल्याने, डीकोडिंगची अचूक तुलना आवश्यक नाही आणि बाइट-बाय-बाइट आधारावर केली जाऊ शकते.

अद्यतनित करा: वापरकर्ता टायोमिच खालील टिप्पण्यांमध्ये UTF-C च्या लागू मर्यादा हायलाइट करणारा आलेख पोस्ट केला. हे दर्शविते की जोपर्यंत पॅक केलेली स्ट्रिंग लहान आहे तोपर्यंत UTF-C सामान्य उद्देश कॉम्प्रेशन अल्गोरिदम (LZW चे भिन्नता) पेक्षा अधिक कार्यक्षम आहे. ~१४० वर्ण (तथापि, मी लक्षात घेतो की तुलना एका मजकुरावर केली गेली होती; इतर भाषांसाठी परिणाम भिन्न असू शकतो).


स्त्रोत: www.habr.com