Čo je Base62?
Base62 je spôsob zápisu čísla iba znakmi, ktoré prežijú vloženie kamkoľvek: desať číslic, 26 veľkých písmen a 26 malých písmen. Žiadna interpunkcia, žiadne medzery, žiadny výplňový znak, nič, čo treba escapovať pred vložením do URL, názvu súboru, cookie alebo kľúča databázy. Desať plus 26 plus 26 je 62 a odtiaľ je názov.
Verzia na 30 sekúnd: číslo 12345 sa zapíše ako 3D7 a 1234567890 ako 1LY7VK. Spätný smer je tá istá operácia v opačnom poradí a potrebuje presne tú abecedu, ktorá kód vytvorila — iná abeceda tých šesť znakov premení na iné číslo bez akejkoľvek chybovej hlášky.
Táto stránka plní dve súvisiace úlohy a rozdiel medzi nimi je dôležitejší než čokoľvek iné na tejto stránke:
- Režim celého čísla berie vstup ako číslo. Desiatkové ID ako
1234567890 sa stane 1LY7VK a úvodné nuly vstupu nie sú súčasťou hodnoty, takže sa nevrátia.
- Bajtový režim berie vstup ako bajtový reťazec. Bajty sa čítajú ako jedno obrovské celé číslo s big-endian poradím a potom sa delia 62, čo je tá istá aritmetika nad iným množstvom. Tu počet úvodných nulových bajtov prežije, jeden nulový bajt na jeden nulový znak.
Odkiaľ berie 62 a čo to stojí
62 nie je mocnina dvoch a táto jediná skutočnosť formuje všetko ostatné. Známe kódovania sa budujú rozdelením vstupu na pevné skupiny bitov: 4 bity sa vytlačia ako jeden hexadecimálny znak, 6 bitov ako jeden znak Base64, 5 bitov ako jeden znak Base32. Base62 to nedokáže, pretože žiadny celý počet bitov nevystačí na znak s 62 hodnotami — 5 bitov pomenuje len 32 hodnôt, 6 bitov 64. Base62 preto ide cez aritmetiku: načíta celý vstup ako jedno celé číslo a vytlačí ho v základe 62.
Jeden znak potom nesie log2(62) = 5,954 bitu, čo je veľmi blízko 6 pri Base64, a v desiatkovom režime jeden znak nahrádza log62(10) = 1,792 desiatkovej číslice. Pár dôsledkov, ktoré sa oplatí poznať pred výberom dĺžky:
| Dĺžka kódu | Hodnoty, ktoré dokáže pomenovať | V praxi |
|---|
| 4 znaky | 624 = 14 776 336 | Dosť pre počítadlo, ktoré zostáva pod osem číslic, a zmestí sa do priestoru jedného telefónneho čísla. |
| 6 znakov | 626 = 56 800 235 584 | Obvyklý tvar ID kódu. Desaťmiestne desiatkové ID sa zmestí do šiestich znakov. |
| 7 znakov | 627 = 3 521 614 606 208 | Za rozsahom 32-bitového počítadla o dva rády, v šírke krátkeho slugu odkazu. |
| 11 znakov | 6211 = 52 036 560 683 837 093 888 | Viac než 264 = 18 446 744 073 709 551 616, takže celé 64-bitové číslo sa zmestí do jedenástich znakov. |
Opačným smerom: 1 000 desiatkových číslic potrebuje približne 558 znakov a 4 096 desiatkových číslic potrebuje 2 285. Úspora je reálna, ale ohraničená: Base62 skráti desiatkové číslo približne o 44% a nikdy neporazí najhustejšie tlačiteľné kódovania, pretože 5,954 bitu na znak je jednoducho menej než 6,4 alebo 6,5.
Režim celého čísla: čo sa stane s úvodnými nulami
Celé číslo má jeden kanonický zápis a začína nulovým znakom abecedy, čo je 0 v dvoch abecedách číslice-najprv a A v abecede písmená-najprv. Všetko naľavo od prvého významného znaku je výplň a výplň nie je súčasťou hodnoty: 00012345 aj 12345 sa stanú 3D7. Ak je potrebná pevná šírka — napríklad sedemznakový kód, ktorý musí byť zarovnaný v stĺpci — políčko Doplniť výsledok na pevnú šírku na tejto stránke opakuje nulové znaky, kým sa nedosiahne šírka, takže 12345 pri šírke 7 vypíše 00003D7 v abecede číslice-najprv a AAAADNH v abecede písmená-najprv. Výplň je kozmetická: tieto úvodné znaky k hodnote nič nepridávajú a dekódovanie ktoréhokoľvek reťazca vráti 12345, pretože 0 × 626 aj 0 × 625 sú nula bez ohľadu na to, ktorý znak nulu zapíše.
Dekódovanie vyplneného reťazca preto tiež funguje a stránka hlási, koľko úvodných znakov bolo nulových, aby rozdiel medzi „kód má sedem znakov“ a „hodnota potrebovala tri znaky“ nebol nikdy záhadou.
Bajtový režim: tá istá aritmetika nad bajtovým reťazcom
Bajtový režim načíta vstupné bajty ako jedno veľké celé číslo s big-endian poradím — celý bajtový reťazec sa berie ako jediné číslo bez ohľadu na dĺžku — a vytlačí ho v základe 62. Pretože bajt obsahuje 8 bitov a znak pomenuje 5,954 z nich, bajtový režim nie je kompresia: potrebuje približne 134% veľkosti vstupu, mierne horšie než 133% pri Base64. Pri 92-bajtovej ukážke z tabuľky veľkostí vyššie sa 92 bajtov vytlačí ako 124 znakov Base62 a Base64 tiež 124 (123 z nich pred svojou výplňou =). Base62 prehráva s Base64 v hustote a vyhráva v bezpečnosti znakov, čo je kompromis, ktorý každý krátky odkaz a pozvánkový kód robí zámerne.
Úvodné nulové bajty sa zachovávajú a v oboch smeroch sa to ľahko pokazí. Dva úvodné nulové bajty nasledované 0x01 sa vytlačia ako 001 v abecede číslice-najprv a ako AAB v abecede písmená-najprv, pretože úvodné znaky predstavujú nulu a je ich jeden na nulový bajt. Bajtový reťazec z jedného 0x00 sa vytlačí ako jediný znak 0 a bajtový reťazec z jedného 0x01 ako 1. Toto je jediné miesto, kde sa bajtový režim a režim celého čísla správajú inak, hoci bežia na rovnakom algoritme.
Cena je taká, že bajtový režim zdedí kvadratický čas aritmetiky: 1 024 bajtov sa odhaduje na približne tretinu sekundy a 2 048 bajtov na približne 1,3 sekundy, rovnaké čísla ako v tabuľke limitov vyššie. Preto je bajtový režim tu obmedzený na 2 048 bajtov na vstupe a 2 048 znakov na výstupe — 2 048 bajtov sa vytlačí ako približne 2 751 znakov, takže najväčší užitočný náklad, ktorý prežije obojsmerný prevod na tejto stránke, je približne 1 520 bajtov — a preto je bajtový režim na tejto stránke referenciou pre malé hodnoty, nie náhradou za Base64 alebo Base91 pre reálne súbory.
Tri abecedy a prečo je abeceda celým príbehom
Znaky abecedy sú pevná postupnosť a hodnota znaku je jeho pozícia v tejto postupnosti. Presun postupnosti mení, čo každý znak znamená. Široko sa používajú tri poradia a toto je to isté číslo zapísané tromi spôsobmi v každom z nich:
| Desiatkovo | 0-9 potom A-Z potom a-z | 0-9 potom a-z potom A-Z | A-Z potom a-z potom 0-9 |
|---|
| 0 | 0 | 0 | A |
| 61 | z | Z | 9 |
| 62 | 10 | 10 | BA |
| 12 345 | 3D7 | 3d7 | DNH |
| 1 234 567 890 | 1LY7VK | 1ly7vk | BViHfU |
Ak posledné tri stĺpce čítate ako jednu abecedu, je to jedna súvislá schéma. Ak ich čítate ako zameniteľné, rozpadne sa to, lebo dekódovanie je slepé voči abecede v najhoršom zmysle: každý znak vstupu je vo všetkých troch abecedách, takže zlá abeceda nevyvolá žiadnu chybu, len inú hodnotu.
| Kód | Čítané ako 0-9 A-Z a-z | Čítané ako 0-9 a-z A-Z | Čítané ako A-Z a-z 0-9 |
|---|
| 3D7 | 12 345 | 13 957 | 211 665 |
| 1LY7VK | 1 234 567 890 | 1 624 950 792 | 48 723 527 772 |
Veľkosť písmen je druhá, ostrejšia verzia tej istej pasce. Base62 rozlišuje veľkosť písmen vo všetkých poradiach, takže zmena na malé písmená mlčky prepíše kód: 1LY7VK je 1 234 567 890 v abecede číslice-najprv, zatiaľ čo 1ly7vk je v tej istej abecede 1 624 950 792 — a v abecede číslice-potom-malé je to 1 234 567 890, pretože toto poradie je presne abecedou číslice-najprv s prehodenými dvoma veľkosťami písmen. Nulový znak sa tiež nezdieľa: obe abecedy číslice-najprv píšu nulu ako 0, zatiaľ čo abeceda písmená-najprv ju píše ako A, takže táto abeceda sa vôbec nezačína číslicou.
Base62 vedľa ostatných kódovaní
| Kódovanie | Bity na znak | Veľkosť voči vstupu | Poznámky |
|---|
| Base16 (hex) | 4 | 200% | Dva znaky na bajt, ľahko čitateľné, žiadna abeceda na vyhľadávanie. |
| Base32 | 5 | 160% | Nerozlišuje veľkosť písmen a je bezpečný na diktovanie, najplytvavejší v skupine. |
| Base36 (0-9 a-z) | ~5,17 | ~155% | Iba číslice a malé písmená, takže prežije prevod na malé písmená. 12345 je 9ix. |
| Base58 | ~5,86 | ~137% | Vybraná pre adresy, nie pre hustotu: štyri podobne vyzerajúce znaky sa vynechajú namiesto usporiadania$1Súvisiace: Base32 / Base58. |
| Base62 | ~5,95 | ~134% | Každý znak je číslica alebo písmeno, takže sa nikdy nič neescapuje. Hustota je medzi Base58 a Base64. |
| Base64 | 6 | 133% | Predvolená voľba všade, za cenu +, / a =, troch znakov, ktoré si vynucujú escapovanie$1Súvisiace: Prevodník Base64. |
| Ascii85 / Base85 | 6,4 | 125% | 5 znakov na 4 bajty, ale delí 85 a jeho abeceda potrebuje úvodzovky$1Súvisiace: Ascii85. |
| Base91 | ~6,5 | ~123% | Najhustejšie z týchto a to, ktorého výstup je najmenej bezpečné vložiť bez escapovania$1Súvisiace: Base91. |
Percentá sú asymptotické náklady, zaokrúhlené; skutočné počty znakov pre jeden reálny 92-bajtový vstup sú v tabuľke veľkostí vyššie na tejto stránke. V režime celého čísla porovnanie beží opačne, pretože vstup je desiatkový text a nie bajty: tam je Base62 približne o 44% kratší než číslice, ktoré nahrádza, a Base36 približne o 36% kratší, preto je ID kód zvyčajne Base62 alebo Base36 a nie Base58.
Čím Base62 nie je
- Nie je to norma. Neexistuje žiadny RFC ani špecifikácia. Žiadny normalizačný orgán nikdy nedefinoval Base62, preto nie je zaručená abeceda a táto stránka vytlačí všetky tri poradia namiesto toho, aby mlčky vybrala jedno.
- Nie je to šifrovanie. Je to len zmena základu. Každý, kto pozná abecedu, to vráti späť jedným prechodom; nie je tu kľúč, soľ ani žiadna forma tajnosti.
- Nie je to kompresia. Bajtový režim zväčší dáta približne o tretinu. Režim celého čísla len vyzerá ako kompresia, pretože desiatkový text je aj tak neefektívny spôsob zápisu čísla.
- Nerozlišuje veľkosť písmen. Base32 sa dá previesť na malé písmená a prečítať späť; Base62 nie. Kód, ktorý prejde systémom normalizujúcim veľkosť písmen, je poškodený kód.
- Nemá vlastnú kontrolu. Nie je tu kontrolný súčet ani kontrolný znak, takže jeden zlý znak dá platne vyzerajúci výsledok s inou hodnotou. Ak na tom záleží, poradie Bitcoin má kontrolný súčet — oddiel Base58Check na stránke Base32 / Base58.
- Nemá pevnú dĺžku. Počet znakov rastie s hodnotou, takže počítadlo, ktoré začína na 1 a dosiahne 627, prejde z jedného znaku na osem. Ak je potrebný stabilný stĺpec, doplní sa na pevnú šírku.
Pasce, ktoré skutočne kusnú
- Abeceda je odpoveďou na deväť z desiatich záhad. Ak iný nástroj dá pre to isté číslo iný kód, pred podozrením na chybu sa dve abecedy porovnajú znak po znaku. Tabuľka vyššie ukazuje tú istú hodnotu v troch abecedách a všetky tri sú správne.
- Zlá abeceda zlyhá potichu. Pre ňu neexistuje chybová cesta:
3D7 sa dekóduje na 12 345, 13 957 alebo 211 665 podľa toho, ktoré poradie sa predpokladá. Prvý znak, ktorý je najpravdepodobnejšie nulová výplň, sa skontroluje, rovnako ako to, či abeceda na začiatku obsahuje číslice alebo písmená.
- Úvodné nuly znamenajú dve rozdielne veci. V režime celého čísla sa
00012345 a 12345 rovnajú rovnakému číslu a vypíšu sa rovnako. V bajtovom režime je úvodný nulový bajt dátom a vytlačí sa ako jeden navyše nulový znak. Vynechanie jedného z týchto znakov zmení bajtový reťazec.
- Normalizácia veľkosti písmen kód zničí. E-mailová adresa, názov hostiteľa alebo cesta Windows sa môžu počas prenosu previesť na malé písmená. Kód Base62 to neprežije, a preto Base36 stále existuje.
- Dlhé vstupy sú pomalé, nielen veľké. Prevod je aritmetika nad celým vstupom naraz, takže zdvojnásobenie dĺžky vstupu zčetverinásobí čas. Táto stránka odmietne vstupy nad svoje namerané limity namiesto zamŕznutia; tabuľka veľkostí vyššie uvádza namerané čísla.
- Reťazec Base62 nie je dôkaz ničoho. Keďže takmer každý reťazec číslic a písmen sa dekóduje bez sťažností, ľubovoľný slug odkazu sa dekóduje na nejaké číslo. Kód má zmysel len vtedy, ak systém, ktorý ho vydal, ukladá aj mapovanie.
Rýchle odpovede
„Prečo iný nástroj Base62 dá pre to isté číslo iný kód?“
Pretože sa abeceda líši. Base62 nemá špecifikáciu, s ktorou by sa dalo nesúhlasiť, takže implementácie vyberajú poradie: číslice a veľké písmená najprv, číslice a malé písmená najprv alebo písmená pred číslicami. Prepnutím výberu abecedy hore na tejto stránke sa všetky tri odpovede zobrazia vedľa seba.
„Je Base62 bezpečný v URL?“
Áno, v každom z troch poradí. Všetkých 62 znakov je neescapovaných písmen a číslic, takže žiadny z nich sa nerozvinie na percentuálnu trojicu v dotaze a žiadny neukončí URL, segment cesty ani atribút HTML. Práve preto sú krátke odkazy Base62 a nie Base64.
„Ktorý je menší, Base62 alebo Base64?“
Pre bajty je Base64 veľmi mierne menší: približne 133% vstupu oproti približne 134%. Pri 92-bajtovej ukážke vyššie sú obe rovnaké na 124 znakoch. Pre desiatkové čísla Base62 skráti text približne o 44%, a tam je praktický zisk.
„Môžem tu dekódovať reťazec Base64?“
Nie, a neoznámi, že zlyhal. Obe abecedy sa prekrývajú vo všetkých 62 znakoch, takže reťazec Base64 je tu zvyčajne tiež „platný“ vstup a jednoducho sa dekóduje na iné číslo. Pre Base64 sa použije Base64.
„Má kód Base62 maximálnu dĺžku?“
Teoreticky algoritmus nemá hranicu. Prakticky táto stránka končí pri 4 096 desiatkových číslicách alebo 2 048 bajtoch, pretože aritmetika za ňou je kvadratická a karta by zamrzla bez čohokoľvek na obrazovke, čo by to vysvetlilo. Tabuľka limitov vyššie na tejto stránke uvádza namerané čísla.
„Ako viem, že výsledok na tejto stránke je správny?“
Kliknutím na Autotest sa spustí všetky zdokumentované ukážky, každú dĺžku bajtov od 0 do 64 a rozptyl desiatkových čísel naprieč všetkými tromi abecedami, porovná vrátené hodnoty s tým, čo vstúpilo, a znovu skontroluje, že všetkých 62 znakov každej abecedy je v URL bezpečných. Tlačidlo Ukážka navyše porovná svoje tri výsledky s hodnotami zapísanými v dátovom súbore tejto stránky, ktoré boli overené voči druhej, nezávislej implementácii s veľkými číslami v testovacích nástrojoch tejto lokality.
Normy a zdroje
Tu nie je žiadna norma na implementáciu: Base62 je konvencia, nie špecifikácia, a tri abecedy vytlačené vyššie sú tie, ktoré sa objavujú v reálnom softvéri. Táto stránka ju implementuje vlastnými rutinami pre veľké celé čísla stránky, napísanými v čistej aritmetike nad poliami číslic, takže žiadna veľkosť nie je obmedzená číselným typom JavaScriptu.
Text stránky bol napísaný pre túto lokalitu. Každý prepracovaný príklad na tejto stránke vytvoril kód samotnej stránky a potom bol overený voči druhej, nezávislej implementácii s natívnymi veľkými číslami, ktorá je uložená v testovacích nástrojoch tejto lokality; tá istá implementácia overila tabuľky ukážok a veľkostí v dátovom súbore.
