Ответ 1

Рабочее решение, объединяющее различные кусочки хороших (или так я думаю) идей

Я сделал это для удовольствия, главным образом потому, что это дало мне возможность реализовать кодировщик Хаффмана в PHP, и я не смог найти удовлетворительную существующую реализацию.

Однако это может сэкономить вам некоторое время, если вы планируете исследовать аналогичный путь.

Burrows-Wheeler + перемещение вперед + преобразование Хаффмана

Я не совсем уверен, что BWT лучше всего подходит для вашего ввода.
Это не обычный текст, поэтому повторяющиеся шаблоны, вероятно, не будут происходить так часто, как в исходном коде или просто английском.

Кроме того, динамический код Хаффмана должен быть передан вместе с закодированными данными, которые для очень коротких входных строк могут сильно повредить коэффициент сжатия.

Возможно, я ошибаюсь, и в этом случае я с радостью увижу, как кто-то докажет мне, что я.

Во всяком случае, я решил попробовать другой подход.

Общий принцип

1) определите структуру параметров URL и разделите константную часть

например, начиная с:

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

экстракт:

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

где , и | действуют как строковые и/или полевые терминаторы, тогда как логические значения не нуждаются.

2) определяют статическое разбиение символов на основе ожидаемого среднего ввода и вывод статического кода Хаффмана

Поскольку передача динамической таблицы занимает больше места, чем ваша исходная строка, я думаю, что единственный способ добиться какого-либо сжатия вообще - это статическая таблица huffman.

Однако вы можете использовать структуру своих данных в своих интересах для вычисления разумных вероятностей.

Вы можете начать с перераспределения букв на английском или других языках и указать определенный процент чисел и других знаков препинания.

Тестирование с помощью динамического кодирования Хаффмана показало, что коэффициент сжатия составляет от 30 до 50%.

Это означает, что с помощью статической таблицы вы можете ожидать, что коэффициент сжатия .6 (уменьшая длину ваших данных на 1/3), не намного больше.

3) преобразовать этот двоичный код Хаффмана во что-то, что URI может обрабатывать

70 обычных символов ASCII 7 бит в этом списке

!'()*-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz

даст вам коэффициент расширения около 30%, практически не лучше, чем base64.

30% -ное расширение разрушило бы выигрыш от статического сжатия Хаффмана, так что это вряд ли вариант!

Однако, поскольку вы управляете клиентом и сервером кодирования, вы можете использовать все, что не является зарезервированным символом URI.

Интересной возможностью было бы завершить вышеописанное значение до 256 с любыми глифами Unicode, что позволило бы кодировать ваши двоичные данные с одинаковым количеством символов, совместимых с URI, таким образом, заменяя болезненную и медленную связку длинных целых делений с быстрым просмотром таблицы.

Описание структуры

Кодек предназначен для использования как на стороне клиента, так и на стороне сервера, поэтому важно, чтобы сервер и клиенты имели общее определение структуры данных.

Поскольку интерфейс, вероятно, будет развиваться, кажется разумным сохранить номер версии для повышения совместимости.

В определении интерфейса будет использоваться очень минималистический язык описания, например:

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

Каждый поддерживаемый язык будет иметь частотную таблицу для всех использованных букв

и другие компьютерные символы, такие как -, . или _, будут иметь глобальную частоту, независимо от языков

(, и |) будут вычисляться в соответствии с количеством списков и полей, присутствующих в структуре.

Все остальные "чужие" символы будут экранированы специальным кодом и закодированы как простой UTF-8.

Реализация

Двунаправленный путь преобразования выглядит следующим образом:

список полей ↔ UTF-8 поток данных ↔ huffman codes ↔ URI

Вот главный кодек

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

В основе кодека Huffman

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

И словарь 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);
    }
}

Пример

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

выход:

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

В этом примере вход был упакован в 64 символа Юникода для входной длины около 100, что дает уменьшение на 1/3.

Эквивалентная строка:

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

Будет сжиматься динамической таблицей Хаффмана до 59 символов. Не большая разница.

Без сомнения, интеллектуальное переупорядочение данных уменьшит это, но тогда вам нужно будет пройти динамическую таблицу вдоль...

Китайский на помощь?

Опираясь на ttepasseидея, можно было бы использовать огромное количество азиатских символов, чтобы найти диапазон смежных значений 0x4000 (12 бит), чтобы закодировать 3 байта на 2 символа CJK, например:

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

и обратно:

    // 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]);
    }

Предыдущий вывод 64 латинских символов

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

будет "сжиматься" до 42 азиатских символов:

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

Однако, как вы можете видеть, основная масса вашей средней идеограммы делает строку более длинной (по пикселям), поэтому, даже если идея была многообещающей, результат довольно разочаровывает.

Выбор более тонких глифов

С другой стороны, вы можете попытаться выбрать "тонкие" символы в качестве базы для кодирования URI. Например:

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

вместо

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

Это сократит длину пополам пропорциональными шрифтами, в том числе в адресной строке браузера.

Мой лучший набор кандидатов из 256 "тонких" глифов:

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

Заключение

Эта реализация должна быть перенесена на JavaScript, чтобы разрешить обмен клиент-сервер.
Вы также должны предоставить способ совместного использования структуры и кодов Хаффмана с клиентами.

Это не сложно и довольно забавно, но это означает еще большую работу:).

Усиление Хаффмана в терминах персонажей составляет около 30%.

Конечно, эти символы являются многобайтными по большей части, но если вы стремитесь к кратчайшему URI, это не имеет значения.
За исключением булевых элементов, которые могут быть легко упакованы в 1 бит, эти надоедливые строки кажутся довольно неохотными для сжатия.
Возможно, будет лучше настроить частоты, но я сомневаюсь, что вы получите более 50% скорости сжатия.

С другой стороны, сбор тонких глифов делает больше для сокращения строки.

Таким образом, вся комбинация обоих может действительно что-то достичь, хотя для работы с небольшим результатом очень много работы.

Ответ 2

Как вы сами предлагаете, я сначала избавлюсь от всех символов, которые не содержат никакой информации, потому что они являются частью "формата".

например. turn "labels = open, ssl, cypher & repository = 275643 & username = ryanbrg & milestones = & with_comment = yes" to "Открытым, SSL, Cyper | 275643 | ryanbrg || да".

Затем используйте кодировку Хаффмана с фиксированным вектором вероятности (приводящее к фиксированному сопоставлению от символов к битрейтам переменной длины) с наиболее вероятными символами, сопоставленными более короткими битрейтами и менее вероятными символами, сопоставленными более длинными битрейтами).

Вы даже можете использовать разные векторы вероятности для разных параметров. Например, в параметре "метки" альфа-символы будут иметь высокую вероятность, но в параметре "репозиторий" числовые символы будут иметь наивысшую вероятность. Если вы это сделаете, вы должны рассмотреть разделитель "|" часть предыдущего параметра.

И, наконец, превратите длинную битовую строку (которая является конкатенацией всех битрейтов, к которым были привязаны символы), к чему-то, что вы можете поместить в URL по кодировке base64url.

Если бы вы могли отправить мне набор репрезентативных списков параметров, я мог бы запустить их через кодировщик Хаффмана, чтобы увидеть, насколько они сжимаются.

Вероятностный вектор (или, что то же самое, отображение от символов к бистровым строкам) должен быть закодирован как постоянные массивы в функцию Javascript, которая отправляется в браузер.

Конечно, вы могли бы пойти еще дальше и, например, попытаться получить список возможных таблиц со своими вероятностями. Затем вы можете сопоставить всю таблицу с битами с кодировкой Хаффмана. Это даст вам лучшее сжатие, но у вас будет дополнительная работа для новых ярлыков (например, возврат к одиночной кодировке символов), и, конечно, отображение (которое, как упоминалось выше, является постоянным массивом в функции Javascript ) будет намного больше.

Ответ 3

У меня есть хитрый план! ^{(И напиток джинсовой тоники)}

Кажется, вы не заботитесь о длине байта, но о длине результирующих глифов, например. что строка, отображаемая пользователю.

Браузер неплохо конвертирует IRI в базовый [URI] [2], сохраняя при этом IRI в адресной строке. IRI имеют больший репертуар возможных символов, в то время как ваш набор возможных символов довольно ограничен.

Это означает, что вы можете кодировать биграмы ваших символов (aa, ab, ac,..., zz и специальные символы) в один char полного спектра Юникода. Скажем, у вас есть 80 возможных символов ASCII: количество возможных комбинаций из двух символов - 6400. Что легко найти в символах, обозначенных Unicodes, например. в объединенном спектре CJK han:

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

Я выбрал CJK, потому что это только (слегка) разумно, если целевые символы назначены в юникоде и назначены глифы в главном браузере и операционных системах. По этой причине область частного использования отсутствует, и более эффективная версия с использованием триграмм (чьи возможные комбинации могут использовать все Unicodes 1114112 возможных кодовых точек).

Повторить: базовые байты все еще присутствуют и - при условии кодировки UTF-8 - возможны даже дольше, но строка отображаемых символов, которую пользователь видит, и копии на 50% короче.

Хорошо, хорошо, почему это решение безумно:

• IRI не идеальны. У многих меньших инструментов, чем у современного браузера, есть свои проблемы.

• Алгоритм, очевидно, требует много работы. Вам понадобится функция, которая сопоставляет биграмм с целевыми символами и обратно. И это должно быть предпочтительной работой арифметически, чтобы избежать больших хеш-таблиц в памяти.

• Целевые символы должны быть проверены, если они назначены, и если они являются простыми символами и не представляют собой уникодианные вещи, такие как объединение символов или вещей, которые потерялись где-то в нормализации Юникода. Также, если целевая область представляет собой непрерывный диапазон назначенных символов с глифами.

• Браузер иногда опасается IRI. По уважительной причине, учитывая атаки гомографа IDN. Они в порядке со всеми этими не-ASCII-символами в своей адресной строке?

• И самое большое: люди, как известно, плохо помнят персонажей в сценариях, которые они не знают. Они еще хуже при попытке (повторения) типа этих символов. И copy'n'paste может пойти не так во многих кликах. Существует причина, по которой укороченные URL-адреса используют Base64 и даже меньшие алфавиты.

... говоря о котором: Это было бы моим решением. Развертывание работы по сокращению ссылок либо пользователю, либо интеграции goo.gl или bit.ly через их API.

Ответ 4

Маленький совет: обе parseInt и Number#toString поддерживают аргументы radix. Попробуйте использовать радиус 36 для кодирования чисел (или индексов в списки) в URL-адресах.

Ответ 5

Почему бы не использовать протокольные буферы?

Буферы протокола - это гибкий, эффективный и автоматизированный механизм сериализации структурированных данных - думаю, XML, но меньше, быстрее и проще. Вы определяете, как вы хотите, чтобы ваши данные были структурированы один раз, затем вы можете использовать специальный сгенерированный исходный код, чтобы легко писать и читать ваши структурированные данные в различные потоки данных и из разных источников и из разных языков. Вы даже можете обновить свою структуру данных, не разбирая развернутые программы, которые скомпилированы против "старого" формата.

ProtoBuf.js преобразует объекты в сообщения буфера протокола и вице-вера.

Следующий объект преобразуется в: CgFhCgFiCgFjEgFkEgFlEgFmGgFnGgFoGgFpIgNqZ2I=

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

пример

Следующий пример построен с использованием require.js. Попробуйте этот 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')
});

Ответ 6

Есть два основных аспекта проблемы: кодирование и сжатие.

Сжатие общего назначения, по-видимому, плохо работает на небольших строках. Поскольку браузеры не предоставляют api для сжатия строки, вам также необходимо загрузить источник, который может быть огромным.

Множество символов можно сохранить с помощью эффективного кодирования. Я написал библиотеку с именем μ для обработки части кодирования и декодирования. Идея состоит в том, чтобы указать как доступную информацию о структуре и домене параметров URL как спецификацию. Затем эту спецификацию можно использовать для кодирования и декодирования. Например, логическое значение может быть закодировано с использованием всего одного бита, целое число может быть преобразовано в другую базу (64), тем самым уменьшив количество требуемых символов, ключи объектов не обязательно должны быть закодированы, поскольку это можно сделать из спецификации, перечисления могут быть закодированы с использованием log ₂ (numberOfAllowedValues).

Ответ 7

Обновление: я выпустил пакет NPM с некоторыми дополнительными оптимизациями, см. Https://www.npmjs.com/package/@yaska-eu/jsurl2

Еще несколько советов:

• Base64 кодируется с помощью a..zA..Z0..9+/=, а a..zA..Z0..9-_.~ символы URI являются a..zA..Z0..9-_.~. Таким образом, для результатов Base64 требуется только обмен +/= для -_. и он не будет расширять URI.
• Вы можете сохранить массив имен ключей, чтобы объекты могли быть представлены с первым символом, являющимся смещением в массиве, например {foo:3,bar:{g:'hi'}} становится a3,b{c'hi'} заданный массив ключей ['foo','bar','g']

Интересные библиотеки:

• JSUrl специально кодирует JSON, поэтому его можно поместить в URL без изменений, хотя он использует больше символов, чем указано в RFC. {"name":"John Doe","age":42,"children":["Mary","Bill"]} становится ~(name~'John*20Doe~age~42~children~(~'Mary~'Bill)) и с ключевым словарем ['name','age','children'] который может быть ~(0~'John*20Doe~1~42~2~(~'Mary~'Bill)), таким образом переходя от 101 байта URI, закодированного до 38.
  • Малый размер, быстрое и разумное сжатие.
• lz-string использует алгоритм LZW для сжатия строк в UTF16 для хранения в localStorage. Он также имеет функцию compressToEncodedURIComponent() для создания URI-безопасного выхода.
  • Все еще только несколько КБ кода, довольно быстрое, хорошее/отличное сжатие.

Поэтому в принципе я бы рекомендовал выбрать одну из этих двух библиотек и решить проблему.

Ответ 8

Похоже, что API-интерфейсы Github имеют числовые идентификаторы для многих вещей (они выглядят как репозитории, а пользователи имеют их, а метки - нет) под обложками. Возможно, можно использовать эти числа вместо имен там, где это выгодно. Затем вам нужно выяснить, как наилучшим образом закодировать их в том, что сохранится в строке запроса, например. что-то вроде base64 (url).

Например, ваш репозиторий hoodie.js имеет идентификатор 4780572.

Упаковка в бинардный неподписанный int (столько, сколько нам нужно) получает \x00H\xf2\x1c.

Мы будем просто бросать ведущий ноль, мы можем всегда восстановить это позже, теперь у нас есть H\xf2\x1c.

Кодировать как безопасный для базы данных base64, и у вас есть SPIc (подбрасывать любое дополнение, которое вы можете получить).

Переход от hoodiehq/hoodie.js в SPIc кажется хорошим выигрышем!

В более общем плане, если вы готовы потратить время, вы можете попытаться использовать кучу редумантов в ваших строках запросов. Другие идеи заключаются в том, что они упаковывают два булевых параметра в один символ, возможно, вместе с другим состоянием (например, какие поля включены). Если вы используете base64-кодирование (что кажется лучшим вариантом из-за версии с безопасным URL-адресом, я посмотрел на base85, но у него есть куча символов, которые не сохранится в URL-адресе), что дает вам 6 бит энтропия на символ... там вы многое можете сделать.

Чтобы добавить к примечанию Томаса Фукса, да, если в некоторых вещах, которые вы кодируете, есть какой-то неотъемлемый, неизменный порядок, чем это, очевидно, также поможет. Тем не менее, это кажется трудным для ярлыков и этапов.

Ответ 9

Возможно, вы можете найти сократитель URL-адресов с помощью jsonp API, таким образом вы могли бы сделать все URL-адреса действительно короткими автоматически.

http://yourls.org/ даже поддерживает jsonp.

Ответ 10

Почему бы не использовать сторонний укупорщик ссылок?

(Я предполагаю, что у вас нет проблемы с ограничениями длины URI, поскольку вы упомянули, что это существующее приложение.)

Похоже, вы пишете Greasemonkey script или около того, поэтому, возможно, у вас есть доступ к GM_xmlhttpRequest(), который позволит использовать сторонний укороченный канал связи.

В противном случае вам нужно будет использовать XMLHttpRequest() и разместить свою собственную службу сокращения ссылок на том же сервере, чтобы избежать перехода на граница одного и того же происхождения. Быстрый онлайн-поиск хостинга ваших собственных сокращений предоставил мне список из 7 бесплатных/открытых исходных скриптов для ссылок на PHP и еще один на GitHub, хотя вопрос, вероятно, исключает такой подход, поскольку "Логика приложений только в браузере, и нет бэкэнд, на который я могу писать".

Вы можете увидеть пример кода, реализующего этот вид в URL Shortener UserScript (для Greasemonkey), в котором появляется сокращенная версия текущий URL страницы при нажатии SHIFT + T.

Конечно, укороченные пользователи будут перенаправлять пользователей на длинный URL формы, но это будет проблемой в любом решении, отличном от сервера. По крайней мере, укороченный может теоретически прокси (например, Apache RewriteRule с [P]) или использовать <frame> тег.

Ответ 11

Может быть, любой простой JS minifier поможет вам. Вам нужно только интегрировать его только в точки сериализации и десериализации. Я думаю, что это будет самое простое решение.

Ответ 12

короткий

Используйте схему упаковки URL, такую как моя, начиная только с раздела параметров вашего URL-адреса.

дольше

Как уже отмечалось, типичные системы сжатия не работают для коротких строк. Но важно признать, что URL-адреса и Params представляют собой формат сериализации модели данных: текстовый формат, читаемый человеком, с определенными разделами - мы знаем, что схема сначала, хост найден сразу после, порт подразумевается, но может быть отмененным и т.д....

С исходной моделью данных можно сериализовать с более битовой схемой сериализации. На самом деле, я создал такую сериализацию, которая архивирует около 50% сжатия: см. Http://blog.alivate.com.au/packed-url/