将各种好的（或者我认为是好的）想法放在一起的可行解决方案
我这样做只是为了好玩，主要是因为它给了我一个机会在PHP中实现Huffman编码器，而我找不到一个令人满意的现有实现。
然而，如果您计划探索类似的路径，这可能会为您节省一些时间。
Burrows-Wheeler+move-to-front+Huffman变换
我不确定BWT是否最适合您的输入类型。
这不是常规文本，因此重复模式可能不像源代码或纯英语那样经常出现。
此外，对于非常短的输入字符串，必须传递动态Huffman代码以及编码数据，这将严重损害压缩增益。
我可能是错的，如果是这样，我很乐意看到有人证明我是错的。
无论如何，我决定尝试另一种方法。
一般原则
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码。
由于传输动态表所需的空间比初始字符串更大，因此我认为实现任何压缩的唯一方法是具有静态哈夫曼表。
但是，您可以利用数据的结构来计算合理的概率。
您可以从英语或其他语言中字母的重新分配开始，并投入一定比例的数字和其他标点符号。
使用动态Huffman编码进行测试，我看到了30至50％的压缩率。
这意味着使用静态表，您可能会期望0.6的压缩系数（将数据长度减少1/3），并没有更多。
3）将此二进制Huffmann码转换为URI可以处理的内容
该列表中的70个常规ASCII 7位字符
!'()*-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz
这将给你一个大约30%的扩展因子，实际上并不比base64编码好多少。
30%的扩展会破坏静态Huffman压缩所获得的收益，因此这几乎不是一个选项！
然而，由于您控制着编码客户端和服务器端，因此您可以使用任何不是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数据流 <-> 哈夫曼编码 <-> URI
这是主要编解码器。
include ('class.huffman.codec.php');
class IRI_prm_codec
{
static private $translator = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzÀÁÂÃÄÅÆÇÈÉÊËÌÍÎÏÐÑÒÓÔÕÖÙÚÛÜÝÞßàáâãäåæçèéêëìíîïðñòóôõöùúûüýþÿĀāĂ㥹ĆćĈĉĊċČčĎďĐđĒēĔĕĖėĘęĚěĜĝĞğĠġĢģĤĥĦħĨĩĪīĬĭĮįİıIJijĴĵĶķĸĹĺĻļĽľĿŀŁłŃńŅņŇňʼnŊŋŌōŎŏŐőŒœŔŕŖŗŘřŚśŜŝŞşŠšŢţŤťŦŧŨũŪūŬŭŮůŰűŲųŴŵŶŷŸŹźŻżŽžſƀƁƂƃƄƅ";
const VERSION_LEN = 6;
public function __construct ($config)
{
$num_record_terminators = 0;
$num_record_separators = 0;
$num_text_sym = 0;
$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");
}
}
$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);
$this->huffman = new Huffman_codec();
$this->huffman->make_code ($this->frequency);
}
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;
}
}
private function set_frequencies ($symbols, $coef)
{
$coef /= strlen ($symbols);
for ($i = 0 ; $i != strlen($symbols) ; $i++) $this->frequency[$symbols[$i]] = $coef;
}
public function encode($input)
{
$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 ?!?");
}
}
$prefix = sprintf ("%0".self::VERSION_LEN."b$bools", $this->version);
$strings = implode ("|", $strings);
$huff = $this->huffman->encode ($strings, $prefix, "UTF-8");
mb_internal_encoding("UTF-8");
$res = '';
for ($i = 0 ; $i != strlen($huff) ; $i++) $res .= mb_substr (self::$translator, ord($huff[$i]), 1);
return $res;
}
public function decode($input)
{
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 = '';
$version = $this->read_bits ($raw, self::VERSION_LEN);
if ($version != $this->version) throw new Exception ("Version mismatch: expected {$this->version}, found $version");
foreach ($this->type as $field => $type)
if ($type == 'b')
$res->$field = $this->read_bits ($raw, 1) != 0;
$strings = explode ('|', $this->huffman->decode ($raw, $this->bin));
$i = 0;
foreach ($this->type as $field => $type)
if ($type == 's')
$res->$field = $strings[$i++];
return $res;
}
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;
}
}
底层的哈夫曼编解码器
include ('class.huffman.dict.php');
class Huffman_codec
{
public $dict = null;
public function encode($input, $prefix='', $encoding="UTF-8")
{
mb_internal_encoding($encoding);
$bin = $prefix;
$res = '';
$input .= "\0";
$len = mb_strlen ($input);
while ($len--)
{
$c = mb_substr ($input, 0, 1);
$input = substr($input, strlen($c));
if (isset($this->dict->code[$c]))
{
$bin .= $this->dict->code[$c];
}
else
{
$lc = strlen($c);
$bin .= $this->dict->code["\1"]
. sprintf("%02b", $lc-1);
for ($i=0 ; $i != $lc ; $i++) $bin .= sprintf("%08b", ord($c[$i]));
}
while (strlen($bin) >= 8)
{
$res .= chr(bindec(substr ($bin, 0, 8)));
$bin = substr($bin, 8);
}
}
if (strlen($bin) > 0)
{
$bin .= str_repeat ('0', 8-strlen($bin));
$res .= chr(bindec($bin));
}
return $res;
}
public function decode($input, $prefix='')
{
$bin = $prefix;
$res = '';
$len = strlen($input);
for ($i=0 ;;)
{
$c = $this->dict->symbol($bin);
switch ((string)$c)
{
case "\0":
break 2;
case "\1":
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);
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:
if ($i == $len) throw new Exception ("no end of input mark found");
$bin .= sprintf ("%08b", ord($input[$i++]));
break;
default:
$res .= $c;
break;
}
}
if (bindec ($bin) != 0) throw new Exception ("trailing bits in input");
return $res;
}
public function make_code ($input, $encoding="UTF-8")
{
if (is_string ($input))
{
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
{
$this->dict = new Huffman_dict ($input);
}
}
}
以及哈夫曼字典
class Huffman_dict
{
public $code = array();
public function __construct ($frequency = array())
{
if (!isset ($frequency["\0"])) $frequency["\0"] = 1e-100;
if (!isset ($frequency["\1"])) $frequency["\1"] = 1e-100;
asort ($frequency);
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], '');
}
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];
}
}
public function symbol(&$code_stream)
{
list ($symbol, $code) = $this->get_symbol ($this->tree, $code_stream);
if ($symbol !== null) $code_stream = $code;
return $symbol;
}
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个Unicode字符，输入长度约为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字符，如下所示：
$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
+ ($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");
并返回：
$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个“细”的字形：
᠊།ᑊʲ་༌ᵎᵢᶤᶩᶪᶦᶧˡ ⁄∕เ'Ꞌꞌ꡶ᶥᵗᶵᶨ|¦ǀᴵ ᐧᶠᶡ༴ˢᶳ⁏ᶴʳʴʵ։᛬⍮ʹ′ ⁚⁝ᵣ⍘༔⍿ᠵᥣᵋᵌᶟᴶǂˀˁˤ༑,. ∙Ɩ៲᠙ᵉᵊᵓᶜᶝₑₔյⵏⵑ༝༎՛ᵞᵧᚽᛁᛂᛌᛍᛙᛧᶢᶾ৷⍳ɩΐίιϊᵼἰἱἲἳἴἵἶἷὶίῐῑῒΐῖῗ⎰⎱᠆ᶿ՝ᵟᶫᵃᵄᶻᶼₐ∫ª౹᠔/:
结论
这个实现应该被移植到JavaScript，以便允许客户端和服务器之间的交换。
您还应该提供一种与客户端共享结构和Huffman编码的方式。
这并不难，而且相当有趣，但这意味着更多的工作：）。
从字符角度来看，Huffman编码可以减少约30%。
当然，这些字符大部分是多字节的，但如果您追求最短的URI，那就无所谓了。
除了布尔值可以轻松压缩为1位之外，那些令人讨厌的字符串似乎不太愿意被压缩。
也许可以更好地调整频率，但我怀疑您能达到50%以上的压缩率。
另一方面，选择细小的字形确实可以更好地缩小字符串。
总而言之，两者的组合可能确实可以取得一些成果，尽管这需要很多工作才能获得适度的结果。
