基于方位信息的改进LZW前缀编码方案

doi:10.11896/j.issn.1002-137X.2019.08.026

摘要/Abstract

摘要： LZW压缩算法在实时采集与无线传输中具有重要应用价值,一般采用采集-压缩-传输的工作模式,该模式下的较高压缩比可极大降低对无线传输的压力。但在采集速度较快、数据传输带宽较低、硬件资源受限的情况下,在对采样点概率分布较均匀的数字信号进行压缩时,易出现压缩率不高或采集速度与压缩速度不匹配的问题。对此,文中提出了基于方位信息的改进LZW前缀编码方案。该改进压缩算法基于压缩比因子对采样点进行映射操作,使其能够标识后面相邻采样点的压缩情况,然后通过采样点间的方位信息,缩短采样点的码长,实现对采样点数据的压缩。实验表明,与原LZW压缩算法相比,该改进算法在不增加算法复杂度和硬件存储空间的条件下,压缩比可提高26.25%,证明了该算法在采集系统中的有效性。

关键词: LZW算法, 编码, 方位信息, 数字信号, 映射

Abstract: LZW compression algorithm has important application value in real-time acquisition and wireless transmission.Generally,it adopts the acquisition-compression-transmission working mode,and high compression ratio in this mode can greatly reduce the pressure on wireless transmission.But in the case of fast acquisition speed,low data transmission bandwidth and limited hardware resources,it can easily lead to problems that the compression rate is not high or the speed of acquisition is mismatched when compressing the digital signal which has a sampling point of uniform probability distribution.To this end,this paper proposed an improved LZW prefix encoding scheme based on azimuth information.Firstly,the improved compression algorithm maps the sampling points based on compression ratio factor,so that it can identify the compression condition of adjacent sampling points.Secondly,through the azimuth information between the sampling points,the code length of the sampling points is shortened,so the data of the sampling points is compressed.Experiments show that,compared with the original LZW compression algorithm,the improved algorithm can increase the compression ratio by 26.25% without increasing the complexity and hardware storage space.Therefore,the effectiveness of the algorithm in the acquisition system was proved

Key words: Coding, Digital signal, LZW algorithm, Mapping, Orientation information

中图分类号:

TP301.6

韩宾, 张红红, 江虹, 丁一. 基于方位信息的改进LZW前缀编码方案[J]. 计算机科学, 2019, 46(8): 157-162. https://doi.org/10.11896/j.issn.1002-137X.2019.08.026

HAN Bin, ZHANG Hong-hong, JIANG Hong, DING Yi. Improved LZW Prefix Coding Scheme Based on Azimuth Information[J]. Computer Science, 2019, 46(8): 157-162. https://doi.org/10.11896/j.issn.1002-137X.2019.08.026

参考文献

[1]XIE R Y,HAI B Z.Lossless Compression Algorithm Based on Hybrid Coding of Adaptive Huffman and Golomb-Rice for WSN[J].Computer Engineering,2016,42(7):86-93.(in Chinese) 解瑞云,海本斋.基于自适应霍夫曼和Golomb-Rice混合编码的WSN无损压缩算法[J].计算机工程,2016,42(7):86-93.
[2]SAYOOD K.数据压缩导论(4版)[M].贾洪峰,译.北京:人民邮电出版社,2014.
[3]HUFFMAN D A.A for the Construction of Minimum-redundancy Codes[J].Proceedings of the IRE,1952,40(9):1098-1101.
[4]AL-OKAILY,ALMARRI A,YAMI B A,et al.Toward a Better compression for DNA Sequences Using huffman Encoding [J].Journal of Computational Biology,2017,24(4):280-288.
[5]ZIV J,LEMPEL A.A Universal Algorithm for Sequential Data Compression[J].IEEE Transactions on Information Theory,1977,23(3):337-443.
[6]ZIV J,LEMPEL A.Compression of Individual Sequences via Variable-rate Coding[J].IEEE Transactions on Information Theory,1978,24(5):530-536.
[7]CHEN Q H,CHEN X S,HAN D L.Compression on algorithm LZW on Chinese text[J].Computer Engineering and Application,2014,50(3):112-116.(in Chinese) 陈庆辉,陈小松,韩德良.中文文本压缩的LZW算法[J].计算机工程与应用,2014,50(3):112-116.
[8]WANG H G,ZHANG P L,WU D H,et al.Lossless compression of slowly varying signals based on dynamic LZW and arithmetic coding[J].Application Research of Computers,2015,32(9):2742-2756.(in Chinese) 王怀光,张培林,吴定海,等.基于动态LZW与算术编码的缓变信号压缩[J].计算机应用研究,2015,32(9):2742-2756.
[9]TRABUCO M H,COSTA M V C,et al.S-EMG Signal Com- pression in One-Dimensional and Two-Dimensional Approaches [J].IEEE Journal of Biomedical and Health Informatics,2018,22(4):1104-1113.
[10]SANGEETHA M,BETTY P,KUMAR G S N.A Biometric Iris Image Compression using LZW and Hybrid LZW Coding Algorithm [C]∥2017 International Conference on Innovations in Information,Embedded and Communication Systems (ICIIECS).Coimbatore,India:IEEE Press,2017:75-81.
[11]LI T J,ZHAO T D,NHO M,et al.AN ovel RLE & LZW for Bit-Stream Compression[C]∥2016 13th IEEE International Conference on Solid-State and Integrated Circuit Technology (ICSICT).Hangzhou,China:IEEE Conferences,2016:1600-1602.
[12]GAO F,SUN C J,SHAO Q L,et al.Lossless compression of hyperspectral images based on k-mean clustering and conventional recursive least-squares[J].Journal of Electronics & Information Technology,2016,38(11):2709-2714.(in Chinese) 高放,孙长建,邵庆龙,等.基于 K-均值聚类和传统递归最小二乘法的高光谱图像无损压缩[J].电子与信息学报,2016,38(11):2709-2714.
[13]NANDI U,MANDAL J K.A Compression Technique Based on optimality of LZW Code(OLZW)[C]∥Proceedings of the 3rd International Conference on Computer and Communication Technology.Washington D.C.,USA:IEEE Press,2012:166-170.
[14]XU D W,WANG Y D,JIA L M,et al.Compression Algorithm of Road Traffic Spatial Data Based on LZW Encoding[J].Journal of Advanced Transportation,2017,16(2):1-13.
[15]MARTIN T,MARKETA T.Data reduction for Boolean matrix factorization algorithms based on formal concept analysis [J].Knowledge-based Systems,2018,158(15):75-80.
[16]YAN H Z,XU B G,SHI D J,et al.Prefix Encoding Optimization and Application of Lossless Compression Algorithm LZW[J].Computer Engineering,2017,43(3):299-303.(in Chinese) 鄢海舟,胥布工,石东江,等.无损压缩算法LZW前缀编码优化及应用[J].计算机工程,2017,43(3):299-303.
[17]XU J P,LIU L,LI W,et al.A New Lossless Compression Algorithm Based on Array Configuration Speedup Model[J].Journal of Electronics & Information Technology,2018,40(6):1492-1498.(in Chinese) 徐金甫,刘露,李伟,等.一种基于阵列匹配加速比模型的无损压缩算法[J].电子与信息学报,2018,40(6):1492-1498.
[18]LI C Z,YU J B,ZHANG M,et al.Obfuscation tool for mobile apps based on Huffman and LZW encoding[J].Journal of Software,2017,28(9):2264-2280.(in Chinese) 李承泽,於剑波,张淼,等.一种基于 Huffman 和 LZW 编码的移动应用混淆方法[J].软件学报,2017,28(9):2264-2280.
[19]TUAMA A Y,MOHAMED M A,MUHAMMED A,et al.A new compression algorithm for small data communication in wireless sensor network [J].International Journal of Sensor Networks,2017,25(3):163-175.
[20]LIU Y Q,GONG S R.A Sort-once and Dynamic Encoding (sode) Based Huffman Coding Algorithm[J].Computer Applications and Software,2009,26(12):86-89.(in Chinese) 刘燕清,龚声蓉.基于一次排序动态编码的Huffman编码算法[J].计算机应用与软件,2009,26(12):86-89.
[21]FILATOV G,BAUWENS B,KERTÉSZ-FARKAS A.lzw-Kernel:fast kernel utilizing variable length code blocks from lzwcompressors for protein sequence classification[J].Bioinforma-tics,2018,34(19):3281-3288.

相关文章 15

[1]	刘鑫, 王珺, 宋巧凤, 刘家豪. 一种基于AAE的协同多播主动缓存方案 Collaborative Multicast Proactive Caching Scheme Based on AAE 计算机科学, 2022, 49(9): 260-267. https://doi.org/10.11896/jsjkx.210800019
[2]	王冠宇, 钟婷, 冯宇, 周帆. 基于矢量量化编码的协同过滤推荐方法 Collaborative Filtering Recommendation Method Based on Vector Quantization Coding 计算机科学, 2022, 49(9): 48-54. https://doi.org/10.11896/jsjkx.210700109
[3]	姜梦函, 李邵梅, 郑洪浩, 张建朋. 基于改进位置编码的谣言检测模型 Rumor Detection Model Based on Improved Position Embedding 计算机科学, 2022, 49(8): 330-335. https://doi.org/10.11896/jsjkx.210600046
[4]	胡艳羽, 赵龙, 董祥军. 一种用于癌症分类的两阶段深度特征选择提取算法 Two-stage Deep Feature Selection Extraction Algorithm for Cancer Classification 计算机科学, 2022, 49(7): 73-78. https://doi.org/10.11896/jsjkx.210500092
[5]	张颖涛, 张杰, 张睿, 张文强. 全局信息引导的真实图像风格迁移 Photorealistic Style Transfer Guided by Global Information 计算机科学, 2022, 49(7): 100-105. https://doi.org/10.11896/jsjkx.210600036
[6]	刘月红, 牛少华, 神显豪. 基于卷积神经网络的虚拟现实视频帧内预测编码 Virtual Reality Video Intraframe Prediction Coding Based on Convolutional Neural Network 计算机科学, 2022, 49(7): 127-131. https://doi.org/10.11896/jsjkx.211100179
[7]	杜航原, 李铎, 王文剑. 一种面向电商网络的异常用户检测方法 Method for Abnormal Users Detection Oriented to E-commerce Network 计算机科学, 2022, 49(7): 170-178. https://doi.org/10.11896/jsjkx.210600092
[8]	郁舒昊, 周辉, 叶春杨, 王太正. SDFA:基于多特征融合的船舶轨迹聚类方法研究 SDFA:Study on Ship Trajectory Clustering Method Based on Multi-feature Fusion 计算机科学, 2022, 49(6A): 256-260. https://doi.org/10.11896/jsjkx.211100253
[9]	杨桃雨, 徐媛媛, 谭增洁. 面向6G的全景视频片划分优化编码算法 Tile Partition Optimized Omnidirectional Video Coding for 6G Network 计算机科学, 2022, 49(6): 66-72. https://doi.org/10.11896/jsjkx.220400034
[10]	陈章辉, 熊贇. 基于解耦-检索-生成的图像风格化描述生成模型 Stylized Image Captioning Model Based on Disentangle-Retrieve-Generate 计算机科学, 2022, 49(6): 180-186. https://doi.org/10.11896/jsjkx.211100129
[11]	冯雁, 王蕊聪. 基于量子傅里叶变换求和的量子投票协议 Quantum Voting Protocol Based on Quantum Fourier Transform Summation 计算机科学, 2022, 49(5): 311-317. https://doi.org/10.11896/jsjkx.210300058
[12]	蒋锐, 徐姗姗, 徐友云. 一种新的基于子连接结构的混合预编码算法 New Hybrid Precoding Algorithm Based on Sub-connected Structure 计算机科学, 2022, 49(5): 256-261. https://doi.org/10.11896/jsjkx.210300138
[13]	韩洁, 陈俊芬, 李艳, 湛泽聪. 基于自注意力的自监督深度聚类算法 Self-supervised Deep Clustering Algorithm Based on Self-attention 计算机科学, 2022, 49(3): 134-143. https://doi.org/10.11896/jsjkx.210100001
[14]	武玉坤, 李伟, 倪敏雅, 许志骋. 单类支持向量机融合深度自编码器的异常检测模型 Anomaly Detection Model Based on One-class Support Vector Machine Fused Deep Auto-encoder 计算机科学, 2022, 49(3): 144-151. https://doi.org/10.11896/jsjkx.210100142
[15]	瞿中, 陈雯. 基于空洞卷积和多特征融合的混凝土路面裂缝检测 Concrete Pavement Crack Detection Based on Dilated Convolution and Multi-features Fusion 计算机科学, 2022, 49(3): 192-196. https://doi.org/10.11896/jsjkx.210100164

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed