javascript - paginas - pasar parametros post por url
Cómo comprimir parámetros de URL (12)
Supongamos que tengo una aplicación de una sola página que utiliza una API de terceros para el contenido. La lógica de la aplicación solo está en el navegador y no hay un servidor en el que pueda escribir.
Para permitir el deep-linking en el estado de la aplicación, utilizo pushState para realizar un seguimiento de algunas variables que determinan el estado de la aplicación (tenga en cuenta que la versión pública de Ubersicht aún no lo hace). En este caso, repos , labels , milestones y username , show_open (bool) y with_comments (bool) y without_comments (bool). El formato de URL es ?label=label_1,label_2,label_3&repos=repo_1… Los valores son los sospechosos habituales, aproximadamente [a-zA-Z][a-zA-Z0-9_-] , o cualquier indicador booleano.
Hasta aquí todo bien. Ahora que la cadena de consulta puede ser un poco larga y difícil de manejar y me gustaría poder pasar URL como http://espy.github.io/ubersicht/?state=SOMOPAQUETOKENTHATLOSSLESSLYDECOMPRESSESINTOTHEORIGINALVALUES#hoodiehq , cuanto más corta, mejor.
Mi primer intento fue usar algún algoritmo zlib para esto ( https://github.com/imaya/zlib.js ) y @flipzagging apuntando a antirez / smaz (https // github.com / antirez / smaz) que suena más adecuado para cadenas cortas (versión de JavaScript en https://github.com/personalcomputer/smaz.js ).
Dado que = y & no se manejan específicamente en https://github.com/personalcomputer/smaz.js/blob/master/lib/smaz.js#L9 , es posible que podamos modificar un poco las cosas allí.
Además, hay una opción para codificar los valores en una tabla fija, por ejemplo, el orden de los argumentos está predefinido y todo lo que necesitamos hacer un seguimiento es el valor real. Por ejemplo, convertir a=hamster&b=cat en 7hamster3cat (length + chars) o hamster | cat (value + | ), potencialmente antes de la compresión smaz.
¿Hay algo más que debería estar buscando?
¡Tengo un plan astuto! (Y una bebida de gin tonic)
No parece importarle la longitud de la corriente de bits sino la longitud de los glifos resultantes, por ejemplo, la cadena que se muestra al usuario.
El navegador es bastante bueno para convertir un IRI al [URI] subyacente [2] mientras sigue mostrando el IRI en la barra de direcciones. Los IRI tienen un mayor repertorio de caracteres posibles, mientras que su conjunto de caracteres posibles es bastante limitado.
Eso significa que puedes codificar bigramas de tus caracteres (aa, ab, ac, ..., zz y caracteres especiales) en un carácter del espectro Unicode completo. Digamos que tienes 80 posibles caracteres ASCII: el número de combinaciones posibles de dos caracteres es 6400. Los cuales son fáciles de encontrar en los caracteres asignados Unicodes, por ejemplo, en el espectro unificado CJK:
aa → 一
ab → 丁
ac → 丂
ad → 七
…
Elegí CJK porque esto es solo (levemente) razonable si los caracteres de destino están asignados en Unicode y tienen glifos asignados en el navegador principal y en los sistemas operativos. Por esa razón, el área de uso privado está fuera y la versión más eficiente que usa trigramas (cuyas combinaciones posibles podrían usar todos los posibles puntos de código de Unicodes 1114112) están fuera.
Para recapitular: los bytes subyacentes aún están allí y, dada la codificación UTF-8, es posible incluso más, pero la cadena de caracteres que el usuario ve y copia es un 50% más corta.
Ok, Ok, razones, por qué esta solución es una locura:
Los IRI no son perfectos. Muchas herramientas menores que el navegador moderno tienen sus problemas.
El algoritmo obviamente necesita mucho más trabajo. Necesitarás una función que asigne los bigrams a los caracteres de destino y viceversa. Y debería ser preferible trabajar aritméticamente para evitar grandes tablas hash en la memoria.
Los caracteres de destino deben verificarse si están asignados y si son caracteres simples y no elementos de fantasía unicornios como combinar caracteres o cosas que se perdieron en algún lugar de la normalización de Unicode. También si el área objetivo es un tramo continuo de caracteres asignados con glifos.
El navegador a veces desconfía de los IRI. Por una buena razón, dados los ataques homógrafos de IDN. ¿Están bien con todos estos caracteres no ASCII en su barra de direcciones?
Y el más grande: la gente es notoriamente mala recordando personajes en guiones que no conocen. Son aún peores al tratar de (re) escribir estos caracteres. Y copy''n''paste puede salir mal en muchos clics diferentes. Hay una razón por la que los acortadores de URL usan Base64 e incluso alfabetos más pequeños.
... hablando de eso: esa sería mi solución. Descargando el trabajo de acortar enlaces al usuario o integrando goo.gl o bit.ly a través de sus API.
¿Por qué no usar protocol-buffers ?
Los búferes de protocolo son un mecanismo flexible, eficiente y automatizado para serializar datos estructurados, piense en XML, pero más pequeño, más rápido y más simple. Usted define cómo desea que sus datos se estructuren una vez, luego puede usar un código fuente especial generado para escribir y leer fácilmente sus datos estructurados desde y hacia una variedad de flujos de datos y usando una variedad de idiomas. Incluso puede actualizar su estructura de datos sin interrumpir los programas implementados que se compilan con el formato "antiguo".
ProtoBuf.js convierte objetos en mensajes de buffer de protocolo y vice vera.
El siguiente objeto se convierte en: CgFhCgFiCgFjEgFkEgFlEgFmGgFnGgFoGgFpIgNqZ2I=
{
repos : [''a'', ''b'', ''c''],
labels: [''d'', ''e'', ''f''],
milestones : [''g'', ''h'', ''i''],
username : ''jgb''
}
Ejemplo
El siguiente ejemplo está construido usando require.js . jsfiddle en este jsfiddle .
require.config({
paths : {
''Math/Long'' : ''//rawgithub.com/dcodeIO/Long.js/master/Long.min'',
''ByteBuffer'' : ''//rawgithub.com/dcodeIO/ByteBuffer.js/master/ByteBuffer.min'',
''ProtoBuf'' : ''//rawgithub.com/dcodeIO/ProtoBuf.js/master/ProtoBuf.min''
}
})
require([''message''], function(message) {
var data = {
repos : [''a'', ''b'', ''c''],
labels: [''d'', ''e'', ''f''],
milestones : [''g'', ''h'', ''i''],
username : ''jgb''
}
var request = new message.arguments(data);
// Convert request data to base64
var base64String = request.toBase64();
console.log(base64String);
// Convert base64 back
var decodedRequest = message.arguments.decode64(base64String);
console.log(decodedRequest);
});
// Protobuf message definition
// Message definition could also be stored in a .proto definition file
// See: https://github.com/dcodeIO/ProtoBuf.js/wiki
define(''message'', [''ProtoBuf''], function(ProtoBuf) {
var proto = {
package : ''message'',
messages : [
{
name : ''arguments'',
fields : [
{
rule : ''repeated'',
type : ''string'',
name : ''repos'',
id : 1
},
{
rule : ''repeated'',
type : ''string'',
name : ''labels'',
id : 2
},
{
rule : ''repeated'',
type : ''string'',
name : ''milestones'',
id : 3
},
{
rule : ''required'',
type : ''string'',
name : ''username'',
id : 4
},
{
rule : ''optional'',
type : ''bool'',
name : ''with_comments'',
id : 5
},
{
rule : ''optional'',
type : ''bool'',
name : ''without_comments'',
id : 6
}
],
}
]
};
return ProtoBuf.loadJson(proto).build(''message'')
});
Hay dos aspectos principales del problema: codificación y compresión.
La compresión de propósito general no parece funcionar bien en cadenas pequeñas. Como los navegadores no proporcionan api para comprimir cadenas, también debe cargar la fuente, que puede ser enorme.
Muchos de los caracteres se pueden guardar usando una codificación eficiente. He escrito una biblioteca llamada μ para manejar la parte de codificación y decodificación. La idea es especificar tanto como la información disponible sobre la estructura y el dominio de los parámetros de url como una especificación. Esta especificación se puede usar para controlar la codificación y la decodificación. For example, boolean can be encoded using just one bit, integer can be converted to different base(64) thereby reducing the number of characters required, object keys need not be encoded because it can be inferred from the specification, enums can be encoded using log 2 (numberOfAllowedValues) bits.
Tal como lo propones tú mismo, primero me deshace de todos los personajes que no llevan información, porque son parte del "formato".
Por ejemplo, gire "labels = open, ssl, cypher & repository = 275643 & username = ryanbrg & milestones = & with_comment = yes" a "open, ssl, cyper | 275643 | ryanbrg || yes".
A continuación, utilice una codificación de Huffmann con un vector de probabilidad fijo (lo que da como resultado una asignación fija de caracteres a cadenas de bits de longitud variable, con los caracteres más probables asignados a cadenas de bits más cortas y menos probables mapeados a cadenas de bits más largas).
Incluso podría usar diferentes vectores de probabilidad para los diferentes parámetros. Por ejemplo, en el parámetro "etiquetas" los caracteres alfabéticos tendrán una alta probabilidad, pero en el parámetro "repositorio" los caracteres numéricos tendrán la mayor probabilidad. Si haces esto, debes considerar el separador "|" una parte del parámetro precedente.
Y, finalmente, convierta la cadena de bits larga (que es la concatenación de todas las cadenas de bits con la que se mapearon los caracteres) en algo que puede poner en una URL mediante la codificación de base64url.
Si pudiera enviarme un conjunto de listas de parámetros representativos, podría ejecutarlos a través de un codificador Huffmann para ver qué tan bien se comprimen.
El vector de probabilidad (o, de forma equivalente, el mapeo de caracteres a cadenas de bits) debe codificarse como arrays constantes en la función Javascript que se envía al navegador.
Por supuesto, podría ir más allá y, por ejemplo, tratar de obtener una lista de las posibles etiquetas con sus probabilidades. Luego, podría asignar lables completos a cadenas de bits con una codificación de Huffmann. Esto le dará una mejor compresión, pero tendrá trabajo adicional para esas etiquetas que son nuevas (por ejemplo, volver a la codificación de un solo carácter) y, por supuesto, la asignación (que, como se mencionó anteriormente, es una matriz constante en la función Javascript ) será mucho más grande.
Una solución de trabajo que junta varios fragmentos de ideas buenas (o eso creo) juntas
Hice esto por diversión, principalmente porque me dio la oportunidad de implementar un codificador Huffman en PHP y no pude encontrar una implementación satisfactoria.
Sin embargo, esto podría ahorrarle algo de tiempo si planea explorar un camino similar.
Burrows-Wheeler + movimiento hacia adelante + transformación de Huffman
No estoy del todo seguro de que BWT sea el más adecuado para su tipo de entrada.
Este no es un texto regular, por lo que los patrones recurrentes probablemente no ocurran tan a menudo como en el código fuente o en inglés simple.
Además, un código Huffman dinámico tendría que pasar junto con los datos codificados que, para cadenas de entrada muy cortas, perjudicarían gravemente la ganancia de compresión.
Bien podría estar equivocado, en cuyo caso me alegraría ver a alguien demostrar que soy.
De todos modos, decidí probar otro enfoque.
Principio general
1) defina una estructura para sus parámetros de URL y elimine la parte constante
por ejemplo, a partir de:
repos=aaa,bbb,ccc&
labels=ddd,eee,fff&
milestones=ggg,hhh,iii&
username=kkk&
show_open=0&
show_closed=1&
show_commented=1&
show_uncommented=0
extraer:
aaa,bbb,ccc|ddd,eee,fff|ggg,hhh,iii|kkk|0110
donde , y | actúan como terminadores de cadenas y / o campos, mientras que los valores booleanos no necesitan ninguno.
2) definir una repartición estática de símbolos basada en la entrada promedio esperada y derivar un código Huffman estático
Dado que la transmisión de una tabla dinámica tomaría más espacio que la cadena inicial, creo que la única manera de lograr cualquier compresión es tener una tabla huffman estática.
Sin embargo, puede usar la estructura de sus datos a su favor para calcular probabilidades razonables.
Puede comenzar con el reparto de letras en inglés u otros idiomas y agregar un cierto porcentaje de números y otros signos de puntuación.
Probando con una codificación Huffman dinámica, vi tasas de compresión de 30 a 50%.
Esto significa que con una tabla estática puede esperar un factor de compresión de .6 (reduciendo la longitud de sus datos en 1/3), no mucho más.
3) convertir este código binario Huffmann en algo que un URI puede manejar
Los 70 caracteres regulares ASCII de 7 bits en esa lista
!''()*-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz
le daría un factor de expansión de aproximadamente 30%, prácticamente no mejor que una codificación de base64.
Una expansión del 30% arruinaría la ganancia de una compresión estática de Huffman, ¡así que esta no es una opción!
Sin embargo, como controlas el lado del cliente y del servidor de codificación, puedes utilizar cualquier elemento que no sea un carácter reservado de URI.
Una posibilidad interesante sería completar la configuración anterior hasta 256 con cualquier glifo Unicode, lo que permitiría codificar sus datos binarios con el mismo número de caracteres compatibles con URI, reemplazando así un grupo de divisiones enteras largas dolorosas y lentas con un rayo búsqueda rápida de la tabla.
Descripción de la estructura
El códec está destinado a utilizarse tanto en el lado del cliente como del servidor, por lo que es esencial que el servidor y los clientes compartan una definición de estructura de datos común.
Dado que es probable que la interfaz evolucione, parece aconsejable almacenar un número de versión para compatibilidad ascendente.
La definición de la interfaz usará un lenguaje de descripción muy minimalista, así:
v 1 // version number (between 0 and 63)
a en // alphabet used (English)
o 10 // 10% of digits and other punctuation characters
f 1 // 1% of uncompressed "foreign" characters
s 15:3 repos // list of expeced 3 strings of average length 15
s 10:3 labels
s 8:3 milestones
s 10 username // single string of average length 10
b show_open // boolean value
b show_closed
b show_commented
b show_uncommented
Cada idioma admitido tendrá una tabla de frecuencia para todas sus letras usadas
dígitos y otros símbolos de computadora como - . o _ tendrá una frecuencia global, independientemente de los idiomas
las frecuencias de los separadores (y | ) se calcularán de acuerdo con la cantidad de listas y campos presentes en la estructura.
Todos los demás caracteres "foráneos" se escaparán con un código específico y se codificarán como UTF-8 sin formato.
Implementación
La ruta de conversión bidireccional es la siguiente:
lista de campos <-> secuencia de datos UTF-8 <-> códigos huffman <-> URI
Aquí está el códec principal
include (''class.huffman.codec.php'');
class IRI_prm_codec
{
// available characters for IRI translation
static private $translator = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõöùúûüýþÿĀāĂ㥹ĆćĈĉĊċČčĎďĐđĒēĔĕĖėĘęĚěĜĝĞğĠġĢģĤĥĦħĨĩĪīĬĭĮįİıIJijĴĵĶķĸĹĺĻļĽľĿŀŁłŃńŅņŇňʼnŊŋŌōŎŏŐőŒœŔŕŖŗŘřŚśŜŝŞşŠšŢţŤťŦŧŨũŪūŬŭŮůŰűŲųŴŵŶŷŸŹźŻżŽžſƀƁƂƃƄƅ";
const VERSION_LEN = 6; // version number between 0 and 63
// ========================================================================
// constructs an encoder
// ========================================================================
public function __construct ($config)
{
$num_record_terminators = 0;
$num_record_separators = 0;
$num_text_sym = 0;
// parse config file
$lines = file($config, FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
foreach ($lines as $line)
{
list ($code, $val) = preg_split(''//s+/'', $line, 2);
switch ($code)
{
case ''v'': $this->version = intval($val); break;
case ''a'': $alphabet = $val; break;
case ''o'': $percent_others = $val; break;
case ''f'': $percent_foreign = $val; break;
case ''b'':
$this->type[$val] = ''b'';
break;
case ''s'':
list ($val, $field) = preg_split(''//s+/u'', $val, 2);
@list ($len,$num) = explode ('':'', $val);
if (!$num) $num=1;
$this->type[$field] = ''s'';
$num_record_terminators++;
$num_record_separators+=$num-1;
$num_text_sym += $num*$len;
break;
default: throw new Exception ("Invalid config parameter $code");
}
}
// compute symbol frequencies
$total = $num_record_terminators + $num_record_separators + $num_text_sym + 1;
$num_chars = $num_text_sym * (100-($percent_others+$percent_foreign))/100;
$num_sym = $num_text_sym * $percent_others/100;
$num_foreign = $num_text_sym * $percent_foreign/100;
$this->get_frequencies ($alphabet, $num_chars/$total);
$this->set_frequencies (" .-_0123456789", $num_sym/$total);
$this->set_frequencies ("|", $num_record_terminators/$total);
$this->set_frequencies (",", $num_record_separators/$total);
$this->set_frequencies ("/1", $num_foreign/$total);
$this->set_frequencies ("/0", 1/$total);
// create Huffman codec
$this->huffman = new Huffman_codec();
$this->huffman->make_code ($this->frequency);
}
// ------------------------------------------------------------------------
// grab letter frequencies for a given language
// ------------------------------------------------------------------------
private function get_frequencies ($lang, $coef)
{
$coef /= 100;
$frequs = file("$lang.dat", FILE_IGNORE_NEW_LINES|FILE_SKIP_EMPTY_LINES);
foreach ($frequs as $line)
{
$vals = explode (" ", $line);
$this->frequency[$vals[0]] = floatval ($vals[1]) * $coef;
}
}
// ------------------------------------------------------------------------
// set a given frequency for a group of symbols
// ------------------------------------------------------------------------
private function set_frequencies ($symbols, $coef)
{
$coef /= strlen ($symbols);
for ($i = 0 ; $i != strlen($symbols) ; $i++) $this->frequency[$symbols[$i]] = $coef;
}
// ========================================================================
// encodes a parameter block
// ========================================================================
public function encode($input)
{
// get back input values
$bools = '''';
foreach (get_object_vars($input) as $prop => $val)
{
if (!isset ($this->type[$prop])) throw new Exception ("unknown property $prop");
switch ($this->type[$prop])
{
case ''b'': $bools .= $val ? ''1'' : ''0''; break;
case ''s'': $strings[] = $val; break;
default: throw new Exception ("Uh oh... type ".$this->type[$prop]." not handled ?!?");
}
}
// set version number and boolean values in front
$prefix = sprintf ("%0".self::VERSION_LEN."b$bools", $this->version);
// pass strings to our Huffman encoder
$strings = implode ("|", $strings);
$huff = $this->huffman->encode ($strings, $prefix, "UTF-8");
// translate into IRI characters
mb_internal_encoding("UTF-8");
$res = '''';
for ($i = 0 ; $i != strlen($huff) ; $i++) $res .= mb_substr (self::$translator, ord($huff[$i]), 1);
// done
return $res;
}
// ========================================================================
// decodes an IRI string into a lambda object
// ========================================================================
public function decode($input)
{
// convert IRI characters to binary
mb_internal_encoding("UTF-8");
$raw = '''';
$len = mb_strlen ($input);
for ($i = 0 ; $i != $len ; $i++)
{
$c = mb_substr ($input, 0, 1);
$input = mb_substr ($input, 1);
$raw .= chr(mb_strpos (self::$translator, $c));
}
$this->bin = '''';
// check version
$version = $this->read_bits ($raw, self::VERSION_LEN);
if ($version != $this->version) throw new Exception ("Version mismatch: expected {$this->version}, found $version");
// read booleans
foreach ($this->type as $field => $type)
if ($type == ''b'')
$res->$field = $this->read_bits ($raw, 1) != 0;
// decode strings
$strings = explode (''|'', $this->huffman->decode ($raw, $this->bin));
$i = 0;
foreach ($this->type as $field => $type)
if ($type == ''s'')
$res->$field = $strings[$i++];
// done
return $res;
}
// ------------------------------------------------------------------------
// reads raw bit blocks from a binary string
// ------------------------------------------------------------------------
private function read_bits (&$raw, $len)
{
while (strlen($this->bin) < $len)
{
if ($raw == '''') throw new Exception ("premature end of input");
$this->bin .= sprintf ("%08b", ord($raw[0]));
$raw = substr($raw, 1);
}
$res = bindec (substr($this->bin, 0, $len));
$this->bin = substr ($this->bin, $len);
return $res;
}
}
El códec Huffman subyacente
include (''class.huffman.dict.php'');
class Huffman_codec
{
public $dict = null;
// ========================================================================
// encodes a string in a given string encoding (default: UTF-8)
// ========================================================================
public function encode($input, $prefix='''', $encoding="UTF-8")
{
mb_internal_encoding($encoding);
$bin = $prefix;
$res = '''';
$input .= "/0";
$len = mb_strlen ($input);
while ($len--)
{
// get next input character
$c = mb_substr ($input, 0, 1);
$input = substr($input, strlen($c)); // avoid playing Schlemiel the painter
// check for foreign characters
if (isset($this->dict->code[$c]))
{
// output huffman code
$bin .= $this->dict->code[$c];
}
else // foreign character
{
// escape sequence
$lc = strlen($c);
$bin .= $this->dict->code["/1"]
. sprintf("%02b", $lc-1); // character length (1 to 4)
// output plain character
for ($i=0 ; $i != $lc ; $i++) $bin .= sprintf("%08b", ord($c[$i]));
}
// convert code to binary
while (strlen($bin) >= 8)
{
$res .= chr(bindec(substr ($bin, 0, 8)));
$bin = substr($bin, 8);
}
}
// output last byte if needed
if (strlen($bin) > 0)
{
$bin .= str_repeat (''0'', 8-strlen($bin));
$res .= chr(bindec($bin));
}
// done
return $res;
}
// ========================================================================
// decodes a string (will be in the string encoding used during encoding)
// ========================================================================
public function decode($input, $prefix='''')
{
$bin = $prefix;
$res = '''';
$len = strlen($input);
for ($i=0 ;;)
{
$c = $this->dict->symbol($bin);
switch ((string)$c)
{
case "/0": // end of input
break 2;
case "/1": // plain character
// get char byte size
if (strlen($bin) < 2)
{
if ($i == $len) throw new Exception ("incomplete escape sequence");
$bin .= sprintf ("%08b", ord($input[$i++]));
}
$lc = 1 + bindec(substr($bin,0,2));
$bin = substr($bin,2);
// get char bytes
while ($lc--)
{
if ($i == $len) throw new Exception ("incomplete escape sequence");
$bin .= sprintf ("%08b", ord($input[$i++]));
$res .= chr(bindec(substr($bin, 0, 8)));
$bin = substr ($bin, 8);
}
break;
case null: // not enough bits do decode further
// get more input
if ($i == $len) throw new Exception ("no end of input mark found");
$bin .= sprintf ("%08b", ord($input[$i++]));
break;
default: // huffman encoded
$res .= $c;
break;
}
}
if (bindec ($bin) != 0) throw new Exception ("trailing bits in input");
return $res;
}
// ========================================================================
// builds a huffman code from an input string or frequency table
// ========================================================================
public function make_code ($input, $encoding="UTF-8")
{
if (is_string ($input))
{
// make dynamic table from the input message
mb_internal_encoding($encoding);
$frequency = array();
while ($input != '''')
{
$c = mb_substr ($input, 0, 1);
$input = mb_substr ($input, 1);
if (isset ($frequency[$c])) $frequency[$c]++; else $frequency[$c]=1;
}
$this->dict = new Huffman_dict ($frequency);
}
else // assume $input is an array of symbol-indexed frequencies
{
$this->dict = new Huffman_dict ($input);
}
}
}
Y el diccionario Huffman
class Huffman_dict
{
public $code = array();
// ========================================================================
// constructs a dictionnary from an array of frequencies indexed by symbols
// ========================================================================
public function __construct ($frequency = array())
{
// add terminator and escape symbols
if (!isset ($frequency["/0"])) $frequency["/0"] = 1e-100;
if (!isset ($frequency["/1"])) $frequency["/1"] = 1e-100;
// sort symbols by increasing frequencies
asort ($frequency);
// create an initial array of (frequency, symbol) pairs
foreach ($frequency as $symbol => $frequence) $occurences[] = array ($frequence, $symbol);
while (count($occurences) > 1)
{
$leaf1 = array_shift($occurences);
$leaf2 = array_shift($occurences);
$occurences[] = array($leaf1[0] + $leaf2[0], array($leaf1, $leaf2));
sort($occurences);
}
$this->tree = $this->build($occurences[0], '''');
}
// -----------------------------------------------------------
// recursive build of lookup tree and symbol[code] table
// -----------------------------------------------------------
private function build ($node, $prefix)
{
if (is_array($node[1]))
{
return array (
''0'' => $this->build ($node[1][0], $prefix.''0''),
''1'' => $this->build ($node[1][1], $prefix.''1''));
}
else
{
$this->code[$node[1]] = $prefix;
return $node[1];
}
}
// ===========================================================
// extracts a symbol from a code stream
// if found : updates code stream and returns symbol
// if not found : returns null and leave stream intact
// ===========================================================
public function symbol(&$code_stream)
{
list ($symbol, $code) = $this->get_symbol ($this->tree, $code_stream);
if ($symbol !== null) $code_stream = $code;
return $symbol;
}
// -----------------------------------------------------------
// recursive search for a symbol from an huffman code
// -----------------------------------------------------------
private function get_symbol ($node, $code)
{
if (is_array($node))
{
if ($code == '''') return null;
return $this->get_symbol ($node[$code[0]], substr($code, 1));
}
return array ($node, $code);
}
}
Ejemplo
include (''class.iriprm.codec.php'');
$iri = new IRI_prm_codec ("config.txt");
foreach (array (
''repos'' => "discussion,documentation,hoodie-cli",
''labels'' => "enhancement,release-0.3.0,starter",
''milestones'' => "1.0.0,1.1.0,v0.7",
''username'' => "mklappstuhl",
''show_open'' => false,
''show_closed'' => true,
''show_commented'' => true,
''show_uncommented'' => false
) as $prop => $val) $iri_prm->$prop = $val;
$encoded = $iri->encode ($iri_prm);
echo "encoded as $encoded/n";
$decoded = $iri->decode ($encoded);
var_dump($decoded);
salida:
encoded as 5ĶůťÊĕCOĔƀŪļŤłmĄZEÇŽÉįóšüÿjħũÅìÇēOĪäŖÏŅíŻÉĒQmìFOyäŖĞqæŠŹōÍĘÆŤŅËĦ
object(stdClass)#7 (8) {
["show_open"]=>
bool(false)
["show_closed"]=>
bool(true)
["show_commented"]=>
bool(true)
["show_uncommented"]=>
bool(false)
["repos"]=>
string(35) "discussion,documentation,hoodie-cli"
["labels"]=>
string(33) "enhancement,release-0.3.0,starter"
["milestones"]=>
string(16) "1.0.0,1.1.0,v0.7"
["username"]=>
string(11) "mklappstuhl"
}
En ese ejemplo, la entrada se empaquetó en 64 caracteres Unicode, para una longitud de entrada de aproximadamente 100, produciendo una reducción de 1/3.
Una cadena equivalente:
discussion,documentation,hoodie-cli|enhancement,release-0.3.0,starter|
1.0.0,1.1.0,v0.7|mklappstuhl|0110
Sería comprimido por una tabla dinámica de Huffman a 59 caracteres. No es una gran diferencia.
Sin duda, el reordenamiento inteligente de datos reduciría eso, pero luego tendría que pasar la tabla dinámica a lo largo de ...
Chino al rescate?
Basándose en la idea de ttepasse , uno podría aprovechar la gran cantidad de caracteres asiáticos para encontrar un rango de valores contiguos de 0x4000 (12 bits), para codificar 3 bytes en 2 caracteres CJK, de esta manera:
// translate into IRI characters
$res = '''';
$len = strlen ($huff);
for ($i = 0 ; $i != $len ; $i++)
{
$byte = ord($huff[$i]);
$quartet[2*$i ] = $byte >> 4;
$quartet[2*$i+1] = $byte &0xF;
}
$len *= 2;
while ($len%3 != 0) $quartet[$len++] = 0;
$len /= 3;
for ($i = 0 ; $i != $len ; $i++)
{
$utf16 = 0x4E00 // CJK page base, enough range for 2**12 (0x4000) values
+ ($quartet[3*$i+0] << 8)
+ ($quartet[3*$i+1] << 4)
+ ($quartet[3*$i+2] << 0);
$c = chr ($utf16 >> 8) . chr ($utf16 & 0xFF);
$res .= $c;
}
$res = mb_convert_encoding ($res, "UTF-8", "UTF-16");
y de vuelta:
// convert IRI characters to binary
$input = mb_convert_encoding ($input, "UTF-16", "UTF-8");
$len = strlen ($input)/2;
for ($i = 0 ; $i != $len ; $i++)
{
$val = (ord($input[2*$i ]) << 8) + ord ($input[2*$i+1]) - 0x4E00;
$quartet[3*$i+0] = ($val >> 8) &0xF;
$quartet[3*$i+1] = ($val >> 4) &0xF;
$quartet[3*$i+2] = ($val >> 0) &0xF;
}
$len *= 3;
while ($len %2) $quartet[$len++] = 0;
$len /= 2;
$raw = '''';
for ($i = 0 ; $i != $len ; $i++)
{
$raw .= chr (($quartet[2*$i+0] << 4) + $quartet[2*$i+1]);
}
La producción anterior de 64 caracteres latinos
5ĶůťÊĕCOĔƀŪļŤłmĄZEÇŽÉįóšüÿjħũÅìÇēOĪäŖÏŅíŻÉĒQmìFOyäŖĞqæŠŹōÍĘÆŤŅËĦ
se "reduciría" a 42 caracteres asiáticos:
乙堽孴峴勀垧壩坸冫嚘佰嫚凲咩俇噱刵巋娜奾埵峼圔奌夑啝啯嶼勲婒婅凋凋伓傊厷侖咥匄冯塱僌
Sin embargo, como puede ver, la mayor parte de su ideograma promedio hace que la cadena sea más larga (en píxeles), por lo que incluso si la idea era prometedora, el resultado es bastante decepcionante.
Escoger glifos más delgados
Por otro lado, puedes intentar elegir caracteres "delgados" como base para la codificación URI. Por ejemplo:
█ᑊᵄ′ӏᶟⱦᵋᵎiïᵃᶾ᛬ţᶫꞌᶩ᠇܂اlᶨᶾᛁ⁚ᵉʇȋʇίן᠙ۃῗᥣᵋĭꞌ៲ᛧ༚ƫܙ۔ˀȷˁʇʹĭ∕ٱ;łᶥյ;ᴶ⁚ĩi⁄ʈ█
en lugar de
█5ĶůťÊĕCOĔƀŪļŤłmĄZEÇŽÉįóšüÿjħũÅìÇēOĪäŖÏŅíŻÉĒQmìFOyäŖĞqæŠŹōÍĘÆŤŅËĦ█
Eso reducirá la longitud a la mitad con fuentes proporcionales, incluso en una barra de direcciones del navegador.
Mi mejor conjunto de candidatos de 256 glifos "delgados" hasta el momento:
᠊།ᑊʲ་༌ᵎᵢᶤᶩᶪᶦᶧˡ ⁄∕เ''Ꞌꞌ꡶ᶥᵗᶵᶨ|¦ǀᴵ ᐧᶠᶡ༴ˢᶳ⁏ᶴʳʴʵ։᛬⍮ʹ′ ⁚⁝ᵣ⍘༔⍿ᠵᥣᵋᵌᶟᴶǂˀˁˤ༑,. ∙Ɩ៲᠙ᵉᵊᵓᶜᶝₑₔյⵏⵑ༝༎՛ᵞᵧᚽᛁᛂᛌᛍᛙᛧᶢᶾ৷⍳ɩΐίιϊᵼἰἱἲἳἴἵἶἷὶίῐῑῒΐῖῗ⎰⎱᠆ᶿ՝ᵟᶫᵃᵄᶻᶼₐ∫ª౹᠔/:;/ijltìíîïĩīĭįıĵĺļłţŧſƚƫƭǐǰȉȋțȴȷɉɨɪɫɬɭʇʈʝːˑ˸;·ϳіїјӏ᠇ᴉᵵᵻᶅᶖḭḯḷḹḻḽṫṭṯṱẗẛỉị⁞⎺⎻⎼⎽ⱡⱦ꞉༈ǁ‖༅༚ᵑᵝᵡᵦᵪา᠑⫶ᶞᚁᚆᚋᚐᚕᵒᵔᵕᶱₒⵗˣₓᶹๅʶˠ᛫ᵛᵥᶺᴊ
Conclusión
Esta implementación debe ser portada a JavaScript para permitir el intercambio cliente-servidor.
También debe proporcionar una forma de compartir la estructura y los códigos Huffman con los clientes.
No es difícil y divertido de hacer, pero eso significa aún más trabajo :).
La ganancia de Huffman en términos de personajes es de alrededor del 30%.
Por supuesto, estos personajes son multibyte en su mayor parte, pero si buscas el URI más corto, no importa.
Excepto por los booleanos que se pueden empaquetar fácilmente a 1 bit, esas molestas cadenas parecen bastante reacias a ser comprimidas.
Podría ser posible ajustar mejor las frecuencias, pero dudo que obtengas una tasa de compresión superior al 50%.
Por otro lado, elegir glifos delgados hace más para reducir el hilo.
Entonces, en definitiva, la combinación de ambos podría lograr algo, aunque es mucho trabajo para un resultado modesto.
parseInt pequeño: parseInt y Number#toString admiten argumentos de raíz. Intente usar una raíz de 36 para codificar números (o índices en listas) en las URL.
Corto
Use a URL packing scheme such as my own, starting only from the params section of your URL.
Longer
As other''s here have pointed out, typical compression systems don''t work for short strings. But, it''s important to recognise that URLs and Params are a serialization format of a data model: a text human-readable format with specific sections - we know the the scheme is first, the host is found directly after, the port is implied but can be overridden, etc...
With the original data model, one can serialize with a more bit-efficient serialization scheme. In fact, I have created such a serialization myself which archives around 50% compression: see http://blog.alivate.com.au/packed-url/
It looks like the Github APIs have numeric IDs for many things (looks like repos and users have them, but labels don''t) under the covers. It might be possible to use those numbers instead of names wherever advantageous. You then have to figure out how to best encode those in something that''ll survive in a query string, eg something like base64(url).
For example, your hoodie.js repository has ID 4780572 .
Packing that into a big-endian unsigned int (as many bytes as we need) gets us /x00H/xf2/x1c .
We''ll just toss the leading zero, we can always restore that later, now we have H/xf2/x1c .
Encode as URL-safe base64, and you have SPIc (toss any padding you might get).
Going from hoodiehq/hoodie.js to SPIc seems like a good-sized win!
More generally, if you''re willing to invest the time, you can try to exploit a bunch of redudancies in your query strings. Other ideas are along the lines of packing the two boolean params into a single character, possibly along with other state (like what fields are included). If you use base64-encoding (which seems the best option here due to the URL-safe version -- I looked at base85, but it has a bunch of characters that won''t survive in a URL), that gets you 6 bits of entropy per character... there''s a lot you can do with that.
To add to Thomas Fuchs'' note, yes, if there''s some kind of inherent, immutable ordering in some of things you''re encoding, than that would obviously also help. However, that seems hard for both the labels and the milestones.
Maybe any simple JS minifier will help you. You''ll need only to integrate it on serialization and deserialization points only. I think it''d be the easiest solution.
Perhaps you can find a url shortener with a jsonp API, that way you could make all the URLs really short automatically.
http://yourls.org/ even has jsonp support.
Some more tips:
- Base64 encodes with
a..zA..Z0..9+/=, and un-encoded URI characters area..zA..Z0..9-_.~. So Base64 results only need to swap+/=for-_.and it won''t expand URIs. - You could keep an array of key names, so that objects could be represented with the first character being the offset in the array, eg
{foo:3,bar:{g:''hi''}}becomesa3,b{c''hi''}given key array[''foo'',''bar'',''g'']
Interesting libraries:
- JSUrl specifically encodes JSON so it can be put in a URL without changes, even though it uses more characters than specified in the RFC.
{"name":"John Doe","age":42,"children":["Mary","Bill"]}becomes~(name~''John*20Doe~age~42~children~(~''Mary~''Bill))and with a key dictionary[''name'',''age'',''children'']that could be~(0~''John*20Doe~1~42~2~(~''Mary~''Bill)), thus going from 101 bytes URI encoded to 38.- Small footprint, fast, reasonable compression.
- lz-string uses an LZW-based algorithm to compress strings to UTF16 for storing in localStorage. It also has a
compressToEncodedURIComponent()function to produce URI-safe output.- Still only a few KB of code, pretty fast, good/great compression.
So basically I''d recommend picking one of these two libraries and consider the problem solved.
Why not use a third party link shortener?
(I am assuming you don''t have a problem with URI length limits since you mentioned this is an existing application.)
It looks like you''re writing a Greasemonkey script or thereabouts, so perhaps you have access to GM_xmlhttpRequest() , which would allow use of a third party link shortener.
Otherwise, you''d need to use XMLHttpRequest() and host your own link shortening service on the same server to avoid crossing the same-origin policy boundary. A quick online search for hosting your own shorteners supplied me with a list of 7 free/open source PHP link shortener scripts and one more on GitHub, though the question likely excludes this kind of approach since "The app''s logic is in-browser only, and there is no backend I can write to."
You can see example code implementing this kind of thing in the URL Shortener UserScript (for Greasemonkey), which pops up a shortened version of the current page''s URL when you press SHIFT+T.
Of course, shorteners will redirect users to the long form URL, but this would be a problem in any non-server-side solution. At least a shortener can theoretically proxy (like Apache''s RewriteRule with [P]) or use a <frame> tag.