CN104834689A - 一种码流类型快速识别方法 - Google Patents

Abstract

一种码流类型快速识别方法，包括如下步骤：1)根据多个样本码流建立特征库，所述特征库存储多个从样本码流提取的样本特征集与样本类型匹配对，其中，同一样本特征集中的所有样本特征值互不相同；2)识别所有公共特征值并将所有所述公共特征值从特征库中移除，完成特征库优化；3)提取目标码流的目标特征集与特征库比对，完成目标码流的类型识别。本发明通过一个有向连接图，将类型与特征值关联，依托充分必要关系原理，简单通过计数器加1方式进行类型判别；算法复杂度低，识别效率高；比对次数不会超过特征集大小，可以快速识别码流类型。

Description

一种码流类型快速识别方法

技术领域

本发明涉及数字通讯技术领域，尤其涉及一种码流类型快速识别方法。

背景技术

识别码流类型并解析字段是数字通讯过程中的常见操作。通常，通讯协议设计时会指定某字段为特征标识符(即特征值)，用以关联码流与类型，进而方便进一步操作。但存在如下问题：其一，不同通讯协议设计大相径庭，差异性较大，因此需要为不同通讯协议设计不同的识别算法。但不同通讯协议的识别过程及其类型。这样造成重复工作。其二，在某些特殊应用中，如遥控指令识别，码流本身并不包含类型识别字段，使用逐条比较或者分类树，软件设计难度较大，识别效率较低。

因此，需要提供一种码流类型快速识别方法，以通用、快速的实现由码流到类型的映射识别过程。

发明内容

本发明的目的在于，提供一种码流类型快速识别方法，以通用、快速的实现由码流到类型的映射识别过程。

为实现上述目的，本发明提供了一种码流类型快速识别方法，包括如下步骤：(1)根据多个样本码流建立特征库，所述特征库存储多个从样本码流提取的样本特征集与样本类型匹配对，其中，同一样本特征集中的所有样本特征值互不相同；(2)识别所有公共特征值并将所有所述公共特征值从特征库中移除，完成特征库优化；(3)提取目标码流的目标特征集与特征库比对，完成目标码流的类型识别。

本发明的优点在于：通过一个有向连接图，将类型与特征值关联，依托充分必要关系原理，简单通过计数器加1方式进行类型判别；算法复杂度低，识别效率高；比对次数不会超过特征集大小，可以快速识别码流类型。

附图说明

图1，本发明所述的码流类型快速识别方法的流程示意图；

图2，本发明所述的kpClassify特征库示意图；

图3，本发明所述的向特征库添加新样本流程示意图；

图4，本发明所述的特征库优化流程示意图；

图5A-5D，本发明所述的目标特征值识别过程示意图；

图6，本发明所述的目标码流类型识别过程软件流程示意图；

图7，本发明所述的未识别类型建库流程示意图；

图8，本发明所述的kpClassify算法过程示意图。

具体实施方式

下面结合附图对本发明提供的码流类型快速识别方法做详细说明。

参考图1，本发明所述的码流类型快速识别方法的流程示意图，所述方法包括如下步骤：S11：根据多个样本码流建立特征库，所述特征库存储多个从样本码流提取的样本特征集与样本类型匹配对，其中，同一样本特征集中的所有样本特征值互不相同；S12：识别所有公共特征值并将所有所述公共特征值从特征库中移除，完成特征库优化；S13：提取目标码流的目标特征集与特征库比对，完成目标码流的类型识别。以下结合附图给出详细解释。

S11：根据多个样本码流建立特征库，所述特征库存储多个从样本码流提取的样本特征集与样本类型匹配对，其中，同一样本特征集中的所有样本特征值互不相同。

本发明所采用的码流分类识别算法命名为kpClassify，其通过一个有向连接图，将类型与特征值关联，依托充分必要关系原理，简单通过计数器加一方式进行类型判别。kpClassify算法复杂度低，识别效率高，比对次数不会超过特征集大小，其算法核心思想描述如下。

一、基本概念

假设，已经获知某给定的二进制码流的类型，建立如下概念描述：

码流集合(简称码流)C，表征给定的二进制码流。类型P，表征该码流类型。二者有如下关系：

P～C＝[c_i]_l

其中，c_i表征位于i位置的比特值(0，1)，l表征码流长度。

通常计算机最小寻址单位为字节，故而使用字节流集合(简称字节流)B表征码流，即：

P～B＝[b_i]_m

其中，b_i表征位于i位置的字节值(0x00～0xFF)，m表征字节流长度。以下使用字节流表述码流。

通常的通讯协议设计会在某位置设置字段用以标识类型，也即，识别字节流与位置有关。用以识别字节流的特征值需要通过特征提取方法f提取，该识别过程可以描述为：

k_i＝f(b_j)，其中，i≤m，j≤n

式中，k_i表征第i个特征值，其由位于j位置的字节量b_j通过特征提取方法f计算获得。明显，i,j取值小于m。

通常，并非所有字节均与字节流类型的识别有关。故而，某字节流所提取的所有特征值数量至少小于等于字节流长度，于是有：

K＝[k_i]_n

式中，K为字节流B所提取的特征集(即特征值集合)，n为特征值个数。

假设所提取的特征集K能够唯一的标识字节流B的类型，此时，特征集K与字节流类型P便是等价关系，即：P＝K。

综上所述，有如下关系：

P＝K＝[k_i]_n＝[f(b_j)]_n～B＝[b_i]_m＝C＝[c_i]_l

简化后有：

[k_i]_n＝P～B

即，特征集K与类型P等价，均能表征字节流B(码流C)的类型。

二、基本原理

由上节基本概念讨论可知，特征集K与类型P在识别字节流B类型过程中，为等价关系：[k_i]_n＝P。该等价关系可以表达为：类型P与特征集K在表征字节流B类型时相互为充要条件；即，获知特征集K，则可以确定字节流B为类型P；同时，已知字节流类型为P，则一定对应特征集K。

而，特征集K中的某一特征值k_i对于识别字节流B的类型P，为必要不充分条件。也即，获知字节流B拥有特征值k_i，不一定确定该字节流B为类型P；而，已知字节流B类型为P，则一定可以确定其有特征值k_i。

本发明对上述特征提取方法f做如下设定：任何字节b_j经过特征提取方法f运算后的特征值k_i互不相同，即，同一样本特征集中的所有样本特征值互不相同。任一字节流B的类型P，对应n个特征值k_i。

$\left\{\begin{array}{c}k=f\left(b\right)\\ \begin{array}{cc}{k}_i\≠k_j& i,j\≤n;i\≠j\end{array}\end{array}\right.$

通常，通过特征提取方法f，由字节流B获取其特征集K’相对容易，即：

K’＝[k_i’]_n＝[f(b_j)]_n

当能够证明K’与K集一致，或者说，K’与P能够形成充要条件时，字节流B的类型为P，也即，通过特征集K’识别了字节流B的类型。

由于特征值k_i互不相同，识别过程也可以描述为：当该组特征集K’中特征值k_i与目标类型P达成必要不充分条件的次数达到n时，则，K’与K一致，K’与P构成充要条件，从而识别了字节流B的类型。

由前述基本原理描述可知，虽然对同一特征集K中的所有特征值k做了互异性设定，但并不能排除不同类型的字节流拥有共同的特征值。故，kpClassify使用特征值k与类型P所构成的图，组织特征库。

参考图2，本发明所述的kpClassify特征库示意图。如图2所示，P表征某种字节流B的类型，而k表征特征值(为图示方便，省去下标；大写字母K表征特征集，小写字母k表征特征值，下同)。P与k之间的连线表征一条k到P的必要不充分条件；而指向P的所有k与之构成等价的特征集。注意到，同一k可能“从属”于多个不同的类型P。

本发明所述特征库建立的过程可以为：1)添加一条样本码流的新类型于特征库；2)添加所述一条样本码流的样本特征集中各个样本特征值；3)逐一判断所添加的样本特征值在特征库中是否已经存在，若已存在则仅建立所述样本特征值到所述新类型的连线，若不存在则新建所述样本特征值并同时建立所述新类型与所述样本特征值的连线；4)重复上述步骤1)-3)，提取所述多个样本码流的样本特征集以及样本类型，建立所述特征库。

参考图3，本发明所述的向特征库添加新样本流程示意图。按照前述描述，使用字节流表述码流，新样本添加流程为：添加一条新样本字节流B的类型P与特征集K至特征库时，首先添加新类型P；接着循环添加特征集K中各个特征值k，并作判断：如果特征库中已经存在特征值k，那么仅建立该特征值k到类型P的连线，如果特征库中不存在特征值k，那么新建该特征值k并同时建立所述新类型P与该特征值k的连线。按照上述新样本添加流程，提取所有样本字节流类型以及特征集，并最终构成特征库。

S12：识别所有公共特征值并将所有所述公共特征值从特征库中移除，完成特征库优化。

特征库中，同一特征值k可能对应于多个类型P。一种极限情况是，某一特征值对应所有类型P(即，其与所有类型P均连接)，称此类特征值为公共特征值。由于公共特征值对应所有类型P，故而使用公共特征值判定类型时，是无效的，因为公共特征值完全不具备区分不同类型P的能力。特征库优化过程便是识别公共特征值，并将其从特征库中移除，以减小特征库体积，提高识别效率。

识别公共特征值并将其从特征库中移除的具体方式可以为：遍历特征库中的所有样本特征值，逐一判断样本特征值已连接样本类型数量是否与特征库的所有样本类型数量相等，若相等则判定相应样本特征值是公共特征值并移除。也即，在判断某一特征值k是否与所有类型P连接时，可以通过判定特征值k已连接类型P的数量与所有类型P的数量是否相等完成；如图4，本发明所述的特征库优化流程示意图所示。在判定特征值k与所有类型P连接时，移除特征值k，同时移除特征值k与所有类型P之间的连线。若判定已遍历所有特征值，则优化特征库完成。

S13：提取目标码流的目标特征集与特征库比对，完成目标码流的类型识别。

目标码流类型识别的具体方式可以为：1)提取目标码流的目标特征集；2)依次将目标特征集的所有目标特征值与特征库中的样本特征值比对，若特征库中存在与目标特征值相同的样本特征值，则与该目标特征值连接的所有样本类型标记加1；3)比对样本类型标记的累计和是否与指向该样本类型的目标特征值数量相同，若相同则识别出目标码流所对应的码流类型。

目标码流特征集K的特征提取方法f可以根据不同的应用场景分别设计，本发明通常如下的方法构造特征值，即：使用一个32比特长整型依次存放目标特征值对应字段(及表征特征标识符的字节)所在位置i、有效比特掩码mask、以及值value，如表1所示。

16bits	8bits	8bits
			位置i	掩码mask	值value

表1，本发明所述的目标特征值提取方法。

参考图5A-5D，本发明所述的目标特征值识别过程示意图。按照表1所示特征提取方法f，提取目标特征集K。依次向特征库输入目标特征集K中的所有特征值k，如果在特征库中找到该特征值k，则将该特征值k连接的所有类型P的标记加1。类型P标记加1同时，比对此时该类型P的标记累加和是否与指向该类型P的特征值数量相同。当两者相同时，则识别了目标特征集K所对应的类型P，也即识别出目标码流所对应的码流类型。

作为优选的实施方式，在识别目标特征集K的类型前，重置所有类型P的标记累加和，以防止连续前后两次识别过程相互影响。

作为优选的实施方式，如果公共特征值存在，还需要在识别类型P之后，将目标特征集K剩余不在特征库中的特征值与所有公共特征值比对，以提高类型识别精度。

参考图6，本发明所述的目标码流类型识别过程软件流程示意图。该流程工作的前提是：特征库已经建立；其中：类型识别——待识别的字节流；识别的类型——待识别字节流的类型；未识别的类型——不能识别待识别字节流类型；特征值——由待识别字节流所提取的特征集中的元素；类型P——与某特征值直接连接的类型P集合中的元素，其并非值特征库中所有类型，而是与某特征值链接的提取的子集合。识别过程为对该集合进行遍历。

识别过程为：

STEP1：提取待识别字节流特征值集合；

STEP2：对上一步特征值集合中的每一个元素特征值“遍历”执行以下操作：SUB1：判断该特征值是否存在于特征库中，不存在时，中止，遍历下一个提取的特征值；SUB2：如果特征值存在于特征库中，将特征库中所对应的特征值找到，并且找到与该特征值链接的所有类型P；SUB3：对于所找到的所有类型P进行如下操作：SUB_SUB1：对该类型标记计数器加1；SUB_SUB2：判断，该类型P计数器值是否已经达到与该类型P直接连接的所有的特征值的个数。如，类型P与5个特征值链接，而此时计数器值又是5；SUB_SUB3：如果上一步判断为真，则已经初步识别待识别字节流的类型。

STEP3：经过前两步后，并非所有所提取的特征值都经过SUB2-SUB3的过程，再由于特征库有过压缩优化过程。故，此步骤判断，是不是所有公共特征值都能在所提取的特征值集合中找到，如果结果为真。则识别类型。

STEP4：在STEP2中，如果所有特征值都经过了SUB1-SUB3的过程，同时，仍然没有达到SUB_SUB3初步识别的状态。此时，特征值又遍历结束。那么，待识别类型的字节流则无法被识别。

作为优选的实施方式，本发明进一步包括步骤S14：在识别目标码流类型失败后通知用户，待用户指定未识别的目标码流的类型后，将所述未识别的目标码流作为新样本码流添加至特征库中。

参考图7，本发明所述的未识别类型建库流程示意图。识别目标码流类型失败后，对与未识别的目标码流，kpClassify通知用户，之后等待用户指定此未知类型P；根据用户输入，将本条未识别的目标码流作为新样本添加至特征库中。其中，用户输入可以是提前拟定好的类型编码规律，或者类型列表文件，或用户界面等具体方式。

综上，本发明所述的kpClassify算法主要分为三个过程：1、由样本码流建立特征库、并优化过程；2、根据目标码流提取特征集、并比对特征库识别码流类型过程；3、未识别类型添加特征库过程。如图8，本发明所述的kpClassify算法过程示意图所示。

本发明提供的码流类型快速识别方法，通过一个有向连接图，将类型与特征值关联，依托充分必要关系原理，简单通过计数器加1方式进行类型判别；算法复杂度低，识别效率高；比对次数不会超过特征集大小，可以快速识别码流类型。

以上所述仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

Claims (8)

1.一种码流类型快速识别方法，其特征在于，包括如下步骤：

(1)根据多个样本码流建立特征库，所述特征库存储多个从样本码流提取的样本特征集与样本类型匹配对，其中，同一样本特征集中的所有样本特征值互不相同；

(2)识别所有公共特征值并将所有所述公共特征值从特征库中移除，完成特征库优化；

(3)提取目标码流的目标特征集与特征库比对，完成目标码流的类型识别。

2.根据权利要求1所述的识别方法，其特征在于，步骤(1)进一步包括：

(11)添加一条样本码流的新类型于特征库；

(12)添加所述一条样本码流的样本特征集中各个样本特征值；

(13)逐一判断所添加的样本特征值在特征库中是否已经存在，若已存在则仅建立所述样本特征值到所述新类型的连线，若不存在则新建所述样本特征值并同时建立所述新类型与所述样本特征值的连线；

(14)重复上述步骤(11)-(13)，提取所述多个样本码流的样本特征集以及样本类型，建立所述特征库。

3.根据权利要求1所述的识别方法，其特征在于，步骤(2)进一步包括：遍历特征库中的所有样本特征值，逐一判断样本特征值已连接样本类型数量是否与特征库的所有样本类型数量相等，若相等则判定相应样本特征值是公共特征值并移除。

4.根据权利要求1所述的识别方法，其特征在于，步骤(3)进一步包括：

(31)提取目标码流的目标特征集；

(32)依次将目标特征集的所有目标特征值与特征库中的样本特征值比对，若特征库中存在与目标特征值相同的样本特征值，则与该目标特征值连接的所有样本类型标记加1；

(33)比对样本类型标记的累计和是否与指向该样本类型的目标特征值数量相同，若相同则识别出目标码流所对应的码流类型。

5.根据权利要求4所述的识别方法，其特征在于，步骤(32)之前进一步包括：重置所有样本类型标记的累加和。

6.根据权利要求4所述的识别方法，其特征在于，若存在公共特征值，步骤(33)之后进一步包括：在识别码流类型之后，将目标特征集中在特征库中不存在相同的样本特征值的目标特征值与所有公共特征值比对。

7.根据权利要求4所述的识别方法，其特征在于，目标特征集中的目标特征值采用一个32比特长整型依次存放目标特征值对应字段所在位置、有效比特掩码、以及值。

8.根据权利要求1所述的识别方法，其特征在于，步骤(3)之后进一步包括：识别目标码流类型失败后通知用户，待用户指定未识别的目标码流的类型后，将所述未识别的目标码流作为新样本码流添加至特征库中。