Image analysis – Image compression or coding
Reexamination Certificate
1997-08-26
2001-05-01
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
C345S428000
Reexamination Certificate
active
06226411
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method for data compression and restoration, an apparatus and a method for sort-merging, and storage media therefor.
2. Description of the Related Art
As a method for compressing data consisting of numeric characters, alphabetic characters, chinese characters and the like, a dictionary type coding system is known. The dictionary type coding system comprises a dictionary that collects coded data corresponding to different character strings each created in a predetermined form. The system uses the dictionary to compress data having the character strings by the registered codes corresponding to the strings stored in the dictionary. The system further compresses data having the same character in series with the use of control characters. This system is required to register character strings each having a predetermined form and to store the strings with corresponding codes in advance. Namely, time and labour are required for making the dictionary. In addition, any character strings that are not registered cannot be compressed. Furthermore, the system requires time for data compression when sequentially retrieving each of the registered characters.
Therefore, a method of data record compression, as disclosed in the Japanese patent publication No. 7-239771, was proposed that dispenses with creation of the dictionary. According to this method, data records in a file, each record having a plurality of fields, can be compressed when fields having the same value exist in the consecutive data records in the data file.
The above method of data record compression vertically compresses a part in which a predetermined number of the same characters consecutively appear in the same field location in the two consecutive data records, and horizontally compresses a part in which a predetermined number of the same characters consecutively appear in the vertically compressed records.
By the way, in general, a sort-merge process is executed when sorting a large amount of data records. The sort-merge process has the steps of, reading a plurality of data records stored in an input file in a storage unit one by one into an input buffer in a memory, transferring the data records stored in the input buffer to a working area in the memory until the working area becomes full, transferring a group of data records transferred to the working area to a temporary buffer after sorting the group of the data records, and transferring the group of data records from the temporary buffer to a temporary file in the storage unit. The sort-merge process repeats the above series of steps for all of the data records to be sorted, then executes the steps of transferring the group of data records having been sorted and stored in the temporary file to each individual temporary buffer in the memory, transferring the data stored in the temporary buffer to a work area in the memory, generating a string of records by merging, and outputs the string of records to an output file.
However, the method of data record compression disclosed in the Japanese patent publication No. 7-239771 can compress two consecutive data records but cannot compress more than that at one time. Therefore the method is inefficient.
On the other hand, the sort-merge process according to the prior art requires a long time for data transmission between the temporary file in the external storage unit and the temporary buffer in the main memory when a large volume of data records are sorted, and the size of data to be stored in the external storage is increased. Thus, the sort-merge processing time is increased and the disc space in the external storage unit cannot be ensured.
SUMMARY OF THE INVENTION
Therefore, it is a first object of the present invention to provide a method for data compression and restoration that improves compression efficiency by compressing a plurality of data records at one time. It is a second object of the present invention to provide an apparatus and a method for sort-merging that decreases processing time due to compression of data to be transferred, thereby ensuring the disc space in the external storage device.
FIG. 1
is an explanatory drawing of a method for data compression according to the present invention.
In order to accomplish the first object, it is considered that a file may include records, in which each record consists of a plurality of columns and is created in a predetermined format as a unit, such as a spread sheet. In general, such a files has a high probability to have the same data in the same column location throughout the records. Thus, it is considered that these column locations can be used for the purpose of data compression.
According to a first aspect of the present invention that achieves the first object, there is provided a method for compressing a file having a plurality of (n) records each consisting of a plurality of (m) columns and created in a predetermined format, comprising the steps of: searching for one or more column locations
2
,
5
, . . . in which the data is the same throughout the records; calculating the number of records which can be compressed in the file based on the number of the found column locations; determining a first record group
1
,
2
, . . . , K consisting of records to be compressed and a second record group (K+1), . . . , n consisting of one or more records to be excluded based on the calculated number of records which can be compressed; determining a first record
1
from the first record group, the first record data being kept the same; memorizing the addresses of the found column locations in a second record
2
selected from the first record group, the second record
2
being different from the first record
1
; and transferring data stored in other column locations
1
,
3
,
4
,
6
, . . . , m in the one or more records (K+1), . . . , n in the second record group to the column locations
2
,
5
, . . . in records
3
,
4
, . . . , K in the first record group except the first
1
and the second
2
records.
According to the first aspect of the present invention, another method is provided for compressing a file having a plurality of records each consisting of a plurality of fields each having at least a column and created in a predetermined format. This other method searches for field locations in which the data is the same throughout the records instead of the column locations.
According to a second aspect of the present invention that achieves the first object, there is provided a method for restoring a compressed file to an original file. The original file has a plurality of (n) records each consisting of a plurality of (m) columns, is created in a predetermined format, and is divided into a first record group
1
,
2
, . . . , K corresponding to the compressed file and a second record group (K+1), . . . , n, to be excluded from the original file. Column locations in which the data is the same are searched for throughout the records in the original file, and the compressed file stores data in the column locations
2
,
5
, . . . in records except a first
1
and a second
2
records. The data in the first record is kept the same, the second record being different from the first record and having been used for memorizing the addresses of the found column locations before the restoration. The data have been originally stored in the other column locations
1
,
3
,
4
,
6
, . . . , m in one or more records (K+1), . . . , n in the second record group of the original file. This method comprises the steps of: transferring data stored in the column locations
2
,
5
, . . . in the records
3
,
4
, . . . , K except the first and the second records in the compressed file to other column locations
1
,
3
,
4
,
6
, . . . , m in the one or more records (K+1), . . . , n in the second record group of the original file; and copying data stored in the column locations
2
,
5
, . . . in the first record
1
in the first record group, in the addresses of the col
Dang Duy N.
Fujitsu Limited
Staas & Halsey , LLP
Tran Phuoc
LandOfFree
Method for data compression and restoration does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for data compression and restoration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for data compression and restoration will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2443486