Hvad er Base62?
Base62 er en måde at skrive et tal på med udelukkende de tegn, der overlever at blive indsat hvor som helst: de ti cifre, de 26 store bogstaver og de 26 små bogstaver. Ingen tegnsætning, ingen mellemrum, intet opfyldtegn, intet der skal escapes, før det kommer i en URL, et filnavn, en cookie eller en databasenøgle. Ti plus 26 plus 26 er 62, og det er der navnet kommer fra.
Versionen på 30 sekunder: tallet 12345 skrives som 3D7, og 1234567890 skrives som 1LY7VK. At gå tilbage er den samme operation i omvendt rækkefølge, og den kræver præcis det alfabet, der producerede koden — et andet alfabet gør de samme seks tegn om til et andet tal uden nogen fejlmeddelelse.
Denne side udfører to beslægtede opgaver, og forskellen mellem dem betyder mere end noget andet på siden:
- Heltalstilstand behandler inputtet som et tal. Et decimalt ID som
1234567890 bliver til 1LY7VK, og inputtets indledende nuller er ikke en del af værdien, så de kommer ikke tilbage. - Bytetilstand behandler inputtet som en bytestreng. Bytes læses som ét enormt big-endian-heltal og divideres derefter med 62, altså den samme regning på en anden størrelse. Her overlever antallet af indledende nulbytes, én nulbyte pr. nultegn.
Hvor de 62 kommer fra, og hvad det koster
62 er ikke en potens af to, og det ene faktum former alt andet. De velkendte kodninger bygges ved at skære inputtet i faste bitgrupper: 4 bit udskrives som ét hexadecimalt tegn, 6 bit som ét Base64-tegn, 5 bit som ét Base32-tegn. Base62 kan ikke gøre det, fordi intet helt antal bit passer til et tegn med 62 værdier — 5 bit navngiver kun 32 værdier, 6 bit navngiver 64. Så Base62 går via regning i stedet: læs hele inputtet som ét heltal og udskriv det i base 62.
Et tegn bærer så log2(62) = 5,954 bit, hvilket er meget tæt på Base64's 6, og i decimal tilstand erstatter et tegn log62(10) = 1,792 decimale cifre. Nogle konsekvenser, der er værd at kende, før man vælger længde:
| Kodelængde | Værdier den kan navngive | I praksis |
|---|
| 4 tegn | 624 = 14.776.336 | Nok til en tæller, der holder sig under otte cifre, og det passer i et telefonnummers plads. |
| 6 tegn | 626 = 56.800.235.584 | Den sædvanlige form for en ID-kode. Et ti-cifret decimalt ID passer i seks tegn. |
| 7 tegn | 627 = 3.521.614.606.208 | Ud over området for en 32-bit-tæller med to størrelsesordener, i bredden af et kort link-slug. |
| 11 tegn | 6211 = 52.036.560.683.837.093.888 | Mere end 264 = 18.446.744.073.709.551.616, så et fuldt 64-bit-tal passer i elleve tegn. |
Omvendt: 1.000 decimale cifre kræver ca. 558 tegn, og 4.096 decimale cifre kræver 2.285. Gevinsten er reel, men begrænset: Base62 forkorter et decimaltal med ca. 44%, og den slår aldrig de tætteste udskrivbare kodninger, fordi 5,954 bit pr. tegn simpelthen er mindre end 6,4 eller 6,5.
Heltalstilstand: hvad der sker med indledende nuller
Et heltal har én kanonisk skriftlig form, og den begynder med alfabetets nultegn, som er 0 i de to cifre-først-rækkefølger og A i bogstaver-først-rækkefølgen. Alt til venstre for det første betydningsfulde tegn er opfyld, og opfyld er ikke en del af en værdi: 00012345 og 12345 bliver begge til 3D7. Hvis en fast bredde er ønsket — f.eks. en syv tegn lang kode, der skal stå på linje i en kolonne — gentager boksen Udfyld resultatet til fast bredde nultegn, indtil bredden er nået, så 12345 med bredde 7 udskrives som 00003D7 i cifre-først-alfabetet og AAAADNH i bogstaver-først-alfabetet. Opfyldet er kosmetisk: de ledende tegn tilføjer ingenting til værdien, og afkodning af begge strenge giver 12345 tilbage, fordi 0 × 626 og 0 × 625 begge er nul, uanset hvilket tegn der staver nul.
Afkodning af en opfyldt streng virker derfor også, og siden angiver, hvor mange af de ledende tegn der var nultegn, så forskellen mellem "koden er syv tegn" og "værdien krævede tre tegn" aldrig er et mysterium.
Bytetilstand: den samme regning på en bytestreng
Bytetilstand læser inputbytes som ét big-endian-heltal — hele bytestrengen behandles som ét tal, uanset hvor lang den er — og udskriver det tal i base 62. Fordi en byte indeholder 8 bit, og et tegn navngiver 5,954 af dem, er bytetilstand ikke komprimering: den har brug for ca. 134% af inputstørrelsen, marginalt værre end Base64's 133%. På 92-byte-eksemplet, der bruges i størrelsestabellen ovenfor, udskrives 92 bytes som 124 Base62-tegn, og Base64 udskriver også 124 (123 af dem før sit =-opfyld). Base62 taber til Base64 på tæthed og vinder på tegnsikkerhed, og det er den afvejning, hver kort link- og invitationskode bevidst tager.
Ledende nulbytes bevares, og det er let at tage fejl i begge retninger. To ledende nulbytes efterfulgt af 0x01 udskrives som 001 i cifre-først-alfabetet og som AAB i bogstaver-først-alfabetet, fordi de ledende tegn staver nul og er ét pr. nulbyte. En bytestreng med kun 0x00 udskrives som det enkelte tegn 0, og en bytestreng med kun 0x01 udskrives som 1. Det er det ene sted, hvor bytetilstand og heltalstilstand ser forskellige ud, selvom de kører den samme algoritme.
Omkostningen ved det hele er, at bytetilstanden arver regnestykkets kvadratiske tidsforbrug: 1.024 bytes anslås til ca. en tredjedel af et sekund og 2.048 bytes til ca. 1,3 sekunder, de samme tal som grænsetabellen ovenfor viser. Derfor er bytetilstanden her begrænset til 2.048 bytes ud og 2.048 tegn ind — 2.048 bytes udskrives som ca. 2.751 tegn, så ca. 1.520 bytes er den største nyttelast, der overlever en rundtur gennem denne side — og derfor er bytetilstanden på denne side en reference for små værdier, ikke en erstatning for Base64 eller Base91 på rigtige filer.
De tre alfabeter, og hvorfor alfabetet er hele historien
Et alfabets tegn er en fast rækkefølge, og et tegns værdi er dets position i den rækkefølge. Flytter man rundt på rækkefølgen, ændrer man, hvad hvert tegn betyder. Tre rækkefølger er i udbredt brug, og dette er det samme tal skrevet på tre måder i hver af dem:
| Decimal | 0-9, derefter A-Z, derefter a-z | 0-9, derefter a-z, derefter A-Z | A-Z, derefter a-z, derefter 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 |
Læser man de sidste tre kolonner som ét alfabet, er det én sammenhængende kodning. Læser man dem som udskiftelige, falder det fra hinanden, fordi afkodning er alfabetsblind på den værst tænkelige måde: ethvert tegn i inputtet findes i alle tre alfabeter, så et forkert alfabet giver slet ingen fejl, kun et andet tal.
| En kode | Læst som 0-9 A-Z a-z | Læst som 0-9 a-z A-Z | Læst som 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 |
Store/små bogstaver er en anden og skarpere version af den samme fælde. Base62 skelner mellem store og små bogstaver i alle rækkefølger, så en kode, der skrives med små bogstaver, omskrives stille: 1LY7VK er 1.234.567.890 i det cifre-først-alfabet, mens 1ly7vk er 1.624.950.792 i det samme alfabet — og det er tilfældigvis 1.234.567.890 i cifre-derefter-små-alfabetet, fordi den rækkefølge netop er cifre-først-rækkefølgen med de to bogstavtyper byttet om. Nultegnet er heller ikke delt: de to cifre-først-rækkefølger skriver nul som 0, mens bogstaver-først-rækkefølgen skriver det som A, så det alfabet slet ikke begynder med et ciffer.
Base62 sammen med de andre kodninger
| Kodning | Bit pr. tegn | Størrelse i forhold til inputtet | Noter |
|---|
| Base16 (hex) | 4 | 200% | To tegn pr. byte, trivielt læselig, intet alfabet at slå op i. |
| Base32 | 5 | 160% | Ufølsom over for store/små bogstaver og sikker til diktering, den mest ødsle i gruppen. |
| Base36 (0-9 a-z) | ~5,17 | ~155% | Kun cifre og små bogstaver, så den overlever en rutine, der gør alt småt. 12345 er 9ix. |
| Base58 | ~5,86 | ~137% | Valgt til adresser, ikke til tæthed: fire forvekslelige tegn udelades i stedet for at blive ordnet. Se Base32 / Base58. |
| Base62 | ~5,95 | ~134% | Hvert tegn er et ciffer eller et bogstav, så intet bliver nogensinde escapet. Tætheden ligger mellem Base58 og Base64. |
| Base64 | 6 | 133% | Standarden overalt, prisen er +, / og =, de tre tegn der tvinger escaping. Se Base64-konverteren. |
| Ascii85 / Base85 | 6,4 | 125% | 5 tegn pr. 4 bytes, men den dividerer med 85, og dens alfabet skal citeres. Se Ascii85. |
| Base91 | ~6,5 | ~123% | Den tætteste af disse, og den, hvis output er mindst sikker at indsætte uden escaping. Se Base91. |
Procenterne er asymptotiske omkostninger, afrundet; de målte tegnantal for ét reelt 92-byte input findes i størrelsestabellen længere oppe på denne side. I heltalstilstand går sammenligningen den anden vej, fordi inputtet er decimal tekst og ikke bytes: der er Base62 ca. 44% kortere end de cifre, den erstatter, og Base36 ca. 36% kortere, hvilket er grunden til, at en ID-kode normalt er Base62 eller Base36 og ikke Base58.
Hvad Base62 ikke er
- Ikke en standard. Der er ingen RFC og ingen specifikation. Intet standardiseringsorgan har nogensinde defineret Base62, og derfor er alfabetet ikke garanteret, og denne side udskriver alle tre rækkefølger i stedet for stille at vælge én.
- Ikke kryptering. Det er et grundtalsskift, intet mere. Enhver, der kender alfabetet, vender det i ét gennemløb, og der er ingen nøgle, intet salt og ingen hemmeligholdelse af nogen art.
- Ikke komprimering. Bytetilstand gør dataene ca. en tredjedel større. Heltalstilstand ser kun ud som komprimering, fordi decimal tekst i sig selv er en ineffektiv måde at skrive et tal på.
- Ikke ufølsom over for store/små bogstaver. Base32 kan skrives med små bogstaver og læses tilbage; Base62 kan ikke. En kode, der løber gennem et system, som normaliserer store/små bogstaver, er en beskadiget kode.
- Ikke selvkontrollerende. Der er ingen checksum og intet kontroltegn, så ét forkert tegn giver et gyldigt udseende resultat med en anden værdi. Hvis det betyder noget, følger Bitcoin-rækkefølgen med en checksum — se afsnittet Base58Check i Base32 / Base58.
- Ikke fast længde. Antallet af tegn vokser med værdien, så en tæller, der starter ved 1 og når 627, går fra ét tegn til otte. Udfyld til fast bredde, når en stabil kolonne er nødvendig.
Fælder, der faktisk bider
- Alfabetet er svaret på ni ud af ti gåder. Hvis et andet værktøj giver en anden kode for det samme tal, så sammenlign de to alfabeter tegn for tegn, før man mistænker en fejl. Tabellen ovenfor viser den samme værdi i tre alfabeter, og alle tre er korrekte.
- Et forkert alfabet fejler i stilhed. Der er ingen fejlvej for det:
3D7 afkodes til 12.345, 13.957 eller 211.665, afhængigt alene af hvilken rækkefølge der antages. Tjek det første tegn, som er det mest sandsynlige opfyld, og tjek om alfabetet har cifre eller bogstaver forrest. - Ledende nuller betyder to forskellige ting. I heltalstilstand er
00012345 og 12345 det samme tal og udskrives identisk. I bytetilstand er en ledende nulbyte data, og den udskrives som ét ekstra nultegn. At droppe et af disse tegn ændrer bytestrengen. - Normalisering af store/små bogstaver ødelægger en kode. En e-mailadresse, et værtsnavn eller en Windows-sti kan blive skrevet med små bogstaver undervejs. En Base62-kode kan ikke overleve det, og det er grunden til, at Base36 stadig findes.
- Lange input er langsomme, ikke bare store. Konverteringen er regning på hele inputtet på én gang, så en fordobling af inputlængden firdobler tiden. Denne side afviser input ud over sine målte grænser i stedet for at hænge; størrelsestabellen længere oppe giver de målte tal.
- En Base62-streng er ikke et bevis på noget. Eftersom næsten enhver streng af cifre og bogstaver afkodes uden klager, vil en vilkårlig URL-slug afkode til et tal. En kode betyder kun noget, hvis systemet, der udstedte den, også gemmer koblingen.
Hurtige svar
“Hvorfor giver et andet Base62-værktøj en anden kode for det samme tal?”
Fordi alfabetet er forskelligt. Base62 har ingen specifikation at være uenig med, så implementeringer vælger en rækkefølge: cifre og store bogstaver først, cifre og små bogstaver først, eller bogstaver før cifre. Skift alfabetsvalget øverst på denne side for at se alle tre svar side om side.
“Er Base62 sikkert i en URL?”
Ja, i hver af de tre rækkefølger. Alle 62 tegn er uescapede bogstaver og cifre, så ingen af dem udvides til en procent-tripel i en forespørgselsstreng, og ingen af dem afslutter en URL, et stisegment eller en HTML-attribut. Det er hele grunden til, at korte links er Base62 og ikke Base64.
“Hvilken er mindre, Base62 eller Base64?”
For bytes er Base64 en anelse mindre: ca. 133% af inputtet mod ca. 134%. På 92-byte-eksemplet ovenfor er de lige med 124 tegn. For decimaltal forkorter Base62 teksten med ca. 44%, og det er der den praktiske gevinst ligger.
“Kan jeg afkode en Base64-streng med denne side?”
Nej, og den vil ikke fortælle én, at den fejlede. De to alfabeter overlapper i alle 62 tegn, så en Base64-streng er normalt også "gyldig" input her og afkodes blot til et andet tal. Brug Base64 til Base64.
“Har en Base62-kode en maksimal længde?”
Nej. I teorien har algoritmen ingen grænse. I praksis stopper denne side ved 4.096 decimale cifre, eller 2.048 bytes, fordi regnestykket bag den er kvadratisk, og fanen ville fryse uden noget på skærmen, der forklarer hvorfor. Grænsetabellen længere oppe på denne side viser de målte tal.
“Hvordan ved jeg, at resultatet på denne side er rigtigt?”
Tryk på Selvtest. Den kører alle dokumenterede eksempler, hver bytelængde fra 0 til 64 og en spredning af decimaltal gennem alle tre alfabeter og sammenligner de returnerede værdier med det, der blev indsat, og den kontrollerer igen, at hvert alfabets 62 tegn alle er sikre i en URL. Knappen Eksempel sammenligner derudover sine tre resultater med værdierne, der er registreret i denne sides datafil, og som blev verificeret mod en anden, uafhængig implementering med store heltal, der findes i denne sites testværktøjer.
Standarder og krediteringer
Der er ingen standard at implementere her: Base62 er en konvention, ikke en specifikation, og de tre alfabeter, der er udskrevet ovenfor, er dem, der findes i rigtig software. Denne side implementerer det med sitets egne store-heltalsrutiner, skrevet i ren aritmetik på cifferarrays, så ingen størrelse nogensinde er begrænset af JavaScript-talbegrebet.
Siden tekst er skrevet til denne webside. Hvert regneeksempel på denne side er produceret af sidens egen kode og derefter verificeret mod en anden, uafhængig implementering, der bruger native store heltal; den findes i denne sites testværktøjer, og samme implementering verificerede eksempel- og størrelsestabellerne i datafilen.
