La codificació de parells de bytes (també coneguda com BPE, o codificació de digrames) és un algorisme, descrit per primera vegada l'any 1994 per Philip Gage, per codificar cadenes de text en cadenes més petites mitjançant la creació i l'ús d'una taula de traducció. Una versió lleugerament modificada de l'algoritme s'utilitza en tokenitzadors de models de llenguatge grans.
La versió original de l'algorisme es va centrar en la compressió. Substitueix el parell de bytes de freqüència més alta per un byte nou que no estava inclòs al conjunt de dades inicial. Es necessita una taula de cerca dels reemplaçaments per reconstruir el conjunt de dades inicial. La versió modificada crea "fitxes" (unitats de reconeixement) que coincideixen amb quantitats variables de text font, des de caràcters individuals (inclosos uns dígits o signes de puntuació) fins a paraules senceres (fins i tot paraules compostes llargues).
Algorisme original L'algoritme BPE original funciona substituint iterativament les seqüències contigües de caràcters més comunes en un text objectiu per bytes de "marcador de posició" no utilitzats. La iteració acaba quan no es poden trobar seqüències, deixant el text objectiu comprimit de manera efectiva. La descompressió es pot realitzar invertint aquest procés, consultant els termes de marcador de posició coneguts contra la seva seqüència denotada corresponent, utilitzant una taula de cerca. Al document original, aquesta taula de cerca està codificada i emmagatzemada al costat del text comprimit.
Exemple Suposem que les dades a codificar són
aaabdaaabac
El parell de bytes "aa" apareix amb més freqüència, de manera que se substituirà per un byte que no s'utilitza a les dades, com ara "Z". Ara hi ha les següents dades i taula de substitució:
ZabdZabac
Z=aa
A continuació, el procés es repeteix amb el parell de bytes "ab", substituint-lo per "Y":
ZYdZYac
Y=ab
Z=aa
L'únic parell de bytes literal que queda només es produeix una vegada, i la codificació podria aturar-se aquí. Alternativament, el procés podria continuar amb la codificació recursiva de parells de bytes, substituint "ZY" per "X":
XdXac
X=ZY
Y=ab
Z=aa
Per descomprimir les dades, només cal que realitzeu les substitucions en ordre invers.
Algorisme modificat L'algoritme BPE original es modifica per utilitzar-lo en el modelatge del llenguatge, especialment per als grans models de llenguatge basats en xarxes neuronals. En comparació amb el BPE original, el BPE modificat no té com a objectiu comprimir el text al màxim, sinó codificar el text sense format en "tokens", que són nombres naturals. Totes les fitxes úniques que es troben en un corpus s'enumeren en un vocabulari de fitxes, la mida del qual, en el cas de GPT-3.5 i GPT-4, és 100256.
L'algoritme de tokenització modificat inicialment tracta el conjunt de caràcters únics com a n-grams d'1 caràcter (els testimonis inicials). Aleshores, successivament, el parell de fitxes adjacents més freqüent es fusiona en un nou gram-n més llarg i totes les instàncies del parell són substituïdes per aquesta nova fitxa. Això es repeteix fins a obtenir un vocabulari de la mida prescrita. Tingueu en compte que les paraules noves sempre es poden construir a partir de fitxes de vocabulari final i caràcters del conjunt inicial.
Aquest enfocament BPE modificat s'ha estès des del llenguatge parlat al llenguatge de signes en els darrers anys.
Exemple Suposem que estem codificant l'exemple anterior de "aaabdaaabac", amb una mida de vocabulari especificada de 6, primer ens codificaríem com "0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 3" amb un vocabulari de "a=0, b=1, d=2, c=3". Aleshores procediria com abans, i obtindria "4, 5, 2, 4, 5, 0, 3" amb un vocabulari de "a=0, b=1, d=2, c=3, aa=4, ab=5".
Fins ara això és essencialment el mateix que abans. Tanmateix, si només haguéssim especificat una mida de vocabulari de 5, el procés s'aturaria al vocabulari "a=0, b=1, d=2, c=3, aa=4", de manera que l'exemple es codificaria com "4, 0, 1, 2, 4, 0, 1, 0, 3". Per contra, si haguéssim especificat una mida de vocabulari de 8, llavors es codificaria com a "7, 6, 0, 3", amb un vocabulari de "a=0, b=1, d=2, c=3, aa=4, ab=5, aaab=6, aaabd=7". Això no és el màxim d'eficiència, però el BPE modificat no pretén comprimir al màxim un conjunt de dades, sinó que pretén codificar-lo de manera eficient per a l'entrenament del model lingüístic.
BPE a nivell de bytes A l'exemple anterior, la sortida del BPE és un vocabulari, que es pot utilitzar per codificar qualsevol text que s'escriu amb les lletres "abcd". No podrà codificar text que contingui altres símbols, com ara "no". Fins i tot donant una entrada al vocabulari a cadascuna de les 26 lletres, ja que hi ha molts idiomes al món que utilitzen moltes escriptures diferents, inevitablement alguns símbols serien incodificables per aquest vocabulari.
Una solució és substituir qualsevol símbol no codificable per un símbol especial anomenat UNK ("desconegut").
El BPE a nivell de bytes és un altre enfocament. Simplement, primer converteix el text a UTF-8 i el tracta com un flux de bytes. Això garanteix que qualsevol text codificat en UTF-8 pot ser codificat pel BPE. S'ha utilitzat en models semblants a BERT com RoBERTa, BART i DeBERTa, i models semblants a GPT com GPT-2.
Referències
Categoria:Algorismes de compressió