Page 209 - 《软件学报》2021年第11期
P. 209

王震  等:优化简单表缩减算法求解因子分解编码实例                                                       3535


                        效元组,这通过在第 6 行调用 intersectWord 方法来实现;最后,通过被修改过的平凡变量来更新当前的
                        有效元组.
                    •   filterDomains 方法利用 RSparseBitSet 来过滤平凡变量的论域,若使某个变量的论域为空,则发生回溯.
                    •   enforceGAC 方法为 STRFDE add 的入口,在调用 filterDomains 之后,只有因子变量 x 的论域没有被过滤,
                        若有效元组在调用 updateTable 时被平凡变量修改,那么在第 22 行,利用变量的 removeValues 方法根据
                        当前有效元组来更新因子变量的论域.
                 2.2   原始约束
                    原始约束涉及的变量集合 scp 由 n 个平凡变量和 m 个因子变量组成,其中,n 和 m 满足 n≥0,m≥0 且 n+m≥1.
                 原始约束中涉及到的因子变量与附加约束中的因子变量不同,这些因子变量的论域与原始约束的元组不是一
                 一对应的,因此不能使用元组直接更新变量的论域.如前所述,因子变量的论域大小等于附加约束的元组个数,
                 因此,在原始约束中对因子变量的每个值都构造一个 support[x,a]同样可能造成内存溢出问题.为解决这个问题,
                 我们根据 STRbit 提出了一种新的算法.STRbit 也是当前主流的 GAC 算法,它的效率和 CT 不相上下.在给出具
                 体算法之前,我们首先介绍算法中涉及的数据结构.
                    •   bitsup[x,a]是一个数组,用来表示当前约束对变量值(x,a)的 bit 支持集合,它只存储不为 0 的 bit 支持.
                        bitsup[x,a].size 表示当前约束对变量值(x,a)的 bit 支持数量,bitsup[x,a][i]表示第 i 个 bit 支持,
                        bitsup[x,a][i].ts 表示第 i 个 bit 支持中的索引,bitsup[x,a][i].mask 表示第 i 个 bit 支持对应的 mask 向量.
                    •   val 是一个存储元组 bit 向量的数组.
                    •   del[x]是一个变量值的集合,存储所有已经从变量论域 D(x)中删除但还没有更新当前约束中元组的变
                        量值.
                    •   residues 是一个整型数组,residues[x,a]存储对变量值(x,a)最近一次找到的支持索引.
                                       ori
                    算法 3 介绍了 STRFDE 的伪代码,STRbit 中的 LAST 和 restoreL 数据结构有较高的复杂度,可能造成内存
                                    ori
                 溢出问题,因此 STRFDE 没有使用它们.STRbit 中的 bitsup 只存储非 0 的 bit 支持,所以每个 bitsup[x,a]的长度
                 可能是不同的,它的长度在算法初始化时被确定.因子变量的变量值越多,相对应的每个变量值的 bit 支持数量
                 则越少,因此,使用 bitsup 会大幅度地减少内存占用.在算法中,我们使用 residues 去存储变量值最近一次找到的
                 bit 支持索引,若此支持仍然有效,就不必去遍历 bitsup.
                                 ori
                    算法 3. STRFDE .
                    1.   Data: scp: array of variables
                    2.   Method deleteInvalidTuple(⋅):
                    3.      foreach x∈scp do
                    4.         foreach a∈del[x] do
                    5.            for i←bitsup[x,a].size−1 down to 0 do
                    6.               index←bitsup[x,a][i].ts
                    7.               u←bitsup[x,a][i].mask & val[index]
                    8.               if u!=0 then
                    9.                  val[index]←(¬u) & val[index]
                    10.        del[x].clear(⋅):
                    11. Method searchSupport(⋅):
                    12.     foreach x∈scp do
                    13.        foreach a∈D(x) do
                    14.           now←residues[x,a]
                    15.           index←bitsup[x,a][now].ts
                    16.           if bitsup[x,a][i].mask & val[index]=0 then
   204   205   206   207   208   209   210   211   212   213   214