LZW压缩算法

PHP实现的LZW压缩算法

1. /**
2. * @link http://code.google.com/p/php-lzw/
3. * @author Jakub Vrana, http://php.vrana.cz/
4. * @copyright 2009 Jakub Vrana
5. * @license http://www.apache.org/licenses/LICENSE-2.0 Apache License, Version 2.0
6. */
8. /** LZW compression
9. * @param string data to compress
10. * @return string binary data
11. */
12. function lzw_compress($string) {
13. // compression
14. $dictionary = array_flip(range("\0", "\xFF"));
15. $word = "";
16. $codes = array();
17. for ($i=0; $i $x = $string[$i];
18. if (strlen($x) && isset($dictionary[$word . $x])) {
19. $word .= $x;
20. } elseif ($i) {
21. $codes[] = $dictionary[$word];
22. $dictionary[$word . $x] = count($dictionary);
23. $word = $x;
24. }
25. }
27. // convert codes to binary string
28. $dictionary_count = 256;
29. $bits = 8; // ceil(log($dictionary_count, 2))
30. $return = "";
31. $rest = 0;
32. $rest_length = 0;
33. foreach ($codes as $code) {
34. $rest = ($rest $rest_length += $bits;
35. $dictionary_count++;
36. if ($dictionary_count > (1 $bits++;
37. }
38. while ($rest_length > 7) {
39. $rest_length -= 8;
40. $return .= chr($rest >> $rest_length);
41. $rest &= (1 }
42. }
43. return $return . ($rest_length ? chr($rest }
45. /** LZW decompression
46. * @param string compressed binary data
47. * @return string original data
48. */
49. function lzw_decompress($binary) {
50. // convert binary string to codes
51. $dictionary_count = 256;
52. $bits = 8; // ceil(log($dictionary_count, 2))
53. $codes = array();
54. $rest = 0;
55. $rest_length = 0;
56. for ($i=0; $i $rest = ($rest $rest_length += 8;
57. if ($rest_length >= $bits) {
58. $rest_length -= $bits;
59. $codes[] = $rest >> $rest_length;
60. $rest &= (1 $dictionary_count++;
61. if ($dictionary_count > (1 $bits++;
62. }
63. }
64. }
66. // decompression
67. $dictionary = range("\0", "\xFF");
68. $return = "";
69. foreach ($codes as $i => $code) {
70. $element = $dictionary[$code];
71. if (!isset($element)) {
72. $element = $word . $word[0];
73. }
74. $return .= $element;
75. if ($i) {
76. $dictionary[] = $word . $element[0];
77. }
78. $word = $element;
79. }
80. return $return;
81. }
82. $data = "";
83. $compressed = lzw_compress($data);
84. var_dump($data === lzw_decompress($compressed));
85. ?>

复制代码