Compressie script
Ik ben al wat verder aan het zoeken geweest en ik stuitte op LZW (http://en.wikipedia.org/wiki/LZW). Dit lijkt tamelijk eenvoudig te implementeren(en dus te begrijpen) en ook niet té processorintensief.
Ik krijg het echter nog niet volledig aan de praat in php, heb helaas net mijn opzetje weer weggegooid.
Wel vond ik nog een class: http://www.phpclasses.org/browse/file/20090.html
Maar die zit vol errors en decode ook niet helemaal goed. Mijn insteek is om dit in twee functies te bouwen (compress/decompress)
Dus, voor de geinteresseerde/geprikkelde mede phphulper:
Compressor
Code (php)
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
w = NIL;
while (read a char c) do
if (wc exists in dictionary) then
w = wc;
else
add wc to the dictionary;
output the code for w;
w = c;
endif
done
output the code for w;
while (read a char c) do
if (wc exists in dictionary) then
w = wc;
else
add wc to the dictionary;
output the code for w;
w = c;
endif
done
output the code for w;
Decompress
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
read a char k;
output k;
w = k;
while (read a char k) do
if (index k exists in dictionary) then
entry = dictionary entry for k;
else if (index k does not exist in dictionary && k == currSizeDict)
entry = w + w[0];
else
signal invalid code;
endif
output entry;
add w+entry[0] to the dictionary;
w = entry;
done
output k;
w = k;
while (read a char k) do
if (index k exists in dictionary) then
entry = dictionary entry for k;
else if (index k does not exist in dictionary && k == currSizeDict)
entry = w + w[0];
else
signal invalid code;
endif
output entry;
add w+entry[0] to the dictionary;
w = entry;
done
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
http://httpd.apache.org/docs/2.0/mod/mod_deflate.html
http://nl2.php.net/manual/en/ref.zlib.php
Ook weet ik niet zeker of dit wel op ascii (text) niveau gaat werken. LWZ werkt voorzover ik weet op byte niveau. Bedenk eens wat er gebeurd als je een binair bestand als een bmp/rar bestand probeert te lezen? Wanneer deze naar ascii wordt vertaald loopt het compleet in de soep. Dus je zult waarschijnlijk een manier moeten verzinnen om de code naar een binair systeem te vertalen, dan wordt het opeens een stuk ingewikkelder.
Wat ik begrijp uit het apache verhaal, dat is vooral voor text/html en consorten en niet zozeer voor transport van data.
Ik wil tussen een server en een client communicatie mogelijk maken, het liefst wat compressie erover om het leed wat te verzachten. Begrijp me goed, die compressie hoeft niet super te zijn, maar op normale tekst/programmeercode moet toch wel een 25% te winnen zijn zonder ingewikkelde zaken.
Toch maar ff mijn code plaatsen welke misschien nog ooit in de library belandt:
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
<?php
// to convert ascii text use this function
function asc2bin($in) #syntax - asc2bin("text to convert");
{
$out = '';
for ($i = 0, $len = strlen($in); $i < $len; $i++) {
$out .= sprintf("%08b", ord($in{$i}) );
}
return $out;
}
//use this function to convert binary back to readable ascii text
function bin2asc($in)#syntax - bin2asc("binary to convert");
{
$out = '';
for ($i = 0, $len = strlen($in); $i < $len; $i += 8) {
$out .= chr(bindec(substr($in,$i,8)));
}
return $out;
}
function compressLzw( $input){
$inputArr = str_split( $input, 1);
$w = NULL;
$wc = '';
$dict = array();
$arrOutput = array();
$iPos = 0;
for( $iPos; $iPos<256; $iPos++){
$dict[$iPos] = chr($iPos);
}
foreach( $inputArr as $char ){
$wc = $w . $char;
if( in_array($wc, $dict) ){
$w = $wc;
}else{
$dict[$iPos] = $wc;
$iPos++;
$arrOutput[] = array_search($w, $dict);
$w = $char;
}
}
$arrOutput[] = array_search($w, $dict);
$strBitlength = strlen(decbin($iPos));
$strOutput = str_pad( $strBitlength, 2, "0", STR_PAD_LEFT);
$strBinOutput = '';
foreach( $arrOutput as $index ){
$strBinOutput .= sprintf("%0".$strBitlength."b", $index);
}
$iPadSize = 8 - strlen($strBinOutput)%8;
$strBinOutput = sprintf("%0" . $iPadSize."b", "0") . $strBinOutput;
return $strOutput . strval($iPadSize) . bin2asc( $strBinOutput );
}
function decompressLzw( $input ){
$iBitlength = intval(substr($input, 0, 2));
$iPadLength = intval(substr($input, 2, 1));
$input = substr($input, 3 );
$inputBinary = substr(asc2bin($input), $iPadLength);
$inputArr = str_split( $inputBinary, $iBitlength);
$entry = '';
$dict = array();
$iPos = 0;
for( $iPos; $iPos<256; $iPos++){
$dict[$iPos] = chr($iPos);
}
$w = $output = chr( bindec( array_shift($inputArr) ) );
foreach( $inputArr as $binCode){
$intVal = bindec($binCode);
if( isset($dict[ $intVal ]) ){
$entry = $dict[ $intVal ];
}elseif( $intVal >= $iPos ){
$entry = $w . $w{0};
}else{
die('invalid');
}
$output .= $entry;
$dict[$iPos] = $w . $entry{0};
$iPos++;
$w = $entry;
}
return $output;
}
[/code]
// to convert ascii text use this function
function asc2bin($in) #syntax - asc2bin("text to convert");
{
$out = '';
for ($i = 0, $len = strlen($in); $i < $len; $i++) {
$out .= sprintf("%08b", ord($in{$i}) );
}
return $out;
}
//use this function to convert binary back to readable ascii text
function bin2asc($in)#syntax - bin2asc("binary to convert");
{
$out = '';
for ($i = 0, $len = strlen($in); $i < $len; $i += 8) {
$out .= chr(bindec(substr($in,$i,8)));
}
return $out;
}
function compressLzw( $input){
$inputArr = str_split( $input, 1);
$w = NULL;
$wc = '';
$dict = array();
$arrOutput = array();
$iPos = 0;
for( $iPos; $iPos<256; $iPos++){
$dict[$iPos] = chr($iPos);
}
foreach( $inputArr as $char ){
$wc = $w . $char;
if( in_array($wc, $dict) ){
$w = $wc;
}else{
$dict[$iPos] = $wc;
$iPos++;
$arrOutput[] = array_search($w, $dict);
$w = $char;
}
}
$arrOutput[] = array_search($w, $dict);
$strBitlength = strlen(decbin($iPos));
$strOutput = str_pad( $strBitlength, 2, "0", STR_PAD_LEFT);
$strBinOutput = '';
foreach( $arrOutput as $index ){
$strBinOutput .= sprintf("%0".$strBitlength."b", $index);
}
$iPadSize = 8 - strlen($strBinOutput)%8;
$strBinOutput = sprintf("%0" . $iPadSize."b", "0") . $strBinOutput;
return $strOutput . strval($iPadSize) . bin2asc( $strBinOutput );
}
function decompressLzw( $input ){
$iBitlength = intval(substr($input, 0, 2));
$iPadLength = intval(substr($input, 2, 1));
$input = substr($input, 3 );
$inputBinary = substr(asc2bin($input), $iPadLength);
$inputArr = str_split( $inputBinary, $iBitlength);
$entry = '';
$dict = array();
$iPos = 0;
for( $iPos; $iPos<256; $iPos++){
$dict[$iPos] = chr($iPos);
}
$w = $output = chr( bindec( array_shift($inputArr) ) );
foreach( $inputArr as $binCode){
$intVal = bindec($binCode);
if( isset($dict[ $intVal ]) ){
$entry = $dict[ $intVal ];
}elseif( $intVal >= $iPos ){
$entry = $w . $w{0};
}else{
die('invalid');
}
$output .= $entry;
$dict[$iPos] = $w . $entry{0};
$iPos++;
$w = $entry;
}
return $output;
}
[/code]