Method and means for character string pattern matching for compression and the like using minimal cycles per character
US5525982A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 15, 1994 |
| Grant date | Jun 11, 1996 |
| Priority date | — |
| Expiry date | Apr 15, 2014 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T9/005
- WIPO fieldBasic communication processes
- WIPO sectorElectrical engineering
Abstract
A method and means for ascertaining maximal length pattern matches of K characters per cycle between character strings in a reduced amount of time using a pipeline like concurrent dataflow model in which a recursive exhaustive greedy comparison matching between the strings in consistent direction yields a parsing of the longest matches, the recursion being constrained by relations among K, the match length L, and a tracking variable J, said constraints governing further recursions ascertaining prefix extensions from one string to another and any intra-string pattern matches. Embodiments processing K equal to one, two, or three characters at a time are disclosed.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.