The Experts below are selected from a list of 309 Experts worldwide ranked by ideXlab platform
Eduardo Sany Laber - One of the best experts on this subject based on the ideXlab platform.
-
[en] Prefix CodeS: ALGORITHMS AND BOUNDS
2009Co-Authors: Eduardo Sany LaberAbstract:[pt] Os codigos de Prefixo tem importância fundamental na comprenssao e transmissao de dados. Estes codigos tambem apresentam relacoes com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algoritimos sobre a classe dos codigos de Prefixo. Explicamos teoricamente as boas taxas de compressao observadas para alguns metodos utilizados na pratica. Propomos tambem algoritmos eficientes para construcao de codigos de Prefixo otimos e variantes. Os principais resultados aqui descritos sao os seguintes: - um novo algoritmo paralelo para construcao de codigos de Prefixos otimos: - uma cota superior para a perda de compressao introduzida pela restricao de comprimento nos codigos de Prefixo: - uma cota superior para a perda de compressao introduzida pela restricao de comprimento nos codigos de Prefixo alfabeticos: - um algoritmo aproximativo e linear para construcao de codigos de Prefixo com restricao de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construcao de codigos de Prefixo alfabeticos com restricao de comprimento: - uma nova versao de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer codigos de Prefixo otimos com restricao de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos codigos de Huffmann dinâmicos construidos pelo algoritmo FGK (Faller, Gallanger e Knuth)%%%%[en] The Prefix Codes play an important role in data compression and data communication. These Codes also present relation with search problems. In this thesis, we present new structural and algorithmic results concerning the Prefix Code class. We theoretically explain results related to the high compression rates of some methods that have been used for pratical purposes. We also propose efficient algorthims for constructing optimal Prefix Codes and some variants. The major results are listed below: -a new parallel algorithm for constructing optimal Prefix Codes: -a sharp upper bound for the compression loss introduced due usage of length restricted Prefix Codes: -an upper bound for the compression loss introduced due the usage of length restricted alphabetic Prefix Codes: -an 0(n log n) time approximative algorithm for constructing lenght restricted Prefix Code: -a 0(n log n) time approximative algorithm for constructing lenght restricted alphabetic Prefix Code: -a strongly polinomial version for the WARM-UP algorithm: -a linear time algorithm for recognizing optimal length restricted Prefix Codes: -a proof for Vitter´s conjecture about the perfomance of the Dynamic Huffman Codes constructed by FGK (Faller, Gallager and Knuth) algorithm.
-
Bounding the Inefficiency of Length-Restricted Prefix Codes
Algorithmica, 2001Co-Authors: Ruy Luiz Milidiú, Eduardo Sany LaberAbstract:Abstract. We consider an alphabet Σ= {a 1 ,\ldots,a n } with corresponding symbol probabilities p 1 ,\ldots,p n . For each Prefix Code associated to Σ , let l i be the length of the Codeword associated to a i . The average Code length c is defined by c=\sum i=1 n p i l i . An optimal Prefix Code for Σ is one that minimizes c . An optimal L -restricted Prefix Code is a Prefix Code that minimizes c constrained to l i ≤ L for i=1,\ldots,n . The value of the length restriction L is an integer no smaller than \lceil log n \rceil . Let A be the average length of an optimal Prefix Code for Σ . Also let A L be the average length of an optimal L -restricted Prefix Code for Σ . The average Code length difference ɛ is defined by ɛ=A L -A . Let ψ be the golden ratio 1.618. In this paper we show that ɛ < 1/ψ L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1 when L > \lceil log n \rceil . We also prove the sharp bound ɛ < \lceil log n \rceil -1 , when L = \lceil log n \rceil . By showing the lower bound 1/(ψ L-\lceil\log n\rceil+2+\lceil\log (n/(n-L))\rceil -1) on the maximum value of ɛ , we guarantee that our bound is asymptotically tight in the range \lceil log n \rceil < L ≤ n/2 . When L\geq \lceil log n \rceil +11 , the bound guarantees that ɛ < 0.01 . From a practical point of view, this is a negligible loss of compression efficiency. Furthermore, we present an O(n) time and space 1/ψ L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1 -approximative algorithm to construct L -restricted Prefix Codes, assuming that the given probabilities are already sorted. The results presented in this paper suggest that one can efficiently implement length restricted Prefix Codes, obtaining also very effective Codes.
-
Three space-economical algorithms for calculating minimum-redundancy Prefix Codes
IEEE Transactions on Information Theory, 2001Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum-redundancy Prefix Code problem is to determine, for a given list W=[/spl omega//sub 1/,..., /spl omega//sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/ 2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/ /spl omega//sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,..., m/sub H/], where m/sub l/, for l=1,...,H, denotes the multiplicity of the Codeword length l in L and H is the length of the greatest Codeword. Fortunately, H is proved to be O(min(log(1/p/sub 1/),n)), where p/sub 1/ is the smallest symbol probability, given by /spl omega//sub 1///spl Sigma//sub i=1//sup n/ /spl omega//sub i/. We present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min(H/sup 2/, n)) additional space. On the other hand, E-LazyHuff runs in O(n+nlog(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes, the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during Code calculation, a feature that is very useful in some applications.
-
Linear Time Recognition of Optimal L-Restricted Prefix Codes
Lecture Notes in Computer Science, 2000Co-Authors: Ruy Luiz Milidiú, Eduardo Sany LaberAbstract:Given an alphabet Σ = {a1,...,an} and a corresponding list of weights [w1,...,wn], an optimal Prefix Code is a Prefix Code for Σ that minimizes the weighted length of a Code string, defined to be \(\sum_{i=1}^{n} w_i l_i\), where li is the length of the Codeword assigned to ai. This problem is equivalent to the following problem: given a list of weights [w1,...,wn], find an optimal binary Code tree, that is, a binary tree T that minimizes the weighted path length\(\sum_{i=1}^{n} w_i l_i\), where li is the level of the i-th leaf of T from left to right. If the list of weights is sorted, this problem can be solved in O(n) by one of the efficient implementations of Huffman’s Algorithm [Huf52]. Any tree constructed by Huffman’s Algorithm is called a Huffman tree.
-
Data Compression Conference - Two space-economical algorithms for calculating minimum redundancy Prefix Codes
Proceedings DCC'99 Data Compression Conference (Cat. No. PR00096), 1999Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum redundancy Prefix Code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,...,m/sub H/], where m(l/sub 1/), for l=1,...,H, denotes the multiplicity of the Codeword length l in L and H is the length of the greatest Codeword. Fortunately, H is proved to be O(min{log(1/(p/sub 1/)),n}), where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. We present the F-LazyHuff and the E-LazyHuff algorithms. F-LazyHuff runs in O(n) time but requires O(min{H/sup 2/,n}) additional space. On the other hand, E-LazyHuff runs in O(nlog(n/H)) time, requiring only O(H) additional space. Finally, since our two algorithms have the advantage of not writing at the input buffer during the Code calculation, we discuss some applications where this feature is very useful.
Chingjung Liao - One of the best experts on this subject based on the ideXlab platform.
-
A Prefix Code Matching Parallel Load-Balancing Method for Solution-Adaptive Unstructured Finite Element Graphs on Distributed Memory Multicomputers
The Journal of Supercomputing, 2000Co-Authors: Yeh-ching Chung, Chingjung Liao, Don-lin YangAbstract:In this paper, we propose a Prefix Code matching parallel load-balancing method (PCMPLB) to efficiently deal with the load imbalance of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the PCMPLB method is first to construct a Prefix Code tree for processors. Based on the Prefix Code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves of the Prefix Code tree are reached. We have implemented the PCMPLB method on an SP2 parallel machine and compared its performance with two load-balancing methods, the directed diffusion method and the multilevel diffusion method, and five mapping methods, the AE/ORB method, the AE/MC method, the MLkP method, the PARTY library method, and the JOSTLE-MS method. An unstructured finite element graph Truss was used as a test sample. During the execution, Truss was refined five times. Three criteria, the execution time of mapping/load-balancing methods, the execution time of an application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for an application program, are used for the performance evaluation. The experimental results show that (1) if a mapping method is used for the initial partitioning and this mapping method or a load-balancing method is used in each refinement, the execution time of an application program under a load-balancing method is less than that of the mapping method. (2) The execution time of an application program under the PCMPLB method is less than that of the directed diffusion method and the multilevel diffusion method.
-
A Prefix Code Matching Parallel Load-Balancing Method for Solution-Adaptive Unstructured Finite Element Graphs on Distributed Memory Multicomputers
The Journal of Supercomputing, 2000Co-Authors: Yeh-ching Chung, Chingjung Liao, Don-lin YangAbstract:[[abstract]]In this paper, we propose a Prefix Code matching parallel load-balancing method (PCMPLB) to efficiently deal with the load imbalance of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the PCMPLB method is first to construct a Prefix Code tree for processors. Based on the Prefix Code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves of the Prefix Code tree are reached. We have implemented the PCMPLB method on an SP2 parallel machine and compared its performance with two load-balancing methods, the directed diffusion method and the multilevel diffusion method, and five mapping methods, the AE/ORB method, the AE/MC method, the MLkP method, the PARTY library method, and the JOSTLE-MS method. An unstructured finite element graph Truss was used as a test sample. During the execution, Truss was refined five times. Three criteria, the execution time of mapping/load-balancing methods, the execution time of an application program under different mapping/load-balancing methods, and the speedups achieved by mapping/load-balancing methods for an application program, are used for the performance evaluation. The experimental results show that (1) if a mapping method is used for the initial partitioning and this mapping method or a load-balancing method is used in each refinement, the execution time of an application program under a load-balancing method is less than that of the mapping method. (2) The execution time of an application program under the PCMPLB method is less than that of the directed diffusion method and the multilevel diffusion method.[[fileno]]2030220010025[[department]]資訊工程學
-
a Prefix Code matching parallel load balancing method for solution adaptive unstructured finite element graphs on distributed memory multicomputers
International Conference on Parallel Processing, 1998Co-Authors: Yehching Chun, Chingjung LiaoAbstract:In this paper, we propose a Prefix Code matching parallel load-balancing method (PCMPLB) to efficiently deal with the load unbalancing problems of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the PCMPLB method is first to construct a Prefix Code tree for processors. Based on the Prefix Code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves of the Prefix Code tree are reached. The experimental results show that the execution time of an application program under the PCMPLB method is less than that of the direct diffusion method and the multilevel diffusion method.
-
ICPP - A Prefix Code matching parallel load-balancing method for solution-adaptive unstructured finite element graphs on distributed memory multicomputers
Proceedings. 1998 International Conference on Parallel Processing (Cat. No.98EX205), 1Co-Authors: Yehching Chun, Chingjung LiaoAbstract:In this paper, we propose a Prefix Code matching parallel load-balancing method (PCMPLB) to efficiently deal with the load unbalancing problems of solution-adaptive finite element application programs on distributed memory multicomputers. The main idea of the PCMPLB method is first to construct a Prefix Code tree for processors. Based on the Prefix Code tree, a schedule for performing load transfer among processors can be determined by concurrently and recursively dividing the tree into two subtrees and finding a maximum matching for processors in the two subtrees until the leaves of the Prefix Code tree are reached. The experimental results show that the execution time of an application program under the PCMPLB method is less than that of the direct diffusion method and the multilevel diffusion method.
Ruy Luiz Milidiú - One of the best experts on this subject based on the ideXlab platform.
-
Bounding the Inefficiency of Length-Restricted Prefix Codes
Algorithmica, 2001Co-Authors: Ruy Luiz Milidiú, Eduardo Sany LaberAbstract:Abstract. We consider an alphabet Σ= {a 1 ,\ldots,a n } with corresponding symbol probabilities p 1 ,\ldots,p n . For each Prefix Code associated to Σ , let l i be the length of the Codeword associated to a i . The average Code length c is defined by c=\sum i=1 n p i l i . An optimal Prefix Code for Σ is one that minimizes c . An optimal L -restricted Prefix Code is a Prefix Code that minimizes c constrained to l i ≤ L for i=1,\ldots,n . The value of the length restriction L is an integer no smaller than \lceil log n \rceil . Let A be the average length of an optimal Prefix Code for Σ . Also let A L be the average length of an optimal L -restricted Prefix Code for Σ . The average Code length difference ɛ is defined by ɛ=A L -A . Let ψ be the golden ratio 1.618. In this paper we show that ɛ < 1/ψ L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1 when L > \lceil log n \rceil . We also prove the sharp bound ɛ < \lceil log n \rceil -1 , when L = \lceil log n \rceil . By showing the lower bound 1/(ψ L-\lceil\log n\rceil+2+\lceil\log (n/(n-L))\rceil -1) on the maximum value of ɛ , we guarantee that our bound is asymptotically tight in the range \lceil log n \rceil < L ≤ n/2 . When L\geq \lceil log n \rceil +11 , the bound guarantees that ɛ < 0.01 . From a practical point of view, this is a negligible loss of compression efficiency. Furthermore, we present an O(n) time and space 1/ψ L-\lceil\log (n+\lceil\log n\rceil-L)\rceil-1 -approximative algorithm to construct L -restricted Prefix Codes, assuming that the given probabilities are already sorted. The results presented in this paper suggest that one can efficiently implement length restricted Prefix Codes, obtaining also very effective Codes.
-
Three space-economical algorithms for calculating minimum-redundancy Prefix Codes
IEEE Transactions on Information Theory, 2001Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum-redundancy Prefix Code problem is to determine, for a given list W=[/spl omega//sub 1/,..., /spl omega//sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/ 2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/ /spl omega//sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,..., m/sub H/], where m/sub l/, for l=1,...,H, denotes the multiplicity of the Codeword length l in L and H is the length of the greatest Codeword. Fortunately, H is proved to be O(min(log(1/p/sub 1/),n)), where p/sub 1/ is the smallest symbol probability, given by /spl omega//sub 1///spl Sigma//sub i=1//sup n/ /spl omega//sub i/. We present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min(H/sup 2/, n)) additional space. On the other hand, E-LazyHuff runs in O(n+nlog(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes, the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during Code calculation, a feature that is very useful in some applications.
-
Linear Time Recognition of Optimal L-Restricted Prefix Codes
Lecture Notes in Computer Science, 2000Co-Authors: Ruy Luiz Milidiú, Eduardo Sany LaberAbstract:Given an alphabet Σ = {a1,...,an} and a corresponding list of weights [w1,...,wn], an optimal Prefix Code is a Prefix Code for Σ that minimizes the weighted length of a Code string, defined to be \(\sum_{i=1}^{n} w_i l_i\), where li is the length of the Codeword assigned to ai. This problem is equivalent to the following problem: given a list of weights [w1,...,wn], find an optimal binary Code tree, that is, a binary tree T that minimizes the weighted path length\(\sum_{i=1}^{n} w_i l_i\), where li is the level of the i-th leaf of T from left to right. If the list of weights is sorted, this problem can be solved in O(n) by one of the efficient implementations of Huffman’s Algorithm [Huf52]. Any tree constructed by Huffman’s Algorithm is called a Huffman tree.
-
Data Compression Conference - Two space-economical algorithms for calculating minimum redundancy Prefix Codes
Proceedings DCC'99 Data Compression Conference (Cat. No. PR00096), 1999Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum redundancy Prefix Code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,...,m/sub H/], where m(l/sub 1/), for l=1,...,H, denotes the multiplicity of the Codeword length l in L and H is the length of the greatest Codeword. Fortunately, H is proved to be O(min{log(1/(p/sub 1/)),n}), where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. We present the F-LazyHuff and the E-LazyHuff algorithms. F-LazyHuff runs in O(n) time but requires O(min{H/sup 2/,n}) additional space. On the other hand, E-LazyHuff runs in O(nlog(n/H)) time, requiring only O(H) additional space. Finally, since our two algorithms have the advantage of not writing at the input buffer during the Code calculation, we discuss some applications where this feature is very useful.
-
SPIRE/CRIWG - A fast and space-economical algorithm for calculating minimum redundancy Prefix Codes
6th International Symposium on String Processing and Information Retrieval. 5th International Workshop on Groupware (Cat. No.PR00268), 1Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum redundancy Prefix Code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. With the optimal list of Codeword lengths, an optimal canonical Code can be easily obtained. If W is already sorted, then this optimal Code can also be represented by the list M=[m/sub 1/,...,m/sub H/], where m/sub l/, for l=1,...,H, denotes the number of Codewords with length l and H is the length of the longest Codeword. Fortunately, H is proved to be O(min{log(1/p/sub 1/),n}, where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. The E-LazyHuff algorithm uses a lazy approach to calculate optimal Codes in O(nlog(n/H)) time, requiring only O(H) additional space. In addition, the input weights are not destroyed during the Code calculation. We propose a new technique, which we call homogenization, that can be used to improve the time efficiency of algorithms for constructing optimal Prefix Codes. Next, we introduce the Best LazyHuff algorithm (B-LazyHuff) as an application of this technique. B-LazyHuff is an O(n)-time variation of the E-LazyHuff algorithm. It also requires O(H) additional space and does not destroy the input data.
Hiroki Arimura - One of the best experts on this subject based on the ideXlab platform.
-
CPM - Sparse and truncated suffix trees on variable-length Codes
Combinatorial Pattern Matching, 2011Co-Authors: Takashi Uemura, Hiroki ArimuraAbstract:The sparse suffix trees (SST), introduced by (Karkkainen and Ukkonen, COCOON 1996), is the suffix tree for a subset of all suffixes of an input text T of length n. In this paper, we study a special case that an input string is a sequence of k Codewords drawn from a regular Prefix Code Δ ⊆ Σ+ recognized by a finite automaton, and index points locate on the Code boundaries. In this case, we present an online algorithm that constructs the sparse suffix tree for an input string T on any variable-length regular Prefix Code, called the Code suffix tree (CST), in O(n + m) time and O(k) additional space for a fixed base alphabet Σ, where m is the size of an automaton for Δ. Furthermore, we present a modified algorithm for l-truncated version of Code suffix trees that runs in the same time and space complexities. Hence, these results generalize the previous results (Inenaga and Takeda, CPM 2006) for word suffix trees and (Na, Apostolico, Iliopoulos, and Park, Theor. Comp. Sci., 304, 2003) for truncated suffix trees on arbitrary variable-length regular Prefix Codes, such as Huffman Codes and multi-byte Codes (e.g. UTF-8).
Artur Alves Pessoa - One of the best experts on this subject based on the ideXlab platform.
-
A note on the construction of error detecting/correcting Prefix Codes
Information Processing Letters, 2008Co-Authors: Artur Alves PessoaAbstract:A k-bit Hamming Prefix Code is a binary Code with the following property: for any Codeword x and any Prefix y of another Codeword, both x and y having the same length, the Hamming distance between x and y is at least k. Given an alphabet A=[a"1,...,a"n] with corresponding probabilities [p"1,...,p"n], the k-bit Hamming Prefix Code problem is to find a k-bit Hamming Prefix Code for A with minimum average Codeword length @?"i"="1^np"[email protected]?"i, where @?"i is the length of the Codeword assigned to a"i. In this paper, we propose a general approximation algorithm for the k-bit Hamming Prefix Code problem. Let @a"k be an O(r"k(n))-time algorithm for calculating fixed-length Codes with Hamming distances k whose Codewords are d"k(n) bits longer than @?log"[email protected]?. Our algorithm uses @a"k to calculate a k-bit Hamming Prefix Code in O(r"k(n)+nlogn) time with an additive error of at most O(d"k(n)+log^*n) bits with respect to the optimal Prefix Code for A, under reasonable assumptions on the function d"k.
-
Three space-economical algorithms for calculating minimum-redundancy Prefix Codes
IEEE Transactions on Information Theory, 2001Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum-redundancy Prefix Code problem is to determine, for a given list W=[/spl omega//sub 1/,..., /spl omega//sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/ 2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/ /spl omega//sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,..., m/sub H/], where m/sub l/, for l=1,...,H, denotes the multiplicity of the Codeword length l in L and H is the length of the greatest Codeword. Fortunately, H is proved to be O(min(log(1/p/sub 1/),n)), where p/sub 1/ is the smallest symbol probability, given by /spl omega//sub 1///spl Sigma//sub i=1//sup n/ /spl omega//sub i/. We present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min(H/sup 2/, n)) additional space. On the other hand, E-LazyHuff runs in O(n+nlog(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes, the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during Code calculation, a feature that is very useful in some applications.
-
Data Compression Conference - Two space-economical algorithms for calculating minimum redundancy Prefix Codes
Proceedings DCC'99 Data Compression Conference (Cat. No. PR00096), 1999Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum redundancy Prefix Code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M=[m/sub 1/,...,m/sub H/], where m(l/sub 1/), for l=1,...,H, denotes the multiplicity of the Codeword length l in L and H is the length of the greatest Codeword. Fortunately, H is proved to be O(min{log(1/(p/sub 1/)),n}), where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. We present the F-LazyHuff and the E-LazyHuff algorithms. F-LazyHuff runs in O(n) time but requires O(min{H/sup 2/,n}) additional space. On the other hand, E-LazyHuff runs in O(nlog(n/H)) time, requiring only O(H) additional space. Finally, since our two algorithms have the advantage of not writing at the input buffer during the Code calculation, we discuss some applications where this feature is very useful.
-
SPIRE/CRIWG - A fast and space-economical algorithm for calculating minimum redundancy Prefix Codes
6th International Symposium on String Processing and Information Retrieval. 5th International Workshop on Groupware (Cat. No.PR00268), 1Co-Authors: Ruy Luiz Milidiú, Artur Alves Pessoa, Eduardo Sany LaberAbstract:The minimum redundancy Prefix Code problem is to determine, for a given list W=[w/sub 1/,...,w/sub n/] of n positive symbol weights, a list L=[l/sub 1/,...,l/sub n/] of n corresponding integer Codeword lengths such that /spl Sigma//sub i=1//sup n/2/sup -li//spl les/1 and /spl Sigma//sub i=1//sup n/w/sub i/l/sub i/ is minimized. With the optimal list of Codeword lengths, an optimal canonical Code can be easily obtained. If W is already sorted, then this optimal Code can also be represented by the list M=[m/sub 1/,...,m/sub H/], where m/sub l/, for l=1,...,H, denotes the number of Codewords with length l and H is the length of the longest Codeword. Fortunately, H is proved to be O(min{log(1/p/sub 1/),n}, where p/sub 1/ is the smallest symbol probability, given by w/sub 1///spl Sigma//sub i=1//sup n/w/sub i/. The E-LazyHuff algorithm uses a lazy approach to calculate optimal Codes in O(nlog(n/H)) time, requiring only O(H) additional space. In addition, the input weights are not destroyed during the Code calculation. We propose a new technique, which we call homogenization, that can be used to improve the time efficiency of algorithms for constructing optimal Prefix Codes. Next, we introduce the Best LazyHuff algorithm (B-LazyHuff) as an application of this technique. B-LazyHuff is an O(n)-time variation of the E-LazyHuff algorithm. It also requires O(H) additional space and does not destroy the input data.