| In the era of big data when the Internet of Things(IoT)is emerging,data compression performs a significant role in storage and communication.Almost instantaneous variable-to-fixed length(AIVF)code is a subclass of lossless data compression.Specifically,it parses source string into variable-length parsewords which do not obey prefix condition.And then,each parseword will be encoded into a fixed-length codeword.AIVF code can be applied to high throughput compression and achieve competitive decoding speed above GB/s.Also,it can prevent error propagation in decoding.However,the current dictionary construction of optimal AIVF code consumes much time and space.Thus,this dissertation proposes an efficient algorithm to construct optimal AIVF dictionary,or called parse tree.Meanwhile,another important factor in multimedia data transmission is to safeguard the confidentiality of data.The traditional way,which encrypts the compressed bitstream,is not suitable for most IoT devices because of resource limitations.In this dissertation,two lightweight joint compression and encryption schemes are proposed using as little cryptography as possible.The main work of this dissertation is summarized in the following two points:1.An efficient algorithm is proposed to construct optimal AIVF code.Recently,the dictionary construction of optimal AIVF code has been proposed via a dynamic programming algorithm by Dube and Haddad.However,the algorithm has time and node complexity O(AM2)in both single and multiple-tree mode,where A denotes the alphabet size and M denotes the dictionary size.In this dissertation,a more efficient algorithm which based on greedy algorithm is proposed.It contains two steps,the build step and the check step,to construct the dictionary of AIVF code.In particular,the proposed algorithm has time complexity O(M log M)and node complexity O(M)in single-tree mode.Also,it has time complexity O(AM log M)and node complexity O(AM)in multipletree mode.It can be proved that the parse tree based on the proposed technique can maximize the average parseword length.2.Two solutions for joint compression and encryption are proposed.Without reduction in compression ratio,randomness is added to the mapping relationship between parsewords and codewords by pseudo-random bit generators(PRBG).The first solution performs linear transformation on the codewords by PRBG.The second solution generates multiple mapping relationships between parsewords and codewords and chooses a certain one by PRBG.In addition,National Institute of Standards and Technology(NIST)statistical test suite is used to quantify the randomness quality brought by the two solutions. |
