Computer Science ›› 2019, Vol. 46 ›› Issue (8): 157-162.doi: 10.11896/j.issn.1002-137X.2019.08.026

• Network & Communication • Previous Articles     Next Articles

Improved LZW Prefix Coding Scheme Based on Azimuth Information

HAN Bin, ZHANG Hong-hong, JIANG Hong, DING Yi   

  1. (College of Information Engineering,Southwest University of Science and Technology,Mianyang,Sichuan 621010,China)
  • Received:2018-08-24 Online:2019-08-15 Published:2019-08-15

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: LZW algorithm, Orientation information, Digital signal, Mapping, Coding

CLC Number: 

  • TP301.6
[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.
[1] YU Xue-yong, CHEN Tao. Privacy Protection Offloading Algorithm Based on Virtual Mapping in Edge Computing Scene [J]. Computer Science, 2021, 48(1): 65-71.
[2] QI Shao-hua, XU He-gen, WAN You-wen, FU Hao. Construction of Semantic Mapping in Dynamic Environments [J]. Computer Science, 2020, 47(9): 198-203.
[3] WANG Bing-zhou, WANG Hui-bin, SHEN Jie, ZHANG Li-li. FastSLAM Algorithm Based on Adaptive Fading Unscented Kalman Filter [J]. Computer Science, 2020, 47(9): 213-218.
[4] HAN Xiao-dong, GAO Fei, ZHANG Li-wei. Novel Real-time Algorithm for Critical Path of Linear Network Coding [J]. Computer Science, 2020, 47(9): 232-237.
[5] GAO Fang-yuan, WANG Xiu-mei. Subspace Clustering Method Based on Block Diagonal Representation and Neighbor Constraint [J]. Computer Science, 2020, 47(7): 66-70.
[6] XU Guang-xian, CUI Jun-jie. Anti-eavesdropping Network Coding Based on Quantum GHZ State [J]. Computer Science, 2020, 47(7): 314-321.
[7] NI Xiao-jun, SHE Xu-hao. Improvement of LZW Algorithms for Wireless Sensor Networks [J]. Computer Science, 2020, 47(5): 260-264.
[8] ZHANG Hao, CAI Ying, XIA Hong-ke. RSU-based Assisting Ring Formation Scheme in VANET [J]. Computer Science, 2020, 47(5): 301-305.
[9] WEI De-bin,YANG Peng,YANG Li,SHI Huai-feng. Virtual Network Function Fast Mapping Algorithm over Satellite Network [J]. Computer Science, 2020, 47(3): 248-254.
[10] XI Chen-jing,GAO Yuan-yuan,SHA Nan. Performance Study on Constellation Obfuscation Design Method for Physical Layer Security [J]. Computer Science, 2020, 47(3): 304-311.
[11] CAI Yu-han,XIONG Shu-hua,SUN Wei-heng,Karn PRADEEP,HE Xiao-hai. Video Compression Algorithm Combining Frame Rate Up-conversion with HEVC Standard Based on Motion Vector Refinement [J]. Computer Science, 2020, 47(2): 76-82.
[12] QIAO Bo-wen,LI Jun-hui. Neural Machine Translation Combining Source Semantic Roles [J]. Computer Science, 2020, 47(2): 163-168.
[13] HONG Hai-cheng,CHEN Dan-wei. Replica Dynamic Storage Based on RBEC [J]. Computer Science, 2020, 47(2): 313-319.
[14] JI Ming-xuan, SONG Yu-rong. New Machine Translation Model Based on Logarithmic Position Representation and Self-attention [J]. Computer Science, 2020, 47(11A): 86-91.
[15] QIN Xu-jia, CHEN Guo-fu, SHAN Yang-yang, ZHENG Hong-bo, ZHANG Mei-yu. Streamline Adaptive Color Mapping Enhancement Algorithm for Vector Field Visualization [J]. Computer Science, 2020, 47(11A): 236-240.
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .