{"id":61,"date":"2025-12-30T08:31:15","date_gmt":"2025-12-30T08:31:15","guid":{"rendered":"https:\/\/pulki.es\/blog\/?p=61"},"modified":"2025-12-30T08:31:15","modified_gmt":"2025-12-30T08:31:15","slug":"large-language-model-llm-from-scratch-algoritmo-bpe","status":"publish","type":"post","link":"https:\/\/pulki.es\/blog\/index.php\/2025\/12\/30\/large-language-model-llm-from-scratch-algoritmo-bpe\/","title":{"rendered":"Large Language Model (LLM) from scratch. Algoritmo BPE."},"content":{"rendered":"\n

En la entrada anterior<\/a> motivamos el algoritmo BPE. Ahora hablaremos brevemente de su historia y explicaremos en detalle c\u00f3mo funciona.<\/p>\n\n\n\n

El algoritmo BPE, desarrollado por Philip Gage (1994)<\/a>, es un m\u00e9todo cl\u00e1sico en lo que respecta a la compresi\u00f3n de datos. Su idea central es recorrer los datos y encontrar el par de bytes adyacentes m\u00e1s frecuente para, luego, sustituir esas apariciones por un byte libre. A modo de ejemplo, supongamos que tenemos 10 bytes:<\/p>\n\n\n\n

65<\/td>66<\/td>65<\/td>66<\/td>65<\/td>66<\/td>67<\/td>68<\/td>69<\/td>70<\/td><\/tr>
A<\/td>B<\/td>A<\/td>B<\/td>A<\/td>B<\/td>C<\/td>D<\/td>E<\/td>F<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

En este caso, la primera fila representa el n\u00famero del byte escrito en decimal. La segunda corresponde a su interpretaci\u00f3n en ASCII. Entonces, acorde con la l\u00f3gica del algoritmo, debemos recorrer esa tabla y encontrar el par de bytes m\u00e1s frecuente. En nuestro caso, ser\u00eda:<\/p>\n\n\n\n

Car\u00e1cter<\/td>Frecuencia<\/td><\/tr>
AB<\/td>3<\/td><\/tr>
BA<\/td>2<\/td><\/tr>
BC<\/td>1<\/td><\/tr>
CD<\/td>1<\/td><\/tr>
DE<\/td>1<\/td><\/tr>
EF<\/td>1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Seg\u00fan la tabla, el par m\u00e1s frecuente es AB. A partir de aqu\u00ed, debemos elegir un \u00abbyte libre\u00bb. De antemano, sabemos que los bytes que van desde 65 a 70 est\u00e1n ocupados, y que los que van desde 0 a 64, y de 71 a 255, est\u00e1n libres. Para efectos de este ejemplo, utilizaremos el byte 80 como el \u00abbyte libre\u00bb que denotar\u00e1 el par \u00abAB\u00bb. Dicho lo anterior, podemos escribir la siguiente tabla:<\/p>\n\n\n\n

80<\/td>80<\/td>80<\/td>67<\/td>68<\/td>69<\/td>70<\/td><\/tr>
AB<\/td>AB<\/td>AB<\/td>C<\/td>D<\/td>E<\/td>F<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Vale la pena destacar que esta matriz ya no tiene la misma interpretaci\u00f3n que la anterior. En este caso, 80 representa \u00abAB\u00bb en el algoritmo, pero eso no implica que su interpretaci\u00f3n en ASCII sea \u00abAB\u00bb (de hecho, en ASCII es la letra P). Dicho esto, como podemos ver, un archivo que antes ten\u00eda 10 bytes pudo reducirse a 7 (y podr\u00eda reducirse a\u00fan m\u00e1s). En la siguiente secci\u00f3n, veremos c\u00f3mo este algoritmo ha sido adaptado para llevar a cabo una segmentaci\u00f3n en subwords<\/em>.<\/p>\n\n\n\n

Adaptando BPE para construir subwords<\/em> (Senrich et al., 2016).<\/strong><\/p>\n\n\n\n

Senrich et al. (2016)<\/a>, tomaron el concepto desarrollado por Gage (1994), y lo extendieron para tokenizar en modelos modernos de lenguaje. <\/p>\n\n\n\n

Este algoritmo consta de dos partes: un entrenador y un codificador. En la etapa de entrenamiento, debemos tomar un texto crudo para inducir un conjunto de tokens. Luego, en la etapa de codificaci\u00f3n, empleamos una sentencia de prueba para tokenizarla, utilizando las fusiones de la etapa previa en el orden en que fueron aprendidas. Dicho esto, empezaremos explicando la fase de entrenamiento.<\/p>\n\n\n\n

Etapa de entrenamiento…<\/strong><\/p>\n\n\n\n

Su funcionamiento es muy similar al algoritmo propuesto por Gage (1994). Iterativamente, se fusionan tokens aleda\u00f1os frecuentes para crear nuevos, cuyas cadenas de texto sean cada vez m\u00e1s largas. Para ilustrar la mec\u00e1nica subyacente, tomaremos el ejemplo del libro que estamos usando como referencia (Jurafsky y James H. Martin, 2025<\/a>). Supongamos que tenemos un corpus de 10 caracteres de largo, y que nuestro vocabulario es de 5 caracteres, es decir, A,B,C,D,E:<\/p>\n\n\n\n

A<\/td>B<\/td>D<\/td>C<\/td>A<\/td>B<\/td>E<\/td>C<\/td>A<\/td>B<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Esto nos entrega la siguiente tabla de frecuencias,<\/p>\n\n\n\n

Par<\/strong><\/td>Frecuencia<\/strong><\/td><\/tr>
AB<\/td>3<\/td><\/tr>
CA<\/td>2<\/td><\/tr>
DC<\/td>1<\/td><\/tr>
BD<\/td>1<\/td><\/tr>
BE<\/td>1<\/td><\/tr>
EC<\/td>1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

De aqu\u00ed, deducimos que el par m\u00e1s frecuente es \u00abAB\u00bb. Por tanto, debemos fusionar los pares adyacentes \u00abA | B\u00bb en \u00abAB\u00bb, lo que genera un nuevo corpus de 7 tokens, cuya estructura se muestra en la siguiente tabla:<\/p>\n\n\n\n

AB<\/td>D<\/td>C<\/td>AB<\/td>E<\/td>C<\/td>AB<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Y constar\u00e1 de un vocabulario de 6 tokens: A, B, C, D, E y AB. Ahora, repitiendo el proceso, el par m\u00e1s frecuente es \u00abC | AB\u00bb, lo que convierte nuestro corpus en:<\/p>\n\n\n\n

AB<\/td>D<\/td>CAB<\/td>E<\/td>CAB<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Y el vocabulario asociado, en el siguiente conjunto: A, B, C, D, E, AB y CAB. El algoritmo contin\u00faa hasta generar k<\/em> fusiones, siendo k<\/em> un n\u00famero definido ex\u00f3genamente.<\/p>\n\n\n\n

En este ejemplo, utilizamos una cadena de texto con una palabra de 10 caracteres. No obstante, en la pr\u00e1ctica, un corpus est\u00e1 compuesto por m\u00e1s de una palabra, que, generalmente, est\u00e1n separadas por un espacio en blanco. Entonces, \u00bfc\u00f3mo lidiamos con m\u00e1s de una palabra? Ve\u00e1moslo con un ejemplo:<\/p>\n\n\n\n

Supongamos que tenemos el siguiente texto, donde \u00ab_\u00bb representa un espacio en blanco:<\/p>\n\n\n\n

set_new_new_renew_reset_renew<\/code><\/pre>\n\n\n\n
Al igual que en el ejemplo anterior, podemos separar los caracteres de la siguiente forma:<\/p>\n\n\n\n
s<\/td>e<\/td>t<\/td>_<\/td>n<\/td>e<\/td><\/tr>
w<\/td>_<\/td>n<\/td>e<\/td>w<\/td>_<\/td><\/tr>
r<\/td>e<\/td>n<\/td>e<\/td>w<\/td>_<\/td><\/tr>
r<\/td>e<\/td>s<\/td>e<\/td>t<\/td>_<\/td><\/tr>
r<\/td>e<\/td>n<\/td>e<\/td>w<\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
y caracterizar el vocabulario como: _, e, n, r, s, t y w. En este caso, tal como lo hemos hecho anteriormente, debemos contar los pares m\u00e1s frecuentes del texto original. En particular, el par \u00abne\u00bb es el m\u00e1s frecuente (se repite 4 veces). Entonces, la nueva tabla puede reescribirse como:<\/p>\n\n\n\n
s<\/td>e<\/td>t<\/td>_<\/td>ne<\/td>w<\/td><\/tr>
_<\/td>ne<\/td>w<\/td>_<\/td>r<\/td>e<\/td><\/tr>
ne<\/td>w<\/td>_<\/td>r<\/td>e<\/td>s<\/td><\/tr>
e<\/td>t<\/td>_<\/td>r<\/td>e<\/td>ne<\/td><\/tr>
w<\/td><\/td><\/td><\/td><\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
lo que genera el siguiente vocabulario: _, e, n, r, s, t, w, ne. Repitiendo el proceso,<\/p>\n\n\n\n
s<\/td>e<\/td>t<\/td>_<\/td>ne<\/td>w<\/td><\/tr>
_<\/td>ne<\/td>w<\/td>_<\/td>r<\/td>e<\/td><\/tr>
ne<\/td>w<\/td>_<\/td>r<\/td>e<\/td>s<\/td><\/tr>
e<\/td>t<\/td>_<\/td>r<\/td>e<\/td>ne<\/td><\/tr>
w<\/td><\/td><\/td><\/td><\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
el par m\u00e1s frecuente es \u00abne w\u00bb. Por tanto, la nueva tabla viene dada por:<\/p>\n\n\n\n
s<\/td>e<\/td>t<\/td>_<\/td>new<\/td>_<\/td><\/tr>
new<\/td>_<\/td>r<\/td>e<\/td>new<\/td>_<\/td><\/tr>
r<\/td>e<\/td>s<\/td>e<\/td>t<\/td>_<\/td><\/tr>
r<\/td>e<\/td>new<\/td><\/td><\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
y el nuevo vocabulario por: _, e, n, r, s, t, w, ne, new. Si repetimos una vez m\u00e1s este proceso, el par m\u00e1s frecuente es \u00ab_r\u00bb, lo que convierte nuestro corpus en:<\/p>\n\n\n\n
s<\/td>e<\/td>t<\/td>_<\/td>new<\/td>_<\/td><\/tr>
new<\/td>_r<\/td>e<\/td>new<\/td>_r<\/td>e<\/td><\/tr>
s<\/td>e<\/td>t<\/td>_r<\/td>e<\/td>new<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
con el siguiente vocabulario: _, e, n, r, s, t, w, ne, new, _r. De esta forma, podemos seguir hasta generar k <\/em>uniones.<\/p>\n\n\n\n
Etapa de codificaci\u00f3n…<\/strong><\/p>\n\n\n\n
En esta etapa convertimos un texto nuevo en una secuencia de tokens usando las fusiones que hemos aprendido, en el mismo orden que fueron aprendidas, y de forma greedy<\/em> (si se puede fusionar, fusiona). A modo de ejemplo, supongamos que este fue el orden de aprendizaje en la etapa de entrenamiento:<\/p>\n\n\n\n
1) n + e<\/td>ne<\/td><\/tr>
2) ne + w<\/td>new<\/td><\/tr>
3) _ + r<\/td>_r<\/td><\/tr>
4) _r + e<\/td>_re<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Adem\u00e1s, supondremos que nuestro texto de prueba s\u00f3lo contiene la palabra \u00abnew\u00bb, es decir,<\/p>\n\n\n\n
n<\/td>e<\/td>w<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
Luego, como tenemos una fusi\u00f3n \u00abn+e = ne\u00bb, el resultado ser\u00eda:<\/p>\n\n\n\n
ne<\/td>w<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
y finalmente, ne + w = new. Vale la pena destacar que debido a la trivialidad del ejemplo, el orden de prioridad no juega un rol importante en el resultado. Para que veas que el orden puede alterarlo, te dejo el siguiente ejercicio: dado estos dos rankings<\/em>,<\/p>\n\n\n\n
1) n + e<\/td>ne<\/td>1) e +w<\/td>ew<\/td><\/tr>
2) ne + w<\/td>new<\/td>2) n + e<\/td>ne<\/td><\/tr>
<\/td><\/td>3) ne+w<\/td>new<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
trata de codificar la palabra \u00abnew\u00bb. Hint<\/strong>: para el primer ranking, terminar\u00e1s con [new], y para el segundo terminar\u00e1s con [n,ew].<\/p>\n\n\n\n
Notas finales, y pr\u00f3xima entrada\u2026<\/em><\/strong><\/p>\n\n\n\n
En esta entrada vimos como funciona el algoritmo BPE en el contexto de la construcci\u00f3n de subwords<\/em>, y en el art\u00edculo en que se basaron los autores para idearlo. En la pr\u00f3xima entrada veremos como funciona este procedimiento en la pr\u00e1ctica! Stay tuned!<\/p>\n\n\n\n
Jos\u00e9 Miguel Mu\u00f1oz Urra \u2013 jmunozu@pulki.es<\/a><\/p>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
En la entrada anterior motivamos el algoritmo BPE. Ahora hablaremos brevemente de su historia y explicaremos en detalle c\u00f3mo funciona. El algoritmo BPE, desarrollado por Philip Gage (1994), es un m\u00e9todo cl\u00e1sico en lo que respecta a la compresi\u00f3n de datos. Su idea central es recorrer los datos y encontrar el par de bytes adyacentes […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-61","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/posts\/61","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=61"}],"version-history":[{"count":5,"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/posts\/61\/revisions"}],"predecessor-version":[{"id":66,"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/posts\/61\/revisions\/66"}],"wp:attachment":[{"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=61"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=61"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pulki.es\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=61"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}