Search

The continuous growth of traffic in the telecommunication networks has motivated the search for optimal source codes that can achieve high percentages of compression of the information to be transmitted. However, the compression rates are limited in the practice for the type of messages to encode. For this reason, new techniques have been developed in order to improve the compression rates of the traditional algorithms. In particular, source coding techniques based on computational intelligence algorithms are being studied lately. Hence, this paper proposes a new source coding technique for text compression based on two stages: the initial stage uses a deep neural network, called Text Embedding Neural Network, and the second stage uses a Canonical Huffman Code. The deep neural network increases the compression rate by controlling the level of syntax loss allowed in each message through a single adjustable parameter. This combination is able to reduce the size of the transmitted messages up to 30% with relation to only use traditional source coding algorithms.

Recently proposed real number systems like Posits and Elias codes make use of tapered accuracy resulting from variable-length coding of exponents and significands. Several quite different interpretations of these number systems have been provided, though most often these rely on some combination of fixed- and variable-length codes for exponent and significand. We provide a new perspective on these number systems that unifies known representations while suggesting new ones. Our framework is based on multibit radix representations that encode the exponent in unary, the leading nonzero digit in a variablelength code, and the remaining digits in fixed-length binary code. We show how Posits, the various Elias codes, and ieee 754 like representations can be expressed in this framework. Moreover, we show that Posits and the Elias γ and δ codes represent the leading digit using the canonical Huffman code for a probability distribution given by Benford’s law, which governs the probability of leading digits. We further show that Posits correspond to the use of a fixed radix while Elias δ and ω codes are based on simple sequences of increasing radix. Our approach provides for an intuitive and uniform framework for representing numbers that reveals a visual mapping between codewords and the binary representation of real numbers obscured by prior frameworks. This new interpretation suggests a generalization of Posits and other number systems and provides simple rules for designing information-theoretically optimal codes.

Given a file T, we suggest a data structure based on pruning a Huffman shaped Wavelet tree (WT) according to the underlying skeleton Huffman tree that enables direct access to the i-th element of T. This pruned WT is especially designed to support faster random access and save memory storage, at the price of less effective rank and select operations, as compared to the original Huffman shaped WT. The savings are significant only if the underlying alphabet is large enough. We give empirical evidence that when memory storage is of main concern, our suggested data structure generally outperforms other direct access techniques such as those due to Klekci, dacs and sampling, with a slowdown as compared to dacs and fixed length encoding. A Huffman shaped Wavelet tree is pruned by means of a Skeleton Huffman tree.The data structure supports faster random access and saves memory storage.It enables an enhanced rank and select operation rather than an exhaustive one.

The paper focuses on an engineering perspective of Data Mining, specifically using it as a tool for efficient data compression. Huffman encoding, a lossless compression technique is refined to incorporate frequent itemset mining, an important phase of Association Rule Mining. The research exploits the principle of assigning shorter codes to frequently occurring patterns(sequence of characters) in relation to single character based code assignment approach of Huffman encoding. Simulation results indicate the benefits of the Data Mining approach to compression, resulting in an efficient data compression algorithm.

The well-known Huffman algorithm is an elegant approach to solve the basic problem of finding the optimal code among those with Kraft sums smaller than or equal to 1. In this paper, an extended problem is investigated, where the Kraft sum of the usable codes is limited to a given real number $\gamma $ , $0 . Unlike the case $\gamma =1$ (i.e., Huffman coding), for $\gamma , the Kraft sum of the optimal code is not necessarily equal to $\gamma $ . However, we show that the Kraft sum of the optimal code lies in a finite set of rational numbers which depend on the value of $\gamma $ . This motivates us to first devise a recursive algorithm to obtain the optimal codelengths with Kraft sum equal to $\gamma '$ , where $\gamma '$ has a finite binary representation and $0 . To do so, the set of $N$ -tuple codelength vectors with a specific Kraft sum $\gamma '$ is characterized. The binary representation of $\gamma $ plays a fundamental role in all problems that arise for $\gamma .

This paper presents a new code compression method where we merge the Huffman algorithm with the formation of patterns of blocks, which are found into the dictionary. We seek two consecutive blocks in two levels, one of them into compressed code and the other related to uncompressed code. We have used simulation with SimpleScalar and programs from MiBench. Our proposal has achieved a compression rate of 34.5% and 7% improvement in code compression when compared to the Huffman traditional method.

A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem., Article, IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES. E98A(6):1189-1196 (2015)

With the development of multimedia network and computer technology, Canonical Huffman Code hybrid compression algorithm has been widely used, improving image processing technology rapidly. As an important subset of the Huffman algorithm, Canonical Huffman Code solves many shortcomings of the Huffman algorithm. The Canonical Huffman Code can be coded based on the coded bit length. So that the output of the code table is greatly reduced, and the coding process no longer needs a binary tree structure. At the same time, memory footprint is also reduced significantly because the speed of coding is increasing. In this paper, we use the optimized bubble sort algorithm and Canonical Huffman Code algorithm. In the case of using a small amount of FPGA hardware resources and ensuring a minimum coding variance, a comparable clock frequency can be made.

The increase in the size of the data used in natural language processing activities brings with it time and space constraints. Thus, it is important to both store and access data efficiently. This study includes experiments for storing the term-document index, which will be used in a natural language processing project, effectively in memory. For this purpose, the indexed data is compressed using Run-Length coding and then Huffman coding algorithm. Compression experiments have been conducted with new versions of Huffman Coding which are arranged in a structure suitable for indexing data used in the study. The results were compared with the results of commonly used compression tools and the results turned out to be successful.

This paper proposes a steganography algorithm based on MP3 linbits bit of Huffman codeword by analyzing the structure of MP3 bitstream and the characteristics of the linbits of MP3 encoding. Experimental results show that the proposed algorithm not only has very high embedding capacity and keeps transparency, but also has low computational complexity and has good real-time performance for embedding and extraction.

Double Weight (DW) code families are constructed with different algorithms and fixed value of users at basic code matrix. A single code construction algorithm is proposed for DW code families in which, number of users for basic code matrix depends on the code weight and on a constant value. Mapping is used to provide the greater number of users. Affect of basic matrix (used in mapping) on Bit Error Rate (BER) and code length is analyzed. The properties of proposed code construction algorithm are easy code construction, any positive integer value of weight is used for code construction, design of different code set by varying size of basic matrix. Ex-OR function is used in balanced detection technique at receiver. Numerical results are calculated using MATLAB.

Binary AIFV codes, which can attain better compression rate than Huffman codes, uses two code trees that may have incomplete internal nodes, and source symbols are assigned to some internal nodes in addition to leaves. Although the code trees of Huffman codes, which are full binary trees, are well studied, the AIFV code trees have not been yet studied in detail. In this paper, we show that there exists a bijection between binary AIFV code trees and Schroder paths, and give two coding schemes to represent Schroder paths. The first one is a fixed length coding scheme, which has O(n2) time-complexity. The second one is a variable length coding scheme using a simple AIFV code. The latter attains O(n) time-complexity, but the coding rate has loss less than 4.1% of the optimal coding rate.

In this paper, we focus on the use of quaternary tree instead of binary tree to speed up the decoding time for Huffman codes. It is usually difficult to achieve a balance between speed and memory usage using variable-length binary Huffman code. Quaternary tree is used here to produce optimal codeword that speeds up the way of searching. We analyzed the performance of our algorithms with the Huffman-based techniques in terms of decoding speed and compression ratio. The proposed decoding algorithm outperforms the Huffman-based techniques in terms of speed while the compression performance remains almost same.

This paper proposes a novel and generic Huffman code table HCT transform and a simple parallel Huffman decoding method. Codes of the original HCT are left-aligned, reordered in value, and partitioned into sub-bands. Two kinds of modification to the codes are introduced in order to reduce the number of sub-bands. The Huffman decoder can be implemented with a minimized size of single LUT, and the parallel decoding can be completed easily, at a constant rate of up to one code per cycle. An example of MP3 decoder and AAC decoder has been designed to demonstrate the efficiency of the proposed method. Copyright © 2014 John Wiley & Sons, Ltd.

An MPEG-2 AAC Huffman decoding method based on the fixed length compacted codeword tables, where each codeword can contain multiple number of Huffman codes, was proposed. The proposed method enhances the searching efficiency by finding multiple symbols in a single search, i.e., a direct memory reading of the compacted codeword table. The memory usage is significantly saved by separately handling the Huffman codes that exceed the length of the compacted codewords. The trade-off relation between the computational complexity and the amount of memory usage was analytically derived to find the proper codeword length of the compacted codewords for the design of MPEG-2 AAC decoder. To validate the proposed algorithm, its performance was experimentally evaluated with an implemented MPEG-2 AAC decoder. The results showed that the computational complexity of the proposed method is reduced to 54% of that of the most up-to-date method.

A Reed-Solomon code construction that avoids or excludes particular symbols in a linear Reed-Solomon code is presented. The resulting code, from our symbol avoidance construction, has the same or better error-correcting capabilities compared to the original Reed-Solomon code, but with reduced efficiency in terms of rate. The codebook of the new code is a subset of the original Reed-Solomon code and the code may no longer be linear. We also present computer search results for the bound on the number of symbols that can be avoided, and we make an attempt to find an expression for the bound. Such a code, by symbol avoidance, can be well suited to a number of applications, some of which include markers for synchronization, frequency hopping signatures, and pulse position modulation.

The performance of optimal prefix-free encoding for memoryless sources with a large alphabet size is studied. It is shown that the redundancy of the Huffman code for almost all sources with a large alphabet size n is very close to that of the average distribution of the monotone sources with n symbols. This value lies between 0.02873 and 0.02877 bit for sufficiently large n.

According to analysis of manufacturing enterprise coding requirements, Visual flexible coding system (VFCS) is proposed based on code classification theory. It has four function modules: code structure design, code segment & bit design, visual coding and interpreting, code query. Firstly, code rules are expressed by extendable XML format as data structure. Secondly, code design is regulated into two stages: code structure design and code segment design, so as to realize separation of code structure logical and contents. finally, code segment structure information is described as graphic nodes, using interactive graphics drawing for visual modeling, finite state machine algorithm are used implementing code structure interpreter.

Individuals with severe motor impairments commonly enter text using a single binary switch and symbol scanning methods. We present a new scanning method – Huffman scanning – which uses Huffman coding to select the symbols to highlight during scanning, thus minimizing the expected bits per symbol. With our method, the user can select the intended symbol even after switch activation errors. We describe two varieties of Huffman scanning – synchronous and asynchronous – and present experimental results, demonstrating speedups over row/column and linear scanning.

Digital rights management (DRM) system is a promising technique to allow copyrighted content to be commercialized in digital format without the risk of revenue loss due to piracy. However, traditional DRMs are achieved with individual function modules of cryptography and watermarking. Therefore, all digital contents are temporarily disclosed in perfect condition via decryption process in the user-side risking illegal redistribution. This paper describes the basic idea of a novel DRM method composed of an incomplete cryptography using invariant Huffman code length feature and the user identification mechanism to control the quality of digital contents. The proposed incomplete cryptography consists of two processes: the incomplete encoding and the incomplete decoding. These processes are presented by randomly selecting the coefficients that belong to the same category or different category of Huffman code. In our scheme, the copyright information is embedded into the decoded content during the decoding process, and the size of digital contents are invariant during the process. Experimental results with simulation confirmed that the modified codes are compatible with standard JPEG format, and revealed the proposed method to be suitable for DRM in the network distribution system.

Article, Formalized Mathematics. 21(2): 133-143 (2013)

In order to determine how suboptimal the Shannon code is, one should compare its performance with that of the optimal code, i.e., the corresponding Huffman code, in some sense. It is well known that in the worst case the redundancy of both the Shannon and Huffman codes can be arbitrarily close to 1. Beyond this worst case viewpoint, very little is known. In this paper, we compare the performance of these codes from an average point of view. The redundancy is considered as a random variable on the set of all sources with n symbols and its average is evaluated. It is shown that the average redundancy of the Shannon code is very close to 0.5 bits, whereas the average redundancy of the Huffman code is less than n-1(1+ln n)+0.086 bits . It is also proven that the variance of the redundancy of the Shannon code tends to zero as n increases. Therefore, for sources with alphabet size n, the redundancy of the Shannon code is approximately 0.5 bits with probability approaching 1 as n→ ∞.

A compression technique for image is proposed that is SPIHT algorithm based. Encoding of wavelet transformed quantized image is done using variants of Huffman coding. Comparisons are made among the binary un-coded SPIHT, SPIHT with Huffman coding, the proposed technique and its modified variant which show that the proposed techniques offer better PSNRs maintaining the same compression rates. But, the encoding time of the proposed techniques are slightly high.

Huffman coding [11] is a most popular technique for generating prefix-free codes [7, 10]. It is an efficient algorithm in the field of source coding. It produces the lowest possible number of code symbols of a single source symbol [1]. Huffman coding is a most widely used lossless compression technique [2]. However, there are some limitations that arise in Huffman coding [20, 21]. This method produces a code of few bits for a symbol having high probability of occurrence and large number of bits for a symbol having low probability of occurrence [3]. Instead of this, in Double Huffman Coding when the code word of the symbol has been generated it will be compressed on binary basis. Through this technique a better result be achieved. In this paper we discussed the technique of Huffman Coding and Double Huffman coding and compare their performance analysis.

We propose directive-based automatic code generation for a multiple-precision code from a C code with double precision. The multiple-precision code uses the GNU Multiple Precision Arithmetic Library (GMP). Our code generation functions can be separated into binary operations by automatically creating a temporary variable, transforming C mathematical functions into corresponding GMP functions, and managing functions that return a double-precision value. Our proposed system enables users to check the accuracy dependency of many algorithms by adding a few directives to C codes with double precision.

File fragmentation proves to be a major challenge for the majority of file carving techniques. Following the works of Simson Garfinkel, Nasir Memon and other authors we seek to find a technique to identify digital fragments (clusters or sectors) of JPEG-files on the digital storage medium or at least sort all the fragments of the storage based on their probability of being the part of JPEG-file from the most probable to the least probable. This paper offers the technique of identifying clusters of JPEG-files on the storage medium based on binary patterns and the experimental results of an attempt to build a similar technique for sector identifying.

In order to familiarize and comprehend the learning of Huffman algorithm in a simpler way, we have implemented Huffman algorithm in Julia language which can be visualized in an interactive platform called IJulia supported by Jupyter and it creates a learning platform that increases the understanding of the coding technique for students. It involves a set of commands that are understandable and familiar to the user. Data compression is an essential requirement for lossless data transmission. Message bits are encoded in the transmitter end so as to avoid errors and redundancy during the transmission of information. Huffman code is a prefix type code which compresses the message bits by knowing the frequency of occurrence of each character or probability of each symbol. A Huffman/binary tree is formed based on the occurrence of the symbols and symbols are then encoded. Huffman algorithm implements bottom-up approach. Each symbol encoded with the Huffman tree logic is decodable. Each encoded information can be decoded by tracing from the top of the tree to the required symbol. This paper introduces the implementation of this algorithm using Julia programming language supported by Jupyter platform. This encoding algorithm is the most efficient way of compressing data.

Code compression technique is used for the reduction of codes to allow transportation of digital data from the transmitter (source) to the receiver (destination). These fixed length codes are converted into variable length codes having varied number of bits. The Huffman coding technique is found to be an optimal solution of transportation of data. It generally follows the Lossless Compression technique where symbols in encoded data are converted into a binary symbol and this precomputed text availed is further divided into blocks having variable lengths and condensed under efficient algorithm encoding procedure using code words having limited value. To increase the compression ratio these code words could be reused for encoding different compatible blocks. An Android app is been created to portray this technique for the ease understanding.

Cryptography is a technique by which the stored and transferred data in a particular form can be comprehended and processed by only those, who it is intended for. In the modern era, cryptography is most often associated with the deception of the plaintext into a cipher text using a process called Encryption then back to the original plaintext using a process called Decryption. Strong cryptography refers to those cryptographic systems or components that provide considerable immunity to cryptanalysis. The potency of any cryptographic algorithm is solely dependent on the strength of the key used. This paper aims at improving the strength of the key by making use of modified Huffman Code which is a special kind of prefix code which is optimal in nature and is prevalently used for lossless data compression. The outcome of Huffman code is a code of variable length which can be effectively used encoding a source character. The aforementioned concept makes use of the Blowfish algorithm for encryption and is implemented using Java.

While dealing with large data array required in various applications, the memory required for the data storage and data transfer of that bulk data becomes difficult. If the array size can be reduced without losing the data, the problem of storage and data transfer can be avoided. In this paper, a Huffman Coding based data compression algorithm is proposed and tested in MATLAB environment which will significantly reduce the size of one dimensional data array. Though the algorithm is tested with number array only, the algorithm can be extended to be applied with character array with slight modification.

In this paper, we study the redundancy of Huffman codes. In particular, we consider sources for which the probability of one of the source symbols is known. We prove a conjecture of Ye and Yeung regarding the upper bound on the redundancy of such Huffman codes, which yields in a tight upper bound. We also derive a tight lower bound for the redundancy under the same assumption. We further apply the method introduced in this paper to other related problems. It is shown that several other previously known bounds with different constraints follow immediately from our results.

In this paper, the comparative studies of Adaptive Region Based Huffman compression techniques are done. All these techniques use a region formation algorithm that is also discussed. This algorithm is used to form regions whose size is adjusted depending on the ASCII value difference of elements in the file. One of the techniques is Size Adaptive Region Based Huffman Compression (SARBH) where Huffman codes for entire file are obtained after formation of regions to encode elements of the files. Another technique known as Size Adaptive Region Based Huffman Compression with code interchanging (SARBHI) where interchanging of codes are done between the maximum frequency element of a region and maximum frequency element of entire file before elements of that region are compressed. Another variation of the technique is Size Adaptive Region Based Huffman Compression with selective code interchanging (SARBHS) where region wise interchanging of code is done based on an additional condition. Comparisons in terms of compression ratios and compression times are made among these three techniques and also with Region Based Huffman compression technique and classical Huffman technique. The proposed techniques offer better rates of compression for most of the files. Among these techniques, SARBHS is more effective for all most all types of files.

This paper focuses on the time efficiency of Huffman decoding. In this paper, we utilize numerical interpretation to speed up the decoding process. The proposed algorithm firstly transforms the given Huffman tree into a recursion Huffman tree. Then, with the help of the recursion Huffman tree, the algorithm has the possibility to decode more than one symbol at a time if the minimum code length is less than or equal to half of the width of the processing unit. When the minimum code length is larger than the half of the width of the processing unit, the proposed method can still increase the average symbols decoded in one table access (thus speeding up the decoding time). In fact, the experimental results of the test files show that the average number of decoded symbols at one time for the proposed method ranges from 1.91 to 2.13 when the processing unit is 10. The experimental comparisons show that, compared to the conventional binary tree search method and the level-compressed Huffman decoding method, the decoding time of the proposed method is a great improvement.

The Shannon code is a very simple suboptimal scheme for computing prefix-free codelengths for a given memoryless source. A recursive version of the well-known Shannon code (RSh) is investigated in this paper. It has a redundancy which never exceeds that of the Shannon code. Unlike the Huffman code, the RSh code and its variations can be directly applied to sources with an infinitely countable alphabet. The average redundancy, taken over the set of all n-tuple distributions, is considered as a criterion for code comparisons. For n>;40, the average redundancy is approximately 0.14 bits for the RSh code, compared to approximately 0.5 and 0.03 bits for the Shannon and Huffman codes, respectively. For large n, a constrained version of the RSh code, called CRSh, has an average redundancy of only 0.07 bits for unsorted symbol probabilities. If the symbol probabilities are sorted in descending order, then a very simple modification of the RSh algorithm results in a code which is near-optimal from the average redundancy point of view.

In this paper we propose an efficient approach to the compressed string matching problem on Huffman encoded texts, based on the BOYER-MOORE strategy. Once a candidate valid shift has been located, a subsequent verification phase checks whether the shift is codeword aligned by taking advantage of the skeleton tree data structure. Our approach leads to algorithms that exhibit a sublinear behavior on the average, as shown by extensive experimentation.

Huffman tree is also called the optimal binary tree, is a kind of weighted shortest path length of the binary tree; Huffman coding is a coding method, which is used for a lossless data compression entropy coding ( right encoding ) optimal coding method. The realization of Huffman tree visualization is of great significance, this paper uses the object-oriented method, using a complete binary tree of Huffman tree visualization, visual image display of the Huffman coding process.

Encryption is one of the fundamental technologies that is used in the security of multimedia data. Unlike ordinary computer applications, multimedia applications generate large amount of data that has to be processed in real time. This work investigates the problem of efficient multimedia data encryption. A scheme known as the Randomized Huffman Table scheme was recently proposed to achieve encryption along with compression. Though this scheme has several advantages it cannot overcome the chosen plaintext attack. An enhancement of this Huffman scheme is proposed in this work which essentially overcomes the attack and improves the security. The proposed encryption approach consists of two modules. The first module is the Randomized Huffman Table module, the output of which is fed to the second XOR module to enhance the performance. Security analysis shows that the proposed scheme can withstand the chosen plaintext attack. The efficiency and security of the proposed scheme makes it an ideal choice for real time secure multimedia applications.

The adaptive Huffman coding with a window of limited distinct symbols is proposed. The window buffer is used to store a specified number of distinct symbols most recently processed. The total number of symbols within the window may vary, but number of distinct symbols does not exceed a specified value. The adaptive Huffman tree is constructed based on the probability distribution of symbols within the window. Then, a variant of the proposed method is introduced. The proposed variant uses two windows. A small primary window buffer is used to store the most recently processed symbols. A comparatively large secondary window buffer is used to store more past processed symbols. The two separate Huffman tree are constructed based on the probabilities of symbols within the two windows. A symbol is encoded using first Huffman tree if it is found in the first window. Otherwise, the symbol is encoded using second Huffman tree if it is found in the second window. The first proposed technique comparatively offers better results than its counterpart for most of the file type. The performance of the second proposed technique is also close to the other techniques.

1. ABSTRACT In information age, sending the data from one end to another end need lot of space as well as time. Data compression is a technique to compress the information source (e.g. a data file, a speech signal, an image, or a video signal) in poss ible few numbers of bits. One of the major factors that influence the Data Compression technique is the procedure to encode the source data and space required for encoded data. There are many data compressions methods which are used for data compression an d out of which Huffman is mostly used for same. Huffman algorithms have two ranges static as well as adaptive. Static Huffman algorithm is a technique that encoded the data in two passes. In first pass it requires to calculate the frequency of each symbol and in second pass it constructs the Huffman tree. Adaptive Huffman algorithm is expanded on Huffman algorithm that constructs the Huffman tree but take more space than Static Huffman algorithm. This paper introduces a new data compression Algorithm which is based on Huffman coding. This algorithm not only reduces the number of pass but also reduce the storage space in compare to adaptive Huffman algorithm and comparable to static.

JPEG coder is still the most attractive compression scheme for still image. Using Huffman coding makes the JPEG coder very sensitive to communication error. In this paper we propose a simple modification to JPEG coder by using reversible variable length code designed for the DC coefficients of each block. The results show great improvement in error resilience in a binary symmetric channel transmission with an average reduction of 5---10% in compression ratio.