Hola,
algunos de vosotros ya sabréis de los trabajos que he hecho en la SNES traduciendo juegos y ahora que estoy traduciendo el
Romancing Saga 3 me gustaría que me ayudarais con algún aporte o idea que se os ocurra para el algoritmo de compresión de texto.
Aunque el texto del juego no es demasiado extenso, me gustaría que los traductores que están ahora mismo con el script tuvieran toda la libertad para poder poner todo el texto que quieran, sin limitaciones de espacio. Por eso llevo maquinando un algoritmo de compresión basado en el que implementé en
Seiken Densetu 3 y que llevan otros juegos como
Tales of Phantasia o
Star Ocean.
Está basado en comprimir el texto con un diccionario y luego aplicarle la compresión Huffman para reducir al máximo el tamaño.
El algoritmo está aquí explicado:
* El árbol Huffman se guardará en ROM con esta estructura:
INICIO
/\
/ \
/ \
3 BYTES -> (RAMA) 0 1 (RAMA)
/\ /\
/ \ / \
/ \
(12 bits de puntero) 0 1 (12 bits de dato)
índice del árbol $800 - $84F -> comandos
respecto a INICIO $850 - $8CF -> caracteres
donde empieza el $8D0 - $8FF -> DTE
siguiente nodo $900 - $7FF -> resto de combinaciones
* El árbol Huffman tendrá un tamaño máximo limitado por el número de bits dedicados a los punteros; como son 12 bits, el puntero vale entre
0 y 4096; cada RAMA del árbol llevará el MSBit a '0' indicando que es un puntero, siendo útiles los 11 bits restantes. El valor que llevan estos
11 bits es el índice al árbol del siguiente salto/bifurcación, de modo que habrá que multiplicar este valor por 3 para obtener el offset final.
* En las hojas tendremos datos de 11 bits, porque el bit más alto siempre estára a '1' indicando que es una HOJA. En la implementación del
codificador tendremos que considerar la posibilidad de reducir el tamaño del árbol no usando los 11 bits de los datos, es decir, limitando el
número de HOJAs del árbol, ya que TODOS los datos del alfabeto en 11 bits han de aparecer como hojas en el árbol, y si usáramos las 2048 entradas
posibles del alfabeto con 11 bits, el árbol Huffman ocuparía AL MENOS 2048*3 = 6144 bytes (6Kbytes). Esto significa la mitad del tamaño del árbol,
que es de 4096 entradas * 3 bytes = 12288 bytes (12 Kbytes).
* En la ROM, el árbol Huffman se almacenará de esta forma:
INICIO+$0 INICIO+$3 INICIO+$6 INICIO+$9 INICIO+$C
----------------- ----------------- ----------------- ----------------- -----------------
| $001 - $002 | $003 - $004 | $005 - $8D4 | $006 - $007 | $9A1 - $008 | ...
----------------- ----------------- ----------------- ----------------- -----------------
es equivalente a:
----------------- ----------------- ----------------- ----------------- -----------------
| (0) RAMA+RAMA | (1) RAMA+RAMA | (2) RAMA+HOJA | (3) RAMA+RAMA | (4) HOJA+RAMA | ...
----------------- ----------------- ----------------- ----------------- -----------------
* Para hacer más efectiva la codificación Huffman hay que expandir el diccionario inicial (formado por los bytes de comando y los bytes de los
caracteres, cuya distribución de probabilidad es bastante uniforme en según qué letras) para que aparezcan en él elementos muy repetitivos. Esto
lo conseguimos agrupando todos los bytes del diccionario inicial de dos en dos y eligiendo las parejas que aparezcan más en el script. El algoritmo
será el siguiente:
1) Buscamos en el script las parejas de letras/comandos que más se repitan y elegimos las 32 más frecuentes para completar el rango entre $D0
y $FF. Sustituimos estas parejas por sus valores en todo el script para reducir su tamaño y convertimos el script a unsigned short, de
modo que todas los bytes se convierten en palabras de 16 bits, pero ocupando por el momento sólo el byte más bajo.
2) Volvemos a buscar en el script las parejas de letras/comandos/DTE que más se repitan y elegimos las 256 más repetitivas. Esto completará
el rango entre $0100 y $0200, por lo que ya tendremos en el script un alfabeto que va desde $0000 hasta $0200.
3) Con todas las entradas que hemos agrupado formamos la primera parte del diccionario que tendrá 288 entradas de 2 bytes cada una (cada
byte tendrá una letra o comando o bien un DTE del rango $00D0 a $00FF).
4) Repetimos el paso 2 tantas veces como sea necesario para completar el alfabeto hasta el número de entradas que consideremos necesarias.
En este caso ya no será necesario completar 256 entradas en cada iteración, el umbral se decidirá según las necesidades.
5) Con todas las entradas obtenidas en el paso 4 se creará la segunda parte del diccionario, en el que meteremos esta vez entradas de 4
bytes en los que los dos primeros son para un valor entre $0000 y $07FF y los dos siguientes bytes son para otro valor comprendido entre
$0000 y $07FF.
* Algunas mejoras para reducir el tamaño del script final serán:
1) Cambiar en el script ANTES DE INICIAR LA COMPRESIÓN todas las mayúsculas detrás de un punto o al principio de un diálogo por las letras
equivalentes en minúscula. El algoritmo de descompresión en el juego tendrá en cuenta cuándo ha aparecido un punto o cuándo se va a iniciar
un diálogo para convertir esa letra minúscula en mayúscula. Con esto conseguimos que esas letras mayúsculas no se tengan que codificar como
parte del alfabeto sino que contribuyan a incrementar la frecuencia de aparición de alguna pareja ya existente del diccionario.
2) Podemos usar el puntero del árbol Huffman como puntero relativo a la posición actual donde éste aparece: es decir, es un valor entero con
signo que nos dice a qué índice antes o después del actual saltamos para ir al siguiente nodo. Este valor al ser multiplicado por 3 nos da
el offset en bytes desde la posición de ese puntero al que saltamos. Con esto el árbol Huffman puede ser mayor ya que el límite lo impondrá
lo grande que sea la base, que podrá tener hasta 2048 entradas.
3) La parte del diccionario que esté formada por entradas de 16 bits se puede compactar ya que, realmente, cada entrada del diccionario
tendrá 12 bits, por lo que se puede usar parejas de 3 bytes en vez de 4.
A ver si a alguien se le puede ocurrir alguna idea más para reducir el tamaño final del texto comprmido, por ejemplo, incrementando las probabilidades del alfabeto, con alguna idea feliz de creación del árbol Huffman que dé el número de bits óptimo para cada símbolo junto con un menor tamaño del árbol, o cosas por el estilo.
¡Un saludo y gracias por anticipado!
