Order preserving run length encoding with compression codeword extraction for comparisons
US5629695A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Jun 6, 1995 |
| Grant date | May 13, 1997 |
| Priority date | — |
| Expiry date | Jun 6, 2015 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99937
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The present invention provides a system and method for the dictionary ordering of keys after expansion, compression and concatenation of their key parts. After each key part has been expanded through padding, each substring of identical characters of length greater than or equal to three is compressed through run-length encoding algorithm. The substring is replaced by the sequence character, a compression identifying character and a number identifying the number of characters being replaced. After compression and the subsequent concatenation, the keys are compared character by character. At the first instance of a miscomparison, the comparison scheme performs a normal dictionary ordering if neither of the characters are part of a compression sequence. If a character at the point of miscomparison is part of a compression sequence then an ordering decision is made based on the compression character, the length of the compressed substring and the character following the compressed substring.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.