System and method for compressed level-ordered edge sequence encoding

Patent metadata

Field	Value
Publication number	US-9876638-B2
Application number	US-201213531290-A
Country	US
Kind code	B2
Filing date	Jun 22, 2012
Priority date	Jun 22, 2012
Publication date	Jan 23, 2018
Grant date	Jan 23, 2018

Abstract

Compressed Level-Ordered Edge Sequence (CLOES) encodings are described. These techniques enable more aggressive compression of a state-set representation.

First claim

What is claimed is:

1. A method for encoding state sets comprising:
encoding, by an electronic computing device, a prefix tree representation of a set of states as a level ordered edge sequence (LOES) which encodes each inner tree node from left to right, and top to bottom order as bit pairs;
identifying, by the electronic computing device, a presence of a complete subtree having a root node within the prefix tree;
denoting, by the electronic computing device, the root node of the subtree using a special two-bit code-point inserted in the encoding to represent the complete subtree within the prefix tree; and
compressing the encoding by pruning the complete subtree.

2. The method as set forth in claim 1 wherein the special code-point is “00”.

3. The method as set forth in claim 1 wherein the pruning comprises pruning the complete subtree, except for its root node, from the prefix tree.

4. The method as set forth in claim 1 wherein the prefix tree is based on a pattern database.

5. A system configured to encode state sets comprising:
an electronic computing device having a memory storage and an electronic processor, wherein the electronic processor is configured to:
encode a prefix tree representation of a set of states as a level ordered edge sequence (LOES) which encodes each inner tree node from left to right, and top to bottom order as bit pairs;
identify a presence of a complete subtree having a root node within the prefix tree;
denote the root node of the subtree using a special two-bit code-point inserted in the encoding to represent the complete subtree within the prefix tree; and
compress the encoding by pruning the complete subtree.

6. The system as set forth in claim 5 wherein the special code-point is “00”.

7. The system as set forth in claim 5 wherein the electronic computing device is operative to prune the complete subtree, except for its root node, from the prefix tree.

8. The system as set forth in claim 5 wherein the prefix tree is based on a pattern database.

9. A method for decoding state sets comprising:
decoding by an electronic computing device, a level ordered edge sequence (LOES) code for a binary prefix tree of a set of states;
identifying, by the electronic computing device, a presence of a special, inserted two-bit code-point denoting a root node of, and representing, a complete subtree within the prefix tree;
returning, by the electronic computing device, a success result indicating a presence of the subtree of the prefix tree based on the identifying of the presence of the code-point; and
constructing, by the electronic computing device, the complete subtree in an implicit or explicit manner.

10. The method as set forth in claim 9 wherein the special code-point is “00”.

11. The method as set forth in claim 9 wherein the prefix tree is based on a pattern database.

12. A system configured to decode state sets comprising:
an electronic computing device having a memory storage and an electronic processor, wherein the electronic processor is configured to:
decode a level ordered edge sequence (LOES) code for a prefix tree representing a set of states;
identify a presence of a special, inserted two-bit code-point denoting a root node of, and representing, a complete subtree within the prefix tree;
return a success result indicating a presence of the subtree of the prefix tree based on the identifying of the presence of the code-point; and
construct the complete subtree in an implicit or explicit manner.

13. The system as set forth in claim 12 wherein the special code-point is “00”.

14. The system as set forth in claim 12 wherein the prefix tree is based on a pattern database.

Assignees

• Zhou Rong
• Schmidt Tim C
• Palo Alto Res Ct Inc

Inventors

• Zhou Rong
• Schmidt Tim C

Classifications

• G06F16/9027

  Trees · CPC title

• H03M7/00

  Conversion of a code where information is represented by a given sequence or number of digits to a code where the same {, similar or subset of} information is represented by a different sequence or number of digits · CPC title

• G06F16/322

  Trees · CPC title

• G06F16/90344

  by using string matching techniques · CPC title

• H04L9/00

  {Cryptographic mechanisms or cryptographic} arrangements for secret or secure communications; Network security protocols · CPC title