Apparatus and method for data compression/expansion using block-based coding with top flag

• US 6,057,790 A
• Filed: 09/03/1997
• Issued: 05/02/2000
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Igata, Nobuyuki, Namba, Isao, Matsui, Kunio
• Primary Examiner(s): Williams, Howard L.
• Application Number:
  US08/922,676
• Time in Patent Office: 972 Days
• Field of Search: 341/50, 341/95, 341/55, 707/101
• US Class Current: 341/95
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A compression unit compresses original data in block units and encodes compressed data, and it generates continuation flag information expressive of the block length of the compressed data at the top part of the compressed data stored in a storage unit. An expansion unit determines the block length of the remaining data of the compressed data on the basis of the continuation flag information, fetches the remaining data from the storage unit and restores the original data.

Claims

1. A data compression apparatus comprising:

a compression device compressing given data according to a block-based coding method, and generating continuation flag information expressive of a length of compressed data in block units at a top part of the compressed data; and

a storage device storing said compressed data.

2. A data compression apparatus according to claim 1, wherein said compression device compresses numerical data for use in an index for information retrieval.

3. A data compression apparatus according to claim 2, wherein said compression device compresses at least one numerical data among "document No." data, "number of occurrences of a word within a document" data, "occurring position of a word within a document" data, and data expressive of a size of an area of the "occurring position of a word within a document" data.

4. A data compression apparatus according to claim 3, wherein at least one of the "document No." data and said "occurring position of a word within a document" data expresses difference information.

5. A data compression apparatus according to claim 1, wherein said compression device generates the continuation flag information expressive of a block length of said compressed data at the top part of said compressed data of at least one block, and generates data expressive of given data so as to succeed said continuation flag information.

6. A data compression apparatus according to claim 5, wherein said compression device includes an encoding device encoding said given data with 4 bits as a unit of the block.

7. A data compression apparatus according to claim 5, wherein said compression device includes an encoding device encoding given numerical data of at most 127 with a block of 8 bits, and encoding given numerical data of at least 128 with a top block of 8 bits and at least one succeeding block having 4 bits as a unit thereof.

8. A data compression apparatus according to claim 7, wherein said encoding device expresses numerical data of at most 127 by "0" of one bit and a bit pattern of 7 bits.

9. A data compression apparatus according to claim 5, wherein said compression device includes an encoding device encoding given numerical data of at most 2 with a block of 2 bits, and encoding given numerical data of at least 3 with 4 bits as a unit of the block.

10. A data compression apparatus according to claim 9, wherein said encoding device expresses given numerical data of at least 3 and at most 6 by the continuation flag information of 2 bits and a bit pattern of 2 bits.

11. A data compression apparatus comprising:

a conversion device converting numerical data to use in an index for information retrieval into interim numerical data expressive of a smaller numerical value;

a compression device compressing the interim numerical data by coding the interim numerical data; and

a storage device storing the compressed data.

12. A data compression apparatus according to claim 11, wherein said compression device compresses at least one numerical data between "number of occurrences of a word within a document" data and "occurring position of a word within a document" data for use in an index for information retrieval.

13. A data compression apparatus according to claim 11, wherein said compression device compresses the interim numerical data with 4 bits as a unit of a block, and generates continuation flag information expressive of a block length of said compressed data at a top part of said compressed data.

14. A data compression apparatus according to claim 11, wherein said compression device expresses the interim numerical data by expressing a numerical value of at most 2, by a block of 2 bits, and compresses the interim numerical data expressing a numerical value of at least 3, with 4 bits as a unit of a block.

15. A data compression apparatus according to claim 14, wherein said compression device expresses given numerical data of at least 3 and at most 6 by continuation flag information of 2 bits and a bit pattern of 2 bits.

16. A data compression apparatus comprising:

a compression device describing size data in block units, the size data expressing a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval, and for compressing said size data; and

a storage device storing the compressed size data therein.

17. A data expansion apparatus comprising:

a storage device storing therein data compressed in block units according to a block-based coding method; and

an expansion device determining a length of the compressed data based on continuation flag information at a top part of said compressed data, and then restoring original data.

18. A data expansion apparatus according to claim 17, wherein said expansion device restores numerical data for use in an index for information retrieval.

19. A data expansion apparatus according to claim 18, wherein said expansion device restores at least one numerical data among "document No." data, "number of occurrences of a word within a document" data, "occurring position of a word within a document" data, and data expressive of a size of an area of the "occurring position of a word within a document" data.

20. A data expansion apparatus according to claim 17, wherein said expansion device derives data expressive of the original data succeeding the continuation flag information, on the basis of said continuation flag information expressive of a block length of said compressed data of at least one block, and then restores said original data.

21. A data expansion apparatus according to claim 20, wherein said expansion device includes a decoding device decoding a code given as said compressed data and described with 4 bits as a unit of a block.

22. A data expansion apparatus according to claim 20, wherein said expansion device includes a decoding device decoding one block of 8 bits given as said compressed data, to generate numerical data of at most 127, and decoding a top block of 8 bits and at least one succeeding block having 4 bits as a unit thereof, the blocks having been given as said compressed data, thereby to generate numerical data of at least 128.

23. A data expansion apparatus according to claim 22, wherein said decoding device generates the numerical data of at most 127 when said one block of 8 bits is composed of "0" of one bit and a bit pattern of 7 bits.

24. A data expansion apparatus according to claim 20, wherein said expansion device includes a decoding device decoding one block of 2 bits given as said compressed data, thereby to generate numerical data of at most 2, and for decoding at least one block having 4 bits as a unit thereof and given as said compressed data, thereby to generate numerical data of at least 3.

25. A data expansion apparatus according to claim 24, wherein said decoding device generates numerical data of at least 3 and at most 6 when said compressed data is composed of said continuation flag information of 2 bits and a bit pattern of 2 bits.

26. A data expansion apparatus comprising:

a storage device converting numerical data for use in an index for information retrieval into interim numerical data expressive of a smaller numerical value, compressing the interim numerical data and storing the compressed numerical data therein; and

an expansion device expanding said compressed numerical data and converting the expanded numerical data into a larger numerical value.

27. A data expansion apparatus comprising:

a storage device compressing size data which describes in block units a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval, and storing the compressed size data therein; and

an expansion device restoring said size data.

28. An information retrieval system comprising:

a storage device compressing, according to a block-based coding method, numerical data for use in an index for information retrieval, and storing compressed data in block units therein;

an expansion device determining a length of said compressed data on the basis of continuation flag information at a top part of said compressed data, and then restoring the original data; and

a retrieval device retrieving a database by use of said original data restored.

29. An information retrieval system comprising:

a storage device converting numerical data for use in an index for information retrieval into interim numerical data expressive of a smaller numerical value, compressing the interim numerical data and storing the compressed numerical data therein;

an expansion device expanding said compressed numerical data and converting the expanded numerical data into a larger numerical value; and

a retrieval device retrieving a database by the use of the larger numerical value.

30. An information retrieval system comprising:

a storage device compressing size data which describes in block units a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval, and storing the compressed size data therein;

an expansion device restoring said size data; and

a retrieval device retrieving a database by the use of said original data restored.

31. A computer-readable storage medium storing a program to perform the process of compressing given data according to a block-based coding method and then generating continuation flag information expressive of a length of compressed data in block units at a top part of the compressed data.

32. A computer-readable storage medium storing a program to perform the process of converting numerical data for use in an index for information retrieval into interim numerical data expressive of a smaller numerical value and then compressing the interim numerical data.

33. A computer-readable storage medium storing a program to perform the process of describing size data in block units, the size data expressing a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval, and then compressing said size data.

34. A computer-readable storage medium storing a program to perform the process of determining a length of compressed in block units according to a block based coding method on the basis of continuation flag information at a top part of the compressed data and then restoring original data.

35. A computer-readable storage medium storing a program to perform the process of expanding data compressed by converting numerical data for use in an index for information retrieval into interim numerical data expressive of a smaller numerical value, and then converting the expanded numerical data into a larger numerical value.

36. A computer-readable storage medium storing a program to perform the process of expanding data compressed by describing in block units a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval.

37. A data compression method comprising:

compressing given data according to a block-based coding method; and

generating continuation flag information expressive of a length of compressed data in block units at a top part of the compressed data.

38. A data compression method comprising:

converting numerical data for use in an index for information retrieval into interim numerical data expressive of a smaller numerical value; and

compressing the interim numerical data.

39. A data compression method comprising:

describing size data in block units, the size data expressing a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval; and

compressing said size data.

40. A data expansion method comprising:

determining a length of data compressed in block units according to a block-based coding method on the basis of continuation flag information at a top part of the compressed data; and

restoring original data.

41. A data expansion method comprising:

expanding data compressed by converting numerical data for use in an index for information retrieval into interim numerical data expressive of a smaller numerical value; and

converting the expanded numerical data into a larger numerical value.

42. A data expansion method comprising:

expanding data compressed by describing in block units a size of an area of "occurring position of a word within a document" data for use in an index for information retrieval.

43. A data compression apparatus comprising:

a compression device compressing given data in block units, and generating continuation flag information expressive of a length of compressed data at a top part of the compressed data;

a storage device storing said compressed data therein; and

said compression device generates the continuation flag information expressive of a block length of said compressed data at the top part of said compressed data of at least one block, and generates data expressive of the given data so as to succeed said continuation flag information.

44. A data compression apparatus according to claim 43, wherein said compression device includes encoding means for encoding said given data with 4 bits as a unit of the block.

45. A data compression apparatus according to claim 43, wherein said compression device includes an encoding device encoding given numerical data of at most 127 with a block of 8 bits, and for encoding given numerical data of at least 128 with a top block of 8 bits and at least one succeeding block having 4 bits as a unit thereof.

46. A data compression apparatus according to claim 45, wherein said encoding device expresses the numerical data of at most 127 by "0" of one bit and a bit pattern of 7 bits.

47. A data compression apparatus according to claim 43, wherein said compression device includes an encoding device encoding given numerical data of at most 2 with a block of 2 bits, and encoding given numerical data of at least 3 with 4 bits as a unit of the block.

48. A data compression apparatus according to claim 47, wherein said encoding device expresses given numerical data of at least 3 and at most 6 by the continuation flag information of 2 bits and a bit pattern of 2 bits.

49. A data compression apparatus comprising:

a compression device for use in an index for information retrieval and compressing numerical data;

a storage device storing the compressed data therein; and

said compression device compresses the interim numerical data with 4 bits as a unit of a block, and generates continuation flag information expressive of a block length of said compressed data at a top part of said compressed data.

50. A data compression apparatus comprising:

a compression device for use in an index for information retrieval and compressing the numerical data;

a storage device storing the compressed data therein; and

said compression device expresses the interim numerical data for a numerical value of at most 2, by a block of 2 bits, and compresses the interim numerical data expressing a numerical value of at least 3, with 4 bits as a unit of a block.

51. A data compression apparatus according to claim 50, wherein said compression device expresses given numerical data of at least 3 and at most 6 by continuation flag information of 2 bits and a bit pattern of 2 bits.

52. A data expansion apparatus comprising:

a storage device storing therein data compressed in block units;

an expansion device determining a length of the compressed data on the basis of continuation flag information at a top part of said compressed data, and then restoring original data;

said expansion device derives data expressive of the original data succeeding the continuation flag information, on the basis of said continuation flag information expressive of a block length of said compressed data of at least one block, and then restores said original data;

said expansion device includes a decoding device decoding a code given as said compressed data and described with 4 bits as a unit of a block.

53. A data expansion apparatus comprising:

a storage device storing therein data compressed in block units;

an expansion device determining a length of the compressed data on the basis of continuation flag information at a top part of said compressed data, and then restoring original data;

said expansion device derives data expressive of the original data succeeding the continuation flag information, on the basis of said continuation flag information expressive of a block length of said compressed data of at least one block, and then restores said original data; and

said expansion device includes a decoding device decoding one block of 8 bits given as said compressed data, thereby to generate numerical data of at most 127, and decoding a top block of 8 bits and at least one succeeding block having 4 bits as a unit thereof, the blocks having been given as said compressed data, thereby to generate numerical data of at least 128.

54. A data expansion apparatus according to claim 53, wherein said decoding device generates the numerical data of at most 127 when said one block of 8 bits is composed of "0" of one bit and a bit pattern of 7 bits.

55. A data expansion apparatus comprising:

a storage device storing therein data compressed in block units;

an expansion device determining a length of the compressed data on the basis of continuation flag information at a top part of said compressed data, and then restoring original data;

said expansion device derives data expressive of the original data succeeding the continuation flag information, on the basis of said continuation flag information expressive of a block length of said compressed data of at least one block, and then restores said original data; and

said expansion device includes a decoding device decoding one block of 2 bits given as said compressed data, thereby to generate numerical data of at most 2, and decoding at least one block having 4 bits as a unit thereof and given as said compressed date, thereby to generate numerical data of at least 3.

56. A data expansion apparatus according to claim 55, wherein said decoding device generates numerical data of at least 3 and at most 6 when said compressed data is composed of said continuation flag information of 2 bits and a bit pattern of 2 bits.

57. A data compression apparatus comprising:

a compression device compressing data by generating a block of continuation flag information and compressing data into compressed data blocks using a block-based method; and

a storage device storing the continuation flag information on top of the compressed data blocks.

58. A data compression method comprising:

generating a block of continuation flag information;

compressing data using a block based method into compressed data blocks; and

concatenating the continuation flag information on top of the compressed data blocks.