Method and apparatus for finding longest and closest matching string in history buffer prior to current string

• US 5,577,248 A
• Filed: 06/06/1995
• Issued: 11/19/1996
• Est. Priority Date: 09/13/1991
• Status: Expired due to Term

• Current Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Original Assignee: Salient Software, Inc.
• Inventors: Chambers, Lloyd L. IV
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/468,923
• Time in Patent Office: 532 Days
• Field of Search: 395/600, 341/51, 341/67, 341/106
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 40/12 Use of codes for handling textual entities
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/008 Vector quantisation
• CPC Class Codes: G06V 10/768 using context analysis, e.g. recognition aided by known co-occurring patterns
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

The invention provides a method and apparatus for finding a longest and closest matching string in a history buffer prior to a current string. A search algorithm in accordance with the invention first tries to find the longest matching old string (MOS) in the history buffer as its major task, and in a case where two MOS'"'"'s are found to have the same longest matching length, the search algorithm tries to select the MOS closest to the current position as its minor task. Linked lists are constructed as searching progresses to speed the search process. The linked lists define a fast-path array which points to all locations within the history buffer containing a specified code sequence. Pointers to locations outside the history buffer are optionally removed and their space returned to memory free space.

Claims

1. An apparatus, operatively couplable to a pre-specified, responsive data processing machine, for defining and conveying instructions to the data processing machine upon coupling therewith, where said machine includes memory means for storing data in identifiable locations thereof;

said couplable instruction defining and conveyance apparatus comprising;

a plurality of instruction means for instructing the data processing machine to perform operations, the plurality of instruction means including;

(a) first means for instructing said machine to specify as current, a particular location within the memory means;

(b) second means for instructing said machine to allocate space within the memory means for storing one or more historical data strings; and

(c) third means for instructing said machine to create within the memory means, a fast-path portion storing groups of one or more history pointers, where each group is dedicated to a respective one of a prespecified plurality of unique code sequences and the one or more history pointers of that group respectively point to and identify a corresponding one or more locations within the memory means that store one or more of the historical data strings, if any, which contain the respective one of the prespecified plurality of unique code sequences to which the corresponding group is dedicated and, in cases where more than one of the identified historical data strings has the same prespecified sequence of code, for arranging the history pointers of the corresponding group to indicate the positional order of the more than one identified historical data strings relative to the current location so that it can be quickly determined from said arrangement of the history pointers whether a first history location that stores a corresponding first of the identified historical data strings is address-wise closer to or further from the current location than is a second history location that stores a corresponding second of the identified historical data strings.

2. An instruction defining and conveyance apparatus according to claim 1 further comprising a recording medium, wherein said plurality of instruction means are defined as instructional signals recorded on the recording medium.

3. An instruction defining and conveyance apparatus according to claim 2 wherein the recording medium is selected from the group consisting of:

a magnetically-encoded disk, an optically-encoded disk, a magnetic tape, and a read-only memory device.

4. An apparatus according to claim 2 further comprising instruction signal conveying means, engageable with the plurality of instruction means and couplable to the instructable data processing machine, for supplying instructions to the instructable data processing machine as electrical or optical signals.

5. An apparatus according to claim 4 wherein the instruction signal conveying means includes means selected from the group consisting of:

a disk drive, a tape drive and a ROM cartridge reader.

6. An apparatus for storing and conveying data to a pre-specified, data processing machine, where said data storage and conveyance apparatus has physical attributes organized to represent data to be conveyed to the data processing machine and the to-be-conveyed data includes a plurality of vectors each generated by the following data processing method:

(a) storing a plurality of data strings within memory;

(b) identifying one or more of the data strings that start with a prespecified code sequence;

(c) in cases where more than one of the identified data strings has the same prespecified sequence of code, indicating the relative positional order of the more than one identified data strings within the memory;

wherein said steps of (b) identifying one or more of the data strings and (c) indicating the relative positional order, include;

(b.1) identifying a position within said memory as a current position; and

(c.1) creating a fast-path array in said memory where the fast-path array includes one or more lists each associated with a unique prespecified code sequence;

where each list contains a head record pointing to an instance of its associated unique code sequence which is closest to the current position;

said method further comprising the steps of;

(d) supplying a current data string having at least first and second codes and using the first and second current data string codes to specify an index-pair code;

(e) converting the index-pair code into a head-record pointer that points to a corresponding head record within the fast-path array;

(f) using the corresponding head record to locate the instance of the associated unique code sequence which is closest to the current position; and

generating a vector representing an offset from the current location to the located instance of the associated unique code sequence.

7. A data storage and conveyance apparatus according to claim 6 wherein, for the underlying vector generating method, the step (f) of using the corresponding head record to locate the instance of the associated unique code sequence which is closest to the current position is followed by the step of:

(f.1) using the corresponding head record and/or subsequent records following the head record to locate within the memory one or more instances of the associated unique code sequence which first match the current string to a maximum extent and thereafter, if two or more such maximum-extent instances are located, to locate the that maximum-extent instance which is closest to the current position.

8. A data storage and conveyance apparatus according to claim 7 wherein the generated vector is a compression vector for replacing the matched current string, the generated compression vector consists of fewer bits than that portion of the current string which it replaces and said data processing method is part of a data compression method that generates plural compression vectors.