In this paper we investigate the semigroup structure of the syntactic monoid Syn(C+) of C+, the semigroup generated by a maximal prefix code C for which C+ is a single class of the syntactic congruence. In articular w...
详细信息
In this paper we investigate the semigroup structure of the syntactic monoid Syn(C+) of C+, the semigroup generated by a maximal prefix code C for which C+ is a single class of the syntactic congruence. In articular we prove that for such a prefixcode C, either Syn(C+) is a group or it is isomorphic to a special type of submonoid of G x T(R) where G is a group and T(R) is the full transformation semigroup on a set R with more than one element. From this description we conclude that Syn(C+) has a kernel J which is a right group. We further investigate separately the case when J is a right aero semigroup and the case when J is a group.
Novel synchronous coding schemes are introduced and relationships between optimal synchronous codes and Huffman codes are discussed. Although the problem of existence of the optimal synchronous codes has not yet resol...
详细信息
Novel synchronous coding schemes are introduced and relationships between optimal synchronous codes and Huffman codes are discussed. Although the problem of existence of the optimal synchronous codes has not yet resolved, we show that any synchronous code can be considered as an optimal synchronous code for some information source alphabet. In other words, synchronous codes are almost optimal and, therefore, are regarded as near optimal with respect to average code word length. It is shown that there always exist optimal synchronous codes for the information source alphabets with a dyadic probability distribution. Comparing with the Huffman coding, the synchronous coding is used not only for statistical modeling but also for dictionary methods. It is also good at using in a large information retrieval system like the Huffman coding. Moreover, from the viewpoint of computational difficulty, it is proven that breaking a synchronous or an optimal synchronous code is NP-complete.
Existence of the optimal prefixcodes is shown in this paper. Relationship between the optimal prefixcode and the Huffman code is also discussed. We prove that all Huffman codes are optimal prefixcodes and conversel...
详细信息
Existence of the optimal prefixcodes is shown in this paper. Relationship between the optimal prefixcode and the Huffman code is also discussed. We prove that all Huffman codes are optimal prefixcodes and conversely optimal prefixcodes need not be Huffman codes. Especially, the problem of whether the optimal prefixcode has to be maximal is presented. Although for information source alphabets of being not greater than four letters we show that an optimal prefixcode must be maximal, it remains to be an open problem in general. As seen from Huffman codes, optimal prefixcodes are used not only for statistical modeling but also for dictionary methods. Moreover, it is obtained that the complexity of breaking an optimal prefixcode is NP-complete from the viewpoint of computational difficulty.
Several properties of the products of finite maximalprefix, maximal biprefix, semaphore, synchronous, maximal infix and maximal outfix codes are discussed respectively, We show that, for two nonempty subsets X and Y ...
详细信息
Several properties of the products of finite maximalprefix, maximal biprefix, semaphore, synchronous, maximal infix and maximal outfix codes are discussed respectively, We show that, for two nonempty subsets X and Y of A* such that the product XY being thin, if XY is a maximal biprefixcode, then X and Y are maximal biprefixcodes. Also, it is shown that, for two finite nonempty subsets X and Y of A* such that the product XY being unambiguous, if XY is a semaphore code then X and Y are semaphore codes. Finally, two open problems to the product of finite semaphore and maximal infix codes are presented.
In this paper,we exhibit a free monoid containing all prefixcodes in connection with the sets of i-th powers of primitive words for all i≥*** extends two results given by Shyr and Tsai in 1998 at the same time.
In this paper,we exhibit a free monoid containing all prefixcodes in connection with the sets of i-th powers of primitive words for all i≥*** extends two results given by Shyr and Tsai in 1998 at the same time.
暂无评论