浅议Pairwise算法
作者： badl
软件测试是软件开发的重要环节，在软件成本中也占有很大的比重。 本文在介绍pairwise算法的基础上，提出并实现了针对某些问题的扩展算法。
本文的组织结构如下
首先，本文首先简要介绍测试界著名的pairwise算法(约占文章的50% )。
第二，其次提出了针对pairwise算法的扩展算法。 扩展算法适合于某种情况下的测试。
第三，最后，基于扩展算法，用java语言开发了测试用例生成工具jCase。
目录
1软件测试. 3
2 pairwise算法. 3
2.1 pairwise算法详细信息. 4
2.2 Pairwise算法的效率. 6
2.3 pairwise算法比较. 6
3 Pairwise扩展算法. 7
3.1 Pairwise维. 7
3.2 Pairwise算法中的关键维算法. 8
4 Pairwise程序. 9
5 Pairwise不足. 10
1软件测试软件测试是软件工程中的一项重要活动有四个原则
)1)尽快、不间断地进行软件测试
)2)对所有产品进行全面测试
)3)关注软件开发全过程
)4)根据需求，选择合适的测试模型
软件测试分为黑盒测试和白盒测试。 Pairwise算法是针对软件测试黑匣子测试提出的有效测试方法。
2 Pairwise算法pairwise最早于1927年由l.l.Thurston e (29 may 188730 September 1955 )提出。 他是美国的心理统计学家。 Pairwise也正是数学统计和传统正交分析法的优化。
Pairwise基于以下两个假设：
(1)每个维度都是正交的。 也就是说，每个维度都不相互交叉。
)数学统计分析表明，73%的缺陷(单因素为35%，双因素为38% )是由单因素或两因素的相互作用产生的。 19%的缺陷是由三个因子的相互作用产生的。
因此，pairwise是基于覆盖所有两个因子的相互作用生成的用例集合性价比最高而产生的。
2.1 pairwise算法的详细解假设有三个维度，每个维度有几个因子。 如下所示。
浏览器： m，o，p
平台： w(windows )、L(linux )、I (IOs ) )。
语言： c(Chinese )，e ) (E(english ) )。
解决方案：
使用pairwise算法有多少个测试case？ 具体是什么case？
我们沿用数学问题的形式。
解：
如果不使用pairwise算法，则需要3*3*2=18个测试case。 具体的case如下所示。
1，M W C
2，MW E
3，M L C
4，M L E
5，M I C
6，M I E
7，O W C
8，O W E
9，甲骨文
10，O L E
11，奥IC
12，O I E
13，P W C
14，P W E
15，P L C
16，P L E
17，P I C
18，P I E
总共有18个。 很麻烦。 但这是测试的覆盖率100%，缺陷率也是100%。
现在用pairwise，看看结果怎么样？
先从最下面的18号开始吧。 那是P I E。 两者的组合是PI、PE、IE。 看看这三者的组合是否出现过以上相同的位置。 PI出现在17日，PE出现在16日，IE出现在12日。 所以18这个case可以舍弃。
最终剩下的如下
1，MWC
4，MLE
6，MIE
7，OWE
9，OLC
11，OIC
14，PWE
15，PLC
17，PIC
总共9个测试case，节约了50%的测试case。
现在，我们从上面再来一次。 1号是MWC，两个组合出现过MW MC WC，去除了。
最终剩下的是：
2，MWE
4，MLE
5，MIC
8，OWE
10，OLE
11，OIC
13 PWC
15 PLC
18 PIE
这也是
剩下9个测试case，但是具体的case内容不一样。经过L. L. Thurstone证明，pairwise算法最终剩下的测试case个数肯定相同，但是可以有不同的case组合。 2.2 Pairwise算法的效率Pairwise算法和正交分析法进行比较，当有3个维度，每个维度有4个因子的时候：
（1）正交分析法的case数量：4*4*4=64个
（2）Pairwise算法的case数量：20个
Pairwise的case数量是正交设计法的三分之一。当维度越多的时候，效果越明显。当有10个维度的时候 4*4*4*4*3*3*3*2*2*2=55296个测试case，pairwise为24个。是原始测试用例规模的0.04%。
2.3 pairwise算法的比较Pairwise算法和单因素测试用例设计的比较，能够覆盖到两个维度的正交组合设计。能适当减少遗漏的测试。
Pairwise算法和全正交设计法的比较，全正交设计法，测试case太多，投入的成本太大。Pairwise算法在数学统计分析的基础上，对传统的全正交设计法进行了优化，适当的提高了效率。
3 Pairwise扩展算法基于XXXX的各类项目，经过初步统计如下：
项目名称
项目组
维度个数
备注
xxx1
张组
3
平台，机器，软件版本
xxx2
张组
4
Ip和域名，udp，后缀表
xxx3
齐组
2
Ip黑白名单，域名黑白名单
xxx4
周
3
注册商，ip和域名
可以看出，每一个项目的维度都保持在5个以下，并且有重要维度和一般维度的区分。根据这2个特点，提出了pairwise的扩展算法。
3.1 Pairwise维度XXXX的各类项目维度都不多，并且每个维度的因子也不太多。测试人员可以很好的把握测试维度，难度不高。适合pairwise算法。
3.2 Pairwise算法中重要维度算法在一般维度方面，重要性是平均的，所以在维度1上，是一个平面，它和维度2（平面），相交，是一条线，具体到因子，就是一个点。所以我们找到了一组case。
在重要维度方面，重要性不是平均的，我们采用正交表的曲面理论。比如维度1是重要维度，我们采用曲面表示，如果维度2也是重要维度，那么，维度1和维度2相交，就是2条线。具体到因素，就是2个点（或者多个点）。如果维度2是一般维度（平面），曲面和平面相交，也有可能是1条线，也可能是2条线。我们这里选1条线。
综上所述，重要维度方面要适当增加测试case。具体怎么加见如下方法：
1， 按照输入维度的顺序全排列测试case。（输入维度的顺序代表重要性从高到底）
2， 从第一个开始往下使用pairwise算法过滤case。
3， 从最后一个开始往上使用pairwise算法过滤case。
4， 找出以上2组中相同case的数量，就是要增加的case的数量。
5， 增加的case是步骤4中相同的case的，变换维度1和维度2生成的case。
4 Pairwise程序现有很多程序都是围绕pairwise算法产生的，最著名的就是ReduceArray；SmartDesgin 和微软的PICT。
按照pairwise扩展算法开发了一个jCase程序，部署在http://xxxxx.cn/ 上的测试工具库中。基本理论如第3小节所述。
开发环境：eclipse 3.2
JDK：1.6+
部署容器：tomcat
核心流程：
1， 获取维度和因子进行全排列。
2， 得到具体的case的两两因子组合（带位置）。
3， 判断这个case中两两因子组合是否在上面出现过，如果出现一个就删除掉。全部都没出现过，就保留这个case。
4， 按照不同的顺序使用pairwise算法再过滤一遍。
5， 得到2组数据，找出相同的case。
6， 按照维度的顺序增加case。
核心代码如下：
private booleanjudge(String[] tpm, HashMap copyresult) {
Stringstr = "";
for(int i=0; i<tpm.length; i++)
{
str+= tpm[i]+";";
}
str= str.substring(0,str.length()-1);
copyresult.remove(str);
ArrayList r =newArrayList();
int len = tpm.length;
for (int i = 0; i < len; i++){
for (int j = i + 1; j < len;j++) {
String[]st = newString[len];
for (int k = 0; k < len; k++){
st[k]= "*";
}
st[i]= tpm[i];
st[j]= tpm[j];
Stringss = java.util.Arrays.asList(st).toString();
ss= ss.replaceAll("\[","").replaceAll("\]","");
// System.out.println(ss);
r.add(ss);
}
}
boolean bol =true;
for (int i = 0; i < r.size();i++) {
boolean flag =false;
Stringk = (String) r.get(i);
Iteratoriter = copyresult.entrySet().iterator();
while (iter.hasNext()) {
Map.Entryentry = (Map.Entry) iter.next();
Stringt = (String)entry.getKey();
if (cnniccompare(t, k)) {
bol= bol && true;
flag= true;
break;
}
}
if (!flag)
bol= false;
}
copyresult.put(str,str);
return bol;
}
5 Pairwise的不足（1）Pairwise对于维度的分解来说，需要对业务很熟悉。以及需要正交测试法的理论支持。需要中等专业的测试人员才能完成。
（2）pairwise还是有一定的遗漏。相比lcddfy正交设计法来说，pairwise算法对于多于2个因素相互作用所产生的bug，没有覆盖到。
转自：http://blog.csdn.net/aassddff261/article/details/42776543