LZW算法PHP实现方法 lzw_decompress php
2023-09-14 08:59:33 时间
LZW算法简介
字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.
根据 Lempel-Ziv-Welch Encoding ,简称 LZW 的压缩算法,用任何一种语言来实现它.
LZW压缩算法[1]的基本概念:LZW压缩有三个重要的对象:数据流(CharStream)、编码流(CodeStream)和编译表(String Table)。在编码时,数据流是输入对象(文本文件的据序列),编码流就是输出对象(经过压缩运算的编码数据);在解码时,编码流则是输入对象,数据流 是输出对象;而编译表是在编码和解码时都须要用借助的对象。字符(Character):最基础的数据元素,在文本文件中就是一个字节,在光栅数据中就是 一个像素的颜色在指定的颜色列表中的索引值;字符串(String):由几个连续的字符组成; 前缀(Prefix):也是一个字符串,不过通常用在另一个字符的前面,而且它的长度可以为0;根(Root):一个长度的字符串;编码(Code):一 个数字,按照固定长度(编码长度)从编码流中取出,编译表的映射值;图案:一个字符串,按不定长度从数据流中读出,映射到编译表条目.
LZW压缩算法的基本原理:提取原始文本文件数据中的不同字符,基于这些字符创建一个编译表,然后用编译表中的字符的索引来替代原始文本文件数据中 的相应字符,减少原始数据大小。看起来和调色板图象的实现原理差不多,但是应该注意到的是,我们这里的编译表不是事先创建好的,而是根据原始文件数据动态 创建的,解码时还要从已编码的数据中还原出原来的编译表.
<?php /** * @link http://code.google.com/p/php-lzw/ * @author Jakub Vrana, http://php.vrana.cz/ * @copyright 2009 Jakub Vrana * @license http://www.apache.org/licenses/LICENSE-2.0 Apache License, Version 2.0 */ /** LZW compression * @param string data to compress * @return string binary data */ function lzw_compress($string) { // compression $dictionary = array_flip(range("\0", "\xFF")); $word = ""; $codes = array(); for ($i=0; $i <= strlen($string); $i++) { $x = $string[$i]; if (strlen($x) && isset($dictionary[$word . $x])) { $word .= $x; } elseif ($i) { $codes[] = $dictionary[$word]; $dictionary[$word . $x] = count($dictionary); $word = $x; } } // convert codes to binary string $dictionary_count = 256; $bits = 8; // ceil(log($dictionary_count, 2)) $return = ""; $rest = 0; $rest_length = 0; foreach ($codes as $code) { $rest = ($rest << $bits) + $code; $rest_length += $bits; $dictionary_count++; if ($dictionary_count > (1 << $bits)) { $bits++; } while ($rest_length > 7) { $rest_length -= 8; $return .= chr($rest >> $rest_length); $rest &= (1 << $rest_length) - 1; } } return $return . ($rest_length ? chr($rest << (8 - $rest_length)) : ""); } /** LZW decompression * @param string compressed binary data * @return string original data */ function lzw_decompress($binary) { // convert binary string to codes $dictionary_count = 256; $bits = 8; // ceil(log($dictionary_count, 2)) $codes = array(); $rest = 0; $rest_length = 0; for ($i=0; $i < strlen($binary); $i++) { $rest = ($rest << 8) + ord($binary[$i]); $rest_length += 8; if ($rest_length >= $bits) { $rest_length -= $bits; $codes[] = $rest >> $rest_length; $rest &= (1 << $rest_length) - 1; $dictionary_count++; if ($dictionary_count > (1 << $bits)) { $bits++; } } } // decompression $dictionary = range("\0", "\xFF"); $return = ""; foreach ($codes as $i => $code) { $element = $dictionary[$code]; if (!isset($element)) { $element = $word . $word[0]; } $return .= $element; if ($i) { $dictionary[] = $word . $element[0]; } $word = $element; } return $return; }
相关文章
- PHP时区设置相差8小时间程序与php.ini配置方法
- PHP常见面试题_php算法面试题及答案
- php替换字符串中,PHP 替换字符串中的一些字符方法介绍
- 笛卡尔积 php,PHP笛卡尔积实现算法示例
- 没想到吧,PHP 中在类的外部也可以调用私有方法!
- PHP 加解密方法大全详解编程语言
- Linux 查看 PHP 版本的方法(linux查php版本)
- Linux切换PHP版本:快速而安全的方法(linux切换php版本)
- PHP连接MySQL的实现方法(php怎么连接mysql)
- 分钟结合简单快捷:PHP跟MySQL搭配,5分钟搞定!(php与mysql5)
- PHP连接MSSQL库的方法(php链接mssql)
- 使用PHP操作Redis:简单灵活的方法(php如何使用redis)
- 数据PHP实现MySQL数据导出的实现方法(php导出mysql)
- PHP读取Linux文件的方法(php读取linux文件)
- 如何使用PHP重启Linux服务:简易教程(php重启linux服务)
- PHP管理MSSQL的方法探索(Php管理mssql)
- 用PHP进行MySQL功能测试(php 测试mysql)
- PHP图片上传至MySQL:实现快速可靠的数据存储(php图片上传mysql)
- linux下php加装mssql模块的方法
- php数据结构算法(PHP描述)简单选择排序simpleselectionsort
- PHP中防止直接访问或查看或下载config.php文件的方法
- PHP数据类型之整数类型、浮点数的介绍
- php操作xml
- PHP批量上传图片的具体实现方法介绍.
- php数组操作之键名比较与差集、交集赋值的方法
- php利用cookies实现购物车的方法
- PHP基于php_imagick_st-Q8.dll实现JPG合成GIF图片的方法
- js+php实现静态页面实时调用用户登陆状态的方法