US5649151A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient method and apparatus for access and storage of compressed data
Assignee: Apple Inc
•
Filing: 1995-05-26
•
Granted: 1997-07-15
•
Expires: 2015-05-26
Abstract
Abstract Storage and access of compressed data via separately compressed and stored fixed size logical blocks. An original uncompressed data file is divided into fixed-size logical blocks and then separately compressed thus resulting in a compressed block of data of a generally known maximum size according to a compression ratio known in advance of the actual compression. After the uncompressed fixed-size logical block has been compressed into a maximum fixed-size logical block it is stored into space allocated to it. Furthermore, a table is built correlating the original uncompressed fixed-size logical block to the sectors allocated for each maximum fixed-size compressed logical block thus providing a mapping between the original uncompressed data file and the physical location on the storage device. Alternatively, because the compression ratio is known and because the size of the uncompressed fixed-size logical blocks is known, the resulting maximum size of the compressed logical blocks is generally known. Therefore, the maximum number of sectors allocated to each logical block is known and can thus provide the necessary mapping between uncompressed logical blocks and compressed data stored in sectors of a magnetic disk.
Inventors
- 👤 Ke-Chiang Chu
- 👤 Calvin K. Y. Lum
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-07 08:02
CPC Classifications
G; G06; G06F; G06F3/00; G06F3/06; G06F3/0601; G06F3/0602; G06F3/061; G06F3/0628; G06F3/0629; G06F3/0631; G06F3/0638; G06F3/064; G06F3/0668; G06F3/0671; G06F3/0673; G06F3/0674; G06F3/0676; G11; G11B; G11B20/00; G11B20/00007; G11B27/00; G11B27/10; G11B27/102; G11B27/105; G06F2212/00; G06F2212/40; G06F2212/401; G11B2220/00; G11B2220/20
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
174 words
An improved method of data storage and access in a storage medium divisible into separately addressable segments, said improved data storage and access method comprising the following steps: a) dividing an uncompressed data file into logical blocks of a predetermined size; b) obtaining a compression ratio of said uncompressed data file; c) allocating as many said storage medium segments as indicated by said compression ratio and said storage medium segment size; d) compressing each said logical block of said data file; e) storing each said compressed logical block of said data file into said allocated storage medium segments; f) for each said uncompressed logical block of said data file, mapping said uncompressed logical block of said data file to said storage medium segments containing said compressed logical block of said uncompressed logical block of said data file, said mapping providing an access correlation between each said uncompressed logical block of said data file and each said storage medium segment containing said compressed logical block of each said uncompressed logical block of said data file.
Claim 2
Dependent Claim
174 words
An improved method of data storage and access in a storage medium divisible into separately addressable segments, said improved data storage and access method comprising the following steps: a) dividing an uncompressed data file into logical blocks of a predetermined size; b) obtaining a compression ratio of said uncompressed data file; c) allocating as many said storage medium segments as indicated by said compression ratio and said storage medium segment size; d) compressing each said logical block of said data file; e) storing each said compressed logical block of said data file into said allocated storage medium segments; f) for each said uncompressed logical block of said data file, mapping said uncompressed logical block of said data file to said storage medium segments containing said compressed logical block of said uncompressed logical block of said data file, said mapping providing an access correlation between each said uncompressed logical block of said data file and each said storage medium segment containing said compressed logical block of each said uncompressed logical block of said data file.
Claim 3
Dependent Claim
27 words
The improved data storage and access method of claim 1 wherein the step of obtaining a compression ratio is accomplished by reading information accompanying said data file.
Claim 4
Dependent Claim
32 words
The improved data storage and access method of claim 1 wherein the step of obtaining a compression ratio is accomplished by analysis of data of a type similar to said data file.
Claim 5
Dependent Claim
55 words
The improved data storage and access method of claim 1 wherein the step of allocating said storage medium segments as indicated by said compression ratio and said storage medium is accomplished in accordance with the following relationship: (said logical block predetermined size/(said storage medium segment size*said compression ratio)) rounded to a next highest whole number.
Claim 6
Dependent Claim
37 words
The improved data storage and access method of claim 4 further including the step of allocating only as many said storage medium segments as are necessary to contain each said compressed logical block of said data file.
Claim 7
Dependent Claim
19 words
The improved data storage and access method of claim 1 wherein said mapping is done during said storage step.
Claim 8
Dependent Claim
20 words
The improved data storage and access method of claim 6 wherein said access correlation is provided via a look-up table.
Claim 9
Dependent Claim
25 words
The improved data storage and access method of claim 7 wherein said predetermined logical block size is in a range of two to four kilobytes.
Claim 10
Dependent Claim
22 words
The improved data storage and access method of claim 8 wherein said storage medium is a magnetic media direct access storage device.
Claim 11
Dependent Claim
25 words
The improved data storage and access method of claim 9 wherein said separately addressable segments are sectors of said magnetic media direct access storage device.
Claim 12
Dependent Claim
111 words
The improved data storage and access method of claim 1 further including the step of if any logical block of said data file does not compress to a degree projected by said obtained compression ratio and causes an overflow condition of said storage medium segments allocated to said logical block of said data file then: i) storing as much of said compressed logical block of said data file into any of said storage medium segments allocated for said compressed logical block of said data file as will fit and storing any remainder of said compressed logical block of said data file into other storage medium segments allocated for said overflow condition.
Claim 13
Dependent Claim
193 words
An improved method of access to a data file compressed and stored in a direct access storage device, said direct access storage device having separately addressable sectors, said improved data file access method comprising the following steps: a) dividing an uncompressed data file into logical blocks of a predetermined size; b) obtaining a compression ratio of said uncompressed data file; c) allocating as many said direct access storage device sectors as indicated by said compression ratio and said direct access storage device sector size; d) compressing each said logical block of said data file; e) storing each said compressed logical block of said data file into said allocated direct access storage device sectors; f) for each said uncompressed logical block of said data file, mapping said uncompressed logical block of said data file to said direct access storage device sectors containing said compressed logical block of said uncompressed logical block of said data file, said mapping providing an access correlation between each said uncompressed logical block of said data file and each said direct access storage device sector containing said compressed logical block of each said uncompressed logical block of said data file.
Claim 14
Dependent Claim
193 words
An improved method of access to a data file compressed and stored in a direct access storage device, said direct access storage device having separately addressable sectors, said improved data file access method comprising the following steps: a) dividing an uncompressed data file into logical blocks of a predetermined size; b) obtaining a compression ratio of said uncompressed data file; c) allocating as many said direct access storage device sectors as indicated by said compression ratio and said direct access storage device sector size; d) compressing each said logical block of said data file; e) storing each said compressed logical block of said data file into said allocated direct access storage device sectors; f) for each said uncompressed logical block of said data file, mapping said uncompressed logical block of said data file to said direct access storage device sectors containing said compressed logical block of said uncompressed logical block of said data file, said mapping providing an access correlation between each said uncompressed logical block of said data file and each said direct access storage device sector containing said compressed logical block of each said uncompressed logical block of said data file.
Claim 15
Dependent Claim
27 words
The improved data storage and access method of claim 12 wherein the step of obtaining a compression ratio is accomplished by reading information accompanying said data file.
Claim 16
Dependent Claim
32 words
The improved data storage and access method of claim 12 wherein the step of obtaining a compression ratio is accomplished by analysis of data of a type similar to said data file.
Claim 17
Dependent Claim
63 words
The improved data storage and access method of claim 12 wherein the step of allocating said direct access storage device sectors as indicated by said compression ratio and said direct access storage device sector size is accomplished in accordance with the following relationship: (said logical block predetermined size/(said direct access storage device sector size*said compression ratio)) rounded to a next highest whole number.
Claim 18
Dependent Claim
39 words
The improved data storage and access method of claim 15 further including the step of allocating only as many said direct access storage device sectors as are necessary to contain each said compressed logical block of said data file.
Claim 19
Dependent Claim
19 words
The improved data storage and access method of claim 12 wherein said mapping is done during said storage step.
Claim 20
Dependent Claim
20 words
The improved data storage and access method of claim 17 wherein said access correlation is provided via a look-up table.
Claim 21
Dependent Claim
25 words
The improved data storage and access method of claim 18 wherein said predetermined logical block size is in a range of two to four kilobytes.
Claim 22
Dependent Claim
117 words
The improved data storage and access method of claim 12 further including the step of if any logical block of said data file does not compress to a degree projected by said obtained compression ratio and causes an overflow condition of said direct access storage device sectors allocated to said logical block of said data file then: i) storing as much of said compressed logical block of said data file into any of said direct access storage device sectors allocated for said compressed logical block of said data file as will fit and storing any remainder of said compressed logical block of said data file into other direct access storage device sectors allocated for said overflow condition.
Claim 23
Dependent Claim
183 words
An improved apparatus for data storage and access in a storage medium divisible into separately addressable segments, said improved data storage and access apparatus comprising: a) means for dividing an uncompressed data file into logical blocks of a predetermined size; b) means for obtaining a compression ratio of said uncompressed data file; c) means for allocating as many said storage medium segments as indicated by said compression ratio and said storage medium segment size; d) means for compressing each said logical block of said data file; e) means for storing each said compressed logical block of said data file into said allocated storage medium segments; f) for each said uncompressed logical block of said data file, means for mapping said uncompressed logical block of said data file to said storage medium segments containing said compressed logical block of said uncompressed logical block of said data file, said mapping providing an access correlation between each said uncompressed logical block of said data file and each said storage medium segment containing said compressed logical block of each said uncompressed logical block of said data file.
Claim 24
Dependent Claim
183 words
An improved apparatus for data storage and access in a storage medium divisible into separately addressable segments, said improved data storage and access apparatus comprising: a) means for dividing an uncompressed data file into logical blocks of a predetermined size; b) means for obtaining a compression ratio of said uncompressed data file; c) means for allocating as many said storage medium segments as indicated by said compression ratio and said storage medium segment size; d) means for compressing each said logical block of said data file; e) means for storing each said compressed logical block of said data file into said allocated storage medium segments; f) for each said uncompressed logical block of said data file, means for mapping said uncompressed logical block of said data file to said storage medium segments containing said compressed logical block of said uncompressed logical block of said data file, said mapping providing an access correlation between each said uncompressed logical block of said data file and each said storage medium segment containing said compressed logical block of each said uncompressed logical block of said data file.
References Cited (Backward Citations)
US4467421A
Cited
US4520506A
Cited
US4782325A
Cited
US5101487A
Cited
US4843389A
Cited
US4996690A
Cited
US4949190A
Cited
US4930142A
Cited
US5126739A
Cited
US5003307A
Cited
US5146221A
Cited
US5016009A
Cited
US5278970A
Cited
US5280600A
Cited
US5148292A
Cited
US5237675A
Cited
US5159678A
Cited
US5237460A
Cited
US5245614A
Cited
US5261049A
Cited
US5281967A
Cited
US5155484A
Cited
US5305295A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-14 | 2001-01-13 | 2001-07-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-14 | 2005-01-13 | 2005-07-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-14 | 2009-01-13 | 2009-07-15 | $7700.00 | Window Closed / Lapsed |