Patent ID: 6762699
Filing Date: 2004-07-13
Classification: H03M

Abstract:
A method of sequentially transforming an original data sequence comprising a plurality of symbols into an irreducible grammar from which the original data can be recovered incrementally, wherein the irreducible grammar is represented by a set of production rules which are formed using from a set of variables representing non-overlapping repeated patterns in the data sequence, the method comprising the steps of:(a) parsing a substring from the sequence, wherein the substring is a longest prefix of a string of previously unparsed symbols of the sequence that can be represented by a variable within the set of variables of a previous irreducible grammar other than one of a first variable of the set of variables and a first symbol of the string of the previously unparsed symbols in the sequence; (b) generating an admissible grammar based on the substring and the previous irreducible grammar; (c) applying at least one of a set of reduction rules to the admissible grammar to generate the irreducible grammar; (d) repeating steps (a) through (c) until all of the symbols of the sequence are represented by the irreducible granmmar.