Une solution de travail mettre des divers éléments d'un bon (ou du moins je le pense) idées

j'ai fait cela pour le plaisir, principalement parce que cela m'a donné l'occasion d'implémenter un encodeur Huffman en PHP et je n'ai pas pu trouver une implémentation existante satisfaisante.

cependant, cela pourrait vous faire gagner du temps si vous envisagez d'explorer un chemin similaire.

Burrows-Wheeler+move-to-front+Huffman transform

Je ne suis pas sûr que BWT soit le mieux adapté à vos commentaires.

Il ne s'agit pas d'un texte régulier, de sorte que les modèles récurrents ne se produiraient probablement pas aussi souvent qu'en code source ou en anglais simple.

de plus, un code Huffman dynamique devrait être transmis avec les données encodées qui, pour des chaînes d'entrée très courtes, nuiraient gravement au gain de compression.

je pourrais bien me tromper, auquel cas je verrais volontiers quelqu'un me prouver à être.

de toute façon, j'ai décidé d'essayer une autre approche.

principe général

1) définissez une structure pour vos paramètres D'URL et supprimez la partie constante

par exemple, à 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

extrait:

aaa,bbb,ccc|ddd,eee,fff|ggg,hhh,iii|kkk|0110

où , et | agissent comme des terminateurs de chaîne et/ou de champ, tandis que les valeurs booléennes n'en a pas besoin.

2) Définir une répartition statique des symboles basée sur l'entrée moyenne attendue et dériver un code Huffman statique

comme la transmission d'une table dynamique prendrait plus d'espace que votre chaîne initiale, je pense que la seule façon d'obtenir une compression est d'avoir une table de huffman statique.

Cependant, vous pouvez utiliser la structure de vos données à votre avantage pour calculer des probabilités raisonnables.

vous pouvez commencer par la répartition des lettres en anglais ou dans d'autres langues et Ajouter un certain pourcentage de chiffres et d'autres signes de ponctuation.

test avec un codage Huffman dynamique, j'ai vu des taux de compression de 30 à 50%.

cela signifie Avec une table statique que vous pouvez attendre peut-être un .6 facteur de compression (réduisant la longueur de vos données de 1/3), pas beaucoup plus.

3) convertir ce code Huffmann binaire dans quelque chose QU'un URI peut gérer

les 70 caractères ordinaires ASCII 7 bits de cette liste

!'()*-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz

vous donnerait un facteur d'expansion d'environ 30%, pratiquement pas mieux qu'un encodage base64.

une extension de 30% ruinerait le gain d'une compression statique de Huffman, donc ce n'est pas vraiment une option!

cependant, puisque vous contrôlez le côté encodage client et serveur, vous pouvez utilisez à propos de tout ce qui n'est pas un caractère URI réservé.

une possibilité intéressante serait de compléter la configuration ci-dessus jusqu'à 256 avec n'importe quelle glyphes unicode, ce qui permettrait de coder vos données binaires avec le même nombre de caractères URI-conforme, remplaçant ainsi un douloureux et lent tas de divisions entières longues avec un éclair rapide Recherche table.

Description de la Structure

Le codec est destiné à être utilisé du côté client et du côté serveur, il est donc essentiel que le serveur et les clients partagent une définition commune de la structure des données.

puisque l'interface est susceptible d'évoluer, il semble sage de stocker un numéro de version pour une compatibilité ascendante.

la définition de l'interface utilisera un langage de description très minimaliste, comme ceci:

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

chaque langue supportée aura une table de fréquence pour toutes ses lettres utilisées

chiffres et autres symboles informatiques comme - , . ou _ auront une fréquence globale, indépendamment des langues

Les fréquences des séparateurs

( , et | ) seront calculées en fonction du nombre de listes et de champs présents dans la structure.

tous les autres caractères" étrangers " seront échappés avec un code spécifique et encodés comme simple UTF-8.

Mise en œuvre

le chemin de conversion bidirectionnel est le suivant:

liste des champs < - > flux de données UTF-8 < - > Codes huffman < - > URI

voici le codec 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 ("", $num_foreign/$total);
        $this->set_frequencies (""151940920"", 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;
    }
}

Le sous-jacent Huffman codec

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 .= ""151950920"";
        $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[""] 
                     . 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 ""151950920"": // end of input
                break 2;

            case "": // 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);
        }
    }
}

Et le huffman dictionnaire

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[""151960920""])) $frequency[""151960920""] = 1e-100;
        if (!isset ($frequency[""])) $frequency[""] = 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);
    }
}

exemple

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);

sortie:

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"
}

dans cet exemple, l'entrée a été emballée en 64 caractères unicode, pour une longueur d'entrée d'environ 100, donnant une réduction de 1/3.

une chaîne équivalente:

discussion,documentation,hoodie-cli|enhancement,release-0.3.0,starter|
1.0.0,1.1.0,v0.7|mklappstuhl|0110

serait compressé par une table Huffman dynamique à 59 caractères. Pas beaucoup de différence.

sans doute smart data reordering would reduce that, Mais alors vous auriez besoin de passer la table dynamique le long...

Chinois à la rescousse?

dessin sur ttepasse l 'idée, on pourrait profiter du grand nombre de caractères asiatiques pour trouver une gamme de 0x4000 (12 bits) valeurs contiguës, de code 3 octets en 2 caractères CJK, comme ainsi:

    // 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");

et retour:

    // 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 production précédente de 64 caractères latins

5ĶůťÊĕCOĔƀŪļŤłmĄZEÇŽÉįóšüÿjħũÅìÇēOĪäŖÏŅíŻÉĒQmìFOyäŖĞqæŠŹōÍĘÆŤŅËĦ

serait "rétrécir" à 42 Caractères asiatiques:

乙堽孴峴勀垧壩坸冫嚘佰嫚凲咩俇噱刵巋娜奾埵峼圔奌夑啝啯嶼勲婒婅凋凋伓傊厷侖咥匄冯塱僌

cependant, comme vous pouvez le voir, le gros de votre idéogramme moyen rend la chaîne en fait plus long (pixel-sage), donc même si l'idée était prometteuse, le résultat est plutôt décevant.

sélection des plus minces glyphes

d'un autre côté, vous pouvez essayer de choisir des caractères" fins " comme base pour l'encodage D'URI. Par exemple:

█ᑊᵄ′ӏᶟⱦᵋᵎiïᵃᶾ᛬ţᶫꞌᶩ᠇܂اlᶨᶾᛁ⁚ᵉʇȋʇίן᠙ۃῗᥣᵋĭꞌ៲ᛧ༚ƫܙ۔ˀȷˁʇʹĭ∕ٱ;łᶥյ;ᴶ⁚ĩi⁄ʈ█

au lieu de

█5ĶůťÊĕCOĔƀŪļŤłmĄZEÇŽÉįóšüÿjħũÅìÇēOĪäŖÏŅíŻÉĒQmìFOyäŖĞqæŠŹōÍĘÆŤŅËĦ█

qui réduira la longueur de moitié avec des polices proportionnelles, y compris dans une barre d'adresse de navigateur.

Mon meilleur candidat 256 "mince" glyphes:

᠊།ᑊʲ་༌ᵎᵢᶤᶩᶪᶦᶧˡ ⁄∕เ'Ꞌꞌ꡶ᶥᵗᶵᶨ|¦ǀᴵ  ᐧᶠᶡ༴ˢᶳ⁏ᶴʳʴʵ։᛬⍮ʹ′ ⁚⁝ᵣ⍘༔⍿ᠵᥣᵋᵌᶟᴶǂˀˁˤ༑,.   ∙Ɩ៲᠙ᵉᵊᵓᶜᶝₑₔյⵏⵑ༝༎՛ᵞᵧᚽᛁᛂᛌᛍᛙᛧᶢᶾ৷⍳ɩΐίιϊᵼἰἱἲἳἴἵἶἷὶίῐῑῒΐῖῗ⎰⎱᠆ᶿ՝ᵟᶫᵃᵄᶻᶼₐ∫ª౹᠔/:;\ijltìíîïĩīĭįıĵĺļłţŧſƚƫƭǐǰȉȋțȴȷɉɨɪɫɬɭʇʈʝːˑ˸;·ϳіїјӏ᠇ᴉᵵᵻᶅᶖḭḯḷḹḻḽṫṭṯṱẗẛỉị⁞⎺⎻⎼⎽ⱡⱦ꞉༈ǁ‖༅༚ᵑᵝᵡᵦᵪา᠑⫶ᶞᚁᚆᚋᚐᚕᵒᵔᵕᶱₒⵗˣₓᶹๅʶˠ᛫ᵛᵥᶺᴊ

Conclusion

cette implémentation doit être portée en JavaScript pour permettre l'échange client-serveur.

Vous devez également fournir un moyen de partager la structure et les codes Huffman avec les clients.

Il n'est pas difficile et plutôt amusant à faire, mais cela signifie encore plus de travail :).

le gain Huffman en terme de caractères est d'environ 30%.

bien sûr, ces caractères sont multibytes pour la plupart, mais si vous visez L'URI le plus court, il n'a pas d'importance.

Sauf pour les booléens qui peuvent facilement être emballés à 1 bit, ces chaînes pesantes semblent plutôt réticents à être compressé.

Il est peut-être possible de mieux ajuster les fréquences, mais je doute que vous arriviez à un taux de compression supérieur à 50%.

d'un autre côté, ramasser des glyphes minces fait en fait plus rétrécir la corde.

donc tout dans toute la combinaison des deux pourrait en effet atteindre quelque chose, bien que ce soit beaucoup de travail pour un résultat modeste.

comme vous le proposez vous-même, je voudrais d'abord me débarrasser de tous les caractères qui ne portent aucune information, parce qu'ils font partie du"format".

E. g. tour "les étiquettes=ouvert,ssl,cypher et de stockage=275643&username=ryanbrg et les étapes=&with_comment=oui" à "ouvert, ssl, cyper / 275643 / ryanbrg / / Oui".

puis utiliser un encodage Huffmann avec un vecteur de probabilité fixe (résultant en une correspondance fixe des caractères aux lacets de longueur variable - avec les caractères les plus probables cartographiés sur des bitstrings plus courts et les caractères les moins probables cartographiés sur des bitstrings plus longs).

vous pourriez même utiliser des vecteurs de probabilité différents pour les différents paramètres. Par exemple dans le paramètre "étiquettes" l'alpha personnages ont une forte probabilité, mais dans le "référentiel" paramètre numérique personnages ont la probabilité la plus élevée. Si vous faites cela, vous devriez considérer le séparateur "|" comme une partie du paramètre précédent.

et finalement transformer le long bitstring (qui est la concaténation de tous les bitstrings auxquels les caractères ont été mappés) en quelque chose que vous pouvez mettre dans une URL en l'encodant base64url.

si vous pouviez m'envoyer un ensemble de listes de paramètres représentatives, je pourrais les passer à travers un codeur Huffmann pour voir comment elles se compressent.

le vecteur de probabilité (ou, de façon équivalente, la mise en correspondance des caractères aux cordons de bits) doit être codé comme constante des tableaux dans la fonction Javascript qui est envoyé au navigateur.

bien sûr, vous pourriez aller encore plus loin et que, par exemple, essayer d'obtenir une liste de etiquettes avec leurs probabilités. Alors vous pourriez mapper des lables entiers à des bitstrings avec un encodage de Huffmann. Cela vous donnera une meilleure compression, mais vous aurez du travail supplémentaire pour les étiquettes qui sont nouvelles (par exemple, en retombant sur l'encodage d'un seul caractère), et bien sûr le mappage (qui - comme mentionné ci - dessus-est un tableau constant dans la fonction Javascript) sera beaucoup plus grand.

j'ai un plan astucieux! ^{(et une boisson de gin tonic)}

vous ne semblez pas vous soucier de la longueur du bytestream mais de la longueur des glyphes résultants, par exemple ce que la chaîne qui est affichée à l'utilisateur.

Les navigateurs

sont assez bons pour convertir un IRI en [URI] sous-jacent[2] tout en affichant l'IRI dans la barre d'adresse. IRIs ont un plus grand répertoire de possibles caractères tandis que votre ensemble de caractères possibles est plutôt limité.

cela signifie que vous pouvez encoder les bigrammes de vos caractères (aa, ab, ac, ..., zz et caractères spéciaux) en un seul caractère du spectre unicode complet. Supposons que vous ayez 80 caractères ASCII possibles: le nombre de combinaisons possibles de deux caractères est de 6400. Qui sont faciles à repérer dans les caractères Unicodes assignés, p.ex. dans le spectre de CJK unifié de han:

aa  →  一
ab  →  丁
ac  →  丂
ad  →  七
…

J'ai choisi CJK parce que c'est seulement (slighty) raisonnable si les caractères cibles sont assignés en unicode et ont assigné des glyphes sur le navigateur principal et les systèmes d'exploitation. Pour cette raison, la zone d'utilisation privée est désactivée et la version plus efficace utilisant trigrams (dont les combinaisons possibles pourraient utiliser tous les points de code possibles Unicodes 1114112) est désactivée.

pour récapituler: les octets sous-jacents sont toujours là et - étant donné l'encodage UTF-8-possible encore plus longtemps, mais la chaîne de caractères affichés que l'utilisateur voit et copie est 50% plus courte.

Ok, Ok, raisons, pourquoi cette solution est insensée:

• IRIs ne sont pas parfaits. Beaucoup moins d'outils de navigateur moderne ont leurs problèmes.

• L'algorithme doit évidemment beaucoup plus de travail. Vous aurez besoin d'une fonction qui établit une correspondance entre les bigrammes et les caractères cibles et vice versa. Et il est préférable de travailler arithmétiquement pour éviter de grandes tables de hachage dans la mémoire.

• les caractères cibles doivent être vérifiés s'ils sont assignés et s'il s'agit de caractères simples et non de caractères unicodiens de fantaisie comme la combinaison de caractères ou de choses qui se sont perdues quelque part dans la normalisation Unicode. Aussi si la zone cible est une étendue continue de caractères assignés avec des glyphes.

• les navigateurs se méfient parfois D'IRIs. Pour une bonne raison, étant donné les attaques de l'homographe IDN. Ils sont OK avec tous ces non-ASCII-chars dans leur barre d'adresse?

• et le plus grand: les gens sont notoirement mauvais à se souvenir des personnages dans des scripts qu'ils ne connaissent pas. Ils sont encore pires à essayer de (re)-type ces chars. Et copy'n'paste peut se tromper en de nombreux clics différents. Il y a une raison pour laquelle les raccourcisseurs D'URL utilisent Base64 et même des alphabets plus petits.

... en parlant de ça: ce serait ma solution. Le déchargement le travail de raccourcir les liens vers l'utilisateur ou d'intégrer goo.gl ou bit.ly via leur API.

petite astuce: les deux parseInt et Number#toString supportent les arguments radix. Essayez d'utiliser un radix de 36 pour encoder des nombres (ou des index dans des listes) dans les URLs.

Pourquoi ne pas utiliser protocole-tampons ?

Les tampons de protocole

sont un mécanisme souple, efficace et automatisé pour sérialiser des données structurées – pensez XML, mais plus petit, plus rapide et plus simple. Vous définissez comment vous voulez que vos données soient structurées une fois, puis vous pouvez utiliser le code source généré spécial pour écrire et lire facilement vos données structurées à et à partir d'une variété de flux de données et en utilisant une variété de langues. Vous pouvez même mettez à jour votre structure de données sans casser les programmes déployés qui sont compilés selon le format "ancien".

ProtoBuf.js convertit les objets en messages de tampon de protocole et vice vera.

l'objet suivant est converti en: CgFhCgFiCgFjEgFkEgFlEgFmGgFnGgFoGgFpIgNqZ2I=

{
    repos : ['a', 'b', 'c'],
    labels: ['d', 'e', 'f'],
    milestones : ['g', 'h', 'i'],
    username : 'jgb'
}

exemple

l'exemple suivant est construit en utilisant require.js . Faire un essai sur ce 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')
});

il y a deux aspects principaux au problème: l'encodage et la compression.

la compression à usage général ne semble pas bien fonctionner sur les petites cordes. Comme les navigateurs ne pas fournir une api pour compresser chaîne, vous devez également charger la source, qui peut être énorme.

beaucoup de caractères peuvent être sauvés en utilisant un encodage efficace. J'ai écrit une bibliothèque appelée μ pour gérer la partie encodage et décodage. L'idée est de spécifiez autant que les informations disponibles sur la structure et le domaine des paramètres d'url en tant que spécification. Cette spécification peut ensuite être utilisée pour piloter l'encodage et le décodage. Par exemple, booléen peut être encodé en utilisant juste un bit, entier peut être converti à une base différente (64) réduisant ainsi le nombre de caractères requis, les clés d'objet n'ont pas besoin d'être encodé parce qu'il peut être déduit de la spécification, enums peut être encodé en utilisant log ₂ (numberOfAllowedValues) bits.

on dirait que les API Github ont des identifiants numériques pour beaucoup de choses (on dirait que les repos et les utilisateurs en ont, mais pas les étiquettes) sous les couvertures. Il pourrait être possible d'utiliser ces numéros à la place des noms chaque fois que cela est avantageux. Vous devez ensuite trouver la meilleure façon de coder ceux dans quelque chose qui survivra dans une chaîne de requête, par exemple quelque chose comme base64(url).

par exemple, ton Sweat à capuche.js repository a un ID 4780572 .

emballage que dans un int big-endian non signé (autant d'octets que nous avons besoin) nous obtient \x00H\xf2\x1c .

nous allons juste jeter le zéro de tête, nous pouvons toujours restaurer que plus tard, maintenant nous avons H\xf2\x1c .

Encoder comme URL-safe base64, et vous avez SPIc (jeter tout rembourrage que vous pourriez obtenir).

passer de hoodiehq/hoodie.js à SPIc semble être une belle victoire!

Plus généralement, si vous êtes prêt à investir le temps, vous pouvez essayer d'exploiter un tas de redondances dans vos chaînes de requête. D'autres idées vont dans le sens d'empaqueter les deux params booléens en un seul caractère, éventuellement avec d'autres États (comme quels champs sont inclus). Si vous utilisez base64-encoding (qui semble la meilleure option ici en raison de la version SANS URL -- j'ai regardé base85, mais il a un tas de caractères qui ne survivront pas dans une URL), qui vous obtient 6 bits d'entropie par caractère... il ya beaucoup que vous pouvez faire avec cela.

pour ajouter à la note de Thomas Fuchs, Oui, s'il y a une sorte d'ordre inhérent, immuable dans certaines choses que vous encodez, que cela aiderait évidemment aussi. Cependant, cela semble difficile tant pour les étiquettes que pour les jalons.

peut-être que vous pouvez trouver un raccourci d'url avec une API jsonp, de cette façon vous pouvez rendre toutes les URLs vraiment courtes automatiquement.

http://yourls.org / a même le support de jsonp.

pourquoi ne pas utiliser un raccourci tiers?

(je suppose que vous n'avez pas de problème avec limites de longueur URI puisque vous avez mentionné qu'il s'agit d'une application existante.)

on dirait que vous écrivez un script Greasemonkey ou aux alentours, donc peut-être avez-vous accès à GM_xmlhttpRequest () , qui permettrait l'utilisation d'un raccourci de lien tiers.

sinon, vous devrez utiliser XMLHttpRequest () et héberger votre propre service de raccourcissement de lien sur le même serveur pour éviter de traverser la frontière Politique de même origine . Une recherche rapide en ligne pour héberger vos propres shorteners m'a fourni une liste de 7 scripts de shortener de lien libre / open source PHP et un de plus sur GitHub, bien que la question exclut probablement ce genre D'approche puisque "le la logique de l'application est dans le navigateur seulement, et il n'y a aucun arrière-plan que je peux écrire."

vous pouvez voir Exemple de code mettant en œuvre ce genre de chose dans le raccourci D'URL UserScript (pour Greasemonkey), qui apparaît une version raccourcie de L'URL de la page actuelle lorsque vous appuyez sur SHIFT+T.

bien sûr, les raccourcisseurs redirigeront les utilisateurs vers L'URL longue forme, mais ce serait un problème dans toute solution non-Côté Serveur. Au moins un raccourci peut théoriquement proxy (comme RewriteRule D'Apache avec [P]) ou utiliser une balise .

quelques conseils supplémentaires:

• Base64 Code avec a..zA..Z0..9+/= , et les caractères URI non codés sont a..zA..Z0..9-_.~ . Ainsi les résultats de Base64 ont seulement besoin d'échanger +/= pour -_. et il ne sera pas étendre URIs.
• vous pouvez conserver un tableau de noms de clés, de sorte que les objets puissent être représentés avec le premier caractère étant l'offset dans le tableau, par exemple {foo:3,bar:{g:'hi'}} devient a3,b{c'hi'} tableau de clés donné ['foo','bar','g']

Intéressant les bibliothèques:

• JSUrl encode spécifiquement JSON de sorte qu'il peut être mis dans une URL sans changements, même si elle utilise plus de caractères que ceux spécifiés dans la RFC. {"name":"John Doe","age":42,"children":["Mary","Bill"]} devient ~(name~'John*20Doe~age~42~children~(~'Mary~'Bill)) et avec un dictionnaire clé ['name','age','children'] qui pourrait être ~(0~'John*20Doe~1~42~2~(~'Mary~'Bill)) , allant ainsi de 101 octets URI encodé à 38.
  • petite empreinte, rapide, raisonnable de compression.
• LZ-string utilise un algorithme basé sur LZW pour compresser les chaînes vers UTF16 pour le stockage dans localStorage. Il dispose également d'une fonction compressToEncodedURIComponent() pour produire une sortie URI-safe.
  • encore quelques Ko de code, assez rapide, bonne/grande compression.

donc en gros, je recommande de choisir l'une de ces deux bibliothèques et considère le problème résolu.

peut-être qu'un simple mini-mini-js vous aidera. Vous n'aurez besoin que de l'intégrer sur les points de sérialisation et de désérialisation uniquement. Je pense que ce serait la solution la plus simple.

Court

utilisez un schéma D'empaquetage D'URL comme le mien, en commençant seulement de la section params de votre URL.

plus long

comme d'autres l'ont fait remarquer, les systèmes de compression typiques ne fonctionnent pas pour les chaînes courtes. Mais, il est important de reconnaître que les URLs et les Params sont un format de sérialisation d'un modèle de données: un format de texte lisible par l'homme avec des sections spécifiques-nous connaître le régime qui est premier, l'hôte se trouve directement après, le port est implicite, mais peuvent être remplacées, etc...

avec le modèle de données original, on peut sérialiser avec un schéma de sérialisation plus efficace en bits. En fait, j'ai moi-même créé une telle sérialisation qui Archive environ 50% de compression: voir http://blog.alivate.com.au/packed-url /