Մեկ այլ հեծանիվ. մենք Unicode տողերը պահում ենք 30-60% ավելի կոմպակտ, քան UTF-8-ը

Եթե ​​դուք ծրագրավորող եք և ձեր առջև կանգնած է կոդավորում ընտրելու խնդիր, ապա Unicode-ը գրեթե միշտ կլինի ճիշտ լուծումը։ Ներկայացման կոնկրետ մեթոդը կախված է համատեքստից, բայց ամենից հաճախ այստեղ նույնպես կա համընդհանուր պատասխան՝ UTF-8: Դրա լավն այն է, որ թույլ է տալիս օգտագործել Յունիկոդի բոլոր նիշերը՝ առանց ծախսելու չափազանց շատ շատ բայթեր շատ դեպքերում: Ճիշտ է, լեզուների համար, որոնք օգտագործում են ավելին, քան պարզապես լատինատառ այբուբենը, «ոչ շատ» առնվազն երկու բայթ մեկ նիշի համար. Կարո՞ղ ենք ավելի լավ անել՝ չվերադառնալով նախապատմական կոդավորումներին, որոնք մեզ սահմանափակում են ընդամենը 256 հասանելի նիշերով:

Ստորև առաջարկում եմ ծանոթանալ այս հարցին պատասխանելու իմ փորձին և իրականացնել համեմատաբար պարզ ալգորիթմ, որը թույլ է տալիս տողեր պահել աշխարհի շատ լեզուներով՝ առանց ավելորդության, որը կա UTF-8-ում:

Հրաժարում պատասխանատվությունից: Ես անմիջապես կանեմ մի քանի կարևոր վերապահումներ. նկարագրված լուծումը չի առաջարկվում որպես UTF-8-ի ունիվերսալ փոխարինում, այն հարմար է միայն դեպքերի նեղ ցանկում (դրանց մասին ավելին ստորև), և ոչ մի դեպքում չպետք է օգտագործվի երրորդ կողմի API-ների հետ փոխազդելու համար (ովքեր նույնիսկ չգիտեն դրա մասին): Ամենից հաճախ, ընդհանուր նշանակության սեղմման ալգորիթմները (օրինակ՝ deflate) հարմար են մեծ ծավալի տեքստային տվյալների կոմպակտ պահպանման համար: Բացի այդ, արդեն իմ լուծումը ստեղծելու գործընթացում ես գտել եմ գոյություն ունեցող ստանդարտ հենց Յունիկոդում, որը լուծում է նույն խնդիրը. դա մի փոքր ավելի բարդ է (և հաճախ ավելի վատ), բայց այնուամենայնիվ այն ընդունված ստանդարտ է, և ոչ միայն դրված: միասին ծնկի վրա: Ես էլ կպատմեմ նրա մասին։

Unicode-ի և UTF-8-ի մասին

Սկսելու համար մի քանի խոսք այն մասին, թե ինչ է դա Unicode и UTF-8.

Ինչպես գիտեք, նախկինում տարածված էին 8-բիթանոց կոդավորումները: Նրանց հետ ամեն ինչ պարզ էր. 256 նիշը կարելի է համարակալել 0-ից 255 թվերով, իսկ 0-ից 255 թվերն ակնհայտորեն կարող են ներկայացվել որպես մեկ բայթ: Եթե ​​վերադառնանք ամենասկզբին, ապա ASCII կոդավորումն ամբողջությամբ սահմանափակվում է 7 բիթով, ուստի դրա բայթերի ներկայացման ամենակարևոր բիթը զրոյական է, և 8-բիթանոց կոդավորումների մեծ մասը համատեղելի է դրա հետ (դրանք տարբերվում են միայն «վերինում» մասը, որտեղ ամենակարևոր բիթը մեկն է):

Ինչպե՞ս է Յունիկոդը տարբերվում այդ կոդավորումներից և ինչո՞ւ են դրա հետ կապված այդքան շատ հատուկ ներկայացումներ՝ UTF-8, UTF-16 (BE և LE), UTF-32: Եկեք դասավորենք այն ըստ հերթականության:

Հիմնական Unicode ստանդարտը նկարագրում է միայն նիշերի (և որոշ դեպքերում՝ նիշերի առանձին բաղադրիչների) և դրանց թվերի համապատասխանությունը։ Եվ այս ստանդարտում շատ հնարավոր թվեր կան՝ սկսած 0x00 դեպի 0x10FFFF (1 հատ): Եթե ​​մենք ցանկանայինք նման տիրույթի թիվ դնել փոփոխականի մեջ, մեզ ոչ 114, ոչ էլ 112 բայթը բավարար չէր լինի։ Եվ քանի որ մեր պրոցեսորները այնքան էլ նախատեսված չեն երեք բայթ թվերի հետ աշխատելու համար, մենք ստիպված կլինենք օգտագործել մինչև 1 բայթ մեկ նիշի համար: Սա UTF-2-ն է, բայց հենց այս «թափոնության» պատճառով է, որ այս ձևաչափը հայտնի չէ:

Բարեբախտաբար, Յունիկոդում նիշերի հերթականությունը պատահական չէ: Նրանց ամբողջ հավաքածուն բաժանված է 17 "ինքնաթիռներ», որոնցից յուրաքանչյուրը պարունակում է 65536 (0x10000) «ծածկագրի կետերը« Այստեղ «կոդային կետ» հասկացությունը պարզ է նիշերի համարը, նրան հանձնարարված է Յունիկոդի կողմից։ Բայց, ինչպես նշվեց վերևում, Unicode-ում համարակալված են ոչ միայն առանձին նիշերը, այլև դրանց բաղադրիչները և սպասարկման նշանները (և երբեմն ընդհանրապես ոչինչ չի համապատասխանում թվին, միգուցե առայժմ, բայց մեզ համար դա այնքան էլ կարևոր չէ): Ավելի ճիշտ է, որ միշտ խոսենք հենց թվերի քանակի մասին, այլ ոչ թե նշանների: Սակայն ստորև, հակիրճ լինելու համար, հաճախ կօգտագործեմ «խորհրդանիշ» բառը՝ ակնարկելով «կոդ» տերմինը։

Unicode ինքնաթիռներ. Ինչպես տեսնում եք, դրա մեծ մասը (4-ից 13 ինքնաթիռները) դեռ չօգտագործված է:

Ամենաուշագրավն այն է, որ ամբողջ հիմնական «մաղձը» գտնվում է զրոյական հարթության մեջ, այն կոչվում է «Հիմնական բազմալեզու ինքնաթիռԵթե ​​տողը պարունակում է տեքստ ժամանակակից լեզուներից մեկով (ներառյալ չինարեն), դուք չեք գնա այս հարթությունից այն կողմ: Բայց դուք չեք կարող կտրել մնացած Unicode-ը, օրինակ, էմոջիները հիմնականում գտնվում են վերջում: հաջորդ ինքնաթիռը»,Լրացուցիչ բազմալեզու ինքնաթիռ«(այն տարածվում է 0x10000 դեպի 0x1FFFF). Այսպիսով, UTF-16-ն անում է սա. բոլոր նիշերը ընկնում են ներսում Հիմնական բազմալեզու ինքնաթիռ, կոդավորված են «ինչպես կա» համապատասխան երկու բայթ թվով: Այնուամենայնիվ, այս տիրույթի որոշ թվեր ընդհանրապես չեն նշում հատուկ նիշեր, այլ ցույց են տալիս, որ այս զույգ բայթերից հետո մենք պետք է դիտարկենք ևս մեկը. այս չորս բայթերի արժեքները միասին համակցելով, մենք ստանում ենք մի թիվ, որը ներառում է. Unicode-ի վավեր տիրույթը: Այս գաղափարը կոչվում է «փոխնակ զույգեր»՝ դուք կարող եք լսել նրանց մասին:

Այսպիսով, UTF-16-ը պահանջում է երկու կամ (շատ հազվադեպ դեպքերում) չորս բայթ յուրաքանչյուր «կոդային կետում»: Սա ավելի լավ է, քան անընդհատ չորս բայթ օգտագործելը, բայց լատիներենը (և ASCII այլ նիշերը) այս կերպ կոդավորվելիս վատնում է տարածքի կեսը զրոների վրա: UTF-8-ը նախատեսված է դա շտկելու համար. ASCII-ը դրանում զբաղեցնում է, ինչպես նախկինում, ընդամենը մեկ բայթ; ծածկագրերը 0x80 դեպի 0x7FF - երկու բայթ; -ից 0x800 դեպի 0xFFFF - երեք, և սկսած 0x10000 դեպի 0x10FFFF - չորս. Մի կողմից, լատինական այբուբենը լավն է դարձել. ASCII-ի հետ համատեղելիությունը վերադարձել է, և բաշխումն ավելի համաչափ է «տարածվել» 1-ից 4 բայթ: Բայց լատիներենից բացի այլ այբուբենները, ավաղ, ոչ մի կերպ չեն շահում UTF-16-ի համեմատ, և շատերն այժմ պահանջում են երեք բայթ երկու բայթի փոխարեն. 0xFFFF դեպի 0x7FF, և դրա մեջ ներառված չեն ոչ չինական, ոչ, օրինակ, վրացական։ Կիրիլիցա և հինգ այլ այբուբեններ - hurray - lucky, 2 բայթ մեկ նիշի համար:

Ինչու է դա տեղի ունենում: Տեսնենք, թե ինչպես է UTF-8-ը ներկայացնում նիշերի կոդերը.

Անմիջապես թվերը ներկայացնելու համար այստեղ օգտագործվում են խորհրդանիշով նշված բիթերը x. Երևում է, որ երկու բայթանոց ձայնագրության մեջ կա ընդամենը 11 այդպիսի բիթ (16-ից)։ Առաջատար բիթերն այստեղ ունեն միայն օժանդակ գործառույթ։ Չորս բայթ ձայնագրության դեպքում 21 բիթից 32-ը հատկացվում է կոդային կետի համարին. թվում է, որ երեք բայթը (որոնք ընդհանուր առմամբ տալիս են 24 բիթ) բավական կլինի, բայց ծառայության մարկերները չափազանց շատ են ուտում:

Սա վա՞տ է: Իրականում ոչ: Մի կողմից, եթե մենք շատ ենք մտածում տարածության մասին, մենք ունենք սեղմման ալգորիթմներ, որոնք հեշտությամբ կարող են վերացնել բոլոր ավելորդ էնտրոպիան և ավելորդությունը: Մյուս կողմից, Յունիկոդի նպատակն էր ապահովել հնարավորինս համընդհանուր կոդավորում: Օրինակ, մենք կարող ենք վստահել UTF-8-ով կոդավորված տողին, որը նախկինում աշխատում էր միայն ASCII-ի հետ, և չվախենանք, որ այն կտեսնի մի նիշ ASCII միջակայքից, որն իրականում այնտեղ չկա (ի վերջո, UTF-8-ում բոլորը բայթեր՝ սկսած զրոյական բիթից. սա հենց այն է, ինչ ASCII է): Եվ եթե մենք հանկարծ ուզում ենք կտրել մի փոքր պոչը մեծ տողից՝ առանց այն հենց սկզբից վերծանելու (կամ վերականգնել տեղեկատվության մի մասը վնասված հատվածից հետո), մեզ համար հեշտ է գտնել այն շեղումը, որտեղ սկսվում է կերպարը (բավական է) բայթերը բաց թողնելու համար, որոնք ունեն բիթ նախածանց 10).

Ինչու՞ այդ դեպքում նոր բան հորինել:

Միևնույն ժամանակ, երբեմն լինում են իրավիճակներ, երբ սեղմման ալգորիթմները, ինչպիսին է deflate-ն է, վատ կիրառելի են, բայց դուք ցանկանում եք հասնել տողերի կոմպակտ պահպանման: Անձամբ ես այս խնդրին բախվել եմ կառուցելու մասին մտածելիս սեղմված նախածանցային ծառ կամայական լեզուներով բառեր ներառող մեծ բառարանի համար: Մի կողմից, յուրաքանչյուր բառը շատ կարճ է, ուստի այն սեղմելը անարդյունավետ կլինի: Մյուս կողմից, ծառի իրականացումը, որը ես համարեցի, նախագծված էր այնպես, որ պահված տողի յուրաքանչյուր բայթ գեներացնի առանձին ծառի գագաթ, ուստի դրանց թիվը նվազագույնի հասցնելը շատ օգտակար էր: Իմ գրադարանում Ազ.ջս (Ինչպես պիմորֆիա2, որի վրա հիմնված է) նմանատիպ խնդիր կարող է լուծվել պարզապես - strings packed into DAWG-բառարան, որը պահվում է այնտեղ լավ հին CP1251. Բայց, ինչպես հեշտ է հասկանալ, սա լավ է աշխատում միայն սահմանափակ այբուբենի դեպքում. չինարեն տող չի կարող ավելացվել նման բառարանում:

Առանձին-առանձին, ես կցանկանայի նշել ևս մեկ տհաճ նրբերանգ, որն առաջանում է UTF-8-ը տվյալների նման կառուցվածքում օգտագործելիս: Վերևի նկարը ցույց է տալիս, որ երբ նիշը գրվում է երկու բայթով, նրա թվի հետ կապված բիթերը իրար հաջորդում չեն, այլ բաժանվում են զույգ բիթերով։ 10 մեջտեղում: 110xxxxx 10xxxxxx. Դրա պատճառով, երբ երկրորդ բայթի ստորին 6 բիթերը լցվում են նիշերի կոդում (այսինքն, տեղի է ունենում անցում 10111111 → 10000000), այնուհետև փոխվում է նաև առաջին բայթը: Պարզվում է, որ «p» տառը նշվում է բայթերով 0xD0 0xBF, իսկ հաջորդ «r»-ն արդեն 0xD1 0x80. Նախածանցային ծառի մեջ դա հանգեցնում է մայր հանգույցի բաժանմանը երկու մասի. մեկը՝ նախածանցի համար: 0xD0, և մեկ այլ համար 0xD1 (թեև ամբողջ կիրիլյան այբուբենը կարող էր կոդավորվել միայն երկրորդ բայթով):

Ինչ ստացա

Այս խնդրի առաջ կանգնելով՝ ես որոշեցի զբաղվել բիթերով խաղեր խաղալով և միևնույն ժամանակ մի փոքր ավելի լավ ծանոթանալ Յունիկոդի կառուցվածքին որպես ամբողջություն։ Արդյունքն եղավ UTF-C կոդավորման ձևաչափը («C» համար կուռ), որը ծախսում է ոչ ավելի, քան 3 բայթ մեկ կոդային կետում, և շատ հաճախ թույլ է տալիս ծախսել միայն մեկ լրացուցիչ բայթ ամբողջ կոդավորված տողի համար. Սա հանգեցնում է նրան, որ շատ ոչ ASCII այբուբենների վրա նման կոդավորում է ստացվում 30-60% ավելի կոմպակտ, քան UTF-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 բայթ յուրաքանչյուր նիշի մեջ:

Մուտքագրեք կոդավորիչի վիճակը

Եկեք հիմա մտածենք հենց տողերի հատկությունների մասին: Բառարանն ամենից հաճախ պարունակում է նույն այբուբենի տառերով գրված բառեր, և դա ճիշտ է նաև շատ այլ տեքստերի համար։ Լավ կլինի մեկ անգամ նշել այս այբուբենը, իսկ հետո նշել միայն տառի թիվը։ Տեսնենք, թե արդյոք Unicode աղյուսակում նիշերի դասավորությունը կօգնի մեզ։

Ինչպես նշվեց վերևում, Յունիկոդը բաժանված է Ինքնաթիռ 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-բիթանոց Unicode տիրույթից, սկզբում մենք ծախսում ենք 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-ի վերադարձին, բայց դրանից հետո մենք լրացուցիչ այբուբենից կստանանք բազմաթիվ ոչ 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 կոդային կետերից, վերցնում է 8 բայթ UTF-25-ում, և մենք տեղավորում ենք այն 14 (ուղղակի երկու բայթ յուրաքանչյուր կոդային կետի համար): Ի դեպ, Հաբրը հրաժարվեց այն մարսելուց (ինչպես հին, այնպես էլ նոր խմբագրության մեջ), ուստի ստիպված էի նկարով տեղադրել։

Փորձենք շտկել ևս մեկ խնդիր. Ինչպես հիշում ենք, հիմնական այբուբենը ըստ էության բարձր 6 բիթ, որը մենք նկատի ունենք և կպչում ենք յուրաքանչյուր հաջորդ վերծանված նշանի ծածկագրին։ Չինական նիշերի դեպքում, որոնք գտնվում են բլոկում 0x4E00 - 0x9FFF, սա կամ 0 կամ 1 բիթ է: Սա այնքան էլ հարմար չէ. մեզ անհրաժեշտ կլինի անընդհատ այբուբենը փոխել այս երկու արժեքների միջև (այսինքն՝ ծախսել երեք բայթ): Բայց նկատի ունեցեք, որ երկար ռեժիմում, ինքնին կոդից, մենք կարող ենք հանել այն նիշերի քանակը, որոնք մենք կոդավորում ենք՝ օգտագործելով կարճ ռեժիմը (վերևում նկարագրված բոլոր հնարքներից հետո սա 10240 է), այնուհետև հիերոգլիֆների տիրույթը կտեղափոխվի դեպի 0x2600 - 0x77FF, և այս դեպքում այս ողջ տիրույթում ամենակարևոր 6 բիթերը (21-ից) հավասար կլինեն 0-ի: Այսպիսով, հիերոգլիֆների հաջորդականությունը կօգտագործի երկու բայթ մեկ հիերոգլիֆի համար (ինչն օպտիմալ է այդպիսի մեծ տիրույթի համար), առանց առաջացնելով այբուբենի անջատիչներ:

Այլընտրանքային լուծումներ՝ SCSU, BOCU-1

Յունիկոդի փորձագետները, հենց նոր կարդալով հոդվածի վերնագիրը, ամենայն հավանականությամբ կշտապեն հիշեցնել ձեզ, որ ուղղակիորեն Յունիկոդի ստանդարտների մեջ կա. Ստանդարտ սեղմման սխեման Unicode-ի համար (SCSU), որը նկարագրում է կոդավորման մեթոդ, որը շատ նման է հոդվածում նկարագրվածին:

Անկեղծորեն խոստովանում եմ. ես իմացա դրա գոյության մասին միայն այն բանից հետո, երբ խորապես խորասուզվեցի իմ որոշումը գրելու մեջ: Եթե ​​ես ի սկզբանե իմանայի այդ մասին, հավանաբար կփորձեի իմ սեփական մոտեցմամբ հանդես գալու փոխարեն կատարելագործում գրել:

Հետաքրքիրն այն է, որ SCSU-ն օգտագործում է գաղափարներ, որոնք շատ նման են այն գաղափարներին, որոնք ես ինքնուրույն եմ հորինել («այբուբենների» հայեցակարգի փոխարեն նրանք օգտագործում են «պատուհաններ», և դրանք ավելի շատ են, քան ես ունեմ): Միևնույն ժամանակ, այս ձևաչափն ունի նաև թերություններ՝ այն մի փոքր ավելի մոտ է սեղմման ալգորիթմներին, քան կոդավորմանը։ Մասնավորապես, ստանդարտը տալիս է բազմաթիվ ներկայացման մեթոդներ, բայց չի ասում, թե ինչպես ընտրել օպտիմալը. դրա համար կոդավորիչը պետք է օգտագործի ինչ-որ էվրիստիկա: Այսպիսով, SCSU կոդավորիչը, որը արտադրում է լավ փաթեթավորում, կլինի ավելի բարդ և դժվար, քան իմ ալգորիթմը:

Համեմատության համար ես փոխանցեցի SCSU-ի համեմատաբար պարզ իրականացումը JavaScript-ին. կոդի ծավալի առումով այն համեմատելի էր իմ UTF-C-ի հետ, բայց որոշ դեպքերում արդյունքը տասնյակ տոկոսով ավելի վատ էր (երբեմն այն կարող է գերազանցել այն, բայց ոչ շատ): Օրինակ, եբրայերեն և հունարեն տեքստերը կոդավորված են UTF-C-ով 60% ավելի լավ, քան SCSU (հավանաբար նրանց կոմպակտ այբուբենների շնորհիվ):

Առանձին-առանձին, ես կավելացնեմ, որ բացի SCSU-ից, կա նաև Unicode-ը կոմպակտ ներկայացնելու մեկ այլ եղանակ. BOCU-1, բայց այն նպատակաուղղված է MIME-ի համատեղելիությանը (ինչն ինձ պետք չէր) և մի փոքր այլ մոտեցում է ցուցաբերում կոդավորման հարցում։ Ես դրա արդյունավետությունը չեմ գնահատել, բայց ինձ թվում է, որ դժվար թե այն ավելի բարձր լինի, քան SCSU-ն։

Հնարավոր բարելավումներ

Իմ ներկայացրած ալգորիթմը նախագծով ունիվերսալ չէ (հավանաբար այստեղ իմ նպատակները ամենից շատ են տարբերվում Յունիկոդ կոնսորցիումի նպատակներից): Ես արդեն նշեցի, որ այն մշակվել է հիմնականում մեկ առաջադրանքի համար (բազմալեզու բառարանը նախածանցի ծառի մեջ պահելը), և դրա որոշ առանձնահատկություններ կարող են հարմար չլինել այլ առաջադրանքների համար: Բայց այն, որ դա չափանիշ չէ, կարող է պլյուս լինել. դուք կարող եք հեշտությամբ փոփոխել այն ձեր կարիքներին համապատասխան.

Օրինակ, ակնհայտ ձևով դուք կարող եք ազատվել վիճակի առկայությունից, կատարել քաղաքացիություն չունեցող կոդավորում. պարզապես մի թարմացրեք փոփոխականները offs, auxOffs и is21Bit կոդավորիչում և ապակոդավորիչում: Այս դեպքում հնարավոր չի լինի արդյունավետ կերպով փաթեթավորել նույն այբուբենի նիշերի հաջորդականությունը, սակայն երաշխիք կլինի, որ նույն նիշը միշտ կոդավորված է նույն բայթերով՝ անկախ համատեքստից:

Բացի այդ, դուք կարող եք հարմարեցնել կոդավորիչը որոշակի լեզվին՝ փոխելով լռելյայն վիճակը, օրինակ՝ կենտրոնանալով ռուսերեն տեքստերի վրա, սկզբում կարգավորեք կոդավորիչը և ապակոդավորիչը: offs = 0x0400 и auxOffs = 0. Սա հատկապես իմաստ ունի քաղաքացիություն չունեցող ռեժիմի դեպքում։ Ընդհանուր առմամբ, սա նման կլինի հին ութ-բիթանոց կոդավորման օգտագործմանը, բայց առանց անհրաժեշտության դեպքում ամբողջ Յունիկոդից նիշեր տեղադրելու հնարավորությունը հեռացնելու:

Նախկինում հիշատակված մեկ այլ թերություն այն է, որ UTF-C-ով կոդավորված մեծ տեքստում չկա կամայական բայթին ամենամոտ նիշերի սահմանը գտնելու արագ միջոց: Եթե ​​դուք կտրում եք վերջին, ասենք, 100 բայթը կոդավորված բուֆերից, դուք ռիսկի եք դիմում ստանալ աղբ, որի հետ դուք ոչինչ չեք կարող անել: Կոդավորումը նախատեսված չէ բազմագիգաբայթանոց տեղեկամատյանները պահելու համար, բայց ընդհանուր առմամբ դա կարելի է ուղղել: Բայթ 0xBF երբեք չպետք է հայտնվի որպես առաջին բայթ (բայց կարող է լինել երկրորդ կամ երրորդ): Հետեւաբար, երբ կոդավորումը, դուք կարող եք տեղադրել հաջորդականությունը 0xBF 0xBF 0xBF ամեն, ասենք, 10 ԿԲ - այնուհետև, եթե ձեզ անհրաժեշտ է սահման գտնել, բավական կլինի սկանավորել ընտրված հատվածը, մինչև գտնվի նմանատիպ մարկեր: Հետևելով վերջին 0xBF երաշխավորված է լինել կերպարի սկիզբ: (Վերծանելիս երեք բայթից բաղկացած այս հաջորդականությունը, իհարկե, պետք է անտեսվի):

Ամփոփելով

Եթե ​​այսքանը կարդացել եք, շնորհավորում եմ: Հուսով եմ, դուք, ինչպես ինձ, նոր բան եք սովորել (կամ թարմացրել եք ձեր հիշողությունը) Unicode-ի կառուցվածքի մասին:

Դեմո էջ. Եբրայերենի օրինակը ցույց է տալիս առավելությունները ինչպես UTF-8-ի, այնպես էլ SCSU-ի նկատմամբ:

Վերը նկարագրված հետազոտությունը չպետք է համարվի ստանդարտների նկատմամբ ոտնձգություն: Այնուամենայնիվ, ես ընդհանուր առմամբ գոհ եմ իմ աշխատանքի արդյունքներից, ուստի գոհ եմ դրանցից բաժինՕրինակ, փոքրացված JS գրադարանը կշռում է ընդամենը 1710 բայթ (և, իհարկե, չունի որևէ կախվածություն): Ինչպես նշեցի վերևում, նրա աշխատանքը կարելի է գտնել այստեղ ցուցադրական էջ (կա նաև մի շարք տեքստեր, որոնց վրա այն կարելի է համեմատել UTF-8-ի և SCSU-ի հետ):

Ի վերջո, ես ևս մեկ անգամ ուշադրություն կդարձնեմ այն ​​դեպքերին, երբ օգտագործվում է UTF-C չարժե այն:

• Եթե ​​ձեր տողերը բավականաչափ երկար են (100-200 նիշից): Այս դեպքում դուք պետք է մտածեք սեղմման ալգորիթմների օգտագործման մասին, ինչպիսին է deflate-ը:
• Եթե ​​պետք է ASCII թափանցիկություն, այսինքն՝ ձեզ համար կարևոր է, որ կոդավորված հաջորդականությունները չպարունակեն ASCII կոդեր, որոնք սկզբնական տողում չեն եղել։ Դրա անհրաժեշտությունից կարելի է խուսափել, եթե երրորդ կողմի API-ների հետ շփվելիս (օրինակ՝ տվյալների բազայի հետ աշխատելիս), կոդավորման արդյունքը փոխանցեք որպես բայթերի վերացական հավաքածու, այլ ոչ թե որպես տողեր։ Հակառակ դեպքում, դուք վտանգում եք ստանալ անսպասելի խոցելիություններ:
• Եթե ​​ցանկանում եք արագորեն գտնել նիշերի սահմանները կամայական շեղումով (օրինակ, երբ տողի մի մասը վնասված է): Դա կարելի է անել, բայց միայն սկզբից տողը սկանավորելով (կամ կիրառելով նախորդ բաժնում նկարագրված փոփոխությունը):
• Եթե ​​Ձեզ անհրաժեշտ է արագ գործողություններ կատարել տողերի բովանդակության վրա (տեսակավորել դրանք, որոնել ենթատողեր դրանցում, միացնել): Սա պահանջում է, որ տողերը նախ վերծանվեն, ուստի UTF-C-ն այս դեպքերում ավելի դանդաղ կլինի, քան UTF-8-ը (բայց ավելի արագ, քան սեղմման ալգորիթմները): Քանի որ նույն տողը միշտ նույն կերպ է կոդավորված, ապա կոդավորման ճշգրիտ համեմատությունը չի պահանջվում և կարող է կատարվել բայթ առ բայթ հիմունքներով:

Թարմացնել: օգտագործողը Տյոմիչ ստորև ներկայացված մեկնաբանություններում տեղադրեց գրաֆիկ, որն ընդգծում է UTF-C-ի կիրառելիության սահմանները: Այն ցույց է տալիս, որ UTF-C-ն ավելի արդյունավետ է, քան ընդհանուր նշանակության սեղմման ալգորիթմը (LZW-ի փոփոխություն), քանի դեռ փաթեթավորված տողը ավելի կարճ է: ~ 140 նիշ (սակայն, ես նշում եմ, որ համեմատությունն իրականացվել է մեկ տեքստի վրա, այլ լեզուների համար արդյունքը կարող է տարբերվել):


Source: www.habr.com