URL 매개 변수를 압축하는 방법
콘텐츠에 타사 API를 사용 하는 단일 페이지 애플리케이션이 있다고 가정 해 보겠습니다 . 앱의 로직은 브라우저 내 전용이며 쓸 수있는 백엔드가 없습니다.
앱 상태에 대한 딥 링크를 허용하기 위해 pushState를 사용하여 앱 상태를 결정하는 몇 가지 변수를 추적합니다 (Ubersicht의 공개 버전은 아직이를 수행하지 않음). 이 경우 repos, labels, milestones와 username, show_open(BOOL) 및 with_comments(BOOL) 및 without_comments(BOOL). URL 형식은 ?label=label_1,label_2,label_3&repos=repo_1…입니다. 값은 일반적인 용의자, 대략 [a-zA-Z][a-zA-Z0-9_-]또는 부울 표시기입니다.
여태까지는 그런대로 잘됐다. 이제 쿼리 문자열이 약간 길고 다루기 어려울 수 있으므로 http://espy.github.io/ubersicht/?state=SOMOPAQUETOKENTHATLOSSLESSLYDECOMPRESSESINTOTHEORIGINALVALUES#hoodiehq, 같은 URL을 전달할 수 있기를 바랍니다 . 짧을수록 좋습니다.
내 첫 번째 시도는 이에 대한 알고리즘과 같은 zlib ( https://github.com/imaya/zlib.js )를 사용하고 @flipzagging은 antirez / smaz (https // github.com / antirez / smaz)를 가리 켰습니다. 짧은 문자열 ( https://github.com/personalcomputer/smaz.js의 자바 스크립트 버전)에 더 적합합니다 .
이후 =그리고 &특별히에서 처리되지 https://github.com/personalcomputer/smaz.js/blob/master/lib/smaz.js#L9 , 우리는 거의 없다 일을 조정할 수 있습니다.
또한 고정 테이블의 값을 인코딩하는 옵션이 있습니다. 예를 들어 인수의 순서는 미리 정의되어 있으며 추적해야하는 것은 실제 값뿐입니다. 예를 a=hamster&b=cat들어 smaz 압축 전에 잠재적 으로 7hamster3cat(length + chars) 또는 hamster | cat (value + |)로 바꿉니다.
내가 찾아야 할 다른 것이 있습니까?
다양한 좋은 아이디어를 모아 놓은 작업 솔루션
이 작업은 주로 PHP로 Huffman 인코더를 구현할 수있는 기회를 주었고 만족스러운 기존 구현을 찾을 수 없었기 때문에 재미로했습니다.
그러나 비슷한 경로를 탐색하려는 경우 시간을 절약 할 수 있습니다.
Burrows-Wheeler + 앞으로 이동 + 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 % 인 것으로 나타났습니다.
이는 정적 테이블을 사용하면 .6 압축 계수 (데이터 길이를 1/3로 줄임)를 기대할 수 있다는 것을 의미합니다.
3)이 바이너리 허프만 코드를 URI가 처리 할 수있는 것으로 변환
해당 목록의 일반 ASCII 7 비트 문자 70 개
!'()*-.0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz
약 30 %의 확장 계수를 제공하며 사실상 base64 인코딩보다 낫지 않습니다.
30 % 확장은 정적 Huffman 압축의 이득을 망칠 수 있으므로 이것은 선택 사항이 아닙니다!
그러나 인코딩 클라이언트와 서버 측을 제어하기 때문에 URI 예약 문자가 아닌 모든 것을 사용할 수 있습니다.
흥미로운 가능성은 어떤 유니 코드 글리프로든 위의 설정을 256 개까지 완료하는 것입니다. 이렇게하면 동일한 수의 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
{
// 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);
}
}
}
그리고 허프만 사전
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"
}
이 예에서는 입력 길이가 약 100 인 64 개의 유니 코드 문자로 압축되어 1/3이 줄어 듭니다.
동등한 문자열 :
discussion,documentation,hoodie-cli|enhancement,release-0.3.0,starter|
1.0.0,1.1.0,v0.7|mklappstuhl|0110
동적 Huffman 테이블에 의해 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로 포팅해야합니다.
또한 구조 및 Huffman 코드를 클라이언트와 공유하는 방법을 제공해야합니다.
어렵지 않고 재밌지 만 더 많은 일을해야합니다. :).
캐릭터 측면 에서 Huffman 이득 은 약 30 %입니다.
물론 이러한 문자는 대부분 멀티 바이트이지만 가장 짧은 URI를 목표로한다면 중요하지 않습니다.
1 비트로 쉽게 압축 될 수있는 부울을 제외하고, 이러한 성가신 문자열은 압축을 꺼리는 것 같습니다.
주파수를 더 잘 조정하는 것이 가능할 수도 있지만 압축률이 50 % 이상이 될 것 같지는 않습니다.
반면에 얇은 글리프를 선택하면 실제로 문자열을 축소하는 데 더 많은 역할을합니다.
따라서 겸손한 결과를 얻으려면 많은 작업이 필요하지만 두 가지를 모두 조합하면 실제로 무언가를 얻을 수 있습니다.
당신이 제안한 것처럼, 나는 어떤 정보도 가지고 있지 않은 모든 문자를 먼저 제거 할 것입니다. 왜냐하면 그것들은 "형식"의 일부이기 때문입니다.
예를 들어 "labels = open, ssl, cypher & repository = 275643 & username = ryanbrg & milestones = & with_comment = yes"를 "open, ssl, cyper | 275643 | ryanbrg || yes"로 변경합니다.
그런 다음 고정 확률 벡터를 사용하여 Huffmann 인코딩을 사용합니다 (문자에서 가변 길이 비트 문자열로의 고정 매핑-가장 가능성이 높은 문자는 더 짧은 비트 문자열에 매핑되고 확률이 낮은 문자는 더 긴 비트 문자열에 매핑 됨).
다른 매개 변수에 대해 다른 확률 벡터를 사용할 수도 있습니다. 예를 들어 "labels"매개 변수에서 영문자는 높은 확률을 가지지 만 "repository"매개 변수에서는 숫자가 가장 높은 확률을 갖습니다. 이렇게하면 구분 기호 "|"를 고려해야합니다. 선행 매개 변수의 일부.
마지막으로 긴 비트 문자열 (문자가 매핑 된 모든 비트 문자열의 연결)을 base64url 인코딩으로 URL에 넣을 수있는 것으로 바꿉니다.
대표 매개 변수 목록을 보내 주시면 Huffmann 코더를 통해 실행하여 얼마나 잘 압축되는지 확인할 수 있습니다.
확률 벡터 (또는 문자에서 비트 문자열로의 매핑)는 브라우저로 전송되는 Javascript 함수에 상수 배열로 인코딩되어야합니다.
물론 더 나아가서-예를 들어-가능성과 함께 가능한 lables 목록을 얻으려고 노력할 수 있습니다. 그런 다음 Huffmann 인코딩을 사용하여 전체 lables를 비트 문자열에 매핑 할 수 있습니다. 이렇게하면 압축률이 향상되지만 새로운 레이블 (예 : 단일 문자 인코딩으로 대체) 및 매핑 (위에서 언급했듯이 Javascript 함수의 상수 배열)에 대한 추가 작업이 있습니다. ) 훨씬 더 커집니다.
나는 교활한 계획이있다! (그리고 진토닉 음료)
바이트 스트림의 길이는 신경 쓰지 않고 결과 글리프의 길이, 예를 들어 사용자에게 표시되는 문자열에 대해 신경 쓰지 않는 것 같습니다.
브라우저는 주소 표시 줄에 IRI를 표시하는 동안 IRI 를 기본 [URI] [2] 로 변환하는 데 꽤 좋습니다 . IRI는 가능한 문자의 레퍼토리가 더 많은 반면 가능한 문자 세트는 다소 제한적입니다.
즉, 문자 (aa, ab, ac,…, zz 및 특수 문자)의 bigram을 전체 유니 코드 스펙트럼의 하나의 문자로 인코딩 할 수 있습니다. 80 개의 가능한 ASCII 문자가 있다고 가정 해 보겠습니다. 두 문자의 가능한 조합 수는 6400 개입니다. 이는 유니 코드 할당 문자에서 쉽게 찾을 수 있습니다. 예를 들어 한 통합 CJK 스펙트럼에서 :
aa → 一
ab → 丁
ac → 丂
ad → 七
…
대상 문자가 유니 코드로 할당되고 주요 브라우저 및 운영 체제에서 글리프를 할당 한 경우에만 (약간) 합리적이기 때문에 CJK를 선택했습니다. 이러한 이유로 개인 사용 영역이 없어지고 트라이 그램을 사용하는보다 효율적인 버전 (가능한 조합이 모든 유니 코드 1114112 가능한 코드 포인트를 사용할 수 있음)이 나와 있습니다.
요약하자면 기본 바이트는 여전히 존재하며 UTF-8 인코딩이 주어지면 더 길어질 수 있지만 사용자가보고 복사하는 표시되는 문자열은 50 % 더 짧습니다.
좋아, 좋아, 이유,이 솔루션이 미친 이유 :
IRI는 완벽하지 않습니다. 최신 브라우저보다 훨씬 적은 도구에 문제가 있습니다.
알고리즘은 분명히 더 많은 작업이 필요합니다. bigram을 대상 문자에 매핑하고 그 반대로 매핑하는 함수가 필요합니다. 그리고 메모리에 큰 해시 테이블을 피하려면 산술적으로 작업하는 것이 좋습니다.
대상 문자는 할당되었는지, 그리고 유니 코드 정규화 어딘가에서 잃어버린 문자 나 물건을 결합하는 것과 같은 단순한 문자가 아닌 단순한 문자인지 확인해야합니다. 또한 대상 영역이 글리프가있는 할당 된 문자의 연속 범위 인 경우.
브라우저는 때때로 IRI를 경계합니다. IDN 동형 이의어 공격을 고려할 때 타당한 이유가 있습니다. 주소 표시 줄에 이러한 ASCII가 아닌 문자를 모두 사용해도 괜찮습니까?
그리고 가장 큰 것은 사람들이 자신이 모르는 대본에서 문자를 기억하는 데 악명이 높습니다. 그들은 이러한 문자를 (재) 타이핑하려고 시도하는 데 훨씬 더 나쁩니다. 그리고 copy'n'paste는 여러 번의 클릭에서 잘못 될 수 있습니다. URL 단축기가 Base64 및 더 작은 알파벳을 사용하는 이유가 있습니다.
… 즉, 그것이 제 해결책이 될 것입니다. 사용자에게 링크를 단축하거나 API를 통해 goo.gl 또는 bit.ly를 통합하는 작업을 오프로드합니다.
프로토콜 버퍼를 사용하지 않는 이유는 무엇 입니까?
프로토콜 버퍼는 구조화 된 데이터를 직렬화하기위한 유연하고 효율적이며 자동화 된 메커니즘입니다. 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')
});
작은 팁 : 둘 다 parseInt및 Number#toString기수 인수를 지원합니다. 36의 기수를 사용하여 URL에서 숫자 (또는 목록으로 색인)를 인코딩 해보십시오.
문제에는 인코딩과 압축이라는 두 가지 주요 측면이 있습니다.
범용 압축은 작은 문자열에서 잘 작동하지 않는 것 같습니다. 브라우저는 문자열을 압축하기위한 API를 제공하지 않으므로 소스도로드해야합니다.
Lot of characters can be saved by using an efficient encoding. I have written a library named μ to handle the encoding and decoding part. The idea is to specify as much as information available about the structure and domain of the url parameters as a specification. This specification can be then used to drive the encoding and decoding. 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 log2(numberOfAllowedValues) bits.
Update: I released an NPM package with some more optimizations, see https://www.npmjs.com/package/@yaska-eu/jsurl2
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, e.g.
{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.
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, e.g. 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.
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.
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.
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.
Short
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/
ReferenceURL : https://stackoverflow.com/questions/21802866/how-to-compress-url-parameters
'UFO ET IT' 카테고리의 다른 글
| yyyymmdd에서 mm / dd / yyyy로 Excel 날짜 변환 (0) | 2021.01.11 |
|---|---|
| 먼저 EntityFramework 코드의 시각적 모델을 만드는 방법 (0) | 2021.01.11 |
| 커피 스크립트에서 케이스 문 전환 (0) | 2021.01.10 |
| hadoop은 로컬 파일 시스템 폴더를 HDFS로 복사합니다. (0) | 2021.01.10 |
| AVPlayer 비디오 재생이 종료되는시기를 감지하는 방법 (0) | 2021.01.10 |