Als u een ontwikkelaar bent en voor de taak staat een codering te kiezen, dan is Unicode vrijwel altijd de juiste oplossing. De specifieke representatiemethode hangt af van de context, maar meestal is er ook hier een universeel antwoord: UTF-8. Het goede eraan is dat je alle Unicode-tekens kunt gebruiken zonder geld uit te geven te veel in de meeste gevallen veel bytes. Toegegeven, voor talen die meer dan alleen het Latijnse alfabet gebruiken, is dat in ieder geval ‘niet te veel’ twee bytes per teken. Kunnen we het beter doen zonder terug te keren naar prehistorische coderingen die ons beperken tot slechts 256 beschikbare karakters?
Hieronder stel ik voor om vertrouwd te raken met mijn poging om deze vraag te beantwoorden en een relatief eenvoudig algoritme te implementeren waarmee je regels in de meeste talen van de wereld kunt opslaan zonder de redundantie toe te voegen die in UTF-8 zit.
Vrijwaring. Ik maak meteen een paar belangrijke voorbehouden: de beschreven oplossing wordt niet aangeboden als universele vervanging voor UTF-8, het is alleen geschikt in een beperkt aantal gevallen (meer daarover hieronder), en mag in geen geval worden gebruikt voor interactie met API's van derden (die er niet eens van op de hoogte zijn). Meestal zijn compressiealgoritmen voor algemene doeleinden (bijvoorbeeld deflate) geschikt voor de compacte opslag van grote hoeveelheden tekstgegevens. Bovendien vond ik al tijdens het maken van mijn oplossing een bestaande standaard in Unicode zelf, die hetzelfde probleem oplost - het is iets ingewikkelder (en vaak erger), maar toch is het een geaccepteerde standaard, en niet alleen maar samen op de knie. Ik zal je ook over hem vertellen.
Over Unicode en UTF-8
Om te beginnen een paar woorden over wat het is Unicode и UTF-8.
Zoals u weet waren 8-bits coderingen populair. Bij hen was alles eenvoudig: 256 tekens kunnen worden genummerd met getallen van 0 tot 255, en getallen van 0 tot 255 kunnen uiteraard worden weergegeven als één byte. Als we teruggaan naar het allereerste begin, is de ASCII-codering volledig beperkt tot 7 bits, dus de meest significante bit in de byteweergave is nul, en de meeste 8-bits coderingen zijn ermee compatibel (ze verschillen alleen in de “bovenste” deel, waarbij het meest significante bit één is).
Hoe verschilt Unicode van deze coderingen en waarom zijn er zoveel specifieke representaties aan verbonden - UTF-8, UTF-16 (BE en LE), UTF-32? Laten we het in volgorde regelen.
De basis Unicode-standaard beschrijft alleen de correspondentie tussen karakters (en in sommige gevallen individuele componenten van karakters) en hun cijfers. En er zijn veel mogelijke cijfers in deze standaard - van 0x00 naar 0x10FFFF (1 stuks). Als we een getal in een dergelijk bereik in een variabele zouden willen stoppen, zouden noch 114 noch 112 bytes genoeg voor ons zijn. En aangezien onze processors niet erg ontworpen zijn om met getallen van drie bytes te werken, zouden we gedwongen zijn om maar liefst 1 bytes per teken te gebruiken! Dit is UTF-2, maar juist vanwege deze “verspilling” is dit formaat niet populair.
Gelukkig is de volgorde van tekens binnen Unicode niet willekeurig. Hun hele set is verdeeld in 17 "vliegtuigen", die elk 65536 bevatten (0x10000) «codepunten" Het concept van een “codepunt” is hier eenvoudig teken nummer, eraan toegewezen door Unicode. Maar zoals hierboven vermeld, zijn in Unicode niet alleen individuele karakters genummerd, maar ook hun componenten en dienstmerken (en soms komt helemaal niets overeen met het nummer - misschien voorlopig, maar voor ons is dit niet zo belangrijk), dus het is juister om altijd specifiek over het aantal cijfers zelf te praten, en niet over symbolen. In het volgende zal ik echter kortheidshalve vaak het woord “symbool” gebruiken, waarmee ik de term “codepunt” impliceer.
Unicode-vlakken. Zoals je kunt zien, is het grootste deel (vliegtuigen 4 tot en met 13) nog steeds ongebruikt.
Het meest opmerkelijke is dat alle belangrijke “pulp” in het nulvlak ligt, dit wordt "Basis meertalig vliegtuig". Als een regel tekst bevat in een van de moderne talen (inclusief Chinees), kom je niet verder dan dit vlak. Maar je kunt de rest van Unicode ook niet afsnijden - emoji bevinden zich bijvoorbeeld voornamelijk aan het einde van het volgende vliegtuig,"Aanvullend meertalig vliegtuig"(Het strekt zich uit van 0x10000 naar 0x1FFFF). Dus UTF-16 doet dit: alle karakters die erin vallen Basis meertalig vliegtuig, worden gecodeerd “zoals ze zijn” met een bijbehorend nummer van twee bytes. Sommige getallen in dit bereik duiden echter helemaal niet op specifieke tekens, maar geven aan dat we na dit paar bytes nog een ander moeten overwegen - door de waarden van deze vier bytes samen te combineren, krijgen we een getal dat dekt het volledige geldige Unicode-bereik. Dit idee wordt ‘surrogaatkoppels’ genoemd; misschien heb je er wel eens van gehoord.
UTF-16 vereist dus twee of (in zeer zeldzame gevallen) vier bytes per "codepunt". Dit is beter dan de hele tijd vier bytes te gebruiken, maar Latijnse (en andere ASCII-tekens) verspillen, wanneer ze op deze manier worden gecodeerd, de helft van de ruimte aan nullen. UTF-8 is ontworpen om dit te corrigeren: ASCII neemt daarin, net als voorheen, slechts één byte in beslag; codes van 0x80 naar 0x7FF - twee bytes; van 0x800 naar 0xFFFF - drie, en van 0x10000 naar 0x10FFFF - vier. Aan de ene kant is het Latijnse alfabet goed geworden: de compatibiliteit met ASCII is teruggekeerd en de verdeling is gelijkmatiger "verspreid" van 1 naar 4 bytes. Maar andere alfabetten dan het Latijn profiteren helaas op geen enkele manier van UTF-16, en velen hebben nu drie bytes nodig in plaats van twee. Het bereik dat wordt gedekt door een record van twee bytes is 32 keer kleiner geworden, met 0xFFFF naar 0x7FF, en noch Chinees, noch bijvoorbeeld Georgisch zijn daarin opgenomen. Cyrillisch en vijf andere alfabetten - hoera - geluk, 2 bytes per teken.
Waarom gebeurt dit? Laten we eens kijken hoe UTF-8 tekencodes vertegenwoordigt:
Direct om getallen weer te geven, worden hier bits gebruikt die zijn gemarkeerd met het symbool x. Het is te zien dat er in een record van twee bytes slechts 11 van dergelijke bits zijn (van de 16). De leidende bits hebben hier slechts een hulpfunctie. In het geval van een record van vier bytes worden 21 van de 32 bits toegewezen voor het codepuntnummer - het lijkt erop dat drie bytes (die in totaal 24 bits opleveren) voldoende zouden zijn, maar servicemarkeringen vreten te veel op.
Is dit erg? Niet echt. Aan de ene kant, als we veel om de ruimte geven, hebben we compressie-algoritmen die gemakkelijk alle extra entropie en redundantie kunnen elimineren. Aan de andere kant was het doel van Unicode om een zo universeel mogelijke codering te bieden. We kunnen bijvoorbeeld een in UTF-8 gecodeerde regel toevertrouwen aan code die voorheen alleen met ASCII werkte, en niet bang zijn dat hij een teken uit het ASCII-bereik te zien krijgt dat er eigenlijk niet is (in UTF-8 zijn immers alle bytes beginnend met de nulbit - dit is precies wat ASCII is). En als we plotseling een kleine staart van een grote reeks willen afsnijden zonder deze vanaf het allereerste begin te decoderen (of een deel van de informatie te herstellen na een beschadigd gedeelte), kunnen we gemakkelijk de offset vinden waar een teken begint (het is voldoende om bytes met een bitvoorvoegsel over te slaan 10).
Waarom dan iets nieuws bedenken?
Tegelijkertijd zijn er af en toe situaties waarin compressie-algoritmen zoals deflate slecht toepasbaar zijn, maar u compacte opslag van tekenreeksen wilt bereiken. Persoonlijk kwam ik dit probleem tegen toen ik nadacht over bouwen voor een groot woordenboek met woorden in willekeurige talen. Aan de ene kant is elk woord erg kort, dus het comprimeren ervan zal niet effectief zijn. Aan de andere kant was de boomimplementatie die ik overwoog zo ontworpen dat elke byte van de opgeslagen string een afzonderlijk boompunt genereerde, dus het minimaliseren van hun aantal was erg nuttig. In mijn bibliotheek (Als in , waarop het is gebaseerd) kan een soortgelijk probleem eenvoudig worden opgelost door strings in te pakken -woordenboek, daarin opgeslagen . Maar zoals gemakkelijk te begrijpen is, werkt dit alleen goed voor een beperkt alfabet: aan zo'n woordenboek kan geen regel in het Chinees worden toegevoegd.
Afzonderlijk zou ik nog een onaangename nuance willen opmerken die ontstaat bij het gebruik van UTF-8 in een dergelijke datastructuur. De afbeelding hierboven laat zien dat wanneer een teken als twee bytes wordt geschreven, de bits die verband houden met het nummer niet op een rij komen, maar worden gescheiden door een paar bits 10 middenin: 110xxxxx 10xxxxxx. Hierdoor, wanneer de onderste 6 bits van de tweede byte overlopen in de tekencode (d.w.z. er vindt een overgang plaats 10111111 → 10000000), dan verandert de eerste byte ook. Het blijkt dat de letter "p" wordt aangegeven met bytes 0xD0 0xBF, en de volgende “r” is al 0xD1 0x80. In een prefixboom leidt dit tot het splitsen van het ouderknooppunt in twee - één voor het prefix 0xD0, en nog een voor 0xD1 (hoewel het hele Cyrillische alfabet alleen door de tweede byte kan worden gecodeerd).
Wat heb ik gekregen
Geconfronteerd met dit probleem besloot ik te oefenen met het spelen van games met bits, en tegelijkertijd wat beter bekend te raken met de structuur van Unicode als geheel. Het resultaat was het UTF-C-coderingsformaat ("C" voor compact), dat niet meer dan 3 bytes per codepunt besteedt, en u vaak alleen maar kunt uitgeven één extra byte voor de gehele gecodeerde regel. Dit leidt ertoe dat een dergelijke codering op veel niet-ASCII-alfabetten blijkt te zijn 30-60% compacter dan UTF-8.
Ik heb voorbeelden gepresenteerd van de implementatie van coderings- en decoderingsalgoritmen in het formulier , kunt u ze vrijelijk in uw code gebruiken. Maar ik zal nog steeds benadrukken dat dit formaat in zekere zin een “fiets” blijft, en ik raad het gebruik ervan niet aan zonder te beseffen waarom je het nodig hebt. Dit is nog steeds meer een experiment dan een serieuze “verbetering van UTF-8”. Niettemin is de code daar netjes en beknopt geschreven, met een groot aantal opmerkingen en testdekking.
Testresultaten en vergelijking met UTF-8
Dat deed ik ook , waar u de prestaties van het algoritme kunt evalueren, en dan zal ik u meer vertellen over de principes en het ontwikkelingsproces ervan.
Het elimineren van overtollige bits
Ik heb uiteraard UTF-8 als basis genomen. Het eerste en meest voor de hand liggende dat daarin kan worden veranderd, is het verminderen van het aantal servicebits in elke byte. De eerste byte in UTF-8 begint bijvoorbeeld altijd met een van beide 0, of met 11 - een voorvoegsel 10 Alleen de volgende bytes hebben dit. Laten we het voorvoegsel vervangen 11 op 1, en voor de volgende bytes zullen we de voorvoegsels volledig verwijderen. Wat zal er gebeuren?
0xxxxxxx — 1 byte
10xxxxxx xxxxxxxx - 2 bytes
110xxxxx xxxxxxxx xxxxxxxx - 3 bytes
Wacht, waar is het record van vier bytes? Maar dat is niet meer nodig - bij het schrijven in drie bytes hebben we nu 21 bits beschikbaar en dit is voldoende voor alle getallen tot en met 0x10FFFF.
Wat hebben we hier opgeofferd? Het allerbelangrijkste is de detectie van karaktergrenzen vanaf een willekeurige locatie in de buffer. We kunnen niet naar een willekeurige byte wijzen en daaruit het begin van het volgende teken vinden. Dit is een beperking van ons format, maar in de praktijk is dit zelden nodig. Meestal kunnen we vanaf het begin de buffer doornemen (vooral als het om korte lijnen gaat).
De situatie met het bedekken van talen met 2 bytes is ook beter geworden: nu geeft het twee-byte-formaat een bereik van 14 bits, en dit zijn codes tot 0x3FFF. De Chinezen hebben pech (hun karakters variëren meestal van 0x4E00 naar 0x9FFF), maar Georgiërs en veel andere mensen hebben meer plezier - hun talen passen ook in 2 bytes per teken.
Voer de encoderstatus in
Laten we nu nadenken over de eigenschappen van de lijnen zelf. Het woordenboek bevat meestal woorden die in karakters van hetzelfde alfabet zijn geschreven, en dit geldt ook voor veel andere teksten. Het zou goed zijn om dit alfabet één keer aan te geven en dan alleen het nummer van de letter erin aan te geven. Laten we eens kijken of de rangschikking van tekens in de Unicode-tabel ons zal helpen.
Zoals hierboven vermeld, is Unicode onderverdeeld in vliegtuig Elk 65536 codes. Maar dit is geen erg bruikbare indeling (zoals al gezegd, meestal bevinden we ons in het nulvlak). Interessanter is de deling door blokken. Deze bereiken hebben niet langer een vaste lengte en zijn betekenisvoller: in de regel combineert elk karakters uit hetzelfde alfabet.
Een blok met tekens uit het Bengaalse alfabet. Helaas is dit om historische redenen een voorbeeld van een niet erg compacte verpakking: 96 tekens zijn chaotisch verspreid over 128 blokcodepunten.
Het begin van blokken en hun afmetingen zijn altijd veelvouden van 16 - dit wordt eenvoudig voor het gemak gedaan. Bovendien beginnen en eindigen veel blokken met waarden die een veelvoud zijn van 128 of zelfs 256. Het standaard Cyrillische alfabet neemt bijvoorbeeld 256 bytes in beslag. 0x0400 naar 0x04FF. Dit is best handig: als we het voorvoegsel één keer opslaan 0x04, dan kan elk Cyrillisch teken in één byte worden geschreven. Het is waar dat we op deze manier de kans verliezen om terug te keren naar ASCII (en naar andere karakters in het algemeen). Daarom doen wij dit:
- Twee bytes
10yyyyyy yxxxxxxxniet alleen een symbool met een getal aanduidenyyyyyy yxxxxxxx, maar ook veranderen huidige alfabet opyyyyyy y0000000(dat wil zeggen: we onthouden alle bits behalve de minst significante 7 bit); - Eén byte
0xxxxxxxdit is het karakter van het huidige alfabet. Het hoeft alleen maar te worden opgeteld bij de offset die we in stap 1 hebben onthouden. Hoewel we het alfabet niet hebben gewijzigd, is de offset nul, dus we behouden de compatibiliteit met ASCII.
Hetzelfde geldt voor codes die 3 bytes vereisen:
- Drie bytes
110yyyyy yxxxxxxx xxxxxxxxgeef een symbool aan met een nummeryyyyyy yxxxxxxx xxxxxxxx, wijziging huidige alfabet opyyyyyy y0000000 00000000(onthield alles behalve de jongeren 15 bit), en vink het vakje aan waarin we ons nu bevinden lang modus (wanneer we het alfabet terugzetten naar een dubbelbyte-alfabet, zullen we deze vlag resetten); - Twee bytes
0xxxxxxx xxxxxxxxin de lange modus is dit het karakter van het huidige alfabet. Op dezelfde manier voegen we het toe met de offset uit stap 1. Het enige verschil is dat we nu twee bytes lezen (omdat we naar deze modus zijn overgeschakeld).
Klinkt goed: terwijl we nu tekens uit hetzelfde 7-bits Unicode-bereik moeten coderen, besteden we aan het begin 1 extra byte en een totaal van één byte per teken.
Werken vanuit een van de eerdere versies. Het verslaat vaak al UTF-8, maar er is nog ruimte voor verbetering.
Wat is erger? Ten eerste hebben we een voorwaarde, namelijk huidige alfabetverschuiving en selectievakje lange modus. Dit beperkt ons verder: nu kunnen dezelfde karakters in verschillende contexten anders worden gecodeerd. Het zoeken naar substrings zal bijvoorbeeld hiermee rekening moeten houden, en niet alleen door bytes te vergelijken. Ten tweede, zodra we het alfabet veranderden, werd het slecht met de codering van ASCII-tekens (en dit is niet alleen het Latijnse alfabet, maar ook basisinterpunctie, inclusief spaties) - ze vereisen dat het alfabet opnieuw wordt gewijzigd naar 0, dat wil zeggen: opnieuw een extra byte (en dan nog een om terug te keren naar ons hoofdpunt).
Eén alfabet is goed, twee is beter
Laten we proberen onze bitvoorvoegsels een beetje te veranderen, door er nog een in te drukken in de drie hierboven beschreven:
0xxxxxxx — 1 byte in normale modus, 2 in lange modus
11xxxxxx — 1 byte
100xxxxx xxxxxxxx - 2 bytes
101xxxxx xxxxxxxx xxxxxxxx - 3 bytes
Nu is er in een record van twee bytes één bit minder beschikbaar - de code wijst naar 0x1FFFEn niet 0x3FFF. Het is echter nog steeds merkbaar groter dan in dubbel-byte UTF-8-codes, de meeste gangbare talen passen er nog steeds in, het meest opvallende verlies is eruit gevallen и , de Japanners zijn verdrietig.
Wat is deze nieuwe code? 11xxxxxx? Dit is een kleine "voorraad" van 64 tekens groot, het is een aanvulling op ons hoofdalfabet, dus ik noemde het hulp(hulp-) alfabet. Wanneer we het huidige alfabet veranderen, wordt een stukje van het oude alfabet een hulpstuk. We zijn bijvoorbeeld overgestapt van ASCII naar Cyrillisch - de voorraad bevat nu 64 tekens met daarin Latijns alfabet, cijfers, spatie en komma (meest voorkomende invoegingen in niet-ASCII-teksten). Schakel terug naar ASCII - en het grootste deel van het Cyrillische alfabet wordt het hulpalfabet.
Dankzij de toegang tot twee alfabetten kunnen we een groot aantal teksten verwerken met minimale kosten voor het wisselen van alfabet (interpunctie zal meestal leiden tot een terugkeer naar ASCII, maar daarna zullen we veel niet-ASCII-tekens uit het extra alfabet halen, zonder weer overstappen).
Bonus: voorvoegsel van het subalfabet 11xxxxxx en het kiezen van de initiële offset 0xC0, krijgen we gedeeltelijke compatibiliteit met CP1252. Met andere woorden: veel (maar niet alle) West-Europese teksten gecodeerd in CP1252 zullen er hetzelfde uitzien in UTF-C.
Hier doet zich echter een probleem voor: hoe kun je een hulpalfabet uit het hoofdalfabet verkrijgen? Je kunt dezelfde offset laten staan, maar helaas speelt de Unicode-structuur hier al tegen ons. Heel vaak staat het grootste deel van het alfabet niet aan het begin van het blok (de Russische hoofdletter “A” heeft bijvoorbeeld de code 0x0410, hoewel het Cyrillische blok begint met 0x0400). Dus nadat we de eerste 64 tekens in de voorraad hebben opgenomen, verliezen we mogelijk de toegang tot het laatste deel van het alfabet.
Om dit probleem op te lossen, heb ik handmatig enkele blokken doorgenomen die overeenkomen met verschillende talen, en de verschuiving van het hulpalfabet binnen het hoofdalfabet voor hen gespecificeerd. Het Latijnse alfabet werd, bij wijze van uitzondering, over het algemeen opnieuw gerangschikt zoals base64.
Laatste hand
Laten we eindelijk eens nadenken over waar we nog iets kunnen verbeteren.
Houd er rekening mee dat het formaat 101xxxxx xxxxxxxx xxxxxxxx Hiermee kunt u getallen coderen tot 0x1FFFFF, en Unicode eindigt eerder, om 0x10FFFF. Met andere woorden, het laatste codepunt wordt weergegeven als 10110000 11111111 11111111. Daarom kunnen we zeggen dat als de eerste byte de vorm heeft 1011xxxx (Waar xxxx groter dan 0), dan betekent het iets anders. Je kunt daar bijvoorbeeld nog eens 15 tekens toevoegen die constant beschikbaar zijn voor codering in één byte, maar ik besloot het anders te doen.
Laten we eens kijken naar de Unicode-blokken die nu drie bytes nodig hebben. Kortom, zoals reeds vermeld, zijn dit Chinese karakters - maar het is moeilijk om er iets mee te doen, er zijn er 21 duizend. Maar hiragana en katakana vlogen daar ook - en er zijn er niet zo veel meer, minder dan tweehonderd. En sinds we ons de Japanners herinnerden, zijn er ook emoji's (in feite zijn ze op veel plaatsen verspreid in Unicode, maar de hoofdblokken bevinden zich in het bereik 0x1F300 - 0x1FBFF). Als je bedenkt dat er nu emoji's zijn die uit verschillende codepunten tegelijk zijn samengesteld (bijvoorbeeld de emoji bestaat uit maar liefst 7 codes!), dan wordt het zonde om drie bytes aan elk te besteden (7×3 = 21 bytes omwille van één pictogram, een nachtmerrie).
Daarom selecteren we een paar geselecteerde bereiken die overeenkomen met emoji, hiragana en katakana, hernummeren ze tot één doorlopende lijst en coderen ze als twee bytes in plaats van drie:
1011xxxx xxxxxxxx
Leuk: de eerder genoemde emoji, bestaande uit 7 codepunten, neemt 8 bytes in beslag in UTF-25, en we passen het erin 14 (precies twee bytes voor elk codepunt). Trouwens, Habr weigerde het te verwerken (zowel in de oude als in de nieuwe editor), dus moest ik het met een afbeelding invoegen.
Laten we proberen nog een probleem op te lossen. Zoals we ons herinneren, is het basisalfabet in wezen hoog 6 bits, die we in gedachten houden en aan de code van elk volgend gedecodeerd symbool plakken. In het geval van Chinese karakters die in het blok staan 0x4E00 - 0x9FFF, dit is bit 0 of 1. Dit is niet erg handig: we zullen het alfabet voortdurend tussen deze twee waarden moeten schakelen (d.w.z. drie bytes uitgeven). Maar houd er rekening mee dat we in de lange modus van de code zelf het aantal tekens kunnen aftrekken dat we coderen met behulp van de korte modus (na alle hierboven beschreven trucs is dit 10240) - dan zal het bereik van hiërogliefen verschuiven naar 0x2600 - 0x77FF, en in dit geval zullen over dit hele bereik de meest significante 6 bits (van de 21) gelijk zijn aan 0. Reeksen hiërogliefen zullen dus twee bytes per hiëroglief gebruiken (wat optimaal is voor zo'n groot bereik), zonder alfabetwisselingen veroorzaken.
Alternatieve oplossingen: SCSU, BOCU-1
Unicode-experts, die zojuist de titel van het artikel hebben gelezen, zullen zich hoogstwaarschijnlijk haasten om u eraan te herinneren dat er direct onder de Unicode-standaarden (SCSU), die een coderingsmethode beschrijft die sterk lijkt op die beschreven in het artikel.
Ik geef eerlijk toe: ik hoorde pas van het bestaan ervan nadat ik diep verdiept was in het schrijven van mijn beslissing. Als ik het vanaf het begin had geweten, had ik waarschijnlijk geprobeerd een implementatie te schrijven in plaats van met mijn eigen aanpak te komen.
Wat interessant is, is dat SCSU ideeën gebruikt die erg lijken op de ideeën die ik zelf heb bedacht (in plaats van het concept van "alfabetten" gebruiken ze "vensters", en er zijn er meer beschikbaar dan ik). Tegelijkertijd heeft dit formaat ook nadelen: het ligt iets dichter bij compressie-algoritmen dan bij het coderen ervan. In het bijzonder geeft de standaard veel representatiemethoden, maar zegt niet hoe de optimale moet worden gekozen - hiervoor moet de encoder een soort heuristiek gebruiken. Een SCSU-encoder die goede verpakkingen produceert, zal dus complexer en omslachtiger zijn dan mijn algoritme.
Ter vergelijking heb ik een relatief eenvoudige implementatie van SCSU naar JavaScript overgebracht - qua codevolume bleek het vergelijkbaar met mijn UTF-C, maar in sommige gevallen was het resultaat tientallen procenten slechter (soms kan het hoger zijn, maar niet veel). Teksten in het Hebreeuws en Grieks werden bijvoorbeeld gecodeerd door UTF-C 60% beter dan SCSU (waarschijnlijk vanwege hun compacte alfabetten).
Afzonderlijk zal ik hieraan toevoegen dat er naast SCSU ook een andere manier is om Unicode compact weer te geven: , maar het streeft naar MIME-compatibiliteit (wat ik niet nodig had) en hanteert een iets andere benadering van codering. Ik heb de effectiviteit ervan niet beoordeeld, maar het lijkt mij onwaarschijnlijk dat deze hoger zal zijn dan SCSU.
Mogelijke verbeteringen
Het algoritme dat ik presenteerde is niet universeel van opzet (dit is waarschijnlijk waar mijn doelen het meest afwijken van de doelen van het Unicode Consortium). Ik heb al gezegd dat het in de eerste plaats voor één taak is ontwikkeld (het opslaan van een meertalig woordenboek in een voorvoegselboom), en dat sommige functies ervan misschien niet zo geschikt zijn voor andere taken. Maar het feit dat het geen standaard is, kan een pluspunt zijn - u kunt het eenvoudig aanpassen aan uw behoeften.
Op de voor de hand liggende manier kunt u bijvoorbeeld de aanwezigheid van status wegnemen, staatloze codering maken - variabelen alleen niet bijwerken offs, auxOffs и is21Bit in de encoder en decoder. In dit geval zal het niet mogelijk zijn om reeksen karakters van hetzelfde alfabet effectief in te pakken, maar er zal een garantie zijn dat hetzelfde karakter altijd gecodeerd wordt met dezelfde bytes, ongeacht de context.
Bovendien kunt u de encoder aanpassen aan een specifieke taal door de standaardstatus te wijzigen, bijvoorbeeld door u te concentreren op Russische teksten, de encoder en decoder aan het begin in te stellen offs = 0x0400 и auxOffs = 0. Dit is vooral zinvol in het geval van de staatloze modus. Over het algemeen zal dit vergelijkbaar zijn met het gebruik van de oude XNUMX-bits codering, maar zonder de mogelijkheid te verwijderen om indien nodig tekens uit alle Unicode in te voegen.
Een ander eerder genoemd nadeel is dat er in grote tekst gecodeerd in UTF-C geen snelle manier is om de tekengrens te vinden die het dichtst bij een willekeurige byte ligt. Als je de laatste, laten we zeggen, 100 bytes uit de gecodeerde buffer afsnijdt, loop je het risico rommel te krijgen waar je niets mee kunt doen. De codering is niet ontworpen voor het opslaan van logbestanden van meerdere gigabytes, maar over het algemeen kan dit worden gecorrigeerd. Byte 0xBF mag nooit verschijnen als de eerste byte (maar mag de tweede of derde zijn). Daarom kunt u bij het coderen de reeks invoegen 0xBF 0xBF 0xBF elke bijvoorbeeld 10 KB - als u dan een grens moet vinden, is het voldoende om het geselecteerde stuk te scannen totdat een soortgelijke markering wordt gevonden. Na de laatste 0xBF is gegarandeerd het begin van een personage. (Bij het decoderen moet deze reeks van drie bytes uiteraard worden genegeerd.)
Samengevat
Als je tot hier hebt gelezen: gefeliciteerd! Ik hoop dat je, net als ik, iets nieuws hebt geleerd (of je geheugen hebt opgefrist) over de structuur van Unicode.
Demopagina. Het voorbeeld van het Hebreeuws toont de voordelen ten opzichte van zowel UTF-8 als SCSU.
Het hierboven beschreven onderzoek mag niet worden beschouwd als een inbreuk op de normen. Over het algemeen ben ik echter tevreden met de resultaten van mijn werk, dus ik ben er ook blij mee : een verkleinde JS-bibliotheek weegt bijvoorbeeld slechts 1710 bytes (en heeft uiteraard geen afhankelijkheden). Zoals ik hierboven al zei, is haar werk te vinden op (er is ook een set teksten waarop het kan worden vergeleken met UTF-8 en SCSU).
Tot slot vestig ik nogmaals de aandacht op gevallen waarin UTF-C wordt gebruikt niet de moeite waard:
- Als uw regels lang genoeg zijn (van 100-200 tekens). In dit geval moet u nadenken over het gebruik van compressie-algoritmen zoals deflate.
- Als je nodig hebt ASCII-transparantie, dat wil zeggen dat het belangrijk voor u is dat de gecodeerde reeksen geen ASCII-codes bevatten die niet in de originele string voorkomen. De noodzaak hiervoor kan worden vermeden als u bij interactie met API's van derden (bijvoorbeeld bij het werken met een database) het coderingsresultaat doorgeeft als een abstracte set bytes, en niet als tekenreeksen. Anders riskeert u onverwachte kwetsbaarheden te krijgen.
- Als u snel tekengrenzen op een willekeurige afstand wilt kunnen vinden (bijvoorbeeld wanneer een deel van een regel beschadigd is). Dit kan worden gedaan, maar alleen door de regel vanaf het begin te scannen (of door de wijziging toe te passen die in de vorige sectie is beschreven).
- Als u snel bewerkingen moet uitvoeren op de inhoud van tekenreeksen (sorteer ze, zoek naar subtekenreeksen erin, voeg ze samen). Hiervoor moeten de tekenreeksen eerst worden gedecodeerd, dus UTF-C zal in deze gevallen langzamer zijn dan UTF-8 (maar sneller dan compressie-algoritmen). Omdat dezelfde string altijd op dezelfde manier wordt gecodeerd, is een exacte vergelijking van de decodering niet vereist en kan deze per byte worden uitgevoerd.
update: gebruiker heeft een grafiek gepost waarin de toepasbaarheidslimieten van UTF-C worden benadrukt. Het laat zien dat UTF-C efficiënter is dan een compressie-algoritme voor algemene doeleinden (een variatie op LZW), zolang de ingepakte string korter is ~140 tekens (Ik merk echter op dat de vergelijking op één tekst is uitgevoerd; voor andere talen kan het resultaat verschillen).
Bron: www.habr.com