Methods and devices for creating, compressing and searching binary tree
AssigneeHuawei Technologies Co., Ltd.
InventorsWenyong Zhang, Hui Wang
Life of this patent
Estimating the term…
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.
Claims30
A method for compressing a binary tree, comprising:
- determining, by a processor, a compression parameter, wherein the compression parameter is a number n of a compression layer or a number K of an intermediate node, wherein determining the compression parameter comprises:
- determining the 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, 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 the bitmap,
- compressing, by the processor, a binary tree according to the compression parameter to form at least one compression node;
- and
- creating, by the processor, a bitmap of the compression node.
A method for creating a binary tree, comprising:
- segmenting, by a processor, a non-range rule in a rule set by using a bit selection segmentation algorithm;
- converting, by the processor, a range rule in the rule set into a prefix when segmentation efficiency is lower than a preset threshold, and keeping an identifier of a rule corresponding to the prefix and an identifier corresponding to the range rule unchanged;
- segmenting, by the processor, a converted rule set by using the bit selection segmentation algorithm;
- and
- creating, by the processor, a binary tree corresponding to the rule set according to all segmentation results.
A method for creating a binary tree, comprising:
- segmenting, by a processor, a rule set by using a bit selection segmentation algorithm;
- extracting, by the processor, rules in a segmentation process that need to be replicated, and putting the rules in another sub-rule set;
- and
- creating, by the processor, binary trees corresponding to the rule set and the another sub-rule set respectively.
A device for compressing a binary tree, comprising a hardware processor and a non-transitory storage medium accessible to the hardware processor, the non-transitory storage medium:
- a determination module, configured to determine a compression parameter according to a plurality of parameters, wherein the compression parameter is a number n of a compression layer or a number K of an intermediate node, wherein the plurality of parameters comprises:
- 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, 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 the bitmap;
- a compression module, configured to compress a binary tree according to the compression parameter to form at least one compression node;
- and
- a bitmap module, configured to create a bitmap of the compression node.
A device for creating a binary tree, comprising:
- a first segmentation module, configured to segment a non-range rule in a rule set by using a bit selection segmentation algorithm;
- a conversion module, configured to convert a range rule in the rule set into prefix when segmentation efficiency is lower than a preset threshold, and keep an identifier of a rule corresponding to the prefix and an identifier corresponding to the range rule unchanged;
- a second segmentation module, configured to segment a converted rule set by using the bit selection segmentation algorithm;
- and
- a creation module, configured to create a binary tree corresponding to the rule set according to all segmentation results.
A device for creating a binary tree, comprising:
- a segmentation module, configured to segment a rule set by using a bit selection segmentation algorithm;
- an extraction module, configured to extract rules in a segmentation process that need to be replicated, and put the rules in another sub-rule set;
- and
- a creation module, configured to create binary trees corresponding to the rule set and the another sub-rule set respectively.
A method for searching a binary tree, comprising:
- obtaining, by a processor, a search keyword;
- determining, by the processor, whether each node of a binary tree is a leaf node or a compression node;
- when a node is a compression node, parsing the compression node;
- and
- when a node is a leaf node, traversing a linear table corresponding to the leaf node to search for a rule matching the keyword.
A device for searching a binary tree, comprising:
- an obtaining module, configured to obtain a search keyword;
- a determination module, configured to determine whether each node of a binary tree is a leaf node or a compression node;
- and
- a processing module, configured to, when the node is a compression node, parse the compression node;
- and when the node is a leaf node, traverse a linear table corresponding to the leaf node to search for a rule matching the keyword.
Dependencies are inferred from the claim text.