Apparatus for data compression and data decompression

• US 5,717,393 A
• Filed: 07/19/1996
• Issued: 02/10/1998
• Est. Priority Date: 02/08/1996
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Murashita, Kimitaka, Okada, Yoshiyuki, Yoshida, Shigeru, Nakano, Yasuhiko, Tokuyo, Masanaga
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): KOST, JASON L
• Application Number:
  US08/684,045
• Time in Patent Office: 571 Days
• Field of Search: 341/50, 341/51, 341/61, 341/65, 341/67, 341/87, 341/106, 341/107
• US Class Current: 341/50
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

The present invention provides a plurality of code tables such as a high-usage code table and a low-usage code table in an entropy coding unit, and transforms a block-sorted last character string from a block-sorting transforming unit into an MTF code string in an MTF transforming unit. The entropy coding unit switches the code tables at a discontinuous part of the MTF code string to perform entropy coding. In addition, the present invention stores reference lists, whose number is equal to the number of kinds of used characters, in a reference list memory. The MTF transforming unit selects a reference list corresponding to a first character of the block-sorted character string to perform an MTF transformation.

Claims

1. An apparatus for data compression comprising:

a block-sorting transforming unit generating a new two-dimensional character matrix with rotating a character string in a block by a number of times equal to a number of characters in the block, the block which is obtained through dividing input data of a string into predetermined size of blocks, sorting rows in the matrix lexicographically, picking up last characters in the matrix in a sorted order, and outputting them as a block-sorted character string;

a move-to-front (hereinafter;

MTF) transforming unit having a reference list including all of characters composing said block-sorted character string, transforming each character of said block-sorted character string from a first character in turn into a code showing a registered position on said reference list, subsequently transforming a next character after moving the transformed character to the head of the reference list, transforming said block-sorted character string into an intermediate code string showing registered positions on said reference list, and outputting the intermediate code; and

an entropy coding unit having a plurality of code tables corresponding to a change of an input character string, and applying entropy coding to the intermediate code inputted from said MTF transforming unit with using the plurality of code table.

2. An apparatus for data compression according to claim 1, wherein said entropy coding unit has two kinds of switching timing for said plurality of code tables, a first switching timing when a discontinuous part is detected with a first character of the present block-sorted character string changing from one of the previous block-sorted character string, and a second switching timing when a number of processed blocks having the same first character reaches at the predetermined number after detection of said discontinuous part.

3. An apparatus for data compression according to claim 2, wherein said entropy coding unit has said plurality of code tables, a first code table where bit lengths assigned to high-usage characters and low-usage ones are greatly different, and a second code table where bit lengths assigned to high-usage characters and low-usage ones are not so different, and wherein, at said first timing when said discontinuous part is detected, said first code table is switched to said second code table, and, at said second timing when a number of processed blocks reaches at a predetermined number after detection of the discontinuous part, said second code table is switched to said first code table.

4. An apparatus for data compression according to claim 3, wherein, regarding n blocks having identical first characters of said block-sorted character strings, said entropy coding unit changes a number of blocks processed during switching to the second code table after detection of a discontinuous part and switching to the first code table, applies entropy coding, calculates a total amount of codes, and decides said number of switched blocks, at which a minimum total amount of codes is obtained, as an optimum value of the number of processed blocks with which said second switching timing is decided.

5. An apparatus for data compression according to claim 4, wherein said entropy coding unit decides said optimum value of the number of switched blocks, while the unit transforms an input string, and uses the value to switch code tables for subsequent blocks.

6. An apparatus for data compression according to claim 4, wherein said entropy coding unit decides said optimum value of the number of switched blocks beforehand, while the unit transforms an input string composed of typical data, and uses the value to switch code tables for all blocks.

7. An apparatus for data compression according to claim 3, wherein said entropy coding unit provides a plurality of said first code tables corresponding to combination of a plurality of characters starting with the head of said block-sorted character string, and, in case the unit switches the second code table to the first code table after detecting said discontinuous part, the unit selects a first code table corresponding to the combination of a plurality of characters starting with the head of a block-sorted character string.

8. In an apparatus for data decompression:

generating a new two-dimensional character matrix with rotating a character string in a block by a number of times equal to a number of characters in the block, the block which is obtained through dividing input data of a string into predetermined size of blocks, sorting rows in the matrix lexicographically, picking up last characters of the two-dimensional character matrix in a sorted order, and outputting them as a block-sorted character string;

having a reference list including all of characters composing said block-sorted character string, transforming each character of said block-sorted character string from a first character in turn into a code showing a registered position on said reference list, subsequently transforming a next character after moving the transformed character to the head of the reference list, transforming said block-sorted character string into an intermediate code string showing registered positions on said reference list, and outputting the intermediate code; and

having a plurality of code tables corresponding to a change of an input character string, applying entropy coding to the intermediate code inputted from said MTF transforming unit, and decompressing said entropy-coded code string into an original character string, the apparatus for data decompression comprising;

an entropy decoding unit having a plurality of code tables corresponding to a change of an input string, inputting said entropy-coded code string and decoding the string into said intermediate code string;

an MTF inverse transforming unit restoring the intermediate code to said block-sorted character string using said reference list; and

a block-sorting inverse transforming unit restoring to an original character string the block-sorted character string transformed by said MTF inverse transforming unit.

9. An apparatus for data compression according to claim 8, wherein said entropy decoding unit has two kinds of switching timing for code tables, a first switching timing when a discontinuous part is detected with a first character of a present block-sorted character string changing from one of a previous block-sorted character string, and a second switching timing when a number of processed blocks having the same first character reaches at a predetermined number after detection of said discontinuous part.

10. An apparatus for data decompression according to claim 9, wherein said entropy decoding unit has said plurality of code tables:

a first code table where bit lengths assigned to high-usage characters and low-usage ones are greatly different; and

a second code table where bit lengths assigned to high-usage characters and low-usage ones are not so different, and

wherein, at said first timing when said discontinuous part is detected, said first code table is switched to said second code table, and, at said second timing when a number of processed blocks reaches at a predetermined number after detection of the discontinuous part, said second code table is switched to said first code table.

11. An apparatus for data decompression according to claim 10, wherein, regarding n blocks having identical first characters of said block-sorted character strings, said entropy decoding unit changes a number of blocks processed during switching to the second code table after detection of a discontinuous part and switching to the first code table, applies entropy coding, calculates a total amount of codes, and decides said number of switched blocks, at which a minimum total amount of codes is obtained, as an optimum value of the number of processed blocks with which said second switching timing is decided.

12. An apparatus for data decompression according to claim 11, wherein said entropy decoding unit decides said optimum value of the number of switched blocks, while the unit transforms an input string, and uses the value to switch code tables for subsequent blocks.

13. An apparatus for data decompression according to claim 11, wherein said entropy decoding unit decides said optimum value of the number of switched blocks beforehand, while the unit transforms an input string composed of typical data, and uses the value to switch code tables for all blocks.

14. An apparatus for data decompression according to claim 10, wherein said entropy decoding unit provides a plurality of said first code tables corresponding to combination of a plurality of characters starting with the head of said block-sorted character string, and, in case the unit switches the second code table to the first code table after detecting said discontinuous part, the unit selects a first code table corresponding to the combination of a plurality of characters starting with the head of a block-sorted character string.

15. An apparatus for data compression comprising:

a block-sorting transforming unit generating a new two-dimensional character matrix with rotating a character string in a block by a number of times equal to a number of characters in the block, the block which is obtained through dividing input data of a string into predetermined size of blocks, sorting rows in the matrix lexicographically, picking up last characters in the matrix in a sorted order, and outputting them as a block-sorted character string;

a reference list memory storing a plurality of reference lists including characters composing said block-sorted character string;

an intermediate code transforming unit selecting one of said plurality of reference lists, transforming each character of said block-sorted character string from a first character in turn into a code showing a registered position on said reference list, subsequently transforming a next character after moving the transformed character to the preceding position of the reference list, transforming said block-sorted character string into an intermediate code string showing registered positions on said reference list, and outputting the intermediate code; and

an entropy coding unit having a plurality of code tables corresponding to a change of an input character string, and applying entropy coding to identification information on the used reference list and the intermediate code inputted from said intermediate code transforming unit.

16. An apparatus for data compression according to claim 15, wherein said intermediate code transforming unit selects a reference list in said reference list memory in correspondence to a character or a plurality of characters starting with the head of said block-sorted character string.

17. An apparatus for data compression according to claim 15, wherein said intermediate code transforming unit moves a character transformed into a code showing a registered position on said reference list to the head on the list, and transforms a next character.

18. An apparatus for data compression according to claim 15, wherein said intermediate code transforming unit moves a character transformed into a code showing a registered position on said reference list to a position preceding by one character on the list, and transforms a next character.

19. An apparatus for data compression according to claim 15, wherein said intermediate code transforming unit continuously uses for subsequent blocks a reference list selected and updated in a transformation of a first block.

20. In an apparatus for data decompression:

generating a new two-dimensional character matrix through rotating a character string in a block by a number of times equal to a number of characters in the block, the block which is obtained through dividing input data of a string into predetermined size of blocks, sorting rows in the matrix lexicographically, picking up last characters of the two-dimensional character matrix in a sorted order, and outputting them as a block-sorted character string;

having a plurality of reference lists including all of characters composing said block-sorted character string, selecting one of them, transforming each character of said block-sorted character string from a first character in turn into a code showing a registered position on said reference list, subsequently transforming a next character after moving the transformed character to a preceding position of the reference list, transforming said block-sorted character string into an intermediate code string showing registered positions on said reference list; and

having a code table corresponding to a change of an input character string, inputting said intermediate code string and identification information on the reference list used for the transformation, applying entropy coding to them and decompressing the entropy-coded code string into the original character string, the apparatus for data decompression comprising;

an entropy decoding unit having a code table corresponding to a change of an input string, inputting said entropy-coded code string and decoding the string into said intermediate code string and identification information on the reference list;

a reference list memory storing a plurality of reference lists including all characters composing said block-sorted character string;

an MTF inverse transforming unit restoring the intermediate code to said block-sorted character string with selecting a reference list specified by said identification information from said reference list memory; and

a block-sorting inverse transforming unit restoring to the original character string the block-sorted character string transformed by said MTF inverse transforming unit.

21. An apparatus for data decompression according to claim 20, wherein said intermediate code inverse transforming unit selects a reference list in said reference list memory in correspondence to a character or a plurality of characters starting with the head of said block-sorted character string.

22. An apparatus for data decompression according to claim 20, wherein said intermediate code inverse transforming unit moves a character transformed into a code showing a registered position on said reference list to the head on the list, and transforms a next character.

23. An apparatus for data decompression according to claim 20, wherein said intermediate code inverse transforming unit moves a character transformed into a code showing a registered position on said reference list to a position preceding by one character on the list, and transforms a next character.

24. An apparatus for data decompression according to claim 20, wherein said intermediate code inverse transforming unit continuously uses for subsequent blocks a reference list selected and updated in a transformation of a first block.