Polynomial-time, sequential, adaptive system and method for lossy data compression

• US 6,798,362 B2
• Filed: 10/30/2002
• Issued: 09/28/2004
• Est. Priority Date: 10/30/2002
• Status: Active Grant

• Current Assignee: Uniloc 2017 LLC (SoftBank Group Corp.)
• Original Assignee: International Business Machines Corporation
• Inventors: Modha, Dharmendra Shantilal
• Primary Examiner(s): Young, Brian
• Assistant Examiner(s): LAUTURE, JOSEPH J
• Application Number:
  US10/285,131
• Publication Number:
  US 20040085228A1
• Time in Patent Office: 699 Days
• Field of Search: 341/51, 341/50, 341/67, 382/40, 704/260
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A system and method are provided for lossy compression of finite alphabet source sequences subject to an average-per-letter distortion constraint. The source sequence is sequentially parsed into phrases and each source phrase is mapped to a distorted phrase such that average per-letter distortion between the two phrases does not exceed the desired distortion. The present system adaptively maintains a codebook as the collection of all one-letter extensions of previously emitted distorted phrases. The present system uses approximate string matching and carries out a sequential procedure by iterating the following steps: (i) given the current codebook find the longest source phrase that can be transmitted at a given distortion, (ii) from all codewords that match the source phrase carefully choose that which is most likely to be useful in the future. For every new source phrase, the present system judiciously selects one of the many approximately matching codewords to balance between the code rate for the current phrase versus the code rate from resulting codebooks for the future source phrases. The present system outputs a distorted sequence that can be naturally losslessly compressed using the Lempel-Ziv algorithm or any variation thereof. Such judicious codeword selection is intended to iteratively improve the codebook quality. The entire present sequence can be implemented in quadratic-time in the length of the source sequence. The present system is sequential and adaptive.

Claims

1. A lossy data compression method for converting a source sequence over a source alphabet to a distorted sequence over a reproduction alphabet by intentionally introducing errors, the method comprising:

parsing the source sequence into a plurality of source phrases;

mapping each source phrase to a distorted phrase of equal length and that includes a distortion that is less than an allowed per-symbol distortion budget; and

synthesizing the distorted sequence by concatenating the distorted phrases.

2. The method of claim 1, wherein parsing the source sequence comprises parsing the source sequence sequentially into the source phrases, one phrase at a time, and mapping each source phrase to a distorted phrase before moving onto a next source phrase, until the source sequence is exhausted.

3. The method of claim 2, further comprising losslessly compressing each distorted phrase before the next source phrase is processed.

4. The method of claim 2, further comprising adaptively maintaining a codebook that includes a collection of codewords, in response to an observed source sequence, and updating the codebook after every source phrase has been processed.

5. The method of claim 4, wherein the codebook comprises all phrases that are obtained by extending all previously processed distorted phrases by all symbols of the reproduction alphabet.

6. The method of claim 5, further defining a new distorted phrase as a shortest phrase that is not the same as any of previously processed distorted phrases.

7. The method of claim 4, further defining a new source phrase as a prefix of an unprocessed source sequence that matches at least one codeword in the codebook within the allowed per-symbol distortion budget.

8. The method of claim 7, wherein each new source phrase is a longest prefix of the unprocessed source sequence that matches at least one codeword in the codebook within the allowed per-symbol distortion budget.

9. The method of claim 7, wherein mapping each source phrase comprises mopping the source phrase to a codeword in the codebook that matches the source phrase within the allowed per-symbol distortion budget.

10. The method of claim 9, wherein mapping each source phrase comprises mapping the source phrase to a codeword that has a smallest per-symbol distortion amongst all matching codewords.

11. The method of claim 9, wherein mapping each source phrase comprises mapping the source phrase to a codeword that is a most recent codeword amongst all matching codewords.

12. The method of claim 9, wherein mopping each source phrase comprises mapping the source phrase to a codeword amongst all matching codewords so as to maximize a number of bits required to encode on entire processed source sequence subject to an entire resulting processed distorted sequence as side information.

13. The method of claim 12, wherein computing the number of bits required to encode the entire processed source sequence subject to the entire resulting processed distorted sequence as side information comprises using a lossless compression code with a side information sequence.

14. The method of claim 13, wherein the lossless compression code with a side information sequence is a Lempel-Ziv code with side information.

15. The method of claim 13, wherein the lossless compression code with a side information sequence is an adoptive arithmetic code with side information.

16. The method of claim 13, wherein the lossless compression code with a side information sequence is a dynamic Huffman code with side information.

17. The method of claim 13, wherein the lossless compression code with a side information sequence is a Lempel-Ziv-Welch code with side information.

18. The method of claim 9, wherein mapping each source phrase comprises mapping the source phrase to a codeword amongst all matching codewords so that a difference between a number of bits required to encode an entire processed source sequence subject to an entire resulting processed distorted sequence as side information and the number of bits required to encode an entire resulting processed distorted sequence subject to an entire processed source sequence as side information is maximized.

19. The method of claim 18, wherein computing the number of bits required to encode the entire processed source sequence subject to the entire resulting processed distorted sequence as side information comprises using a lossless compression code with a side information sequence;

and

wherein computing the number of bits required to encode the entire resulting processed distorted sequence subject to the entire processed source sequence as side information comprises using a lossless compression code with a side information sequence.

20. The method of claim 19, wherein the lossless compression code with a side information sequence is a Lempel-Ziv code with side information.

21. The method of claim 19, wherein the lossless compression code with a side information sequence is an adaptive arithmetic code with side information.

22. The method of claim 19, wherein the lossless compression code with a side information sequence is an dynamic Huffman code with side information.

23. The method of claim 19, wherein the lossless compression code with a side information sequence is an Lempel-Ziv-Welch code with side information.

24. The method of claim 1, further comprising losslessly compressing the distorted sequence.

25. The method of claim 24, further comprising decompressing the compressed distorted sequence.

26. The method of claim 25, wherein losslessly compressing and decompressing the distorted sequence comprises using a Lempel-Ziv code.

27. The method of claim 25, wherein losslessly compressing and decompressing the distorted sequence comprises using an adaptive arithmetic code.

28. The method of claim 25, wherein losslessly compressing and decompressing the distorted sequence comprises using a Lempel-Ziv-Welch code.

29. The method of claim 25, wherein losslessly compressing and decompressing the distorted sequence comprises using a dynamic Huffman code.

30. The method of claim 25, wherein losslessly compressing and decompressing the distorted sequence comprises using a locally adaptive move-to-front code.

31. A computer program product having instruction codes for converting a source sequence over a source alphabet to a distorted sequence over a reproduction alphabet by intentionally introducing errors, the computer program product comprising:

a first set of instruction codes for parsing the source sequence into a plurality of source phrases;

a second set of instruction codes for mapping each source phrase to a distorted phrase of equal length and that includes a distortion that is less than an allowed per-symbol distortion budget; and

a third set of instruction codes for synthesizing the distorted sequence by concatenating the distorted phrases.

32. The computer program product of claim 31, wherein the first set of instruction codes for parsing the source sequence parses the source sequence sequentially into the source phrases, one phrase at a time, and maps each source phrase to a distorted phrase before moving onto a next source phrase, until the source sequence is exhausted.

33. The computer program product of claim 32, further comprising a fourth set of instruction codes for losslessly compressing each distorted phrase before the next source phrase is processed.

34. The computer program product of claim 33, further comprising a fifth set of instruction codes for adaptively maintaining a codebook that includes a collection of codewords, in response to on observed source sequence, and for updating the codebook after every source phrase has been processed.

35. The computer program product of claim 34, wherein the codebook comprises all phrases that are obtained by extending all previously processed distorted phrases by all symbols of the reproduction alphabet.

36. The computer program product of claim 35, wherein a new distorted phrase is a shortest phrase that is not the same as any of previously processed distorted phrases.

37. The computer program product of claim 34, wherein a new source phrase is a prefix of an unprocessed source sequence that matches at least one codeword in the codebook within the allowed per-symbol distortion budget.

38. The computer program product of claim 37, wherein each new source phrase is a longest prefix of the unprocessed source sequence that matches at least one codeword in the codebook within the allowed per-symbol distortion budget.

39. The computer program product of claim 37, wherein the second set of instruction codes maps the source phrase to a codeword in the codebook that matches the source phrase within the allowed per-symbol distortion budget.

40. The computer program product of claim 39, wherein the second set of instruction codes maps the source phrase to the codeword that has a smallest per-symbol distortion amongst all matching codewords.

41. The computer program product of claim 39, wherein the second set of instruction codes maps the source phrase to the codeword that is a most recent codeword amongst all matching codewords.

42. The computer program product of claim 39, wherein the second set of instruction codes maps the source phrase to a codeword amongst all matching Codewords so as to maximize a number of bits required to encode an entire processed source sequence subject to an entire resulting processed distorted sequence as side information.

43. The computer program product of claim 42, wherein the second set of instruction codes computes the number of bits required to encode the entire processed source sequence subject to the entire resulting processed distorted sequence as side information using a lossless compression code with a side information sequence.

44. The computer program product of claim 43, wherein the lossless compression code with a side information sequence is a Lempel-Ziv code with side information.

45. The computer program product of claim 43, wherein the lossless compression code with a side information sequence is an adaptive arithmetic code with side information.

46. The computer program product of claim 43, wherein the lossless compression code with a side information sequence is a dynamic Huffman code with side information.

47. The computer program product of claim 43, wherein the lossless compression code with a side information sequence is a Lempel-Ziv-Welch code with side information.

48. The computer program product of claim 39, wherein the second set of instruction codes maps the source phrase to a codeword amongst all matching codewords so that a difference between a number of bits required to encode an entire processed source sequence subject to an entire resulting processed distorted sequence as side information and the number of bits required to encode an entire resulting processed distorted sequence subject to an entire processed source sequence as side information is maximized.

49. The computer program product of claim 48, wherein the second set of instruction codes computes the number of bits required to encode the entire processed source sequence subject to the entire resulting processed distorted sequence as side information using a lossless compression code with a side information sequence;

and

wherein the second set of instruction codes further computes the number of bits required to encode the entire resulting processed distorted sequence subject to the entire processed source sequence as side information using a lossless compression code with a side information sequence.

50. The computer program product of claim 33, wherein the fourth set of instruction codes losslessly compresses the distorted sequence, and further decompresses the compressed distorted sequence.

51. A system for converting a source sequence over a source alphabet to a distorted sequence over a reproduction alphabet by intentionally introducing errors, the system comprising:

means for parsing the source sequence into a plurality of source phrases;

means for mapping each source phrase to a distorted phrase of equal length and that includes a distortion that is less than an allowed per-symbol distortion budget; and

means for synthesizing the distorted sequence by concatenating the distorted phrases.

52. The system of claim 51, wherein the parsing means parses the source sequence sequentially into the source phrases, one phrase at a time, and maps each source phrase to a distorted phrase before moving onto a next source phrase, until the source sequence is exhausted.

53. The system of claim 52, further comprising means for losslessly compressing each distorted phrase before the next source phrase is processed.

54. The system of claim 53, further comprising means for adaptively maintaining a codebook that includes a collection of codewords, in response to an observed source sequence, and for updating the codebook after every source phrase has been processed.

55. The system of claim 54, wherein the codebook comprises all phrases that ore obtained by extending all previously processed distorted phrases by all symbols of the reproduction alphabet;

wherein a new distorted phrase is a shortest phrase that is not the same as any of previously processed distorted phrases;

wherein a new source phrase is a prefix of an unprocessed source sequence that matches at least one codeword in the codebook within the allowed per-symbol distortion budget; and

wherein each new source phrase is a longest prefix of the unprocessed source sequence that matches at least one codeword in the codebook within the allowed per-symbol distortion budget.

56. The system of claim 55, wherein the mapping means maps the source phrase to a codeword in the codebook that matches the source phrase within the allowed per-symbol distortion budget;

wherein the mapping means further maps the source phrase to the codeword that has a smallest per-symbol distortion amongst all matching codewords;

wherein the mapping means further maps the source phrase to the codeword that is a most recent codeword amongst all matching codewords;

wherein the mapping means further maps the source phrase to a codeword amongst all matching codewords so as to maximize a number of bits required to encode an entire processed source sequence subject to an entire resulting processed distorted sequence as side information; and

wherein the mapping means further computes the number of bits required to encode an entire processed source sequence subject to the entire resulting processed distorted sequence as side information using a lossless compression code with a side information sequence.

57. The system of claim 56, wherein the lossless compression code with a side information sequence is any one of:

a Lempel-Ziv code with side information;

an adaptive arithmetic code with side information;

a dynamic Huffman code with side information;

or

a Lempel-Ziv-Welch code with side information.

58. The system of claim 56, wherein the mapping means maps the source phrase to a codeword amongst all matching codewords so that a difference between the number of bits required to encode the entire processed source sequence subject to an entire resulting processed distorted sequence as side information and the number of bits required to encode an entire resulting processed distorted sequence subject to an entire processed source sequence as side information is maximized.

59. The system of claim 58, wherein the mapping means computes the number of bits required to encode the entire processed source sequence subject to the entire resulting processed distorted sequence as side information using a lossless compression code with a side information sequence;

and

wherein the mapping means further computes the number of bits required to encode the entire resulting processed distorted sequence subject to the entire processed source sequence as side information using a lossless compression code with a side information sequence.

60. The system of claim 53, wherein the means losslessly compressing compresses the distorted sequence, and further decompresses the compressed distorted sequence.