Search

Aiming at high real-time performance processing requirements for large amounts of online text data in natural language processing applications, an online word vector model generation method based on incremental Huffman tree merging is proposed. Maintaining the inherited word Huffman tree in existing word vector model unchanged, a new Huffman tree of incoming words is constructed and ensures that there is no leaf node identical to the inherited Huffman tree. Then the Huffman tree is updated by a method of node merging. Thus based on the existing word vector model, each word still has a unique encoding for the calculation of the hierarchical softmax model. Finally, the generation of incremental word vector model is realized by using neural network on the basis of hierarchical softmax model. The experimental results show that the method could realize the word vector model generation online based on incremental learning with faster time and better performance.

A skeleton Huffman tree is a Huffman tree from which all full subtrees of depth h ≥ 1 have been pruned. Skeleton Huffman trees are used to save storage and enhance processing time in several applications such as decoding, compressed pattern matching and wavelet trees for random access. A reduced skeleton tree prunes the skeleton Huffman tree further to an even smaller tree. The resulting more compact trees can be used to further enhance the time and space complexities of the corresponding algorithms. However, it is shown that the straightforward ways of basing the constructions of a skeleton tree as well as that of a reduced skeleton tree on a canonical Huffman tree do not necessarily yield the least number of nodes. New algorithms for achieving such trees are given. [ABSTRACT FROM AUTHOR]

An increasing number of vehicles are now equipped with GPS devices to facilitate fleet management and send their GPS locations continuously, generating a huge volume of trajectory data. Sending and storing such vehicle trajectory data cause sustainable communication and storage overheads. Trajectory data compression becomes a promising way to alleviate overhead issues. However, previous solutions are commonly carried out at the side of the data center after data having been received, thus saving the storage cost only. Here, we bring the idea of mobile edge computing and transfer the computation-intensive data compression task to the mobile devices of drivers. As a result, the trajectory data is reduced at the side of data generators before being sent out; thus, it can lower data communication and storage costs simultaneously. We propose DAVT, an error-bounded trajectory data representation, and a compression framework. Specifically, the trajectory data is reformatted into three parts (i.e., Distance, Acceleration & Velocity, and Time), and three compressors are wisely devised to compress each part. For D and AV parts, a similar Huffman tree-forest structure is exploited to encode data elements effectively, but with quite different rationales. For the T part, the large absolute timestamps are transformed to small time intervals firstly, and different encoding techniques are adopted based on the data quality. We evaluate our proposed system using a large-scale taxi trajectory dataset collected from the city of Beijing, China. Our results show that our compressors outperform other baselines. [ABSTRACT FROM AUTHOR]

To achieve safe and efficient ciphertext retrieval of data in cloud, this paper proposed a scheme of ciphertext index construction and retrieval based on Huffman tree. T le scheme introduced the idea of the Huffman tree structure and its coding into the construction of ciphertext index structure, improved Chinese word segmentation algorithm based on knowledge understanding to extract keywords of plaintext, sorted the search result set through the improved rule of TF-IDF to return the Top-A' results that meet the users’ needs mostly,and added forged nodes of ciphertext index to enhance capabilities of resistance to statistical analysis of the index structure. Through the experimental lest and comparison analysis of performance, it can be concluded that the scheme can improve the efficiency of ciphertext retrieval, which can ensure the security of ciphertext and index simultaneously. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Multi-channel wireless data broadcast is an appropriate approach to disseminate data to a mass number of mobile clients. In this paper, we present a global optimization for multi-channel wireless data broadcast with Alphabetic Huffman Tree (AH-Tree) Indexing scheme, which can deal with skewed access frequencies well. We present three novel designs to reduce the access latency and tuning time of the broadcast system. Firstly, we design a dynamic programming for AH-Tree construction with low time complexity. Compared with traditional Hu-Tucker algorithm in $O(n^k)$ , our algorithm can build a $k$ -ary AH-Tree index in $O(n^2)$ . Next, we depict a new control table design, which eliminates up to 50 percent redundant entries while keeps the searching efficiency. We also theoretically prove that an optimal alphabetic tree has the minimum average tuning time among all tree-based index structures for skewed data broadcast. Thirdly, we design the new index and data allocation algorithms to further reduce the tuning time and access latency. The simulation results validate the effectiveness of our algorithms. In all, our global optimization mechanism can greatly improve the system performance and time efficiency for wireless data broadcast applications. [ABSTRACT FROM AUTHOR]

There exists error accumulation in the multi-classification method, based on support vector machines and decision trees. It tends to decrease classification accuracy and results in a bad classification. With a careful analysis of error accumulation, it proposes a new multi-classification method, based on Huffman Tree and SVM. It divided a multi-classification problem into multiple binary classification problems, and gave classification priority, depending on the dissimilarity. At last, through an experiment with Lecast open source data sets, it verified the effectiveness. The experimental results show that the new method is superior to the traditional multi-classification method in classification speed and classification accuracy. [ABSTRACT FROM AUTHOR]

Abstract: The Huffman tree is a well known concept in data compression discovered by David Huffman in 1952 [7]. A Huffman tree is a binary tree and represents the most efficient binary code for a given alphabet with respect to a distribution of frequency of its characters. In this paper, we associate any Huffman tree of leaves with the point in having as coordinates the length of the paths from the root to every leaf from the left to right. We then study the convex hull, that we call Huffmanhedron, of those points associated with all the possible Huffman trees of leaves. First, we present some basic properties of Huffmanhedron, especially, about its dimensions and its extreme vertices. Next we give a partial linear description of Huffmanhedron which includes in particular a complete characterization of the facet defining inequalities with nonnegative coefficients that are tight at a vertex corresponding to some maximum height Huffman tree (i.e. a Huffman tree of depth ). The latter contains a family of facet defining inequalities in which coefficients follow in some way the law of the Fibonacci sequence. This result shows that the number of facets of Huffmanhedron is at least a factorial of and consequently shows that the facial structure of Huffmanhedron is rather complex. This is quite in contrast with the fact that using the algorithm of Huffman described in [7], one can minimize any linear objective function over the Huffmanhedron in time. We also give two procedures for lifting and facet composition allowing us to derive facet-defining inequalities from the ones in lower dimensions. [Copyright &y& Elsevier]

Abstract: Based on Huffman tree method, we propose a new 2D graphic representation of protein sequence. This representation can completely avoid loss of information in the transfer of data from a protein sequence to its graphic representation. The method consists of two parts. One is about the 0–1 codes of 20 amino acids by Huffman tree with amino acid frequency. The amino acid frequency is defined as the statistical number of an amino acid in the analyzed protein sequences. The other is about the 2D graphic representation of protein sequence based on the 0–1 codes. Then the applications of the method on ten ND5 genes and seven Escherichia coli strains are presented in detail. The results show that the proposed model may provide us with some new sights to understand the evolution patterns determined from protein sequences and complete genomes. [Copyright &y& Elsevier]

Abstract: 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. [Copyright &y& Elsevier]

Abstract: Given a search space , an unknown element and fixed integers and , a -ary -restricted query is of the following form: which one of the set is the in?, where is a partition of and for . The problem of finding from with -ary size-restricted queries is called as a -ary search game with small sets. In this paper, we consider sequential algorithms for the above problem, and establish the minimum number of average-case sequential queries when satisfies the uniform distribution on . [Copyright &y& Elsevier]

Abstract: A well-known kind of binary tree in information theory is Huffman tree. Given any linear objective function f, Huffman has given an algorithm allowing to find an optimal Huffman tree minimizing f. In this paper, we associate to each Huffman point of n nodes, a point in called Huffman point whose components are the length of the path from the root of the tree to each leaf. In this paper, we study the Huffmanhedron, , which is the convex hull of the Huffman points in . In particular, we present a family of facet-defining inequalities for whose coefficients form a Fibonacci sequence. We describe several lifting and composition methods which allow to derive new facet-defining inequalities from existing ones. Finally, we show that these methods together with the Fibonacci family of facet-defining inequalities characterize all facets of non-negative coefficients for containing a deepest Huffman point, i.e. a permutation of the Huffman point . [ABSTRACT FROM AUTHOR]

There were few research works are continuing to increase the performance of Huffman coding. The proposed paper is based on the new technique region based Huffman to increase the performance of the Huffman coding. The proposed technique divides the input file into a number of regions. Huffman codes are obtained for entire file. For each region, the code between the maximum frequency element of that region and maximum frequency element of entire file are interchanged and the symbols of that region are compressed. This is repeated for each region. Then a small variation of the technique is proposed where instead of interchanging the codes of elements, selection of number of region is done by a proposed algorithm. This modified technique eliminates some limitations of previous proposed technique. Comparisons are made among these two variants with classical Huffman technique. [ABSTRACT FROM AUTHOR]

Abstract: The following restricted model of coin-weighing problem is considered: there is a heavier coin in a set of n coins, of which are good coins having the same weight. The test device is a two-arms balance scale and each test-set is of the form with , where is a given integer. We present an optimal sequential algorithm requiring the minimal average cost of weighings when the probability distribution on the coin set is uniform distribution. [Copyright &y& Elsevier]

Abstract: In the partial alphabetic tree problem we are given a multiset of non-negative weights , partitioned into blocks . We want to find a binary tree T where the elements of W reside in its leaves such that if we traverse the leaves from left to right then all leaves of precede all leaves of for every . Furthermore among all such trees, T has to minimize , where is the depth of in T. The partial alphabetic tree problem generalizes the problem of finding a Huffman tree over W (there is only one block) and the problem of finding a minimum cost alphabetic tree over W (each block consists of a single item). This problem arises when we need an optimal binary code for a set of items with known frequencies, such that we have a lexicographic restriction for some of the codewords. Our main result is a pseudo-polynomial time algorithm that finds the optimal tree. Our algorithm runs in time where , , and ( is the golden ratio). In particular the running time is polynomial in case the weights are bounded by a polynomial of n. To bound the running time of our algorithm we prove an upper bound of on the depth of the optimal tree. Our algorithm relies on a solution to what we call the layered Huffman forest problem which is of independent interest. In the layered Huffman forest problem we are given an unordered multiset of weights , and a multiset of integers . We look for a forest F with k trees, , where the weights in W correspond to the leaves of F, that minimizes where is the depth of in its tree plus if . Our algorithm for this problem runs in time. [Copyright &y& Elsevier]

An image layering and confidence analysis based small target detection method in infrared image is proposed. First, a Huffman tree is used to refine the histogram curve, and the valleys of the refined curve are detected automatically. Then, the grey values of the detected valleys are recorded as the segmenting thresholds to stratify the original infrared image. After detecting small abnormal regions in each layer and defining them to be candidate targets, the candidate target set is composed of the candidate targets in all layers. Finally, the abnormality‐based confidence of each candidate target is calculated and sorted. The candidate target with maximum confidence is considered as the real one. The experiments show that the proposed method performs robustly and efficiently. [ABSTRACT FROM AUTHOR]