Browse Prior Art Database

Performance enhancement on pattern matching algorithms by minimizing pattern lookup

IP.com Disclosure Number: IPCOM000013552D
Original Publication Date: 2000-Aug-01
Included in the Prior Art Database: 2003-Jun-18
Document File: 1 page(s) / 37K

Publishing Venue

IBM

Abstract

Performance enhancement on pattern matching algorithms by minimizing pattern lookup

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 78% of the total text.

Page 1 of 1

Performance enhancement on pattern matching algorithms by minimizing pattern

lookup

Disclosed is a method of improving performance during compression of datastreams when pattern-matching algorithms are used.

Data streams are often optimized using compression algorithms. An example of this is in images that are commonly transferred over the internet. There are several common compression formats that are used for images. Many of these compression algorithms use the concept of searching for repeating patterns of bits or bytes.

Hashing, which is a common programming practice for storing/searching/retrieving these patterns can cause the compression/decompression algorithm to run slowly. Each unique pattern in the bit stream will be stored. For every bit in the datastream, the hashtable needs to be searched for the current pattern.

In most data streams, there are likely a few small patterns that are very pervasive and occur in multiples to make up larger patterns. The simplest case of this is in a single-bit binary data stream. Strings of continuous zeros or continuous ones of varying lengths can occur throughout the datastream. In a more complex case, a picture that has a solid blue background with have many sequences of varying length of the "blue" color pattern.

The disclosed solution determines certain patterns that fit the criteria described in the section above. For these patterns, a fast-access array is created that is based on the number of contiguous repetitio...