Patent US5564045A successfully refreshed from Google Patents.
US5564045A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for string searching in a linked list data structure using a termination node at the end of the linked list
Assignee: Motorola Solutions Inc
•
Filing: 1994-07-28
•
Granted: 1996-10-08
•
Expires: 2014-07-28
Abstract
Abstract A method and device provide a unique and efficient scheme for utilizing a linked list data structure for encoding and decoding user data, thereby improving the efficiency and speed of data communication. In addition, processor use for computation is minimized, throughput delay is minimized, and throughput performance is maximized in a data communication system.
Inventors
- 👤 Frank Fulling
- 👤 Wayne M. DeMello
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 15:27
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3088; G; G06; G06T; G06T9/00; G06T9/005; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
276 words
An efficient string searching method in a data compression system for efficiently using and maintaining a linked list data structure for input characters, comprising the steps of: A) searching a sequentially linked list; B) checking a character field of each node in the linked list for a match with an input character; C) utilizing repetitive logic to check each node for a match and in the case of a non-match, moving sequentially to a next node to continue searching, and where selected, checking for a condition which indicates an end of the linked list; D) providing a termination node at an end of the linked list, wherein the termination node is initialized to contain a character in the character field that is larger than a predeterminimed maximum number of input characters, to provide for a potential match condition check to be sufficient in terminating the search logic; E) One Of E1-E2: E1) terminating when a node is found that contains a character in the character field which is greater than or equal to the input character; and E2) using, when a no match results from the search operation, the input character to provide a new node which is added to the linked list being searched in a lexicographical order wherein the new node is added as one of: a first node in the list and between the first node and a last node in the list using unique logic for modifying links to add the new node; F) deleting, when the new node is added, another node by checking consecutive nodes until a leaf node is found and deleting the leaf node from its linked list.
Claim 2
Dependent Claim
276 words
An efficient string searching method in a data compression system for efficiently using and maintaining a linked list data structure for input characters, comprising the steps of: A) searching a sequentially linked list; B) checking a character field of each node in the linked list for a match with an input character; C) utilizing repetitive logic to check each node for a match and in the case of a non-match, moving sequentially to a next node to continue searching, and where selected, checking for a condition which indicates an end of the linked list; D) providing a termination node at an end of the linked list, wherein the termination node is initialized to contain a character in the character field that is larger than a predeterminimed maximum number of input characters, to provide for a potential match condition check to be sufficient in terminating the search logic; E) One Of E1-E2: E1) terminating when a node is found that contains a character in the character field which is greater than or equal to the input character; and E2) using, when a no match results from the search operation, the input character to provide a new node which is added to the linked list being searched in a lexicographical order wherein the new node is added as one of: a first node in the list and between the first node and a last node in the list using unique logic for modifying links to add the new node; F) deleting, when the new node is added, another node by checking consecutive nodes until a leaf node is found and deleting the leaf node from its linked list.
Claim 3
Dependent Claim
127 words
A string searching method in a data compression system for efficiently using and maintaining a linked list data structure for input characters, comprising the steps of: A) inserting a termination node in a memory unit wherein the termination node is initially linked to every root node of the memory unit, B) utilizing a termination node-based novel scheme for simplifying a string-searching process in a processor wherein processing is minimized and throughput performance is maximized wherein the termination node-based novel scheme includes utilizing the termination node for determining a potential match in a linked list, adding a new node prior to the termination node, and determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure.
Claim 4
Dependent Claim
127 words
A string searching method in a data compression system for efficiently using and maintaining a linked list data structure for input characters, comprising the steps of: A) inserting a termination node in a memory unit wherein the termination node is initially linked to every root node of the memory unit, B) utilizing a termination node-based novel scheme for simplifying a string-searching process in a processor wherein processing is minimized and throughput performance is maximized wherein the termination node-based novel scheme includes utilizing the termination node for determining a potential match in a linked list, adding a new node prior to the termination node, and determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure.
Claim 5
Dependent Claim
32 words
The string searching method of claim 2 wherein the termination node-based novel scheme includes, wherein the next leaf node is a non-termination node, deleting the leaf node prior to the termination node.
Claim 6
Dependent Claim
24 words
The string searching method of claim 2 wherein the termination node-based novel scheme includes utilizing the termination node to force an immediate no-match condition.
Claim 7
Dependent Claim
39 words
The string searching method of claim 2 wherein the termination node-based novel scheme includes, in a data compression system, utilizing the termination node for detecting loss of synchronization between an encoder and a decoder of the data compression system.
Claim 8
Dependent Claim
161 words
A string searching device in a processor for processing input characters and efficiently using and maintaining a linked list data structure, comprising: A) a termination node inserter for determining a termination node in a memory unit wherein the termination node is positioned at an end of a string-searching data structure to provide for a leaf node as a last node in the data structure for facilitating string-searching wherein determining includes utilizing the termination node for determining a potential match in a linked list, adding a new node prior to the termination node, and determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure, and B) a termination node linker, operably coupled to the termination node inserter and to the memory unit, for linking the termination node to a string-searching data structure for simplifying a string-searching process in a processor wherein processing is minimized and throughput performance is maximized.
Claim 9
Dependent Claim
161 words
A string searching device in a processor for processing input characters and efficiently using and maintaining a linked list data structure, comprising: A) a termination node inserter for determining a termination node in a memory unit wherein the termination node is positioned at an end of a string-searching data structure to provide for a leaf node as a last node in the data structure for facilitating string-searching wherein determining includes utilizing the termination node for determining a potential match in a linked list, adding a new node prior to the termination node, and determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure, and B) a termination node linker, operably coupled to the termination node inserter and to the memory unit, for linking the termination node to a string-searching data structure for simplifying a string-searching process in a processor wherein processing is minimized and throughput performance is maximized.
Claim 10
Dependent Claim
42 words
The string searching device of claim 6 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for utilizing the termination node for determining a potential match in a linked list.
Claim 11
Dependent Claim
43 words
The string searching device of claim 6 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for utilizing the termination node for adding a new node prior to the termination node.
Claim 12
Dependent Claim
52 words
The string searching device of claim 6 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure.
Claim 13
Dependent Claim
47 words
The string searching device of claim 6 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for, wherein the next leaf node is a non-termination node, deleting the leaf node prior to the termination node.
Claim 14
Dependent Claim
39 words
The string searching device of claim 6 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for utilizing the termination node to force an immediate no-match condition.
Claim 15
Dependent Claim
54 words
The string searching device of claim 6 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for, in a data compression system, utilizing the termination node for detecting loss of synchronization between an encoder and a decoder of the data compression system.
Claim 16
Dependent Claim
181 words
A data communications system comprising a plurality of data communications equipment, each having a string searching device in a processor for processing input characters from a transmitter of another data communications equipment and efficiently using and maintaining a linked list data structure, the string searching device comprising: A) a termination node inserter for determining a termination node in a memory unit wherein the termination node is positioned at an end of a string-searching data structure to provide for a leaf node as a last node in the data structure for facilitating string-searching, wherein determining includes utilizing the termination node for determining a potential match in a linked list, adding a new node prior to the termination node, and determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure and B) a termination node linker, operably coupled to the termination node inserter, for linking the termination node to a string-searching data structure for simplifying a string-searching process in a processor wherein processing is minimized and throughput performance is maximized.
Claim 17
Dependent Claim
181 words
A data communications system comprising a plurality of data communications equipment, each having a string searching device in a processor for processing input characters from a transmitter of another data communications equipment and efficiently using and maintaining a linked list data structure, the string searching device comprising: A) a termination node inserter for determining a termination node in a memory unit wherein the termination node is positioned at an end of a string-searching data structure to provide for a leaf node as a last node in the data structure for facilitating string-searching, wherein determining includes utilizing the termination node for determining a potential match in a linked list, adding a new node prior to the termination node, and determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure and B) a termination node linker, operably coupled to the termination node inserter, for linking the termination node to a string-searching data structure for simplifying a string-searching process in a processor wherein processing is minimized and throughput performance is maximized.
Claim 18
Dependent Claim
42 words
The data communications equipment of claim 13 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for utilizing the termination node for determining a potential match in a child list.
Claim 19
Dependent Claim
43 words
The data communications equipment of claim 13 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for utilizing the termination node for adding a new node prior to the termination node.
Claim 20
Dependent Claim
52 words
The data communications equipment of claim 13 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for determining a next leaf node and where the next leaf node is the termination node, recycling to a start of the data structure.
Claim 21
Dependent Claim
47 words
The data communications equipment of claim 13 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for, wherein the next leaf node is a non-termination node, deleting the leaf node prior to the termination node.
Claim 22
Dependent Claim
39 words
The data communications equipment of claim 13 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for utilizing the termination node to force an immediate no-match condition.
Claim 23
Dependent Claim
54 words
The data communications equipment of claim 13 wherein the processor further includes a string searching unit, operably coupled to the termination node linker and the termination node inserter, for, in a data compression system, utilizing the termination node for detecting loss of synchronization between an encoder and a decoder of the data compression system.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-10-08 | 2000-04-08 | 2000-10-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-10-08 | 2004-04-08 | 2004-10-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-10-08 | 2008-04-08 | 2008-10-08 | $7700.00 | Window Closed / Lapsed |