一种基于搜索空间分解的报文分类算法

报文分类算法的关键问题是查找准确且快速，最简单的分类算法就是线性查找，该算法的时间复杂度和空间复杂度均为O(N)，线性查找的思想简单、易于实现、空间复杂度好，可以和其它算法混合使用，进而提高算法的分类速度。快速的分类算法采用很复杂的数据结构，牺牲空间来换取时间，甚至过分要求分类的快速性，忽略了空间性。文章根据这一问题进行展开，详细分析了经典的报文分类hicuts算法，分析其时间复杂度和空间复杂度的关系，并提出一种不过分降低分类速度的前提下，有效降低空间复杂度和预处理时间的改进方法。