Method of storing and retrieving miniaturized data

• US 7,185,018 B2
• Filed: 12/21/2000
• Issued: 02/27/2007
• Est. Priority Date: 12/23/1999
• Status: Expired due to Fees

• Current Assignee: ZENtronix Pty Ltd. (WindSpring, Inc.)
• Original Assignee: ZENtronix Pty Ltd. (WindSpring, Inc.)
• Inventors: Archbold, John, Mele, Graziano
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US10/168,439
• Publication Number:
  US 20030093418A1
• Time in Patent Office: 2,259 Days
• Field of Search: 707/3, 707/101, 707/102, 707/103.R, 709/203, 715/532, 382/232
• US Class Current: 707/693
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of storing data including the steps of providing a first index of first location identifiers, a second index of second location identifiers and a dictionary data base of data items, wherein the first location identifiers are adapted to identify the location of second location identifiers in the second index and the second location identifiers are adapted to identify the location of data items in the dictionary data base, receiving data and separating the data into a plurality of data items and storing the data items in a main data base, whereby at least one of the data items is stored in the main data base as at least one first location identifier, which identifies at least one second location identifier, which identifies the or each data item in the dictionary data base.

Claims

1. Using a data processor according to a sequence of instructions adapted to control the data processor, a method of compressing a dataset comprising:

generating a dictionary database of data items from which data items of the dataset can be represented, wherein the dictionary database is readable by the data processor;

allocating storage for a plurality of first location identifiers readable by the data processsor, wherein the dataset can be represented in compressed form by the plurality of first location identifiers and zero or more exception sequences not represented in the dictionary database;

allocating storage for an identifier index comprising a plurality of second location identifiers readable by the data processor, wherein each second location identifier identifies a location in the dictionary database;

reading the dataset using the data processor;

parsing the dataset into a plurality of data items using the data processor;

generating the plurality of first location identifiers and the plurality of second location identifiers from the dataset such that each of the plurality of first location identifiers points to a location in the identifier index and each of the second location identifiers points to a location in the dictionary database, to thereby form a compressed dataset comprising at least the dictionary database, the identifier index and a sequence of items representing the dataset, the sequence comprising an ordered set of items, wherein each item is a first location identifier when the item is represented in the dictionary database and is an exception sequence corresponding to data of the dataset when the data of the dataset is not represented in the dictionary database.

2. The method as claimed in claim 1, further comprising:

scanning the compressed dataset to identify exception sequences that are not present in the dictionary database;

adding a dictionary database entry for at least one exception sequence in the compressed dataset; and

replacing, in the sequence of items representing the dataset, the at least one exception sequence with a first location identifier that points to a second location identifier that in turn points to the added dictionary database entry.

3. The method as claimed in claim 1, wherein data items include one or more of a string of data, a field of data or other group of data that can represent information in a predetermined format.

4. The method as claimed in claim 1, wherein data items represent streams of data that can be searched.

5. The method as claimed in claim 1, wherein the dictionary database includes a plurality of databases and wherein at least some of the first location identifiers point to locations to second location identifiers that point within more than one of the plurality of databases, thereby allowing for dictionary substitution without requiring modifications to the identifier index.

6. The method as claimed in claim 1, wherein the first location identifiers are pointers that have values indicative of an index number into the identifier index.

7. The method as claimed in claim 1, wherein the second location identifiers are pointers that have values indicative of an index number into the dictionary database wherein an initial symbol of a pointed-to data item resides.

8. The method as claimed in claim 1, further comprising reconstructing the dataset from the compressed dataset using a reverse look-up process that uses the compressed dataset'"'"'s dictionary database, identifier index and sequence of items representing the dataset, the sequence comprising an ordered set of items, wherein each item is a first location identifier when the item is represented in the dictionary database and is an exception sequence corresponding to data of the dataset when the data of the dataset is not represented in the dictionary database.