Data compression system based on tree models

• US 20050171962A1
• Filed: 04/09/2004
• Published: 08/04/2005
• Est. Priority Date: 01/29/2004
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Weinberger, Marcelo, Seroussi, Gadiel, Martin, Alvaro
• Granted Patent: US 7,265,692 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

1. A method for encoding a sequence into a concatenated string, comprising:

building a suffix tree of the sequence in reverse order;

pruning the suffix tree to form a generalized context tree (GCT) having a plurality of states;

obtaining a binary representation of a full tree derived from the GCT;

encoding the sequence into a binary string using a dynamic tree model based on statistics collected at the plurality of states of the GCT; and

concatenating the binary representation of the full tree with the binary string to form the concatenated string.

2. The method of claim 1, further comprising:

building a finite state machine (FSM) closure of the GCT to form an FSM closed tree subsequent to said pruning.

3. The method of claim 2, wherein encoding the sequence into a binary string using a dynamic tree model based on statistics collected at the plurality of states of the GCT comprises encoding the sequence into a binary string using states in the GCT transitioning with the FSM closed tree.

4. The method of claim 1, wherein pruning the suffix tree to form the GCT comprises using a cost function to prune the suffix tree, wherein the cost function is associated with nodes of the suffix tree.

5. The method of claim 4, wherein using the cost function includes determining an overall cost, and wherein the overall cost reflects a combined length of code obtained by encoding the sequence with the full tree and corresponding dynamic tree model, and length of the binary representation of the full tree.

6. The method of claim 2, wherein building the FSM closure of the GCT comprises adding suffix links to the GCT.

7. The method of claim 1, wherein the encoding comprises employing a Krichevsky-Trofimov (KT) probability assignment.

8. The method of claim 1, wherein the sequence is encoded into the binary string using an arithmetic encoder.

9. A method for encoding a sequence into a concatenated string, comprising:

building a suffix tree of the sequence in reverse order;

pruning the suffix tree to form a generalized context tree (GCT) having a plurality of states;

building a finite state machine (FSM) closure of the GCT to form an FSM closed GCT;

obtaining a binary representation of a full tree derived from the GCT;

encoding the sequence into a binary string using a dynamic tree model based on statistics collected at the plurality of states of the GCT;

transitioning to a next state of the GCT with the FSM closed GCT; and

concatenating the binary representation of the full representation of the full tree with the binary string to form the concatenated string.

10. The method of claim 9, wherein transitioning comprises transitioning from a first state to a second state in the GCT.

11. The method of claim 9, wherein building the FSM closure of the GCT comprises adding suffix links to the GCT.

12. The method of claim 9, wherein transitioning states in the GCT employ statistics recursively collected from respective state descendants in the suffix tree.

13. The method of claim 9, wherein the sequence is encoded into the binary string using an arithmetic encoder.

14. The method of claim 9, wherein pruning the suffix tree to form the GCT comprises using a cost function to prune the suffix tree, wherein the cost function is associated with nodes of the suffix tree.

15. The method of claim 14, wherein using the cost function includes determining an overall cost, and wherein the overall cost reflects a combined length of code obtained by encoding the sequence with the full tree and corresponding dynamic tree model, and length of the binary representation of the full tree.

16. A method for decoding a binary string comprising a binary representation of a full tree having a plurality of states associated therewith and an encoded string produced by a corresponding encoder using a dynamic tree model based on the full tree, comprising:

building a finite state machine (FSM) closure of the full tree;

iteratively decoding at least one symbol using the dynamic tree model of the corresponding encoder based on statistics collected at the plurality of states of the full tree; and

transitioning to a next state of the full tree using the FSM closed full tree.

17. The method of claim 16, wherein building the FSM closure of the full tree comprises adding suffix links to the full tree.

18. The method of claim 16, wherein the binary string is received in the form of the full tree in combination with a set of additional bits for all nodes of the full tree indicating whether the nodes of the full tree are nodes of a generalized context tree obtained by intersecting the full tree with the suffix tree of a reversed sequence of symbols represented by the binary string.

19. A method for decoding a binary string, the binary string comprising a binary representation of a generalized context tree (GCT) and an encoded string produced by a corresponding encoder using a dynamic tree model based on the GCT, the GCT having a plurality of states associated therewith, comprising:

building a decoding GCT based on the binary representation of the GCT;

building a finite state machine (FSM) closure of the decoding GCT;

iteratively decoding at least one symbol using the dynamic tree model of the corresponding encoder based on statistics collected at the plurality of states of the decoding GCT; and

transitioning to a next state of the decoding GCT using the FSM closed decoding GCT.

20. The method of claim 19, wherein the previous symbol is decoded by an arithmetic decoder.

21. A method for decoding a binary string, said binary string comprising a binary representation of a full tree and an encoded string produced by a corresponding encoder using a dynamic tree model based on the full tree, the full tree having a plurality of states associated therewith, comprising:

building a decoding full tree based on the binary representation of the full tree;

creating a reduced generalized context tree (GCT) and mapping the reduced GCT to the decoding full tree;

building a finite state machine (FSM) closure of the reduced GCT;

iteratively decoding at least one symbol using the dynamic tree model of the corresponding encoder based on statistics collected at the plurality of states of the decoding full tree; and

transitioning to a next state of the decoding full tree using the FSM closed reduced GCT.

22. The method of claim 21, wherein mapping the reduced GCT to the decoding full tree creates a jump structure.

23. The method of claim 22, further comprising updating the jump structure after said creating and mapping.

24. The method of claim 21, wherein said iteratively decoding comprises determining a state in the decoding full tree based on a corresponding state in the FSM closure of the reduced GCT using the jump structure.

25. A method for decoding a binary string, said binary string comprising a binary representation of a full tree and an encoded string produced by a corresponding encoder using a dynamic tree model based on the full tree, the full tree having a plurality of states associated therewith, comprising:

building a decoding full tree based on the binary representation of the full tree;

creating a reduced generalized context tree (GCT);

building a finite state machine (FSM) closure of the reduced GCT;

iteratively decoding at least one symbol using the dynamic tree model of the corresponding encoder based on statistics collected at the plurality of states of the decoding full tree;

transitioning to a next state of the decoding full tree using the FSM closed GCT; and

adding encountered states from the decoding full tree and suffixes thereof to the FSM closure of the reduced GCT.

26. The method of claim 25, wherein transitioning to a next state comprises incrementing the FSM reduced closed GCT with new nodes.

27. The method of claim 25, wherein said iteratively decoding comprises determining a state in the GCT based on a corresponding state in the FSM closure of the incremented reduced tree representation.

28. The method of claim 25, further comprising verifying states and suffixes thereof added are missing from the incremented FSM closed reduced GCT.

29. The method of claim 25, wherein adding states thereof comprise adding a new node below an existing node and splitting at least one edge departing from the existing node.

30. A method for decoding a binary string ty, formed by concatenating binary strings t and y into a resultant string x, said binary string ty comprising a binary representation t of a tree T and an encoded string y produced by a corresponding encoder using a dynamic tree model based on the tree T, comprising:

building tree T based on the binary representation t;

setting the resultant string x to an empty string;

iteratively decoding at least one symbol using the dynamic tree model of the corresponding encoder based on statistics collected at a state given by a longest ancestor of reversed resultant string x originally in T;

filling the resultant string x with decoded symbols; and

inserting the reversed resultant string x in the tree T.