Data compression system based on tree models

Details Data compression system based on tree models Data compression system based on tree models

2007-09-04

2007-09-04

Barnie, Rexford (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

To or from code based on probability

C707S793000

Reexamination Certificate

active

10821524

ABSTRACT:
A method for encoding and decoding a sequence is provided. The method comprises searching a set of candidate trees varying in size for a tree T having a plurality of states. Tree T provides a structure that relatively minimizes code length of the sequence from among all the candidate trees. The method further comprises encoding data conditioned on the tree T, which may be a generalized context tree (GCT), using a sequential probability assignment conditioned on the states of the tree T. This encoding may use finite state machine (FSM) closure of the tree. Also provided are methods for decoding an encoded binary string when the encoded string includes a full tree or generalized context tree, as well as decoding an encoded string using incomplete FSM closure, incremental FSM, and suffix tree construction concepts.

REFERENCES:
patent: 6401088 (2002-06-01), Jagadish et al.
patent: 7028042 (2006-04-01), Rissanen
Alvaro Martin, et al., “Linear Time Universal Coding and Time Reversal of Tree Sources via FSM Closure,” HPL-2003-87, Apr. 2003.
R. Giegerich and S. Kurtz, “From Ukkonen to McCreight and Weiner: A unifying view to linear-time suffix tree construction,” Algorithmica, vol. 19, pp. 331-353, Nov. 1997.

Affiliated with

Also associated with

Rating

Data compression system based on tree models does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Data compression system based on tree models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression system based on tree models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3783595