Množství s proměnnou délkou - Variable-length quantity
A množství proměnné délky (VLQ) je univerzální kód který používá libovolný počet binární oktety (osm-bit bajtů ) představovat libovolně velký celé číslo. VLQ je v podstatě reprezentace základny 128 nepodepsaného celého čísla s přidáním osmého bitu k označení pokračování bajtů. VLQ je totožný s LEB128 kromě v endianismus. Viz příklad níže.
Aplikace a historie
Komprese Base-128 je známá pod mnoha jmény - VB (Variable Byte), VByte, Varint, VInt, EncInt atd.[1]
A množství proměnné délky (VLQ) byl definován pro použití ve standardu MIDI soubor formát[2] ušetřit další místo pro systém s omezenými prostředky a je také používán později Extensible Music Format (XMF).
Základna 128 se také používá v ASN.1 BER kódování pro kódování čísel značek a Identifikátory objektů.[3] Používá se také v WAP prostředí, kde se tomu říká proměnná délka celé číslo bez znaménka nebo uintvar. The TRPASLÍK formát ladění[4] definuje variantu nazvanou LEB128 (nebo ULEB128 pro nepodepsaná čísla), kde nejméně významná skupina 7 bitů je zakódována v prvním bajtu a nejvýznamnější bity jsou v posledním bajtu (takže ve skutečnosti jde o analogický analog VLQ). Google Vyrovnávací paměti protokolu použít podobný formát pro kompaktní zobrazení celočíselných hodnot,[5] stejně jako Věštec Portable Object Format (POF)[6] a Microsoft .NET Framework "7bitový kódovaný int" v Binární čtečka a Binární spisovatel třídy.[7]
Používá se také ve velké míře ve webových prohlížečích pro mapování zdrojů - které obsahují mnoho mapování celých řádků a čísel sloupců - aby se minimalizovala velikost mapy.[8]
Celá čísla s proměnnou šířkou v LLVM použít podobný princip. Kódovací bloky jsou málo endianové a nemusí mít velikost 8 bitů. Dokumentace LLVM popisuje pole, které používá 4-bitový blok, přičemž každý blok se skládá z 1 bitového pokračování a 3 bitů užitečného zatížení.[9]
Obecná struktura
Kódování předpokládá oktet (osmibitový bajt), kde nejvýznamnější bit (MSB), také běžně známý jako znamení bit, je vyhrazeno k označení, zda následuje další oktet VLQ.
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
---|---|---|---|---|---|---|---|
27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
A | Bn |
Pokud A je 0, pak je to poslední VLQ oktet celého čísla. Pokud A je 1, následuje další oktet VLQ.
B je 7bitové číslo [0x00, 0x7F] an je poloha oktetu VLQ, kde B0 je nejméně významné. Oktety VLQ jsou uspořádány nejdříve nejvýznamnější v proudu.
Varianty
Obecné kódování VLQ je jednoduché, ale v základní formě je definováno pouze pro celá čísla bez znaménka (nezáporné, kladné nebo nulové) a je poněkud nadbytečné, protože předřazení oktetů 0x80 odpovídá nulovému odsazení. Existují různé podepsané číselné reprezentace zacházet se zápornými čísly a techniky k odstranění nadbytečnosti.
Skupinové kódování kódů
Google vyvinul GVE (Group Varint Encoding) poté, co zjistil, že tradiční kódování VLQ během dekomprese napadá mnoho větví CPU. GVE používá jeden bajt jako záhlaví pro 4 hodnoty uint32 s proměnnou délkou. Bajt záhlaví má 4 2bitová čísla představující délku úložiště každého z následujících 4 uint32. Takové rozložení vylučuje potřebu kontrolovat a odstraňovat pokračovací bity VLQ. Datové bajty lze kopírovat přímo na místo určení. Toto rozložení snižuje větve CPU, díky čemuž je GVE rychlejší než VLQ na moderních zřetězených procesorech.[10]
PrefixVarint je podobný design, ale s maximem uint64. Říká se, že „byla vynalezena několikrát samostatně“.[11] Je možné jej změnit na zřetězenou verzi s nekonečně mnoha pokračováními.
Podepsaná čísla
Podepsat bit
Záporná čísla lze zpracovat pomocí a znamení bit, který musí být přítomen pouze v prvním oktetu.
V datovém formátu pro Unreal Packages používané Neskutečný motor, schéma proměnné délky s názvem Compact Indices[12] se používá. Jediný rozdíl v tomto kódování spočívá v tom, že první VLQ má vyhrazený šestý bit, který označuje, zda je kódované celé číslo kladné nebo záporné. Jakýkoli následný oktet VLQ sleduje obecnou strukturu.
První VLQ oktet | Ostatní VLQ oktety | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 | 27 | 26 | 25 | 24 | 23 | 22 | 21 | 20 |
A | B | C0 | A | Cn (n> 0) |
Pokud A je 0, pak je to poslední oktet VLQ celého čísla. Pokud A je 1, pak následuje další oktet VLQ.
Pokud B je 0, pak VLQ představuje kladné celé číslo. Pokud B je 1, pak VLQ představuje záporné číslo.
C je kódovaný blok čísel a n je poloha oktetu VLQ, kde C0 je nejméně významné. Oktety VLQ jsou uspořádány nejdříve nejvýznamnější v proudu.[pochybný ]
Cik-cak kódování
Alternativním způsobem kódování záporných čísel je použití nejméně významného bitu pro znaménko. To se děje zejména u vyrovnávacích pamětí protokolu Google a je známé jako klikaté kódování pro podepsaná celá čísla.[13] Lze kódovat čísla tak, aby kódovaná 0 odpovídala 0, 1 až −1, 10 až 1, 11 až −2, 100 až 2 atd .: počítání se střídá mezi negativními (počínaje 0) a zápornými (od každého kroku) změní nejméně významný bit, tedy znak), odkud pochází název „cikcak kódování“. Konkrétně transformujte celé číslo jako (n << 1) ^ (n >> k - 1)
pro pevné k-bit celá čísla.
Doplněk dvou
Použití LEB128 doplněk dvou reprezentovat podepsaná čísla. V tomto schématu reprezentace n bitů kóduje rozsah od -2n až 2n-1 a všechna záporná čísla začínají 1 v nejvýznamnějším bitu. V Signed LEB128 je vstup znamení prodlouženo takže jeho délka je násobkem 7 bitů. Odtamtud pokračuje kódování jako obvykle.[14]
V LEB128 je stream nejprve uspořádán nejméně významný.[14]
Odstraňování nadbytečnosti
S výše popsaným kódováním VLQ lze libovolné číslo, které lze kódovat pomocí N oktetů, také kódovat více než N oktetů jednoduše přidáním dalších 0x80 oktetů jako nulové výplně. Například desetinné číslo 358 lze kódovat jako 2-oktetový VLQ 0x8266 nebo číslo 0358 lze kódovat jako 3-oktetový VLQ 0x808266 nebo 00358 jako 4-oktetový VLQ 0x80808266 a tak dále.
Formát VLQ použitý v Git[15] odstraní tuto předběžnou redundanci a rozšíří reprezentativní rozsah kratších VLQ přidáním offsetu k VLQ 2 nebo více oktetů takovým způsobem, že nejnižší možná hodnota pro takový (N + 1) -oktetový VLQ se stane přesně o jeden více než maximum možná hodnota pro N-oktet VLQ. Zejména proto, že 1-oktetový VLQ může uložit maximální hodnotu 127, je minimální 2-oktetový VLQ (0x8000) přiřazena hodnota 128 místo 0. Naopak, maximální hodnota takového 2-oktetového VLQ (0xff7f) je 16511 místo pouhých 16383. Podobně má minimální 3-oktetový VLQ (0x808000) hodnotu 16512 místo nuly, což znamená, že maximální 3-oktetový VLQ (0xffff7f) je 2113663 místo pouhých 2097151.
Tímto způsobem existuje jedno a pouze jedno kódování každého celého čísla, což z něj činí základnu 128 bijektivní číslování.
Příklady

Zde je vypracovaný příklad desetinného čísla 137:
- Reprezentujte hodnotu v binární notaci (např. 137 jako 10001001)
- Rozdělte to do skupin po 7 bitech počínaje od nejnižšího významného bitu (např. 137 jako 0000001 0001001). To odpovídá představování čísla v základna 128.
- Vezměte nejnižší 7 bitů a získáte nejméně významný bajt (0000 1001). Tento bajt přichází jako poslední.
- Pro všechny ostatní skupiny 7 bitů (v příkladu je to 000 0001) nastavte MSB na 1 (což dává 1000 0001 v našem příkladu). Tak se stane 137 1000 0001 0000 1001, kde bity v tučně jsou něco, co jsme přidali. Tyto přidané bity označují, zda je třeba následovat další bajt nebo ne. Podle definice tedy bude mít poslední byt celého čísla s proměnnou délkou 0 MSB.
Dalším způsobem, jak se na to podívat, je reprezentovat hodnotu v základně 128 a poté nastavit MSB všech kromě poslední číslice základny 128 na 1.
Specifikace formátu Standard MIDI File uvádí další příklady:[2][16]
Celé číslo (desítkově) | Celé číslo (šestnáctkové) | Celé číslo (binární) | Množství proměnné délky (hexadecimální) | Množství proměnné délky (binární) |
---|---|---|---|---|
0 | 0x00000000 | 00000000 00000000 00000000 00000000 | 0x00 | 00000000 |
127 | 0x0000007F | 00000000 00000000 00000000 01111111 | 0x7F | 01111111 |
128 | 0x00000080 | 00000000 00000000 00000000 10000000 | 0x81 0x00 | 10000001 00000000 |
8192 | 0x00002000 | 00000000 00000000 00100000 00000000 | 0xC0 0x00 | 11000000 00000000 |
16383 | 0x00003FFF | 00000000 00000000 00111111 11111111 | 0xFF 0x7F | 11111111 01111111 |
16384 | 0x00004000 | 00000000 00000000 01000000 00000000 | 0x81 0x80 0x00 | 10000001 10000000 00000000 |
2097151 | 0x001FFFFF | 00000000 00011111 11111111 11111111 | 0xFF 0xFF 0x7F | 11111111 11111111 01111111 |
2097152 | 0x00200000 | 00000000 00100000 00000000 00000000 | 0x81 0x80 0x80 0x00 | 10000001 10000000 10000000 00000000 |
134217728 | 0x08000000 | 00001000 00000000 00000000 00000000 | 0xC0 0x80 0x80 0x00 | 11000000 10000000 10000000 00000000 |
268435455 | 0x0FFFFFFF | 00001111 11111111 11111111 11111111 | 0xFF 0xFF 0xFF 0x7F | 11111111 11111111 11111111 01111111 |
Reference
- ^ Jianguo Wang; Chunbin Lin; Yannis Papakonstantinou; Steven Swanson.„Experimentální studie komprese bitmap vs. komprese obráceného seznamu“.2017.doi:10.1145/3035918.3064007
- ^ A b Formát souboru MIDI: Variabilní množství
- ^ http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf
- ^ Standard DWARF
- ^ Vyrovnávací paměti protokolu Google
- ^ Oracle Portable Object Format (POF)
- ^ Metoda System.IO.BinaryWriter.Write7BitEncodedInt (int) a Metoda System.IO.BinaryReader.Read7BitEncodedInt ()
- ^ Úvod do zdrojových map javascriptů
- ^ "Formát souboru bitcoinu LLVM", část "Celá čísla proměnné šířky". Přístupné 10. 10. 2019.
- ^ Jeff Dean. „Výzvy při budování rozsáhlých informačních systémů“ (PDF). str. 58. Citováno 2020-05-30.
- ^ Olesen, Jakob Stoklund (31. května 2020). "stoklund / varint".
- ^ http://unreal.epicgames.com/Packages.htm
- ^ Vyrovnávací paměti protokolu: Kódování: Podepsaná celá čísla
- ^ A b Skupina bezplatných standardů (prosinec 2005). „Specifikace formátu ladění informací DWARF verze 3.0“ (PDF). str. 70. Citováno 2009-07-19.
- ^ https://github.com/git/git/blob/7fb6aefd2aaffe66e614f7f7b83e5b7ab16d4806/varint.c#L4
- ^ Standardní specifikace formátu MIDI souboru. 1.1 (PDF)
externí odkazy
- Sdružení výrobců MIDI (MMA) - Zdroj pro specifikace MIDI v angličtině
- Asociace hudebního elektronického průmyslu (AMEI) - Zdroj pro specifikace MIDI v japonštině