Hva er Base62?
Base62 er en måte å skrive et tall på med bare tegn som tåler å bli limt inn hvor som helst: de ti sifrene, de 26 store bokstavene og de 26 små bokstavene. Ingen tegnsetting, ingen mellomrom, ingen utfyllingstegn, ingenting som må escapes før det går inn i en URL, et filnavn, en informasjonskapsel eller en databasenøkkel. Ti pluss 26 pluss 26 er 62, og det er der navnet kommer fra.
Versjonen på 30 sekunder: tallet 12345 skrives som 3D7, og 1234567890 skrives som 1LY7VK. Veien tilbake er den samme operasjonen i revers, og den krever det nøyaktige alfabetet som laget koden — et annet alfabet gjør de samme seks tegnene om til et annet tall, uten noen feilmelding.
Denne siden gjør to beslektede jobber, og forskjellen mellom dem betyr mer enn noe annet på siden:
- Heltallsmodus behandler inndataene som et tall. En desimal-ID som
1234567890 blir til 1LY7VK, og de ledende nullene i inndataene er ikke en del av verdien, så de kommer ikke tilbake. - Bytemodus behandler inndataene som en bytesekvens. Bytene leses som ett enormt heltall med big-endian-rekkefølge og deles deretter på 62, altså samme aritmetikk på en annen størrelse. Her overlever antallet ledende nullbyte, ett nullbyte per nulltegn.
Hvor 62-tallet kommer fra, og hva det koster
62 er ikke en tomakt, og det ene faktum former alt annet. De kjente kodingene bygges ved å dele inndataene i faste bitgrupper: 4 bit skrives ut som ett heksadesimalt tegn, 6 bit som ett Base64-tegn, 5 bit som ett Base32-tegn. Base62 kan ikke gjøre det, fordi ingen helt antall bit passer til et tegn med 62 verdier — 5 bit nevner bare 32 verdier, 6 bit nevner 64. Derfor går Base62 gjennom aritmetikk: les hele inndataene som ett heltall, og skriv det ut i grunntall 62.
Ett tegn bærer da log2(62) = 5,954 bit, som ligger svært nær Base64s 6, og i desimalmodus erstatter ett tegn log62(10) = 1,792 desimale siffer. Noen konsekvenser verdt å kjenne til før man velger en lengde:
| Kodelengde | Verdier den kan navngi | I praksis |
|---|
| 4 tegn | 624 = 14 776 336 | Nok for en teller som holder seg under åtte sifre, og den får plass i et telefonnummers plass. |
| 6 tegn | 626 = 56 800 235 584 | Den vanlige formen for en ID-kode. En desimal-ID på ti siffer får plass i seks tegn. |
| 7 tegn | 627 = 3 521 614 606 208 | Over to størrelsesordener forbi rekkevidden til en 32-bit-teller, i bredden til en kort lenke-slug. |
| 11 tegn | 6211 = 52 036 560 683 837 093 888 | Mer enn 264 = 18 446 744 073 709 551 616, så et helt 64-bit-tall får plass i elleve tegn. |
Omvendt trenger 1000 desimale siffer omtrent 558 tegn, og 4096 desimale siffer trenger 2285. Besparelsen er reell, men begrenset: Base62 forkorter et desimaltall med omtrent 44 %, og den slår aldri de tetteste utskrivbare kodingene, fordi 5,954 bit per tegn rett og slett er mindre enn 6,4 eller 6,5.
Heltallsmodus: hva som skjer med ledende nuller
Et heltall har én kanonisk skriveform, og den begynner med alfabetets nulltegn, som er 0 i de to siffer-først-rekkefølgene og A i bokstav-først-rekkefølgen. Alt til venstre for det første signifikante tegnet er utfylling, og utfylling er ikke en del av en verdi: 00012345 og 12345 blir begge til 3D7. Ønsker man fast bredde — for eksempel en syv-tegns kode som må stå på linje i en kolonne — gjentar boksen Fyll ut resultatet til fast bredde nulltegn til bredden er nådd, så 12345 med bredde 7 skrives 00003D7 i siffer-først-alfabetet og AAAADNH i bokstav-først-alfabetet. Utfylling er kosmetisk: de ledende tegnene tilfører ingenting til verdien, og dekoding av begge strengene gir 12345 tilbake, fordi 0 × 626 og 0 × 625 begge er null uansett hvilket tegn som staver nullen.
Dekoding av en utfylt streng fungerer derfor også, og siden rapporterer hvor mange av de ledende tegnene som var nulltegn, slik at forskjellen mellom «koden er syv tegn» og «verdien trengte tre tegn» aldri er et mysterium.
Bytemodus: den samme aritmetikken på en bytesekvens
Bytemodus leser inndatabytene som ett stort heltall med big-endian-rekkefølge — hele bytesekvensen behandles som ett tall, uansett lengde — og skriver det tallet i grunntall 62. Fordi en byte inneholder 8 bit og et tegn representerer 5,954 av dem, er bytemodus ikke komprimering: den trenger omtrent 134 % av inndatastørrelsen, marginalt verre enn Base64s 133 %. På 92-byte-eksempelet som brukes i størrelsestabellen over, skrives 92 byte ut som 124 Base62-tegn, og Base64 skriver også 124 (123 av dem før =-utfyllingen). Base62 taper mot Base64 på tetthet og vinner på tegnsikkerhet, og det er avveiningen hver kort lenke og hver invitasjonskode gjør med vilje.
Ledende nullbyte bevares, og det er lett å ta feil i begge retninger. To ledende nullbyte etterfulgt av 0x01 skrives som 001 i siffer-først-alfabetet og som AAB i bokstav-først-alfabetet, fordi de ledende tegnene staver null og er ett per nullbyte. En bytesekvens med en enkelt 0x00 skrives som det enkle tegnet 0, og en bytesekvens med en enkelt 0x01 skrives som 1. Dette er det ene stedet der bytemodus og heltallsmodus ser ulike ut mens de kjører samme algoritme.
Prisen for alt dette er at bytemodus arver aritmetikkens kvadratiske tidsbruk: 1024 byte anslås til omtrent en tredels sekund og 2048 byte til omtrent 1,3 sekund, de samme tallene som grensetabellen over gir. Derfor er bytemodus her begrenset til 2048 byte ut og 2048 tegn inn — 2048 byte skrives ut som omtrent 2751 tegn, så omtrent 1520 byte er den største nyttelasten som overlever en rundtur gjennom denne siden — og derfor er bytemodusen på denne siden en referanse for små verdier, ikke en erstatning for Base64 eller Base91 på reelle filer.
De tre alfabetene, og hvorfor alfabetet er hele historien
Tegnene i et alfabet er en fast sekvens, og et tegns verdi er posisjonen i sekvensen. Å flytte sekvensen rundt endrer hva hvert tegn betyr. Tre rekkefølger er i bred bruk, og dette er det samme tallet skrevet på tre måter i hver av dem:
| Desimal | 0-9 deretter A-Z deretter a-z | 0-9 deretter a-z deretter A-Z | A-Z deretter a-z deretter 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 |
Leser man de tre siste kolonnene som ett alfabet, er det én sammenhengende ordning. Leser man dem som utskiftbare, faller det fra hverandre, fordi dekoding er alfabet-blind på den verst tenkelige måten: ethvert tegn i inndataene finnes i alle tre alfabetene, så et feil alfabet gir ingen feil i det hele tatt, bare et annet tall.
| En kode | Lest som 0-9 A-Z a-z | Lest som 0-9 a-z A-Z | Lest 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 og små bokstaver er en andre, skarpere variant av den samme fellen. Base62 skiller store og små bokstaver i alle rekkefølgene, så å gjøre en kode til små bokstaver skriver den om i stillhet: 1LY7VK er 1 234 567 890 i siffer-først-alfabetet, mens 1ly7vk er 1 624 950 792 i det samme alfabetet — og den er 1 234 567 890 i siffer-deretter-små-alfabetet, fordi den rekkefølgen nettopp er siffer-først med de to bokstavtilfellene byttet om. Nulltegnet er heller ikke felles: de to siffer-først-rekkefølgene skriver null som 0, mens bokstav-først-rekkefølgen skriver det som A, så det alfabetet begynner ikke med et siffer i det hele tatt.
Base62 ved siden av de andre kodingene
| Koding | Bit per tegn | Størrelse mot inndataene | Merknader |
|---|
| Base16 (heks) | 4 | 200% | To tegn per byte, lett å lese, ingen alfabet å slå opp. |
| Base32 | 5 | 160% | Skiller ikke store og små bokstaver og er trygg å diktere for hånd, den mest sløsende i gruppen. |
| Base36 (0-9 a-z) | ~5,17 | ~155% | Bare siffer og små bokstaver, så den overlever en pipeline som gjør alt til små bokstaver. 12345 er 9ix. |
| Base58 | ~5,86 | ~137% | Valgt for adresser, ikke for tetthet: fire tegn som ser like ut er droppet i stedet for å bli ordnet. Se Base32 / Base58. |
| Base62 | ~5,95 | ~134% | Hvert tegn er et siffer eller en bokstav, så ingenting blir noen gang escapet. Tettheten ligger mellom Base58 og Base64. |
| Base64 | 6 | 133% | Standarden overalt, til prisen av +, / og =, de tre tegnene som tvinger frem escaping. Se Base64-konverteren. |
| Ascii85 / Base85 | 6,4 | 125% | 5 tegn per 4 byte, men den deler på 85, og alfabetet krever anførselstegn. Se Ascii85. |
| Base91 | ~6,5 | ~123% | Den tetteste av disse, og den hvis utdata er minst trygg å lime inn uten escaping. Se Base91. |
Prosentene er asymptotiske kostnader, avrundet; de målte tegnantallene for én reell inndata på 92 byte står i størrelsestabellen lenger opp på denne siden. I heltallsmodus går sammenligningen den andre veien, fordi inndataene er desimaltekst og ikke byte: der er Base62 omtrent 44% kortere enn sifrene den erstatter, og Base36 omtrent 36% kortere, og det er grunnen til at en ID-kode normalt er Base62 eller Base36 og ikke Base58.
Hva Base62 ikke er
- Ikke en standard. Det finnes ingen RFC og ingen spesifikasjon. Ingen standardorganisasjon har noen gang definert Base62, og derfor er alfabetet ikke garantert, og derfor skriver denne siden ut alle tre rekkefølgene i stedet for å velge én stille.
- Ikke kryptering. Det er en grunntallsendring, ikke mer. Den som kjenner alfabetet reverserer den i ett trinn, og det finnes ingen nøkkel, ingen salt og ingen hemmelighold av noe slag.
- Ikke komprimering. Bytemodus gjør dataene omtrent en tredel større. Heltallsmodus ser bare ut som komprimering fordi desimaltekst er en ineffektiv måte å skrive et tall på i utgangspunktet.
- Ikke ufølsom for store og små bokstaver. Base32 kan gjøres til små bokstaver og leses tilbake; Base62 kan ikke det. En kode som reiser gjennom et system som normaliserer store og små bokstaver, er en ødelagt kode.
- Ikke selvkontrollerende. Det finnes ingen kontrollsum og ingen kontrolltegn, så ett feil tegn gir et gyldig utseende resultat med en annen verdi. Hvis det har betydning, følger Bitcoin-ordningen med en kontrollsum — se Base58Check-delen i Base32 / Base58.
- Ikke fast lengde. Antallet tegn vokser med verdien, så en teller som starter på 1 og når 627 går fra ett tegn til åtte. Fyll ut til fast bredde når det trengs en stabil kolonne.
Feller som faktisk biter
- Alfabetet er svaret på ni av ti gåter. Hvis et annet verktøy gir en annen kode for samme tall, sammenlign de to alfabetene tegn for tegn før man mistenker en feil. Tabellen over viser samme verdi i tre alfabeter, og alle tre er riktige.
- Et feil alfabet feiler i stillhet. Det finnes ingen feilvei for det:
3D7 dekodes til 12 345, 13 957 eller 211 665 avhengig bare av hvilken rekkefølge som antas. Sjekk første tegn, som mest sannsynlig er en nullfylling, og sjekk om alfabetet har siffer eller bokstaver først. - Ledende nuller betyr to forskjellige ting. I heltallsmodus er
00012345 og 12345 det samme tallet og skrives likt ut. I bytemodus er en ledende nullbyte data, og den skrives ut som ett ekstra nulltegn. Å fjerne ett av disse tegnene endrer bytesekvensen. - Normalisering av store og små bokstaver ødelegger en kode. En e-postadresse, et vertsnavn eller en Windows-sti kan gjøres til små bokstaver underveis. En Base62-kode tåler ikke det, og det er grunnen til at Base36 fortsatt finnes.
- Lange inndata er trege, ikke bare store. Konverteringen er aritmetikk på hele inndataene på en gang, så en dobling av inndatalengden firedobler tiden. Denne siden avviser inndata over de målte grensene i stedet for å henge; størrelsestabellen lenger opp gir de målte tallene.
- En Base62-streng beviser ingenting. Siden nesten enhver streng med siffer og bokstaver dekodes uten klage, vil en vilkårlig URL-slug dekodes til et tall. En kode betyr bare noe hvis systemet som utstedte den også lagrer tilordningen.
Raske svar
“Hvorfor gir et annet Base62-verktøy en annen kode for samme tall?”
Fordi alfabetet er forskjellig. Base62 har ingen spesifikasjon å være uenige med, så implementasjoner velger en rekkefølge: siffer og store bokstaver først, siffer og små bokstaver først, eller bokstaver før siffer. Bytt alfabetvalget øverst på siden for å se alle tre svarene side om side.
“Er Base62 trygt i en URL?”
Ja, i alle tre rekkefølgene. Alle de 62 tegnene er uescapede bokstaver og siffer, så ingen av dem blir til en prosenttriplett i en spørringsstreng, og ingen av dem avslutter en URL, et stisegment eller en HTML-attributt. Det er hele grunnen til at korte lenker er Base62 og ikke Base64.
“Hva er mindre, Base62 eller Base64?”
For bytes er Base64 litt mindre: omtrent 133 % av inndataene mot omtrent 134 %. På 92-byte-eksempelet over er de uavgjort på 124 tegn. For desimaltall forkorter Base62 teksten med omtrent 44 %, og det er der den praktiske gevinsten ligger.
“Kan jeg dekode en Base64-streng med denne siden?”
Nei, og verktøyet vil ikke si fra når det har feilet. De to alfabetene overlapper i alle 62 tegnene, så en Base64-streng er vanligvis «gyldig» inndata her også og dekoder ganske enkelt til et annet tall. Bruk Base64 til Base64.
“Har en Base62-kode en maksimal lengde?”
Nei. I teorien har algoritmen ingen øvre grense. I praksis stopper denne siden ved 4096 desimale siffer, eller 2048 byte, fordi aritmetikken bak den er kvadratisk, og fanen ville fryse uten noe på skjermen som forklarer hvorfor. Grensetabellen lenger opp på denne siden lister de målte tallene.
“Hvordan vet jeg at resultatet på denne siden er riktig?”
Trykk Selvtest. Den kjører alle dokumenterte eksempler, hver bytelengde fra 0 til 64 og et spenn av desimaltall gjennom alle tre alfabetene, sammenligner de returnerte verdiene med det som gikk inn, og sjekker på nytt at hvert alfabets 62 tegn er trygge i en URL. Eksempel-knappen sammenligner i tillegg resultatene sine med verdiene som er registrert i sidens datafil, som ble verifisert mot en andre, uavhengig big-integer-implementasjon i denne sidens testverktøy.
Standarder og kreditering
Det finnes ingen standard å implementere her: Base62 er en konvensjon, ikke en spesifikasjon, og de tre alfabetene skrevet ut over er de som finnes i reell programvare. Denne siden implementerer det med nettstedets egne rutiner for store heltall, skrevet i ren aritmetikk på sifferarrayer, slik at ingen størrelse noen gang begrenses av JavaScript-tallstypen.
Sidens tekst er skrevet for denne siden. Hvert arbeidseksempel på siden ble laget av sidens egen kode og deretter verifisert mot en andre, uavhengig implementasjon som bruker native store heltall; den implementasjonen ligger i denne sidens testverktøy. Den samme implementasjonen verifiserte eksempel- og størrelsestabellene i datafilen.
