კიდევ ერთი ველოსიპედი: ჩვენ ვინახავთ Unicode სიმებს 30-60% უფრო კომპაქტურად ვიდრე UTF-8

თუ თქვენ ხართ დეველოპერი და გაქვთ კოდირების არჩევის ამოცანა, მაშინ Unicode თითქმის ყოველთვის იქნება სწორი გამოსავალი. კონკრეტული წარმოდგენის მეთოდი დამოკიდებულია კონტექსტზე, მაგრამ ყველაზე ხშირად აქაც არის უნივერსალური პასუხი - UTF-8. კარგი ის არის, რომ ის საშუალებას გაძლევთ გამოიყენოთ უნიკოდის ყველა სიმბოლო დახარჯვის გარეშე ძალიან ბევრი ბევრი ბაიტი უმეტეს შემთხვევაში. მართალია, ენებისთვის, რომლებიც იყენებენ უფრო მეტს, ვიდრე უბრალოდ ლათინური ანბანი, "არც ისე ბევრი" მაინც ორი ბაიტი თითო სიმბოლოზე. შეგვიძლია თუ არა უკეთესი გავაკეთოთ პრეისტორიულ დაშიფვრებში დაბრუნების გარეშე, რომლებიც გვზღუდავს მხოლოდ 256 ხელმისაწვდომი სიმბოლოთი?

ქვემოთ მე გთავაზობთ გაეცნოთ ამ კითხვაზე პასუხის გაცემის ჩემს მცდელობას და განვახორციელოთ შედარებით მარტივი ალგორითმი, რომელიც საშუალებას გაძლევთ შეინახოთ ხაზები მსოფლიოს უმეტეს ენაზე UTF-8-ში არსებული ჭარბი რაოდენობის დამატების გარეშე.

პასუხისმგებლობის უარყოფა. მე დაუყოვნებლივ გავაკეთებ რამდენიმე მნიშვნელოვან დათქმას: აღწერილი გადაწყვეტა არ არის შემოთავაზებული UTF-8-ის უნივერსალური შემცვლელად, ის შესაფერისია მხოლოდ შემთხვევების ვიწრო სიაში (დაწვრილებით მათზე ქვემოთ) და არავითარ შემთხვევაში არ უნდა იქნას გამოყენებული მესამე მხარის API-ებთან ურთიერთობისთვის (რომლებმაც კი არ იციან ამის შესახებ). ყველაზე ხშირად, ზოგადი დანიშნულების შეკუმშვის ალგორითმები (მაგალითად, deflate) შესაფერისია დიდი მოცულობის ტექსტური მონაცემების კომპაქტური შესანახად. გარდა ამისა, უკვე ჩემი გადაწყვეტის შექმნის პროცესში ვიპოვე არსებული სტანდარტი თავად უნიკოდში, რომელიც აგვარებს იგივე პრობლემას - ეს არის გარკვეულწილად უფრო რთული (და ხშირად უარესი), მაგრამ მაინც მიღებული სტანდარტია და არა მხოლოდ ერთად მუხლზე. მეც მოგიყვებით მასზე.

უნიკოდისა და UTF-8-ის შესახებ

დასაწყისისთვის, რამდენიმე სიტყვა იმის შესახებ, თუ რა არის ეს Unicode и UTF-8.

მოგეხსენებათ, ადრე პოპულარული იყო 8-ბიტიანი კოდირება. მათთან ყველაფერი მარტივი იყო: 256 სიმბოლო შეიძლება იყოს დანომრილი 0-დან 255-მდე, ხოლო 0-დან 255-მდე რიცხვები აშკარად შეიძლება იყოს წარმოდგენილი როგორც ერთი ბაიტი. თუ თავიდანვე დავუბრუნდებით, ASCII კოდირება მთლიანად შემოიფარგლება 7 ბიტით, ამიტომ მისი ბაიტის წარმოდგენის ყველაზე მნიშვნელოვანი ბიტი არის ნული და 8-ბიტიანი კოდირების უმეტესობა თავსებადია მასთან (ისინი განსხვავდებიან მხოლოდ "ზედაში" ნაწილი, სადაც ყველაზე მნიშვნელოვანი ბიტი არის ერთი ).

რით განსხვავდება Unicode ამ კოდირებისგან და რატომ არის დაკავშირებული მას ამდენი კონკრეტული წარმოდგენა - UTF-8, UTF-16 (BE და LE), UTF-32? მოდი დავალაგოთ თანმიმდევრობით.

უნიკოდის ძირითადი სტანდარტი აღწერს მხოლოდ სიმბოლოებს (და ზოგიერთ შემთხვევაში, სიმბოლოების ცალკეულ კომპონენტებს) და მათ რიცხვებს შორის შესაბამისობას. და ამ სტანდარტში ბევრი შესაძლო რიცხვია - დან 0x00 დან 0x10FFFF (1 ცალი). თუ გვინდოდა ცვლადში ჩავსვათ რიცხვი ასეთ დიაპაზონში, არც 114 და არც 112 ბაიტი არ იქნებოდა საკმარისი. და რადგან ჩვენი პროცესორები არ არის ძალიან შექმნილი სამბაიტიანი რიცხვებით მუშაობისთვის, ჩვენ იძულებული ვიქნებით გამოვიყენოთ 1 ბაიტი თითო სიმბოლოზე! ეს არის UTF-2, მაგრამ ეს ფორმატი არ არის პოპულარული სწორედ ამ "მფლანგველობის" გამო.

საბედნიეროდ, უნიკოდში სიმბოლოების თანმიმდევრობა შემთხვევითი არ არის. მათი მთელი ნაკრები დაყოფილია 17 "თვითმფრინავები", რომელთაგან თითოეული შეიცავს 65536 (0x10000) "კოდის წერტილები" "კოდური წერტილის" კონცეფცია აქ უბრალოდ არის სიმბოლოს ნომერი, მინიჭებული მას Unicode-ის მიერ. მაგრამ, როგორც ზემოთ აღვნიშნეთ, უნიკოდში ინომრება არა მხოლოდ ცალკეული სიმბოლოები, არამედ მათი კომპონენტები და სერვისის ნიშნები (და ზოგჯერ საერთოდ არაფერი შეესაბამება რიცხვს - შესაძლოა ამ დროისთვის, მაგრამ ჩვენთვის ეს არც ისე მნიშვნელოვანია), ასე რომ. უფრო სწორია, ყოველთვის კონკრეტულად ისაუბროთ თავად რიცხვების რაოდენობაზე და არა სიმბოლოებზე. თუმცა, შემდგომში, მოკლედ, ხშირად გამოვიყენებ სიტყვას „სიმბოლო“, რაც გულისხმობს ტერმინს „კოდი წერტილი“.

უნიკოდის თვითმფრინავები. როგორც ხედავთ, მისი უმეტესი ნაწილი (4-დან 13-მდე თვითმფრინავი) ჯერ კიდევ გამოუყენებელია.

ყველაზე საყურადღებოა ის, რომ მთელი ძირითადი „რბილობი“ დევს ნულოვან სიბრტყეში, მას ე.წ.ძირითადი მრავალენოვანი თვითმფრინავითუ სტრიქონი შეიცავს ტექსტს ერთ-ერთ თანამედროვე ენაზე (მათ შორის ჩინურზე), თქვენ არ წახვალთ ამ სიბრტყის ფარგლებს გარეთ. მაგრამ თქვენ არ შეგიძლიათ გათიშოთ დანარჩენი Unicode - მაგალითად, emoji ძირითადად მდებარეობს ბოლოში. შემდეგი თვითმფრინავი"დამატებითი მრავალენოვანი თვითმფრინავი“ (იგი ვრცელდება საიდან 0x10000 დან 0x1FFFF). ასე რომ, UTF-16 აკეთებს ამას: ყველა სიმბოლო, რომელიც შედის შიგნით ძირითადი მრავალენოვანი თვითმფრინავი, დაშიფრულია „როგორც არის“ შესაბამისი ორ ბაიტიანი ნომრით. თუმცა, ამ დიაპაზონის ზოგიერთი რიცხვი საერთოდ არ მიუთითებს კონკრეტულ სიმბოლოებზე, მაგრამ მიუთითებს იმაზე, რომ ამ წყვილი ბაიტის შემდეგ უნდა განვიხილოთ კიდევ ერთი - ამ ოთხი ბაიტის მნიშვნელობების ერთად შერწყმით, მივიღებთ რიცხვს, რომელიც მოიცავს მთელი მოქმედი Unicode დიაპაზონი. ამ იდეას ჰქვია "სუროგატი წყვილები" - შესაძლოა გსმენიათ მათ შესახებ.

ასე რომ, UTF-16 მოითხოვს ორ ან (ძალიან იშვიათ შემთხვევებში) ოთხ ბაიტს თითო "კოდი წერტილი". ეს უკეთესია, ვიდრე მუდმივად გამოიყენოთ ოთხი ბაიტი, მაგრამ ლათინური (და სხვა ASCII სიმბოლოები) ამ გზით კოდირებით კარგავს სივრცის ნახევარს ნულებზე. UTF-8 შექმნილია ამის გამოსასწორებლად: მასში ASCII, როგორც ადრე, მხოლოდ ერთ ბაიტს იკავებს; კოდებიდან 0x80 დან 0x7FF - ორი ბაიტი; საწყისი 0x800 დან 0xFFFF - სამი და დან 0x10000 დან 0x10FFFF - ოთხი. ერთის მხრივ, ლათინური ანბანი კარგი გახდა: ASCII-თან თავსებადობა დაბრუნდა და განაწილება უფრო თანაბრად "გავრცელდა" 1-დან 4 ბაიტამდე. მაგრამ ლათინური გარდა სხვა ანბანები, სამწუხაროდ, არავითარ სარგებელს არ მოაქვს UTF-16-თან შედარებით და ბევრს ახლა სჭირდება სამი ბაიტი ორის ნაცვლად - დიაპაზონი, რომელიც დაფარულია ორ ბაიტიანი ჩანაწერით, 32-ჯერ შემცირდა. 0xFFFF დან 0x7FF, და მასში არც ჩინური და, მაგალითად, ქართული არ შედის. კირილიცა და ხუთი სხვა ანბანი - hurray - იღბლიანი, 2 ბაიტი თითო სიმბოლოზე.

რატომ ხდება ეს? ვნახოთ, როგორ წარმოადგენს UTF-8 სიმბოლოების კოდებს:

პირდაპირ რიცხვების წარმოსაჩენად, აქ გამოიყენება სიმბოლოთი მონიშნული ბიტები x. ჩანს, რომ ორ ბაიტიან ჩანაწერში მხოლოდ 11 ასეთი ბიტია (16-დან). წამყვან ბიტებს აქ მხოლოდ დამხმარე ფუნქცია აქვთ. ოთხი ბაიტიანი ჩანაწერის შემთხვევაში, 21 ბიტიდან 32 გამოყოფილია კოდის წერტილის ნომრისთვის - როგორც ჩანს, სამი ბაიტი (რომელიც ჯამში იძლევა 24 ბიტს) საკმარისი იქნება, მაგრამ სერვისის მარკერები ძალიან ბევრს ჭამს.

ეს ცუდია? Ნამდვილად არ. ერთის მხრივ, თუ ჩვენ დიდად ვზრუნავთ სივრცეზე, ჩვენ გვაქვს შეკუმშვის ალგორითმები, რომლებიც ადვილად აღმოფხვრის ყველა დამატებით ენტროპიას და ზედმეტობას. მეორეს მხრივ, უნიკოდის მიზანი იყო მაქსიმალურად უნივერსალური კოდირების უზრუნველყოფა. მაგალითად, შეგვიძლია UTF-8-ში კოდირებულ ხაზს მივანდოთ კოდი, რომელიც ადრე მხოლოდ ASCII-ით მუშაობდა და არ გვეშინოდეს, რომ ის დაინახავს სიმბოლოს ASCII დიაპაზონიდან, რომელიც რეალურად არ არის (ბოლოს და ბოლოს, UTF-8-ში ყველა ბაიტი, რომელიც იწყება ნულოვანი ბიტიდან - ეს არის ზუსტად ის, რაც არის ASCII). და თუ მოულოდნელად გვსურს დიდი სიმისგან პატარა კუდის ამოჭრა თავიდანვე მისი გაშიფვრის გარეშე (ან ინფორმაციის ნაწილის აღდგენა დაზიანებული განყოფილების შემდეგ), ჩვენთვის ადვილია ვიპოვოთ ოფსეტი, სადაც პერსონაჟი იწყება (საკმარისია. რომ გამოტოვოთ ბაიტები, რომლებსაც აქვთ ბიტის პრეფიქსი 10).

მაშინ რატომ იგონებ რაიმე ახალს?

ამავდროულად, ზოგჯერ არის სიტუაციები, როდესაც შეკუმშვის ალგორითმები, როგორიცაა deflate, ცუდად გამოიყენება, მაგრამ გსურთ მიაღწიოთ სტრიქონების კომპაქტურ შენახვას. პირადად მე ეს პრობლემა შემხვდა მშენებლობაზე ფიქრისას შეკუმშული პრეფიქსის ხე დიდი ლექსიკონისთვის, რომელშიც შედის სიტყვები თვითნებურ ენებზე. ერთის მხრივ, თითოეული სიტყვა ძალიან მოკლეა, ამიტომ მისი შეკუმშვა არაეფექტური იქნება. მეორეს მხრივ, ხის იმპლემენტაცია, რომელიც მე განვიხილე, ისე იყო შემუშავებული, რომ შენახული სტრიქონის თითოეული ბაიტი წარმოქმნიდა ცალკეულ ხის წვეროს, ამიტომ მათი რაოდენობის შემცირება ძალიან სასარგებლო იყო. ჩემს ბიბლიოთეკაში Az.js (Როგორც პიმორფია2, რომელზედაც ის დაფუძნებულია) მსგავსი პრობლემის გადაჭრა შესაძლებელია უბრალოდ - სტრიქონები შეფუთული DAWG- ლექსიკონი, იქ ინახება კარგი ძველი CP1251. მაგრამ, როგორც ადვილი გასაგებია, ეს კარგად მუშაობს მხოლოდ შეზღუდული ანბანისთვის - ჩინურ ენაზე სტრიქონი არ შეიძლება დაემატოს ასეთ ლექსიკონს.

ცალკე, მინდა აღვნიშნო კიდევ ერთი უსიამოვნო ნიუანსი, რომელიც წარმოიქმნება მონაცემთა ასეთ სტრუქტურაში UTF-8 გამოყენებისას. ზემოთ მოყვანილი სურათი გვიჩვენებს, რომ როდესაც სიმბოლო იწერება როგორც ორი ბაიტი, მის რიცხვთან დაკავშირებული ბიტები არ მოდის ზედიზედ, არამედ გამოყოფილია წყვილი ბიტით. 10 შუაში: 110xxxxx 10xxxxxx. ამის გამო, როდესაც მეორე ბაიტის ქვედა 6 ბიტი გადაედინება სიმბოლოების კოდში (ანუ ხდება გადასვლა 10111111 → 10000000), შემდეგ იცვლება პირველი ბაიტიც. გამოდის, რომ ასო "p" აღინიშნება ბაიტებით 0xD0 0xBF, და შემდეგი "r" უკვე არის 0xD1 0x80. პრეფიქსის ხეში ეს იწვევს მშობელი კვანძის ორად გაყოფას - ერთი პრეფიქსისთვის. 0xD0და მეორე ამისთვის 0xD1 (თუმცა მთელი კირიული ანბანის კოდირება შეიძლებოდა მხოლოდ მეორე ბაიტით).

რა მივიღე

ამ პრობლემის წინაშე გადავწყვიტე ვივარჯიშო ბიტებით თამაშში და ამავდროულად ცოტა უკეთ გავეცნო უნიკოდის სტრუქტურას მთლიანობაში. შედეგი იყო UTF-C კოდირების ფორმატი ("C" for კომპაქტური), რომელიც ხარჯავს არაუმეტეს 3 ბაიტს თითო კოდის წერტილში და ძალიან ხშირად გაძლევთ მხოლოდ დახარჯვის საშუალებას ერთი დამატებითი ბაიტი მთელი კოდირებული ხაზისთვის. ეს მივყავართ იმ ფაქტს, რომ ბევრ არა-ASCII ანბანზე ასეთი კოდირება აღმოჩნდება 30-60% უფრო კომპაქტური ვიდრე UTF-8.

ფორმაში წარმოვადგინე კოდირებისა და დეკოდირების ალგორითმების განხორციელების მაგალითები JavaScript და Go ბიბლიოთეკები, შეგიძლიათ თავისუფლად გამოიყენოთ ისინი თქვენს კოდში. მაგრამ მე მაინც ხაზს ვუსვამ, რომ გარკვეული გაგებით ეს ფორმატი რჩება "ველოსიპედად" და მე არ გირჩევთ მის გამოყენებას იმის გაცნობიერების გარეშე, რატომ გჭირდებათ ეს. ეს ჯერ კიდევ უფრო ექსპერიმენტია, ვიდრე სერიოზული "UTF-8-ის გაუმჯობესება". მიუხედავად ამისა, კოდი იქ არის დაწერილი ლამაზად, მოკლედ, დიდი რაოდენობით კომენტარებითა და ტესტის გაშუქებით.

ტესტის შედეგები და შედარება UTF-8-თან

მეც გავაკეთე დემო გვერდი, სადაც შეგიძლიათ შეაფასოთ ალგორითმის შესრულება, შემდეგ კი უფრო მეტს გეტყვით მის პრინციპებსა და განვითარების პროცესზე.

ზედმეტი ბიტების აღმოფხვრა

რა თქმა უნდა, საფუძვლად ავიღე UTF-8. პირველი და ყველაზე აშკარა, რაც მასში შეიძლება შეიცვალოს არის სერვისის ბიტების რაოდენობის შემცირება თითოეულ ბაიტში. მაგალითად, UTF-8-ში პირველი ბაიტი ყოველთვის იწყება რომელიმეთი 0, ან თან 11 - პრეფიქსი 10 ეს მხოლოდ შემდეგ ბაიტებს აქვთ. მოდით შევცვალოთ პრეფიქსი 11 on 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, არამედ ცვლილებაც მიმდინარე ანბანი on yyyyyy y0000000 (ანუ ჩვენ გვახსოვს ყველა ბიტი, გარდა ყველაზე ნაკლებად მნიშვნელოვანი X სულ ცოტა);
2. ერთი ბაიტი 0xxxxxxx ეს არის მიმდინარე ანბანის ხასიათი. ის უბრალოდ უნდა დაემატოს ოფსეტს, რომელიც გვახსოვდა 1-ელ საფეხურზე. მიუხედავად იმისა, რომ ანბანი არ შევცვალეთ, ოფსეტი არის ნულოვანი, ამიტომ შევინარჩუნეთ თავსებადობა ASCII-თან.

ანალოგიურად კოდებისთვის, რომლებიც საჭიროებენ 3 ბაიტს:

1. სამი ბაიტი 110yyyyy yxxxxxxx xxxxxxxx მიუთითეთ სიმბოლო რიცხვით yyyyyy yxxxxxxx xxxxxxxx, შეცვლა მიმდინარე ანბანი on yyyyyy y0000000 00000000 (ყველაფერი ახსოვდა უმცროსების გარდა X სულ ცოტა) და შეამოწმეთ ყუთი, რომელშიც ახლა ვართ გრძელი რეჟიმი (ანბანის ორბაიტიანზე გადაბრუნებისას, ჩვენ აღვადგენთ ამ დროშას);
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-ზე დაბრუნებას, მაგრამ ამის შემდეგ მივიღებთ ბევრ არა-ASCII სიმბოლოს დამატებითი ანბანიდან, გარეშე ხელახლა გადართვა).

ბონუსი: ქვეანბანის პრეფიქსი 11xxxxxx და ვირჩევთ მის თავდაპირველ კომპენსირებას 0xC0, ჩვენ ვიღებთ ნაწილობრივ თავსებადობას CP1252-თან. სხვა სიტყვებით რომ ვთქვათ, ბევრი (მაგრამ არა ყველა) დასავლეთ ევროპის ტექსტი, რომელიც კოდირებულია CP1252-ში, ერთნაირად გამოიყურება UTF-C-ში.

თუმცა, აქ ჩნდება სირთულე: როგორ მივიღოთ დამხმარე ძირითადი ანბანიდან? თქვენ შეგიძლიათ დატოვოთ იგივე ოფსეტი, მაგრამ - სამწუხაროდ - აქ Unicode სტრუქტურა უკვე თამაშობს ჩვენს წინააღმდეგ. ძალიან ხშირად ანბანის ძირითადი ნაწილი არ არის ბლოკის დასაწყისში (მაგალითად, რუსეთის დედაქალაქ "A"-ს აქვს კოდი 0x0410, თუმცა კირიული ბლოკი იწყება 0x0400). ამრიგად, პირველი 64 სიმბოლოს შენახვაში, ჩვენ შეიძლება დავკარგოთ წვდომა ანბანის კუდის ნაწილზე.

ამ პრობლემის გადასაჭრელად, მე ხელით გავიარე რამდენიმე ბლოკი, რომელიც შეესაბამება სხვადასხვა ენას და დავაფიქსირე დამხმარე ანბანის ოფსეტი მათთვის მთავარში. ლათინური ანბანი, როგორც გამონაკლისი, ზოგადად გადალაგდა, როგორც ბაზა64.

საბოლოო შეხება

მოდი საბოლოოდ ვიფიქროთ იმაზე, სად შეიძლება კიდევ გავაუმჯობესოთ რამე.

გაითვალისწინეთ, რომ ფორმატი 101xxxxx xxxxxxxx xxxxxxxx საშუალებას გაძლევთ დაშიფვროთ რიცხვები მდე 0x1FFFFFდა Unicode მთავრდება ადრე, ზე 0x10FFFF. სხვა სიტყვებით რომ ვთქვათ, ბოლო კოდის წერტილი წარმოდგენილი იქნება როგორც 10110000 11111111 11111111. აქედან გამომდინარე, შეგვიძლია ვთქვათ, რომ თუ პირველი ბაიტი ფორმისაა 1011xxxx (სად xxxx 0-ზე მეტი), მაშინ ეს სხვა რამეს ნიშნავს. მაგალითად, იქ შეგიძლიათ დაამატოთ კიდევ 15 სიმბოლო, რომლებიც მუდმივად ხელმისაწვდომია კოდირებისთვის ერთ ბაიტში, მაგრამ მე გადავწყვიტე სხვაგვარად გამეკეთებინა.

მოდით შევხედოთ უნიკოდის იმ ბლოკებს, რომლებსაც სამი ბაიტი სჭირდებათ. ძირითადად, როგორც უკვე აღვნიშნეთ, ეს ჩინური სიმბოლოა - მაგრამ ძნელია მათთან რაიმეს გაკეთება, მათგან 21 ათასია. მაგრამ ჰირაგანა და კატაკანაც იქ გაფრინდნენ - და მათგან არც ისე ბევრია, ორასზე ნაკლები. და, რადგან იაპონელები გავიხსენეთ, არის ემოჯიც (სინამდვილეში, ისინი უნიკოდში ბევრგან არიან მიმოფანტული, მაგრამ ძირითადი ბლოკები დიაპაზონშია. 0x1F300 - 0x1FBFF). თუ ფიქრობთ იმაზე, რომ ახლა არის ემოციები, რომლებიც აწყობილია რამდენიმე კოდის წერტილიდან ერთდროულად (მაგალითად, emoji შედგება 7 კოდისგან!), მაშინ სრული სირცხვილია თითოეულზე სამი ბაიტის დახარჯვა (7×3 = 21 ბაიტი ერთი ხატის, კოშმარის გულისთვის).

აქედან გამომდინარე, ჩვენ ვირჩევთ რამდენიმე შერჩეულ დიაპაზონს, რომლებიც შეესაბამება emoji-ს, hiragana-ს და კატაკანას, გადავნომრავთ მათ ერთ უწყვეტ სიაში და დაშიფრავთ მათ, როგორც ორი ბაიტის ნაცვლად სამი:

1011xxxx xxxxxxxx

შესანიშნავია: ზემოაღნიშნული emoji, რომელიც შედგება 7 კოდის წერტილისგან, იღებს 8 ბაიტს UTF-25-ში და ჩვენ ვჯდებით მასში 14 (ზუსტად ორი ბაიტი თითოეული კოდის წერტილისთვის). სხვათა შორის, ჰაბრმა უარი თქვა მის მონელებაზე (როგორც ძველ, ასევე ახალ რედაქტორში), ამიტომ მომიწია სურათის ჩასმა.

შევეცადოთ გამოვასწოროთ კიდევ ერთი პრობლემა. როგორც გვახსოვს, ძირითადი ანბანი არსებითად არის მაღალი 6 ბიტი, რომელსაც მხედველობაში ვიტოვებთ და ვაწებებთ ყოველი მომდევნო დეკოდირებული სიმბოლოს კოდს. ჩინური სიმბოლოების შემთხვევაში, რომლებიც ბლოკშია 0x4E00 - 0x9FFFეს არის ბიტი 0 ან 1. ეს არ არის ძალიან მოსახერხებელი: ჩვენ დაგვჭირდება მუდმივად გადართვა ანბანი ამ ორ მნიშვნელობას შორის (ანუ სამი ბაიტის დახარჯვა). მაგრამ გაითვალისწინეთ, რომ გრძელ რეჟიმში, თავად კოდიდან შეგვიძლია გამოვაკლოთ სიმბოლოების რაოდენობა, რომლებსაც დავშიფვრავთ მოკლე რეჟიმის გამოყენებით (ზემოთ აღწერილი ყველა ხრიკის შემდეგ, ეს არის 10240) - შემდეგ იეროგლიფების დიაპაზონი გადავა 0x2600 - 0x77FFდა ამ შემთხვევაში, მთელ ამ დიაპაზონში, ყველაზე მნიშვნელოვანი 6 ბიტი (21-დან) იქნება 0-ის ტოლი. ამრიგად, იეროგლიფების თანმიმდევრობა გამოიყენებს ორ ბაიტს თითო იეროგლიფზე (რაც ოპტიმალურია ასეთი დიდი დიაპაზონისთვის), გარეშე. ანბანის გადართვის გამომწვევი.

ალტერნატიული გადაწყვეტილებები: SCSU, BOCU-1

უნიკოდის ექსპერტები, ახლახან წაიკითხეს სტატიის სათაური, სავარაუდოდ, სასწრაფოდ შეგახსენებთ, რომ უშუალოდ უნიკოდის სტანდარტებს შორის არის სტანდარტული შეკუმშვის სქემა უნიკოდისთვის (SCSU), რომელიც აღწერს კოდირების მეთოდს, რომელიც ძალიან ჰგავს სტატიაში აღწერილი.

გულწრფელად ვაღიარებ: მისი არსებობის შესახებ მხოლოდ მას შემდეგ გავიგე, რაც ღრმად ჩავუღრმავდი ჩემი გადაწყვეტილების წერას. თავიდანვე რომ მცოდნოდა ამის შესახებ, ალბათ შევეცდებოდი დამეწერა იმპლემენტაცია, იმის ნაცვლად, რომ საკუთარი მიდგომა გამომემუშავებინა.

საინტერესო ის არის, რომ SCSU იყენებს იდეებს ძალიან მსგავს იდეებს, რაც მე თვითონ მოვიგონე („ანბანის“ ცნების ნაცვლად ისინი იყენებენ „ფანჯრებს“ და მათზე მეტია ხელმისაწვდომი, ვიდრე მე მაქვს). ამავდროულად, ამ ფორმატს აქვს უარყოფითი მხარეები: ის ოდნავ უფრო ახლოს არის შეკუმშვის ალგორითმებთან, ვიდრე კოდირების. კერძოდ, სტანდარტი იძლევა მრავალი წარმოდგენის მეთოდს, მაგრამ არ ამბობს, თუ როგორ უნდა აირჩიოთ ოპტიმალური - ამისათვის კოდირმა უნდა გამოიყენოს რაიმე სახის ევრისტიკა. ამრიგად, SCSU შიფრატორი, რომელიც აწარმოებს კარგ შეფუთვას, უფრო რთული და რთული იქნება, ვიდრე ჩემი ალგორითმი.

შედარებისთვის, მე გადავეცი SCSU-ს შედარებით მარტივი იმპლემენტაცია JavaScript-ზე - კოდის მოცულობის თვალსაზრისით, ის შედარებული იყო ჩემს UTF-C-სთან, მაგრამ ზოგიერთ შემთხვევაში შედეგი ათობით პროცენტით უარესი იყო (ზოგჯერ შეიძლება გადააჭარბოს მას, მაგრამ დიდად არა). მაგალითად, ტექსტები ებრაულ და ბერძნულ ენებზე იყო კოდირებული UTF-C-ით 60%-ით უკეთესი ვიდრე SCSU (ალბათ მათი კომპაქტური ანბანის გამო).

ცალკე, დავამატებ, რომ SCSU-ს გარდა, ასევე არსებობს უნიკოდის კომპაქტური წარმოდგენის კიდევ ერთი გზა - BOCU-1, მაგრამ ის მიზნად ისახავს MIME თავსებადობას (რაც არ მჭირდებოდა) და ოდნავ განსხვავებულ მიდგომას იღებს კოდირების მიმართ. მე არ შევაფასე მისი ეფექტურობა, მაგრამ მეჩვენება, რომ ნაკლებად სავარაუდოა, რომ ის უფრო მაღალი იყოს ვიდრე SCSU.

შესაძლო გაუმჯობესებები

ალგორითმი, რომელიც წარმოვადგინე, არ არის უნივერსალური დიზაინით (ეს არის ალბათ, სადაც ჩემი მიზნები ყველაზე მეტად განსხვავდება Unicode Consortium-ის მიზნებისგან). მე უკვე აღვნიშნე, რომ იგი შემუშავდა ძირითადად ერთი ამოცანისთვის (მრავალენოვანი ლექსიკონის შენახვა პრეფიქსის ხეში) და მისი ზოგიერთი ფუნქცია შეიძლება არ იყოს კარგად მორგებული სხვა ამოცანებისთვის. მაგრამ ის, რომ ეს არ არის სტანდარტი, შეიძლება იყოს პლუსი - თქვენ შეგიძლიათ მარტივად შეცვალოთ იგი თქვენს საჭიროებებზე.

მაგალითად, აშკარად შეგიძლიათ თავიდან აიცილოთ სახელმწიფოს არსებობა, გააკეთოთ მოქალაქეობის არმქონე კოდირება - უბრალოდ არ განაახლოთ ცვლადები 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 სიმბოლოდან). ამ შემთხვევაში, თქვენ უნდა იფიქროთ შეკუმშვის ალგორითმების გამოყენებაზე, როგორიცაა deflate.
• Თუ გჭირდება ASCII გამჭვირვალობა, ანუ თქვენთვის მნიშვნელოვანია, რომ დაშიფრული თანმიმდევრობები არ შეიცავდეს ASCII კოდებს, რომლებიც არ იყო თავდაპირველ სტრიქონში. ამის საჭიროების თავიდან აცილება შესაძლებელია, თუ მესამე მხარის API-ებთან ურთიერთობისას (მაგალითად, მონაცემთა ბაზასთან მუშაობისას), თქვენ გადასცემთ კოდირების შედეგს, როგორც ბაიტების აბსტრაქტულ კომპლექტს და არა როგორც სტრიქონებს. წინააღმდეგ შემთხვევაში, თქვენ რისკავთ მოულოდნელი დაუცველობის მიღებას.
• თუ გსურთ სწრაფად იპოვოთ სიმბოლოების საზღვრები თვითნებური ოფსეტურით (მაგალითად, როდესაც ხაზის ნაწილი დაზიანებულია). ეს შეიძლება გაკეთდეს, მაგრამ მხოლოდ ხაზის თავიდან სკანირებით (ან წინა ნაწილში აღწერილი მოდიფიკაციის გამოყენებით).
• თუ საჭიროა სტრიქონების შიგთავსზე ოპერაციების სწრაფად შესრულება (დახარისხება, მათში ქვესტრიქონების ძიება, შეერთება). ამისათვის საჭიროა სტრიქონების გაშიფვრა ჯერ, ამიტომ UTF-C ამ შემთხვევებში უფრო ნელი იქნება ვიდრე UTF-8 (მაგრამ უფრო სწრაფი ვიდრე შეკუმშვის ალგორითმები). ვინაიდან ერთი და იგივე სტრიქონი ყოველთვის ერთნაირად არის კოდირებული, დეკოდირების ზუსტი შედარება არ არის საჭირო და შეიძლება გაკეთდეს ბაიტი-ბაიტი საფუძველზე.

განახლების თარიღი: მომხმარებელი ტიომიჩი ქვემოთ მოცემულ კომენტარებში გამოაქვეყნა გრაფიკი, რომელიც ხაზს უსვამს UTF-C-ის გამოყენების ლიმიტებს. ის აჩვენებს, რომ UTF-C უფრო ეფექტურია ვიდრე ზოგადი დანიშნულების შეკუმშვის ალგორითმი (LZW-ის ვარიაცია), სანამ შეფუთული სტრიქონი უფრო მოკლეა. ~ 140 სიმბოლო (თუმცა, აღვნიშნავ, რომ შედარება განხორციელდა ერთ ტექსტზე; სხვა ენებისთვის შედეგი შეიძლება განსხვავდებოდეს).


წყარო: www.habr.com