# US 9,521,082 B2 · Methods and devices for creating, compressing and searching binary tree > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,521,082 B2 - Document ID: US9521082B2 - Status: Granted - Kind: B2 - Application number: 14/213,167 - Filed: 2014-03-14 - Published: 2014-07-17 - Granted: 2016-12-13 - Earliest claimed: 2010-08-24 - Assignees: Huawei Technologies Co., Ltd. - Applicants: Huawei Technologies Co., Ltd. - Inventors: Wenyong Zhang; Hui Wang - Web page: https://patentgrep.com/patent/US9521082B2 ## CPC - H04L 47/2441: relying on flow classification, e.g. using integrated services [IntServ] - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - H03M 7/3066: {by means of a mask or a bit-map} - H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code - H03M 7/6058: {Saving memory space in the encoder or decoder} - H03M 7/707: {Structured documents, e.g. XML} - H04L 45/48: Routing tree calculation - H04L 69/22: Parsing or analysis of headers - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Methods and devices for creating, compressing and searching a binary tree are provided by the present disclosure, which relates to the field of traffic classification. Binary tree compression includes: determining a number of a compression layer or a number of an intermediate node, compressing a binary tree according to the number of the compression layer or the number of the intermediate node to form at least one compression node, and creating a bitmap of the compression node. Therefore, the depth of the decision tree is reduced, the search speed is increased, rule expansion is avoided, and rule replication is reduced. ## Claims ### Claim 1 A computer for compressing a binary tree, comprising: a memory; and a processor coupled with the memory, the processor is configured to perform operations comprising: determining a compression parameter according to a number of bits Nb of data read in one memory access, a number of bits Ni used by a bit index of each intermediate node in intermediate nodes, a number of bits Na used by a start address of sub-nodes of a compression node, a number of bits Nt used by a compression node type, and a number of bits used by a bitmap; compressing the binary tree according to the compression parameter to form the compression node; creating the bitmap of the compression node, wherein the compression parameter is a number n of compressed layers in one compression node, and is determined according to compressed layers in one compression node, and is determined according to n ≤ Log 2 ⁡ ( N b - N a - N t N i + 1 + 1 ) ; applying the bitmap to the binary tree, wherein the binary tree represents a plurality of nodes including the intermediate nodes connected in a tree configuration, and said applying reduces the binary tree into a compressed binary tree with a reduced search depth; and applying the compressed binary tree to a packet classifier for performing routing decision for a packet at each of the plurality of nodes. ### Claim 2 (depends on 1) The computer according to claim 1, wherein the operations of compressing the binary tree according to the compression parameter to form at least one compression node comprises: compressing, starting from a root node of the binary tree, m layers of nodes as a compression node, wherein m is less than or equal to the number n of the compressed layer in one compression node; and continuing to compress the binary tree in the same way as compressing the compression node starting from a sub-node of the compression node until the binary tree is traversed. ### Claim 3 (depends on 1) The computer according to claim 1, wherein the compression parameter is a number K of the intermediate nodes in one compression node, and K is determined according to K ≤ N b - N a - N t + 1 N i + 3 . ### Claim 4 (depends on 3) The computer according to claim 3, wherein compressing the binary tree according to the compression parameter to form at least one compression node comprises: compressing, starting from a root node of the binary tree, nodes including a number T of intermediate nodes as a compression node, wherein the number T is less than or equal to the number K of the intermediate node in one compression node; and continuing to compress the binary tree in the same way as compressing the compression node starting from a sub-node of the compression node until the binary tree is traversed. ### Claim 5 A non-transitory computer readable storage medium storing one or more programs, the one or more programs comprising instructions, which when executed by a computer, cause the computer to perform operations comprising: determining a compression parameter according to a number of bits Nb of data read in one memory access, a number of bits Ni used by a bit index of a intermediate node, a number of bits Na used by a start address of sub-nodes of a compression node, a number of bits Nt used by a compression node type, and a number of bits used by a bitmap; compressing the binary tree according to the compression parameter to form at least one compression node; creating the bitmap of the compression node, wherein the compression parameter is a number n of compressed layers in one compression node, and is determined according to n ≤ Log 2 ⁡ ( N b - N a - N t N i + 1 + 1 ) ; applying the bitmap to the binary tree, wherein the binary tree represents a plurality of nodes including the intermediate nodes connected in a tree configuration, and said applying reduces the binary tree into a compressed binary tree with a reduced search depth; and applying the compressed binary tree to a packet classifier for performing routing decision for a packet at each of the plurality of nodes. ### Claim 6 (depends on 5) The computer readable storage medium according to claim 5, wherein the operations of compressing the binary tree according to the compression parameter to form at least one compression node comprises: compressing, starting from a root node of the binary tree, m layers of nodes as a compression node, wherein m is less than or equal to the number n of the compressed layer in one compression node; and continuing to compress the binary tree in the same way as compressing the compression node starting from a sub-node of the compression node until the binary tree is traversed. ### Claim 7 (depends on 5) The computer readable storage medium according to claim 5, wherein the compression parameter is a number K of the intermediate nodes in one compression node, and K is determined according to K ≤ N b - N a - N t + 1 N i + 3 . ### Claim 8 (depends on 7) The computer readable storage medium according to claim 7, wherein compressing the binary tree according to the compression parameter to form at least one compression node comprises: compressing, starting from a root node of the binary tree, nodes including a number T of intermediate nodes as a compression node, wherein the number T is less than or equal to the number K of the intermediate node in one compression node; and continuing to compress the binary tree in the same way as compressing the compression node starting from a sub-node of the compression node until the binary tree is traversed.