Community Learn Tools Library Leisure
search
English
Home > Backend Development > PHP Tutorial > LZW compression algorithm

LZW compression algorithm

WBOY
Release： 2016-07-25 09:07:59
Original
1639 people have browsed it
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("", "xFF"));
  15. $word = "";
  16. $codes = array();
  17. for ($i=0; $i <= strlen($string); $i++) {
  18. $x = $string[$i];
  19. if (strlen($x) && isset($dictionary[$word . $x])) {
  20. $word .= $x;
  21. } elseif ($i) {
  22. $codes[] = $dictionary[$word];
  23. $dictionary[$word . $x] = count($dictionary);
  24. $word = $x;
  25. }
  26. }
  28. // convert codes to binary string
  29. $dictionary_count = 256;
  30. $bits = 8; // ceil(log($dictionary_count, 2))
  31. $return = "";
  32. $rest = 0;
  33. $rest_length = 0;
  34. foreach ($codes as $code) {
  35. $rest = ($rest << $bits) + $code;
  36. $rest_length += $bits;
  37. $dictionary_count++;
  38. if ($dictionary_count > (1 << $bits)) {
  39. $bits++;
  40. }
  41. while ($rest_length > 7) {
  42. $rest_length -= 8;
  43. $return .= chr($rest >> $rest_length);
  44. $rest &= (1 << $rest_length) - 1;
  45. }
  46. }
  47. return $return . ($rest_length ? chr($rest << (8 - $rest_length)) : "");
  48. }
  50. /**LZW decompression
  51. * @param string compressed binary data
  52. * @return string original data
  53. */
  54. function lzw_decompress($binary) {
  55. // convert binary string to codes
  56. $dictionary_count = 256;
  57. $bits = 8; // ceil(log($dictionary_count, 2))
  58. $codes = array();
  59. $rest = 0;
  60. $rest_length = 0;
  61. for ($i=0; $i < strlen($binary); $i++) {
  62. $rest = ($rest << 8) + ord($binary[$i]);
  63. $rest_length += 8;
  64. if ($rest_length >= $bits) {
  65. $rest_length -= $bits;
  66. $codes[] = $rest >> $rest_length;
  67. $rest &= (1 << $rest_length) - 1;
  68. $dictionary_count++;
  69. if ($dictionary_count > (1 << $bits)) {
  70. $bits++;
  71. }
  72. }
  73. }
  75. // decompression
  76. $dictionary = range("", "xFF");
  77. $return = "";
  78. foreach ($codes as $i => $code) {
  79. $element = $dictionary[$code];
  80. if (!isset($element)) {
  81. $element = $word . $word[0];
  82. }
  83. $return .= $element;
  84. if ($i) {
  85. $dictionary[] = $word . $element[0];
  86. }
  87. $word = $element;
  88. }
  89. return $return;
  90. }
  91. $data = "";
  92. $compressed = lzw_compress($data);
  93. var_dump($data === lzw_decompress($compressed));
  94. ?>
复制代码


Related labels：
LZW压缩算法
source：php.cn
Previous article：Simple, calculator Next article：Broad and profound lunar calendar algorithm
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
React Three Fiber: Why are my scroll events lagging? In ReactThreeFiber, I have a React component that generates a sprite that I want to persis...
From 2024-04-06 13:39:24
0
1
410
Create scalable signposts using HTML, CSS and SVG I want to make a button in the form of a signpost (a rectangle with a tip). _______|\|____...
From 2024-03-31 14:45:14
0
1
294
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template