Sorting network-based dynamic Huffman encoding method, apparatus and device

Patent metadata

Field	Value
Publication number	US-11923875-B2
Application number	US-202118260630-A
Country	US
Kind code	B2
Filing date	Dec 30, 2021
Priority date	Jan 7, 2021
Publication date	Mar 5, 2024
Grant date	Mar 5, 2024

Abstract

Provided is a dynamic Huffman encoding method based on a sorting network. Compared with traditional dynamic Huffman coding solutions, the method implements sorting on the basis of the sorting network, therefore the sorting process is not only stable, but also may ensure a stable sorting result; and moreover, sorting steps and related operations are simpler, thereby greatly simplifying the sorting and iteration processes, and thus the sorting efficiency is higher. In addition, the sorting process better facilitates program implementation and transplantation, and implementation of hardware and software may achieve good effects. In addition, the present disclosure further provides a dynamic Huffman coding apparatus and device based on a sorting network, and a readable storage medium, and the technical effects thereof correspond to the technical effects of the above method.

First claim

What is claimed is:

1. A dynamic Huffman encoding method based on a sorting network, wherein the sorting network comprises n stages of sorting modules, n is a positive integer, and the method comprises:
S 1 , acquiring elements to be sorted, and initializing i=1, wherein the elements to be sorted comprise Literal elements and Length elements, the Literal elements are used for describing a number of occurrences of each character in a target text, and the Length elements are used for describing numbers of occurrences of character strings of different length intervals in the target text;
S 2 , in an ith-stage sorting module, generating, by using each of ith-stage sorting units and by means of i times of parallel comparison, a sorting result of 2 i elements to be sorted according to the sorting result of a previous-stage sorting module, so as to obtain the sorting result of the ith-stage sorting module, wherein the ith-stage sorting module comprises n/2 i parallel ith-stage sorting units;
S 3 , judging whether i is less than n, when i is less than n, increasing i by 1 and entering S 2 ; when i is equal to n, determining that the sorting result of the ith-stage sorting module is the sorting result of the elements to be sorted; and
S 4 , constructing a Huffman tree according to the sorting result of the elements to be sorted, and encoding the target text according to the Huffman tree.

2. The method according to claim 1 , wherein before acquiring the elements to be sorted, the method further comprises:
determining the Literal elements and the Length elements according to the target text;
generating padding elements when a number of the Literal elements and a number of the Length elements fall between 2 n-1 and 2 n , so that the total sum of the number of the Literal elements, the number of the Length elements and the number of the padding elements is 2 n ; and
using the Literal elements, the Length elements and the padding elements as the elements to be sorted.

3. The method according to claim 2 , wherein the Literal element and the Length element each comprises m bits, m1 bits represent the number of occurrences of a character or a character string, m2 bits represent that the current element is the Literal element or the Length element, m is a positive integer greater than 2, and m=m1+m2.

4. The method according to claim 3 , wherein the padding element comprises m bits, and each bit being 1.

5. The method according to claim 4 , wherein a value of m being 16.

6. The method according to claim 1 , wherein in the ith-stage sorting module, generating, by using each of ith-stage sorting units and by means of I times of parallel comparison, the sorting result of 2 i elements to be sorted according to the sorting result of the previous-stage sorting module, comprises:
when I is 1, in a first-stage sorting module, sorting, by the first first-stage sorting unit, the first two elements to be sorted, and a sorting process comprises: comparing the first element to be sorted with the second element to be sorted, so as to obtain the sorting result of the two elements to be sorted.

7. The method according to claim 6 , wherein in the ith-stage sorting module, generating, by using each of ith-stage sorting units and by means of i times of parallel comparison, the sorting result of 2 i elements to be sorted according to the sorting result of the previous-stage sorting module, comprises:
when i is 2, in a second-stage sorting module, sorting, by the first second-stage sorting unit, the sorting results of the first two first-stage sorting units in the first-stage sorting module, and the sorting process comprises: comparing the first element to be sorted with the fourth element to be sorted according to the current sorting result, and meanwhile, comparing the second element to be sorted with the third element to be sorted; adjusting the arrangement sequence of the elements to be sorted according to a comparison result; and comparing the first element to be sorted with the second element to be sorted, and meanwhile, comparing the third element to be sorted with the fourth element to be sorted, so as to obtain the sorting result of the four elements to be sorted.

8. A dynamic Huffman coding device based on a sorting network, wherein the sorting network comprises n stages of sorting modules, n is a positive integer, comprising:
a memory, configured to store a computer program; and
a processor, configured to execute the computer program, so as to:
S 1 , acquire elements to be sorted, and initializing i=1, wherein the elements to be sorted comprise Literal elements and Length elements, the Literal elements are used for describing a number of occurrences of each character in a target text, and the Length elements are used for describing numbers of occurrences of character strings of different length intervals in the target text;
S 2 , in an ith-stage sorting module, generate, by using each of ith-stage sorting units and by means of i times of parallel comparison, a sorting result of 2 i elements to be sorted according to the sorting result of a previous-stage sorting module, so as to obtain the sorting result of the ith-stage sorting module, wherein the ith-stage sorting module comprises n/2 i parallel ith-stage sorting units;
S 3 , judge whether i is less than n, when i is less than n, increase i by 1 and enter S 2 ; when i is equal to n, determine that the sorting result of the ith-stage sorting module is the sorting result of the elements to be sorted; and
S 4 , constructe a Huffman tree according to the sorting result of the elements to be sorted, and encode the target text according to the Huffman tree.

9. A computer-readable storage medium, wherein a computer program is stored on the computer-readable storage medium, and the computer program is configured to, when executed by a processor, cause the processor to:
S 1 , acquire elements to be sorted, and initializing i=1, wherein the elements to be sorted comprise Literal elements and Length elements, the Literal elements are used for describing a number of occurrences of each character in a target text, and the Length elements are used for describing numbers of occurrences of character strings of different length intervals in the target text;
S 2 , in an ith-stage sorting module, generate, by using each of ith-stage sorting units and by means of i times of parallel comparison, a sorting result of 2 i elements to be sorted according to the sorting result of a previous-stage sorting module, so as to obtain the sorting result of the ith-stage sorting module, wherein the ith-stage sorting module comprises n/2 i parallel ith-stage sorting units;
S 3 , judge whether i is less than n, when i is less than n, increase i by 1 and enter S 2 ; when i is equal to n, determine that the sorting result of the ith-stage sorting module is the sorting result of the elements to be sorted; and
S 4 , constructe a Huffman tree according to the sorting result of the elements to be sorted, and encode the target text according to the Huffman tree.

10. The computer-readable storage medium according to claim 9 , the computer program is further configured to cause the processor to:
before acquiring the elements to be sorted, determine the Literal elements and the Length elements according to the target text;
generate padding elements when a number of the Literal elements and a number of the Length elements fall between 2 n-1 and 2 n , so that the total sum of the number of the Literal elements, the number of the Length elements and the number of the padding elements is 2 n ; and
use the Literal elements, the Length elements and the padding elements as the elements to be sorted.

Assignees

• Inspur Suzhou Intelligent Technology Co Ltd

Inventors

• Qin Zhen
• Yuan Tao
• Wang Zhen
• Wang Jinfu

Classifications

• H03M7/3077 Primary

  Sorting · CPC title

• H03M7/40 Primary

  Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code · CPC title

• H03M7/6023 Primary

  Parallelization · CPC title

• H03M7/405

  Tree adaptation · CPC title