Method and apparatus for finding longest and closest matching string in history buffer prior to current string
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
8 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. - View Dependent Claims (2, 3, 4, 5)
- said couplable instruction defining and conveyance apparatus comprising;
-
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. - View Dependent Claims (7, 8)
-
Specification