Patent ID: 6018303
Filing Date: 2000-01-25
Classification: H03M

Abstract:
A method for compressing source data for transmission to a remote location or to a storage medium, the source data being made up of data units from a first alphabet U, the source data units being mappable on to code data units of a second alphabet V, there being defined a distortion measure indicative of the distortion caused by encoding any given source data unit as any given code data unit, the method comprising the steps of:(a) setting a current string length, l, to an initial value;(b) imputting l data units of source data to generate a current string;(c) searching within at least part of a tree-structured database of code data units for a database substring corresponding within a given non-zero average distortion tolerance level per data unit to said current string, said tree-structured database of code data units being structured as a multi-branch structure in which at least one node has in excess of two nodes branching therefrom;(d) in a case that such a said database substring is found:(i) storing last-find pointer information relating to the location within said database of said database substring which corresponds within said average distortion tolerance level per data unit to said current string.(ii) inputting a next data unit of source data and appending said data unit to said current string such that said current string contains l+1 data units made up of a most recently found string and a most recently added data unit,(iii) incrementing said current string length, l, by 1, and(iv) returning to step (c); and(e) when no such said database substring is found:(i) transmitting a compressed data signal indicative of:(A) said last-find pointer information, and(B) a code data unit corresponding to said most recently added unit of said current string, and(ii) updating said database to include a database substring corresponding within said average distortion tolerance level per data unit to said current string.