Data compression system and data compression device for improving data compression rate and coding speed

• US 5,883,588 A
• Filed: 10/04/1995
• Issued: 03/16/1999
• Est. Priority Date: 10/04/1994
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Okamura, Toshihiko
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/538,652
• Time in Patent Office: 1,259 Days
• Field of Search: 341/51, 341/67, 341/106
• US Class Current: 341/5
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77

Abstract

A data compression system includes a data array storage device, a coding device, a retrieving and recording device and a recording controller. The data array storage device stores both the input data to be compressed and the input data coded by the coding device. The recording controller determines the character strings recorded by the retrieving and recording device by discriminating between character strings on the basis of the length of the matched character strings beginning from an intermediate character of the matched character strings. The coding device then codes the matched character strings using the length and position of the recorded character strings.

Claims

1. A data compression system comprising:

historical data array storage means having a plurality of entries for storing input data to be compressed and for storing input data for which coding is completed;

retrieving and recording means for recording character strings in the input data for which coding is completed selected from the input data from which coding is completed and performing a retrieval of matched character strings through a comparison of character strings in the input data to be compressed and the recorded character strings;

recording control means for selecting character strings to be recorded in said retrieving and recording means; and

coding means for performing coding of said matched character strings in the input data to be compressed by using a length of said matched character strings and a position of said matched character strings included in said recorded character strings in said retrieving and recording means,

wherein said recording control means discriminates between character strings with respect to recording a character string in said retrieving and recording means and not recording a character string in said retrieving and recording means, on the basis of the length of said matched character strings beginning from an intermediate character of said matched character strings.

2. A data compression system as set forth in claim 1, wherein said recording control means records the character strings beginning from the leading end of the matched character strings in the input data and the character strings beginning from an intermediate position of the matched character strings having length smaller than or equal to a predetermined threshold value, in said retrieving and recording means.

3. A data compression system as set forth in claim 2, wherein said threshold value is varied dynamically.

4. A data compression system as set forth in claim 1, wherein said recording control means discriminates each of said character strings beginning from the intermediate characters of said matched character strings in said input data to be compressed between the character strings to be recorded in said retrieving and recording means and the character strings not to be recorded on the basis of the position of the leading end of the matched character string in the coded input data in said historical data array storage means.

5. A data compression system as set forth in claim 1, wherein said recording control means records the character strings beginning from the leading end of the matched character strings in the input data and the character strings beginning from an intermediate positions of the matched character strings which has relative distance between the position of the leading end of said matched character string in the coded input data and position of the leading end of the input data to be compressed being greater than or equal to the threshold value, in said retrieving and recording means.

6. A data compression system as set forth in claim 5, wherein said threshold value is varied dynamically depending upon necessity.

7. A data compression system as set forth in claim 1, which further comprises index data array storage means having entries corresponding to respective entries in said historical data array storage means, said index data array storage means assigning index for the leading entry of the character string to be recorded in said retrieving and recording means among entries of said historical data array storage means, maintaining said index at the position of said index data array storage means corresponding to said entry in said historical data array storage means, and generating a position code indicative of the position of said entry in said historical data array storage means on the basis of said index.

8. A data compression system as set forth in claim 7, wherein said recording control means discriminates each of said character strings beginning from the intermediate characters of said matched character strings in said input data to be compressed between the character strings to be recorded in said retrieving and recording means and the character strings not to be recorded on the basis the length of said matched character string.

9. A data compression system as set forth in claim 7, wherein said recording control means records the character strings beginning from the leading end of the matched character strings in the input data and the character strings beginning from an intermediate position of the matched character strings having length smaller than or equal to the predetermined threshold valve, in said retrieving and recording means.

10. A data compression system as set forth in claim 9, wherein said threshold value is varied dynamically.

11. A data compression system as set forth in claim 7, wherein said recording control means discriminates each of said character strings beginning from the intermediate characters of said matched character strings in said input data to be compressed between the character strings to be recorded in said retrieving and recording means and the character strings not to be recorded on the basis of the position of the leading end of the matched character string in the coded input data in said historical data array storage means.

12. A data compression system as set forth in claim 7, wherein said recording control means records the character strings beginning from the leading end of the matched character strings in the input data and the character strings beginning from an intermediate positions of the matched character strings which has relative distance between the position of the leading end of said matched character string in the coded input data and position of the leading end of the input data to be compressed being greater than or equal to the threshold value, in said retrieving and recording means.

13. A data compression system as set forth in claim 12, wherein said threshold value is varied dynamically.

14. A data compression system comprising:

historical data array storage means having a plurality of entries for storing input data and for storing coded input data;

retrieving and recording means for performing retrieval of matched character strings through comparison of the input data to be compressed and the coded input data stored in said historical data array storage means and recording character strings in said historical data array storage means;

recording control means for selectively recording character strings beginning from positions in a range between the leading end of said matched character strings stored in said historical data array storage means and a given number of positions represented by a threshold value from the leading end of said matched character strings in said retrieving and recording means; and

coding means for performing coding of said matched character strings in the input data to be compressed by using the length of said matched character strings and the position of said matched character strings included in said recorded character strings in said retrieving and recording means.

15. A data compression system as set forth in claim 14, which further comprises index data array storage means having entries corresponding to respective entries in said historical data array storage means, said index data array storage means assigning index for the leading entry of the character string to be recorded in said retrieving and recording means among entries of said historical data array storage means, maintaining said index at the position of said index data array storage means corresponding to said entry in said historical data array storage means, and generating a position code indicative of the position of said entry in said historical data array storage means on the basis of said index.