提出一种具有BDD结构的任意形状位矩阵换位算法

Question

我们认为位矩阵(nxm)是包含n行的大小为m的常规数组整数.

我查看了Hacker's Delight和其他来源,我发现的算法是相当专业的:方形矩阵的大小为2,8x8,32x32,64x64(这是正常的,因为机器是这样构建的).

我想到了一个更通用的算法(对于任意的n和m),在更糟糕的情况下,它是预期的复杂性(我认为),但是对于包含大多数相似列的矩阵,或者比那些更多的零,算法似乎有点更有趣(在极端情况下,如果矩阵一遍又一遍地包含相同的线,则它是线性的).它遵循一种二元决策图操作.

输出不是转置矩阵,而是压缩转置矩阵:对列表(V,L),其中L是int_m,表示应该包含int_n的转置矩阵的行(通过设置相应位置的位) V.没有出现在任何一对中的转置矩阵的线用0填充.

例如,对于矩阵

1010111
1111000
0001010

有转置

110
010
110
011
100
101
100

算法输出(010,0100000)(011,0001000)(100,0000101)(101,0000010)(110,1010000),一个读取对(100,0000101),意思是"值100放在第5和转置矩阵的第7行".

这是算法(用伪OCaml/C编写)和上述例子中算法进展的图片.

我们将根据三元组(index_of_current_line,V,L)运行,这是类型的(int, int_n, int_m),其中int_n是n位宽整数的类型,并且int只是一个足够容纳n的机器整数.该函数获取这些三元组的列表,矩阵,行数和输出的累加器(对的列表(int_m,int_n))并在某个时刻返回该累加器.

list of (int_n, int_m) transpose(list of triple t, 
                                int_m[n] mat, 
                                int n,  
                                list of (int_n, int_m) acc)

转置函数的第一个调用是

transpose([(0, 0, 2^m-1)], mat, n, []).

取"&","|" "xor"是通常的逐位操作

transpose(t, mat, n, acc) =
 match t with 
  | [] -> (* the list is empty, we're done *)
    return acc
  | (i, v, l)::tt -> 
    let colIn = mat[i] & l in
    (* colIn contains the positions that were set in the parent's mask "l" 
     and that are also set in the line "i" *)
    match colIn with
    |0 -> (* None of the positions are set in both, do not branch *)
     if (i<n) then (* not done with the matrix, simply move to next line *)
      transpose((i+1,v,l)::tt,mat,n,acc)
     else (* we reached the end of the matrix, we're at a leaf *)
       if (v>0) then
         transpose(tt,mat,n,(v,l)::acc)
       else  (* We ignore the null values and continue *)
         transpose(tt,mat,n,acc)
     |_ -> (* colIn is non null, ie some of the positions set at the parent
              mask "l" are also set in this line. If ALL the positions are, we 
              do not branch either. If only some of them are and some of them
              are not, we branch *)
         (* First, update v *)
        let vv = v | (2^(n-i-1)) in
         (* Then get the mask for the other branch *)
        let colOut = colIn xor l in, 
        match colOut with
        | 0 -> (* All are in, none are out, no need to branch *)
            if (i<n) then
                transpose((i+1,vv,colIn)::tt,mat,n,acc)
            else (* we reached the end of the matrix, we're at a leaf *)             
               transpose(tt,mat,n,(vv,colIn)::acc)
        | _ -> (* Some in, some out : now we branch *)
            if (i<n) then 
               transpose((i+1,vv,colIn)::(i+1,v,colOut)::tt,mat,n,acc)
            else 
             if (v>0) then
               transpose(tt,mat,n,(vv,colIn)::(v,colOut)::acc)
             else
               transpose(tt,mat,n,(vv,colIn)::acc)

请注意,如果矩阵比它更高则更宽,它甚至更快(例如,如果n = 3且m = 64)

我的问题是:这有趣和/或有用吗？我重新发明轮子了吗？"几乎为零"的矩阵或"小差异线"矩阵是否足以让人感兴趣？

PS:如果看起来不清楚,请告诉我,我会重写任何需要的东西!

Answer 1

对于矩阵来说，这是一种有趣的算法，其中零可能多于一，反之亦然，但是，有许多算法利用数字模式来提供一定程度的压缩。
它对于压缩可能很有用，但对于对其执行操作却没有用，例如：

给定一个二进制矩阵M，可以将其压缩为另一个N(A, B) - 正如您所指出的 - 但这将需要一定的计算能力P，并且解压缩也是如此。

M := P[N(A, B)]

除非矩阵中有非常具体的模式，否则不值得花费计算量P来处理其压缩形式N(A, B)。

然而，它在密码学领域可能很有用，因为操作P可以在右块B的矩阵上递归执行。这提供了一种用A的不同因子来表达M 的方法。

M := N(A, B); B := N'(A', B'); ...
M := N(A, N'(A', B'))

换句话说，使用一组A “键”就可以计算M。

它可能在其他场景中有用，但我不知道除了数据压缩和加密之外的任何应用程序。