Method and apparatus for compressing data-carrying signals

• US 8,872,677 B2
• Filed: 03/15/2013
• Issued: 10/28/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Dialogic Networks (Israel) Ltd. (Dialogic, Inc. (United Arab Emirates))
• Original Assignee: Dialogic Networks (Israel) Ltd. (Dialogic, Inc. (United Arab Emirates))
• Inventors: Litvak, Oleg, Ilan, Amir
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US13/838,327
• Publication Number:
  US 20140266816A1
• Time in Patent Office: 592 Days
• Field of Search: 341/51, 341/67, 341/106, 375/240.25, 375/240.01, 713/177, 713/185, 713/193, 370/477, 370/486, 382/232, 382/245, 382/128, 382/209, 382/239, 382/244, 382/246, 711/137, 711/213, 711/E12.057
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

A compression method applies a selection rule to input symbols and generates a reduced partial set of symbols. The partial set is checked against a dictionary-index for a match. A match identifies a range of matching symbols in a dictionary. The length of the matching range is iteratively increased by checking previous and next symbols in the input data and the dictionary until a matching range length meets a threshold limit or the length of the matching range cannot be increased further. Compressed data corresponding to the input symbols is provided where input symbols are copied over and symbols in a matched range of data are replaced with a representation of their corresponding start location and length in the dictionary.

Claims

1. A computer-implemented method of compressing input data comprising a sequence of input data symbols, the method comprising:

(a) copying a predetermined number of input data symbols into a defined block of input data symbols;

(b) selecting a subset of input data symbols S_N in the defined block of input data symbols according to a first predetermined selection rule;

(c) generating a respective input data dictionary-index value DI_N for the selected subset S_N;

(d) if the input data dictionary-index value DI_N represents a range of dictionary data symbols D_N stored in a dictionary, then;

(e) determining a range of input data symbols including the subset of input data symbols S_N that matches a range of dictionary data symbols that includes the range of dictionary data symbols D_N; and

(f) storing a correlation of the matching input data range of symbols and the dictionary data range of symbols, determined in step (e) as a set comprising a pointer to a starting symbol location in the dictionary and a matching range length;

(g) selecting a next subset of input data symbols S_N in the defined block of input data symbols according to the first predetermined selection rule; and

(h) repeating steps (c)-(g) until an end of the defined block of input data symbols is reached; and

converting the defined block of input data symbols into an outgoing data payload by replacing those input data symbols determined to be in a matching range of symbols in the dictionary in steps (b)-(h) with an indication of the stored corresponding pointer and matching range length.

2. The computer-implemented method of claim 1, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective subset of input data symbols S_N to different ranges of dictionary data symbols that include the range of dictionary data symbols D_N.

3. The computer-implemented method of claim 1, further comprising:

searching a dictionary-index for an entry corresponding to the input data dictionary-index value DI_N, where each dictionary-index entry points to a range of dictionary data symbols D and its corresponding location in the dictionary.

4. The computer-implemented method of claim 3, further comprising:

defining a block of dictionary data symbols;

selecting a subset of dictionary data symbols in the defined block of dictionary data symbols according to a second predetermined selection rule different from the first predetermined selection rule and identifying its corresponding location in the dictionary;

calculating a dictionary-index value for the selected subset of dictionary data symbols; and

storing the calculated dictionary-index value and the corresponding dictionary location as an entry in the dictionary-index.

5. The computer-implemented method of claim 1, wherein:

selecting a subset of input data symbols S_N comprises selecting an N^th input data symbol B_N in the defined block of input data symbols;

generating a respective input data dictionary-index value DI_N comprises generating a respective input data hash value HV_N for the selected input data symbol B_N; and

selecting a next subset of input data symbols S_N comprises selecting a next N^th input data symbol B_N in the defined block of input data symbols.

6. The computer-implemented method of claim 5, wherein determining a range of input data symbols including the N^th input data symbol B_N that matches a range of dictionary data symbols that includes the dictionary data symbol HB_N comprises:

terminating the determination when a length of the matching range is at least equal to a predetermined threshold value.

7. The computer-implemented method of claim 5, further comprising:

storing the correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting symbol location in the dictionary and a matching range length only if a length of the matching input data range is greater than or equal to a predetermined minimum length.

8. The computer-implemented method of claim 5, further comprising:

searching a dictionary-index for an entry corresponding to the input data hash value HV_N, where each dictionary-index entry points to a range of dictionary data symbols HB and its corresponding location in the dictionary.

9. The computer-implemented method of claim 8, wherein the entries in the dictionary-index comprise hash values calculated for every M^th symbol in the dictionary, wherein N≠

M.

10. The computer-implemented method of claim 9, wherein N and M do not have a common factor value.

11. The computer-implemented method of claim 8, further comprising:

defining a block of dictionary data symbols;

selecting every M^th symbol in the defined block of dictionary data symbols and identifying its corresponding location in the dictionary;

calculating a hash value HV_M for each selected M^th symbol; and

storing the calculated hash value HV_M and the corresponding dictionary location as an entry in the dictionary-index,

wherein M #N.

12. The computer-implemented method of claim 11, wherein N and M do not have a common factor value.

13. The computer-implemented method of claim 8, wherein generating a respective input data hash value HV_N comprises:

applying a hash function to the N^th input data symbol B_N and a predetermined number of adjacent input data symbols in the defined block of input data symbols.

14. The computer-implemented method of claim 13, wherein the predetermined number of adjacent input data symbols comprises a predetermined number of symbols immediately preceding the respective N^th input data symbol B_N.

15. The computer-implemented method of claim 13, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective input data symbol B_N to different ranges of dictionary data symbols including the dictionary data symbol HB_N.

16. The computer-implemented method of claim 15, wherein iteratively comparing different ranges of input data symbols comprises:

creating different ranges of input data symbols and different ranges of dictionary data symbols by appending adjacent symbols.

17. An apparatus for compressing data, the apparatus comprising:

at least one memory having at least one computer program stored therein;

at least one processor operative to execute the at least one computer program out of the at least one memory to;

(a) receive a sequence of input data symbols;

(b) copy a predetermined number of the received input data symbols into a defined block of input data symbols;

(c) select a subset of input data symbols S_N in the defined block of input data symbols according to a first predetermined selection rule;

(d) generate a respective input data dictionary-index value DI_N for the selected subset of input data symbols S_N;

(e) if the dictionary-index value DI_N represents a range of dictionary data symbols D_N stored in a dictionary, then;

(f) determine a range of input data symbols including the subset of input data symbols S_N that matches a range of dictionary data symbols that includes the range of dictionary data symbols D_N; and

(g) store a correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting symbol location in the dictionary and a matching range length;

(h) select a next subset of input data symbols S_N in the defined block of input data symbols according to the first predetermined selection rule;

(i) repeat steps (d)-(h) until an end of the defined block of input data symbols is reached; and

convert the defined block of input data symbols into an outgoing data payload by replacing those input data symbols determined to be in a matching range of symbols in the dictionary in steps (c)-(i) with an indication of the stored corresponding pointer and matching range length.

18. The apparatus of claim 17, wherein determining the range of matching input data symbols comprises:

is iteratively comparing different ranges of input data symbols including the respective subset of input data symbols S_N to different ranges of dictionary data symbols that include the range of dictionary data symbols D_N.

19. The apparatus of claim 17, wherein:

selecting a subset of input data symbols S_N comprises selecting an N^th input data symbol B_N in the defined block of input data symbols;

generating a respective input data dictionary-index value DI_N comprises generating a respective input data hash value HV_N for the selected input data symbol B_N; and

selecting a next subset of input data symbols S_N comprises selecting a next N^th input data symbol B_N in the defined block of input data symbols.

20. The apparatus of claim 19, wherein determining a range of input data symbols including the N^th input data symbol B_N that matches a range of dictionary data symbols that includes the dictionary data symbol HB_N comprises:

terminating the determination when a length of the matching range is at least equal to a predetermined threshold value.

21. The apparatus of claim 19, wherein the at least one processor is further operative to:

store the correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting symbol location in the dictionary and a matching range length only if a length of the matching input data range is greater than or equal to a predetermined minimum length.

22. The apparatus of claim 19, wherein the at least one processor is further operative to:

search a dictionary-index for an entry corresponding to the input data dictionary-index value DI_N, where each dictionary-index entry points to a range of dictionary data symbols D and its corresponding location in the dictionary.

23. The apparatus of claim 22, wherein the at least one processor is further operative to:

define a block of dictionary data symbols;

select a subset of dictionary data symbols in the defined block of dictionary data symbols according to a second predetermined selection rule different from the first predetermined selection rule and identifying its corresponding location in the dictionary;

calculate a dictionary-index value for the selected subset of dictionary data symbols; and

store the calculated dictionary-index value and the corresponding dictionary location as an entry in the dictionary-index.

24. The apparatus of claim 19, wherein the at least one processor is further operative to:

search a dictionary-index for an entry corresponding to the input data hash value HV_N, where each dictionary-index entry points to a range of dictionary data symbols HB and its corresponding location in the dictionary.

25. The apparatus of claim 24, wherein the entries in the dictionary-index comprise hash values calculated for every M^th symbol in the dictionary, wherein N≠

M.

26. The apparatus of claim 25, wherein N and M do not have a common factor value.

27. The apparatus of claim 24, wherein the at least one processor is further operative to:

define a block of dictionary data symbols;

select every M^th symbol in the defined block of dictionary data symbols and identifying its corresponding location in the dictionary;

calculate a hash value HV_M for each selected M^th symbol; and

store the calculated hash value HV_M and the corresponding dictionary location as an entry in the dictionary-index,

wherein M≠

N.

28. The apparatus of claim 27, wherein N and M do not have a common factor value.

29. The apparatus of claim 24, wherein generating a respective input data hash value HV_N comprises:

applying a hash function to the N^th input data symbol B_N and a predetermined number of adjacent input data symbols in the defined block of input data symbols.

30. The apparatus of claim 29, wherein the predetermined number of adjacent input data symbols comprises a predetermined number of symbols immediately preceding the respective N^th input data symbol B_N.

31. The apparatus of claim 29, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective input data symbol B_N to different ranges of dictionary data symbols including the dictionary data symbol HB_N.

32. The apparatus of claim 31, wherein iteratively comparing different ranges of input data symbols comprises:

creating different ranges of input data symbols and different ranges of dictionary data symbols by appending adjacent symbols.

33. A computer-implemented method of compressing a sequence of input data symbols, the method comprising:

generating a respective input data dictionary-index value DI_N for a subset of input data symbols S_N in the sequence of input data symbols selected according to a first predetermined selection rule;

for each input data dictionary-index value DI_N;

searching a dictionary-index for an entry corresponding to each input data dictionary-index value DI_N, where each dictionary-index entry points to a range of dictionary data symbols D and a corresponding location in a dictionary;

if the input data dictionary-index value DI_N is found in the dictionary-index then determining a range of input data symbols including the subset S_N that matches a range of dictionary data symbols D_N; and

storing the correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting symbol is location in the dictionary and a matching range length; and

for each input data symbol of the sequence of input data symbols;

inserting the input data symbol into an outgoing data payload if the input data symbol is not in a range of matching symbols in the dictionary; and

for those input data symbols in a matching range of symbols in the dictionary then inserting an indication of the stored corresponding pointer and matching range length in the outgoing data payload instead of the input data symbols.

34. The computer-implemented method of claim 33, further comprising:

defining a block of dictionary data symbols;

selecting a subset of dictionary data symbols in the defined block of dictionary data symbols according to a second predetermined selection rule different from the first predetermined selection rule and identifying its corresponding location in the dictionary;

calculating a dictionary-index value for the selected subset of dictionary data symbols; and

storing the calculated dictionary-index value and the corresponding dictionary location as an entry in the dictionary-index.

35. The computer-implemented method of claim 33, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective subset of input data symbols S_N to different ranges of dictionary data symbols that include the range of dictionary data symbols D_N.

36. The computer-implemented method of claim 33, wherein:

selecting a subset of input data symbols S_N comprises generating a respective input data hash value HV_N for each N^th input data symbol B_N in the sequence of input data symbols, and

wherein searching a dictionary-index comprises searching a hash index for an entry corresponding to each input data hash value HV_N, where each hash index entry points to a dictionary data symbol HB and its corresponding location in the dictionary.

37. The computer-implemented method of claim 36, wherein determining a range of input data is symbols including the N^th input data symbol B_N that matches a range of dictionary data symbols that includes the dictionary data symbol HB_N comprises:

terminating the determination when a length of the matching range is at least equal to a predetermined threshold value.

38. The computer-implemented method of claim 36, further comprising:

storing the correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting symbol location in the dictionary and a matching range length only if a length of the matching input data range is greater than or equal to a predetermined minimum length.

39. The computer-implemented method of claim 36, wherein the entries in the dictionary-index comprise hash values calculated for every M^th symbol in the dictionary and wherein N≠

M.

40. The computer-implemented method of claim 39, wherein N and M do not have a common factor value.

41. The computer-implemented method of claim 36, further comprising:

defining a block of dictionary data symbols;

selecting every M^th symbol from the defined block of dictionary data symbols and identifying its corresponding location in the dictionary;

calculating a hash value HV_M for each selected M^th symbol; and

storing the calculated hash value HV_M and the corresponding dictionary location as an entry in the dictionary-index,

wherein M≠

N.

42. The computer-implemented method of claim 41, wherein N and M do not have a common factor value.

43. The computer-implemented method of claim 36, wherein generating a respective input data hash value HV_N comprises:

applying a hash function to the N^th input data symbol B_N and a predetermined number of adjacent input data symbols in the sequence of input data symbols.

44. The computer-implemented method of claim 43, wherein the predetermined number of adjacent input data symbols comprises a predetermined number of symbols immediately preceding the respective N^th input data symbol B_N.

45. The computer-implemented method of claim 43, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective input data symbol B_N to different ranges of dictionary data symbols including the dictionary data symbol HB_N.

46. The computer-implemented method of claim 45, wherein iteratively comparing different ranges of input data symbols comprises:

creating different ranges of input data symbols and different ranges of dictionary data symbols by appending adjacent symbols.

47. An apparatus for compressing data, the apparatus comprising:

at least one memory having at least one computer program stored therein;

at least one processor operative to execute the at least one computer program out of the at least one memory to;

receive sequence of input data symbols,

generate a respective input data dictionary-index value DI_N for a subset of input data symbol S_N in the received sequence of input data symbols selected according to a first predetermined selection rule; and

for each input data dictionary-index value DI_N;

search a dictionary-index for an entry corresponding to each input data dictionary-index value DI_N, where each dictionary-index entry points to a range of dictionary data symbols D and a corresponding location in a dictionary;

if the input data dictionary-index value DI_N is found in the dictionary-index then determine a range of input data symbols including the subset S_N that matches a range of dictionary data symbols D_N; and

store the correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting is symbol location in the dictionary and a matching range length; and

for each input data symbol of the sequence of input data symbols;

insert the input data symbol into an outgoing data payload if the input data symbol is not in a range of matching symbols in the dictionary; and

for those input data symbols in a matching range of symbols in the dictionary then insert an indication of the stored corresponding pointer and matching range length in the outgoing data payload instead of the input data symbols.

48. The apparatus of claim 47, wherein the at least one processor is further operative to:

define a block of dictionary data symbols;

select a subset of dictionary data symbols in the defined block of dictionary data symbols according to a second predetermined selection rule different from the first predetermined selection rule and identify its corresponding location in the dictionary;

calculate a dictionary-index value for the selected subset of dictionary data symbols; and

store the calculated dictionary-index value and the corresponding dictionary location as an entry in the dictionary-index.

49. The apparatus of claim 47, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective subset of input data symbols S_N to different ranges of dictionary data symbols that include the range of dictionary data symbols D_N.

50. The apparatus of claim 47, wherein:

generating a respective input data dictionary-index value comprises generating a respective input data hash value HV_N for each N^th input data symbol B_N in the received sequence of input data symbols, and

wherein searching a dictionary-index for an entry corresponding to each input data dictionary-index value DI_N comprises searching a hash index for an entry corresponding to each input data hash value HV_N, where each hash index entry points to a dictionary data symbol HB and a corresponding location in a dictionary.

51. The apparatus of claim 50, wherein determining a range of input data symbols including the N^th input data symbol B_N that matches a range of dictionary data symbols that includes the dictionary data symbol HB_N comprises:

terminating the determination when a length of the matching range is at least equal to a predetermined threshold value.

52. The apparatus of claim 50, wherein the at least one processor is further operative to:

store the correlation of the matching input data range of symbols and the dictionary data range of symbols as a set comprising a pointer to a starting symbol location in the dictionary and a matching range length only if a length of the matching input data range is greater than or equal to a predetermined minimum length.

53. The apparatus of claim 50, wherein the entries in the dictionary-index comprise hash values calculated for every M^th symbol in the dictionary and wherein N #M.

54. The apparatus of claim 53, wherein N and M do not have a common factor value.

55. The apparatus of claim 50, wherein the at least one processor is further operative to:

retrieve a block of dictionary data symbols;

select every M^th symbol in the block of dictionary data symbols and identifying its corresponding location in the dictionary;

calculate a hash value HV_M for each selected M^th symbol; and

store the calculated hash value HV_M and the corresponding location as an entry in the dictionary-index,

wherein M≠

N.

56. The apparatus of claim 55, wherein N and M do not have a common factor value.

57. The apparatus of claim 50, wherein generating a respective input data hash value HV_N comprises:

applying a hash function to the N^th input data symbol B_N and a predetermined number of adjacent input data symbols in the sequence of input data symbols.

58. The apparatus of claim 57, wherein the predetermined number of adjacent input data symbols comprises a predetermined number of symbols immediately preceding the respective N^th input data symbol B_N.

59. The apparatus of claim 57, wherein determining the range of matching input data symbols comprises:

iteratively comparing different ranges of input data symbols including the respective input data symbol B_N to different ranges of dictionary data symbols including the dictionary data symbol HB_N.

60. The apparatus of claim 59, wherein iteratively comparing different ranges of input data symbols comprises:

creating different ranges of input data symbols and different ranges of dictionary data symbols by appending adjacent symbols.