[0021] 下面对本发明的实施例作详细说明,本实施例在以本发明技术方案为前提下进行实施,给出了详细的实施方式和具体的操作过程,但本发明的保护范围不限于下述的实施例。
[0022] 本发明专利的特点是对压缩后的测试向量再考虑测试模式重排序,然后对重排序后的测试向量进行等分分组,使得重排序之后的完全不兼容的测试向量分组之后能够达到近似兼容的效果。这里先量化测试向量的任意两列之间的关联度,这种关联度决定着这两列测试模式间的产生跳变的概率。
[0023] 基于测试模式重排序的分组测试向量间的兼容性压缩方案的编码压缩的具体步骤:
[0024] 步骤1.获得测试向量的任意两列之间的关联度,即测试向量的每两列测试模式之间的关联度的大小等于在测试模式立方中,此两列测试模式拥有相同逻辑值的次数除以测试模式立方的个数,因为,这种关联度决定着这两列测试模式间的产生跳变的概率,所以关联度较强的测试模式要尽可能的排列在相邻的位置,降低测试模式之间产生跳变的概率;
[0025] 步骤2.构造关联度图,在获得测试模式间的关联度后,我们就构造一个完全无向图称为关联度图,关联度图包括顶点及顶点之间的连线,这里顶点表示每列的测试模式,连线的权为相邻顶点的关联度;
[0026] 步骤3.在关联图上查找最大的哈密尔顿回路,这里我们用的是TSP算法,通过不断迭代最终找到一个最大的回路,即为哈密尔顿回路,对这个哈密尔顿回路,记住相邻测试模式间的关联度,以便下一步骤计算;
[0027] 步骤4.对步骤3中获得的最大哈密尔顿回路,依次查找相邻的测试模式之间最小的权,并且中断这两个相邻的测试模式,即获得一个花费成本最低哈密尔顿路径,这里成本最低的哈密尔顿路径的作用是,使相邻测试模式之间相同逻辑位不同的可能性达到最小,即是各个相邻顶点间所有的(1-相邻顶点的权)权之和,对哈密尔顿回路,寻找这个回路中权为最小的相邻顶点时,若有几个相邻顶点的权都为最小,则选最前面的相邻顶点,从选择的这个相邻顶点上中断这个回路,即为选择的最小哈密尔顿路径;
[0028] 步骤5.使用最小的哈密尔顿路径的排序方式来重新排列测试向量;这里哈密尔顿路径即找到的一个源测试数据集中列的相对最优的一个排序,按照这个哈密尔顿路径将源测试集中的每列测试模式重新排序,即可得到一个重新排列的测试集;
[0029] 步骤6.对重排序的每一个测试向量等分分组,其目的是为了使完全不兼容的测试向量通过分组之后能够达到组间的兼容,相当于使得测试向量之间达到近似分段兼容;
[0030] 步骤7.统计分组测试向量的各对应列的数据块(包括与其反向兼容的数据块)的出现频率,将其各个对应列中出现频率较高的数据块作为此列的参考数据块,当每列都找到它的参考数据块的时候,就将其作为这个测试数据集的参考向量,这里参考测试向量存储在第一个存储器中,压缩后的测试向量存储在第二个存储器中;
[0031] 步骤8.参照参考向量将每个分组测试向量的对应组进行编码压缩,与参考向量对应组的数据块兼容则压缩为0,反向兼容则压缩为1,不兼容则原数据块标记出来,使得源测试数据集达到很好的压缩率,将压缩的测试数据存储在第二个存储器中,以便解压,然后再把下一个分组测试向量压缩存储在第二个存储器中。
[0032] 基于测试模式重排序的分组测试向量间的兼容性实例:
[0033] 我们选择用一个较小的完全不兼容的源测试集,该源测试集包括5个测试向量,每个测试向量的长度为12位,如表1,我们计算测试向量的任意两列之间的关联度,即测试向量的每两列测试模式之间的关联度的大小等于在测试模式立方中,此两列测试模式拥有相同逻辑值的次数除以每一列测试模式立方的个数,这里我们以下面表1中的源测试集中,计算第1列和第2列之间的关联度为例,第一列与第二列拥有的相同逻辑值的位数为2位,这个源测试集总共有5个测试向量,也即每一列的测试模式立方个数为5位,则这两列的关联度计算即为2/5=0.4,故第一列和第二列的关联度为0.4,因为列自身本就相同,这里不需要列自身的关联度,所以列自身的关联度为0,按照此种算法,得到如表2所示的测试向量的任意两列之间的关联度。
[0034] 表1 源测试集
[0035] 101000101010
[0036] 010001101010
[0037] 101110000001
[0038] 000011101010
[0039] 111101100001
[0040] 表2 测试向量的任意两列之间的关联度
[0041] 1 2 3 4 5 6 7 8 9 10 11 12
1 0 0.4 1 0.8 0.4 0.2 0.4 0.4 0.2 0.4 0.2 0.8
2 0.4 0 0.4 0.6 0.2 0.8 0.6 0.6 0.4 0.6 0.4 0.6
3 1 0.4 0 0.8 0.4 0.2 0.4 0.4 0.2 0.4 0.2 0.8
4 0.8 0.6 0.8 0 0.6 0.4 0.2 0.6 0 0.6 0 1
5 0.4 0.2 0.4 0.6 0 0.4 0.2 0.6 0.4 0.6 0.4 0.6
6 0.2 0.8 0.2 0.4 0.4 0 0.8 0.4 0.6 0.4 0.6 0.4
7 0.4 0.6 0.4 0.2 0.2 0.8 0 0.2 0.8 0.2 0.8 0.2
8 0.4 0.6 0.4 0.6 0.6 0.4 0.2 0 0.4 1 0.4 0.6
9 0.2 0.4 0.2 0 0.4 0.6 0.8 0.4 0 0.4 1 0
10 0.4 0.6 0.4 0.6 0.6 0.4 0.2 1 0.4 0 0.4 0.6
11 0.2 0.4 0.2 0 0.4 0.6 0.8 0.4 1 0.4 0 0
12 0.8 0.6 0.8 1 0.6 0.4 0.2 0.6 0 0.6 0 0
[0042] 根据表1中任意两列之间的关联度作一个完全无向图,即为关联图,如图1所示,这里关联图中每条边上的权就不放在图上了,相邻顶点的权见表2。
[0043] 在图1中的关联图中,我们用TSP算法来查找最大的哈密尔顿回路,即相邻边上的权相加之后最大的回路。由于TSP算法是NP-难问题,所以每次获得的一个哈密尔顿回路都不是确定。这里我们通过对图1的关联度图进行多次迭代之后,最终得到一个相对最大的哈密尔顿回路为1→3→4→2→11→7→6→9→5→10→8→12→1.对于获得的最大哈密尔顿回路,我们依次查找相邻的顶点之间2→11和9→5都是最小的权为0.4,则我们选择最前面的一个相邻顶点2→11,并且从这相邻的顶点间中断这个哈密尔顿回路,得到一条成本最低的哈密尔顿路径的顺序为11→7→6→9→5→10→8→12→1→3→4→2,然后我们就按照选择的哈密尔顿路径的排列顺序来重新排列表1中的源测试集,重新排序后的测试向量如表3。
[0044] 表3 重新排序后的测试向量
[0045] 110100001100
[0046] 111100000001
[0047] 000010011110
[0048] 111110000000
[0049] 011000011111
[0050] 我们研究发现重排序的测试集中任意两个测试向量之间的兼容性不是很高,为了增加测试数据压缩率,我们先把重排序的测试向量等分分组为每组4位数据,如表4,这样就能使完全不兼容的测试向量达到两个测试向量之间对应组的兼容性提高,从而达到测试向量之间的近似兼容。
[0051] 表4 分组后的测试向量
[0052]
[0053] 分组测试数据集之后,我们统计第一列数据块1111和与它反相兼容的数据块0000一起出现的频率为3次,数据块1101、0110出现频率都为1次,但是数据块1111的出现频率高于它的反向兼容数据块0000,所以为了更好的提高压缩率,选择数据块1111为第一列的参考数据块;第二列0000出现频率为2次,数据块1001、1000、0001出现频率各为1次,所以选择数据块0000为第二列的参考数据块;第三列1111和与它反向兼容的数据块0000一起出现的频率为2次,0001和与它反相兼容的数据块1110一起出现的频率为2次,剩余的数据块1100的出现频率为1次,那么任选出现频率高的数据块为第三列的参考数据块,这里我们选择数据块0001为第三列参考数据块。因此综上所述,这个分组的测试数据集的参考向量为111100000001,并将其存储在第一个存储器中,以便下面的压缩及解压缩。
[0054] 参考存储器中的参考向量,我们将第一个测试向量压缩为1101 0 1100,并将存储在第二个存储器中,在解压器中进行解压缩;接着第二个测试向量参照第一个存储器中的参照向量压缩为0 0 0,仍然存储在第二个存储器中,用于解压器中的解压缩;以此类推,第三个测试向量压缩为1 1001 1,第四个测试向量压缩为0 1000 0000,第五个测试向量仍然为0110 00011111,因为这三组数据块与对应组的参考向量均不兼容或反向兼容。压缩后的测试数据块减少了21位,显著提高了它的压缩率。
[0055] 对压缩的数据块的解压过程是一个边压缩边解压的并行过程,这里要说的是,对于压缩和解压缩测试向量时,这里有两个存储器,第一个存储器用于一直存放参考测试向量,第二个存储器用于存储压缩的测试数据,便于解压缩,而且这个存储器中的测试数据是动态变化的。在第一列测试向量编码压缩为1101 0 1100时,并将其存储在第二个存储器中,解压时就参照第一个存储器中的参考向量解压为1101 1111 1100;当第一个测试向量压缩之后,就对第二个测试向量进行压缩为0 0 0,并将其存储在第二个存储器中,便于解压,解压时就参照第一个存储器中的参考向量解压为1111 0000 0001;以此类推,每次压缩时都参照第一个存储器中的参考向量,并将压缩后的数据存储在第二个存储器,解压时依然参照第一个存储器中的参考向量,对第二个存储器中的压缩向量进行解压,对下一个测试向量进行压缩和解压时仍然一样,直到这个压缩的测试集解压完毕为止。
[0056] 以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等,均应包含在本发明的保护范围之内。