para - ¿Hace que una cadena utf-8 sea más corta con una codificación utf-32 en Javascript?
javascript descargar (4)
Estoy tratando de encontrar una forma de comprimir / descomprimir una cadena en Javascript. Al comprimir me refiero a hacer que la cuerda parezca más corta (menos carbón). Ese es mi objetivo.
Aquí hay un ejemplo de cómo deberían funcionar las cosas:
// The string that I want to make shorter
// It will only contain [a-zA-Z0-9] chars and some ponctuations like ()[]{}.,;''"!
var string = "I like bananas !";
// The compressed string, maybe something like "䐓㐛꯱字",
// which is shorter than the original
var shortString = compress(string);
// The original string, "I like banana !"
var originalString = decompress(shortString);
Esta es mi primera idea (tal vez haya una mejor manera de llegar a mi objetivo, y si es así, me interesa).
Sé que mi cadena original estará en utf-8. Así que estoy pensando en usar utf-32 para la codificación, que debería dividir por 4 la longitud de la cadena.
Pero no sé cómo hacer estas 2 funciones que construyen nuevas cadenas con codificación diferente. Aquí está el código que tengo hasta ahora que no funciona ...
function compress(string) {
string = unescape(encodeURIComponent(string));
var newString = '''';
for (var i = 0; i < string.length; i++) {
var char = string.charCodeAt(i);
newString += parseInt(char, 8).toString(32);
}
return newString;
}
Si sus cadenas solo contienen caracteres ASCII [0, 127], puede "comprimir" la cadena utilizando una página de códigos personalizada de 6 o 7 bits.
Puede hacerlo de varias maneras, pero creo que uno de los métodos más simples es definir una matriz que contenga todos los caracteres permitidos, una LUT, tabla de búsqueda si lo desea, luego use su valor de índice como el valor codificado. Por supuesto, debe enmascarar y cambiar manualmente el valor codificado en una matriz tipada.
Si su LUT se veía así:
var lut = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,:;!(){}";
En este caso, usted trataría con una LUT de longitud 71, lo que significa que necesitaríamos usar un rango de 7 bits o [0, 127] (si la longitud fuera 64, podríamos haberla reducido a 6 bits [0, 63] ] valores).
Luego, tomaría cada uno de los caracteres de la cadena y los convertiría en valores de índice (normalmente haría todos los siguientes pasos en una sola operación, pero los separé por simplicidad):
var lut = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.,:;!(){}";
var str = "I like bananas !";
var page = [];
Array.prototype.forEach.call(str, function(ch) {
var i = lut.indexOf(ch);
if (i < 0) throw "Invalid character - can''t encode";
page.push(i);
});
console.log("Intermediate page:", page);
Siempre puede ajustar el LUT para que los caracteres más utilizados estén al principio, luego admitir el rango de bits de codificación variable, encontrar el valor máximo y usar eso para determinar en qué rango desea codificar. Puede agregar un bit inicial como indicador en cuanto al rango que utiliza la codificación (por ejemplo, el bit 0 se establece si se ajusta a 6 bits, de lo contrario se utiliza un rango de 7 bits).
Ahora que conoce los índices, podemos comenzar a codificar la salida binaria utilizando un enfoque de 7 bits. Como JavaScript solo admite valores de bytes, es decir, un ancho de 8 bits, debemos realizar todas las operaciones de división, desplazamiento y fusión manualmente.
Esto significa que necesitamos hacer un seguimiento del resto y la posición en un nivel de bit.
Digamos que el primer valor de índice fue el siguiente valor de 7 bits (rango completo de 7 bits para la legibilidad, todo en pseudo-formato):
&b01111111
El primer paso sería desplazarlo a la posición de bit 0 y realizar un seguimiento de un resto:
&b01111111 << 1
Resultando en:
&b11111110
^
new bit position: 7
new remainder : 1
Luego, el siguiente valor de índice, por ejemplo:
&b01010101
se codificaría así: primero conviértalo en valor de 7 bits en su propia representación de bytes:
&b01010101 << 1 => &b10101010
A continuación, obtenga la parte de recordatorio primero. Para obtener esto, cambiará todo a la derecha usando 8 bits menos el resto actual (dentro del módulo de 8):
remainderValue = &b10101010 >>> (8 - remainder)
dejándonos con la siguiente representación:
&b00000001
(Tenga en cuenta que usamos triple >>> para cambiar a la derecha para evitar problemas con el signo).
El siguiente paso ahora es fusionar este valor con nuestro valor anterior que ya ha sido codificado y almacenado en nuestra matriz de bytes de destino, para esto usaremos una operación OR:
Index 0 New value Result in index 0 (index of dst. array)
&b11111110 | &b00000001 => &b11111111
luego vaya al siguiente índice en nuestra matriz de destino y almacene el resto del valor actual, luego actualice el resto y la posición.
El "sobrante" del byte se calcula así utilizando el valor original (después de cambiarlo) de bytes de 7 bits:
leftover = &b10101010 << remainder => &b01010100
que ahora ponemos en la siguiente posición:
Index 0 Index 1 (destination array index, not page index)
&b11111111 01010100
^
new bit position: 14
new remainder : 2
Y así sucesivamente con los valores de índice restantes. Consulte esta respuesta para ver el código real sobre cómo puede hacer esto en JavaScript: el código de esta respuesta no trata con la codificación de cadenas per se, pero muestra cómo puede cambiar los búferes de bytes por bits, que es esencialmente lo mismo que necesita. para esta tarea.
Para calcular el resto del paso , use 8 bits menos su rango de bits personalizado:
step = 8 - newRange (here 7) => 1
Este también será el resto del comienzo. Para cada personaje, agregará el paso al resto después de que se haya procesado, pero recuerde usar el módulo 8 (ancho de bytes) cuando lo use para el cambio:
remainder += step;
numOfBitsToShift = remainder % 8;
La posición de bit usa, por supuesto, el rango de bits, en este caso 7:
bitPosition += 7;
Luego, para encontrar los índices con los que está dividiendo el bitPosition en 8, si hay un decimal, tiene que tratar con dos índices (antiguo y nuevo), si no hay decimal, la posición actual representa un índice nuevo solamente (solo se necesita un cambio para el actual) valor de índice).
También puede usar módulo y cuando módulo de residuo = paso , sabe que está tratando con un único índice en el destino.
Para calcular la longitud final usaría la longitud de bit y la longitud de la cadena, luego ceil el resultado para que todos los caracteres encajen en una matriz de bytes de 8 bytes, que es la única matriz que podemos obtener en JavaScript:
dstLength = Math.ceil(7 * str.length / 8);
Para decodificar simplemente invierte todos los pasos.
Una alternativa, si utiliza cadenas largas o tiene que avanzar rápidamente, es usar un compresor establecido como zlib que tiene un encabezado muy compacto, así como un buen rendimiento en JavaScript en el caso de la solución vinculada. Esto también tratará con "patrones" en la cadena para optimizar aún más el tamaño resultante.
Descargo de responsabilidad: ya que esta es principalmente una respuesta teórica, puede haber algunos errores. No dude en comentar si se encuentran alguno. Consulte la respuesta vinculada para obtener un ejemplo de código real.
Dado que está utilizando un conjunto de menos de 100 caracteres y que las cadenas de javascript están codificadas en UTF-16 (lo que significa que tiene 65536 caracteres posibles), lo que puede hacer es concatenar los códigos de caracteres para tener un carácter "comprimido" por dos personajes básicos. Esto le permite comprimir cadenas a la mitad de la longitud.
Por ejemplo, por ejemplo:
document.getElementById(''compressBtn'').addEventListener(''click'', function() {
var stringToCompress = document.getElementById(''tocompress'').value;
var compressedString = compress(stringToCompress);
var decompressedString = decompress(compressedString);
if (stringToCompress === decompressedString) {
document.getElementById(''display'').innerHTML = stringToCompress + ", length of " + stringToCompress.length + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;
} else {
document.getElementById(''display'').innerHTML = "This string cannot be compressed"
}
})
function compress(string) {
string = unescape(encodeURIComponent(string));
var newString = '''',
char, nextChar, combinedCharCode;
for (var i = 0; i < string.length; i += 2) {
char = string.charCodeAt(i);
if ((i + 1) < string.length) {
// You need to make sure that you don''t have 3 digits second character else you might go over 65536.
// But in UTF-16 the 32 characters aren''t in your basic character set. But it''s a limitation, anything
// under charCode 32 will cause an error
nextChar = string.charCodeAt(i + 1) - 31;
// this is to pad the result, because you could have a code that is single digit, which would make
// decompression a bit harder
combinedCharCode = char + "" + nextChar.toLocaleString(''en'', {
minimumIntegerDigits: 2
});
// You take the concanated code string and convert it back to a number, then a character
newString += String.fromCharCode(parseInt(combinedCharCode, 10));
} else {
// Here because you won''t always have pair number length
newString += string.charAt(i);
}
}
return newString;
}
function decompress(string) {
var newString = '''',
char, codeStr, firstCharCode, lastCharCode;
for (var i = 0; i < string.length; i++) {
char = string.charCodeAt(i);
if (char > 132) {
codeStr = char.toString(10);
// You take the first part of the compressed char code, it''s your first letter
firstCharCode = parseInt(codeStr.substring(0, codeStr.length - 2), 10);
// For the second one you need to add 31 back.
lastCharCode = parseInt(codeStr.substring(codeStr.length - 2, codeStr.length), 10) + 31;
// You put back the 2 characters you had originally
newString += String.fromCharCode(firstCharCode) + String.fromCharCode(lastCharCode);
} else {
newString += string.charAt(i);
}
}
return newString;
}
var stringToCompress = ''I like bananas!'';
var compressedString = compress(stringToCompress);
var decompressedString = decompress(compressedString);
document.getElementById(''display'').innerHTML = stringToCompress + ", length of " + stringToCompress.length + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;
body {
padding: 10px;
}
#tocompress {
width: 200px;
}
<input id="tocompress" placeholder="enter string to compress" />
<button id="compressBtn">
Compress input
</button>
<div id="display">
</div>
En cuanto al posible uso de UTF-32 para comprimir aún más, no estoy seguro de que sea posible, podría estar equivocado al respecto, pero desde mi punto de vista no es factible. Este es el por qué:
El enfoque anterior básicamente concatena dos valores de 1 byte en un valor de 2 bytes. Esto es posible porque las cadenas javascript están codificadas en 2 bytes (o 16 bits) (tenga en cuenta que, por lo que entiendo, el motor podría decidir almacenar de forma diferente haciendo que esta compresión sea innecesaria desde el punto de vista del espacio de memoria puramente; dicho esto, al final , un personaje se considera de 16 bits). Una forma más limpia de hacer la compresión anterior sería, de hecho, utilizar los números binarios en lugar del decimal, tendría mucho más sentido. Por ejemplo, por ejemplo:
document.getElementById(''compressBtn'').addEventListener(''click'', function() {
var stringToCompress = document.getElementById(''tocompress'').value;
var compressedString = compress(stringToCompress);
var decompressedString = decompress(compressedString);
if (stringToCompress === decompressedString) {
document.getElementById(''display'').innerHTML = stringToCompress + ", length of " + stringToCompress.length + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;
} else {
document.getElementById(''display'').innerHTML = "This string cannot be compressed"
}
})
function compress(string) {
string = unescape(encodeURIComponent(string));
var newString = '''',
char, nextChar, combinedCharCode;
for (var i = 0; i < string.length; i += 2) {
// convert to binary instead of keeping the decimal
char = string.charCodeAt(i).toString(2);
if ((i + 1) < string.length) {
nextChar = string.charCodeAt(i + 1).toString(2) ;
// you still need padding, see this answer https://.com/questions/27641812/way-to-add-leading-zeroes-to-binary-string-in-javascript
combinedCharCode = "0000000".substr(char.length) + char + "" + "0000000".substr(nextChar.length) + nextChar;
// You take the concanated code string and convert it back to a binary number, then a character
newString += String.fromCharCode(parseInt(combinedCharCode, 2));
} else {
// Here because you won''t always have pair number length
newString += string.charAt(i);
}
}
return newString;
}
function decompress(string) {
var newString = '''',
char, codeStr, firstCharCode, lastCharCode;
for (var i = 0; i < string.length; i++) {
char = string.charCodeAt(i);
if (char > 132) {
codeStr = char.toString(2);
// You take the first part (the first byte) of the compressed char code, it''s your first letter
firstCharCode = parseInt(codeStr.substring(0, codeStr.length - 7), 2);
// then the second byte
lastCharCode = parseInt(codeStr.substring(codeStr.length - 7, codeStr.length), 2);
// You put back the 2 characters you had originally
newString += String.fromCharCode(firstCharCode) + String.fromCharCode(lastCharCode);
} else {
newString += string.charAt(i);
}
}
return newString;
}
var stringToCompress = ''I like bananas!'';
var compressedString = compress(stringToCompress);
var decompressedString = decompress(compressedString);
document.getElementById(''display'').innerHTML = stringToCompress + ", length of " + stringToCompress.length + " characters compressed to " + compressedString + ", length of " + compressedString.length + " characters back to " + decompressedString;
<input id="tocompress" placeholder="enter string to compress" />
<button id="compressBtn">
Compress input
</button>
<div id="display">
</div>
Entonces, ¿por qué no empujar la lógica y usar utf-32, que debe ser de 4 bytes, es decir, cuatro caracteres de 1 byte. Un problema es que javascript tiene una cadena de 2 bytes. Es cierto que puede usar pares de caracteres de 16 bits para representar caracteres utf-32. Me gusta esto:
document.getElementById(''test'').innerHTML = "/uD834/uDD1E";
<div id="test"></div>
Pero si prueba la longitud de la cadena resultante, verá que es 2, incluso si solo hay un "carácter". Entonces, desde una perspectiva de JavaScript, no estás reduciendo la longitud real de la cadena.
La otra cosa es que UTF-32 tiene de hecho 2 21 caracteres. Mira aquí: https://en.wikipedia.org/wiki/UTF-32
Es un protocolo para codificar puntos de código Unicode que usa exactamente 32 bits por punto de código Unicode (pero un número de bits iniciales debe ser cero ya que hay menos de 221 puntos de código Unicode)
Entonces realmente no tienes 4 bytes, de hecho ni siquiera tienes 3, lo cual sería necesario para codificar 3. Entonces UTF-32 no parece ser una forma de comprimir aún más. Y como javascript tiene cadenas nativas de 2 bytes, me parece que es la más eficiente, usando al menos ese enfoque.
para ver el código completo, consulte aquí: https://repl.it/NyMl/1
usando el Uint8Array puedes trabajar con los bytes.
let msg = "This is some message";
let data = []
for(let i = 0; i < msg.length; ++i){
data[i] = msg.charCodeAt(i);
}
let i8 = new Uint8Array(data);
let i16 = new Uint16Array(i8.buffer);
también podría pensar en una compresión como esta: http://pieroxy.net/blog/pages/lz-string/demo.html
si no desea utilizar una biblioteca de terceros, la compresión basada en lz debería ser bastante simple. ver aquí (wikipedia)
Utilizo la misma biblioteca mencionada anteriormente, lz-string https://github.com/pieroxy/lz-string , y crea tamaños de archivo que son más pequeños que la mayoría de los formatos binarios, como los Buffers de Protocolo.
Comprimo a través de Node.js de esta manera:
var compressedString = LZString.compressToUTF16(str);
Y descomprimo el lado del cliente de esta manera:
var decompressedString = LZString.decompressFromUTF16(str);