„Polynomial-Time Construction of Two-Channel Prefix-Free Codes with Given Codeword Lengths“ erscheint auf ITW 2021
Das Paper „Polynomial-Time Construction of Two-Channel Prefix-Free Codes with Given Codeword Lengths“ von Hoover H. F. Yin, Ka Hei Ng, Yu Ting Shing, Russell W. F. Lai und Xishi Wang erscheint auf dem IEEE Information Theory Workshop 2021.
Unten stehend finden Sie die Kurzfassung des Papers in englischer Sprache.
Although n-channel prefix-free codes are natural extensions of their 1-channel counterpart, the extra dimensions greatly increase the complexity of the problem such that most classical results cannot be generalized directly. Recently, a greedy algorithm was developed for deciding if it is possible to construct a 2-channel prefix-free code from a given multiset of codeword lengths. By dropping the information about codeword assignments which are not necessary for the decision problem, the greedy algorithm runs in polynomial time. However, if we naively turn the decision algorithm into a search algorithm (for constructing a prefix-free code) by retaining the information about codeword assignments, the computational complexity becomes exponential. One puzzle left unsolved was that whether the search problem can also be solved in polynomial time. In this paper, we give an affirmative answer to this question by designing a tailor-made data structure and a new lazy evaluation technique.