我怎样才能有效地encode/decode压缩职位描述？

Question

我正在为日本象棋变体编写 table 基础。为了索引 table 基数，我将每个国际象棋位置编码为一个整数。在其中一个编码步骤中，我对棋子在棋盘上的位置进行了编码。由于实际的方法有点复杂，我就简单的解释一下吧。

编码

在残局 tablebase 中，我有（比方说）六个不同的棋子，我想将它们分配到一个有 9 个方格的棋盘上。我可以天真地用六元组 (a, b, c, d, e, f ) 其中每个变量 a to f是0到8之间的数字，表示对应的棋子所在的位置。

然而，这种表示并不是最优的：没有两个棋子可以占据同一个方块，但上述编码很高兴地允许这样做。我们可以通过六元组 [a, b', c', d', e', f' ] 对相同位置进行编码，其中 a 和前面一样 a，b' 是一个从 0 到 7 的数字，表示第二个棋子所在的方格数。这是通过为第一块不在的每个方块分配一个 0 到 7 的数字来工作的。例如，如果第一块在方格 3 上，则第二块的方块编号为：

1st piece: 0 1 2 3 4 5 6 7 8
2nd piece: 0 1 2 - 3 4 5 6 7

其他部分的编码类似，c'为0到6的数字，d'为0到6的数字5 等。例如，朴素编码 (5, 2, 3, 0, 7, 4) 产生紧凑编码 (5, 2, 2, 0, 3, 1)：

1st: 0 1 2 3 4 5 6 7 8 --> 5
2nd: 0 1 2 3 4 - 5 6 7 --> 2
3rd: 0 1 - 2 3 - 4 5 6 --> 2
4th: 0 1 - - 2 - 3 4 5 --> 0
5th: - 0 - - 1 - 2 3 4 --> 3
6th: - 0 - - 1 - 2 - 3 --> 1

在我实际的编码中，我要编码的片数是不固定的。然而，棋盘上的方格数是。

问题

如何有效地将朴素表示转换为紧凑表示，反之亦然？我为该程序使用标准 C99。在这个问题的上下文中，我对使用非标准构造、内联汇编或内在函数的答案不感兴趣。

问题澄清

因为这个问题似乎有些混乱：

问题是找到一种实用有效的方法来实现朴素和紧凑位置表示之间的转换
两种表示都是n-特定范围内整数的元组。问题不在于如何将这些表示编码为其他任何内容。
在我遇到的一个案例中，正方形的数量是 25，棋子的数量最多是 12。然而，我对一个适用于合理参数 space 的实现感兴趣（例如最多到 64 个正方形，最多 32 个）。
我对替代表示或编码不感兴趣，尤其是不是最佳的表示或编码。
我对紧凑表示不值得付出努力的评论也不感兴趣。

Answer 1

要从 (5, 2, 3, 0, 7, 4) 到 (5, 2, 2, 0, 3, 1)，您只需：

从 (5, 2, 3, 0, 7, 4) 开始，在结果 (5) 中压入五
取2，统计前面小于2的个数，0然后push 2-0: (5, 2)
取3，统计前面小于3的个数，1然后push 3-1: (5, 2, 2)
取0，统计前面小于0的个数，0再压0-0(5,2,2,0)
取 7，数...，4 然后推 7-4：(5,2,2,0,3)
取 4，数...，3 然后推 4-3：(5,2,2,0,3,1)

Answer 2

您的编码技术具有属性输出元组的每个元素的值取决于输入元组的相应元素和所有前面元素的值。我看不出有一种方法可以在计算一个编码元素的过程中累积部分结果，这些结果可以在另一个编码元素的计算中重复使用，如果没有这种方法，编码的计算就无法比（时间）更有效地扩展（时间） o(n²) 中要编码的元素个数。因此，对于你描述的问题规模，我认为你不能做得比这更好：

typedef <your choice> element_t;

void encode(element_t in[], element_t out[], int num_elements) {
    for (int p = 0; p < num_elements; p++) {
        element_t temp = in[p];

        for (int i = 0; i < p; i++) {
            temp -= (in[i] < in[p]);
        }

        out[p] = temp;
    }
}

对应的解码可以这样：

void decode(element_t in[], element_t out[], int num_elements) {
    for (int p = 0; p < num_elements; p++) {
        element_t temp = in[p];

        for (int i = p - 1; i >= 0; i--) {
            temp += (in[i] <= temp);
        }

        out[p] = temp;
    }
}

有些方法可以更好地扩展，其中一些在评论和其他答案中进行了讨论，但我最好的猜测是您的问题规模不够大，无法通过改进的扩展来克服增加的开销。

显然，这些变换本身根本不会改变表示的大小。然而，编码表示更容易验证，因为元组中的每个位置都可以独立于其他位置进行验证。出于这个原因，整个 space 有效元组也可以在编码形式中比在解码形式中更有效地枚举。

我继续坚持解码形式的存储效率几乎与编码形式一样，特别是如果您希望能够处理单个位置描述。如果编码形式的 objective 支持批量枚举，那么您可以考虑以 "encoded" 形式枚举元组，但在 decoded[=40= 中存储并随后使用它们] 形式。需要的少量额外 space 可能非常值得，因为阅读后无需执行解码，特别是如果您打算阅读大量此类内容。

更新：

针对您的评论，房间里的大象是如何将编码形式转换为您描述的单个索引的问题，以便尽可能少地使用未使用的索引。我认为正是这种脱节引发了如此多的讨论，以至于您认为这是题外话，而且我认为您对此有一些假设，这些假设会影响您 24 倍 space 节省的断言。

编码形式更容易转换为紧凑索引。例如，您可以将位置视为小端数字，棋盘大小作为其基数：

#define BOARD_SIZE 25 typedef <big enough> index_t; index_t to_index(element_t in[], int num_elements) { // The leading digit must not be zero index_t result = in[num_elements - 1] + 1; for (int i = num_elements - 1; i--; ) { result = result * BOARD_SIZE + in[i]; } }

可以肯定的是，这方面仍然存在差距，但我估计它们只占所用指数值总体范围的相当小的一部分（并且安排如此是采取一点的原因 -字节序解释）。我把反向转换留作练习 :).

Answer 3

问题的简单解决方案：创建一个数组，其中的值最初等于索引。当您使用正方形时，从数组中获取它的值，然后将所有值向右递减。该解的运行时间是O(n*p)，其中n是棋盘上的方格数，p是棋盘上的棋子数。

int codes[25];

void initCodes( void )
{
    for ( int i = 0; i < 25; i++ )
        codes[i] = i;
}

int getCodeForLocation( int location )
{
    for ( int i = location + 1; i < 25; i++ )
        codes[i]--;
    return codes[location];
}

您可以尝试通过合并来提高此代码的性能。将棋盘上的位置视为 5 个箱子，每个箱子有 5 个位置。每个 bin 都有一个偏移量，并且 bin 中的每个位置都有一个值。当从位置 x 的 bin y 中获取值时，y 下面的所有 bin 的偏移量都会递减。并且 bin y 中 x 右侧的所有值都递减。

int codes[5][5];
int offset[5];

void initCodes( void )
{
    int code = 0;
    for ( int row = 0; row < 5; row++ )
    {
        for ( int col = 0; col < 5; col++ )
            codes[row][col] = code++;
        offset[row] = 0;
    }
}

int getCodeForLocation( int location )
{
    int startRow = location / 5;
    int startCol = location % 5;
    for ( int col = startCol+1; col < 5; col++ )
        codes[startRow][col]--;
    for ( int row = startRow+1; row < 5; row++ )
        offset[row]--;
    return codes[startRow][startCol] + offset[startRow];
}

该解的运行时间为O(sqrt(n) * p)。但是，在有 25 个方块的棋盘上，您不会看到太大的改进。要了解为什么要考虑由原始解决方案与分箱解决方案完成的实际操作。最坏的情况，天真的解决方案更新 24 个位置。最坏的情况是，分箱解决方案更新 offset 数组中的 4 个条目和 codes 数组中的 4 个位置。所以这似乎是一个 3:1 加速。但是，合并后的代码包含一个令人讨厌的 division/modulo 指令，并且总体上更加复杂。因此，如果幸运的话，您可能会获得 2:1 加速。

如果电路板尺寸很大，例如256x256，然后合并会很棒。天真的解决方案的最坏情况是 65535 个条目，而分箱最多会更新 255+255=510 个数组条目。所以这肯定会弥补讨厌的分裂和增加的代码复杂性。

这就是试图优化小问题集的徒劳之处。当您有 n=25 sqrt(n)=5 log(n)=5 时，将 O(n) 更改为 O(sqrt(n)) 或 O(log(n)) 不会节省太多。你得到了理论上的加速，但当你考虑到 big-O 如此愉快地忽略的无数常数因素时，这几乎总是错误的节省。

为完整起见，下面是可与上述任一代码段一起使用的驱动程序代码

int main( void )
{
    int locations[6] = { 5,2,3,0,7,4 };
    initCodes();
    for ( int i = 0; i < 6; i++ )
        printf( "%d ", getCodeForLocation(locations[i]) );
    printf( "\n" );
}

输出：5 2 2 0 3 1

Answer 4

要从原始位置转换为紧凑位置，您可以迭代 n 元组并对每个位置执行这些步骤 p:

可选地检查位置 p 是否可用
将位置 p 设为忙碌
从p中减去忙碌的较低职位的数量
将结果存储到目标 n 元组中

您可以通过为忙碌状态维护一个 n 位数组来做到这一点：

步骤 1、2 和 4 在恒定时间内计算
如果数组很小，即：64 位，则可以高效地计算步骤 3。

这是一个实现：

#include <stdio.h>
#include <stdlib.h>

/* version for up to 9 positions */
#define BC9(n)  ((((n)>>0)&1) + (((n)>>1)&1) + (((n)>>2)&1) + \
                 (((n)>>3)&1) + (((n)>>4)&1) + (((n)>>5)&1) + \
                 (((n)>>6)&1) + (((n)>>7)&1) + (((n)>>8)&1))
#define x4(m,n)    m(n), m((n)+1), m((n)+2), m((n)+3)
#define x16(m,n)   x4(m,n), x4(m,(n)+4), x4(m,(n)+8), x4(m,(n)+12)
#define x64(m,n)   x16(m,n), x16(m,(n)+16), x16(m,(n)+32), x16(m,(n)+48)
#define x256(m,n)  x64(m,n), x64(m,(n)+64), x64(m,(n)+128), x64(m,(n)+192)

static int const bc512[1 << 9] = {
    x256(BC9, 0),
    x256(BC9, 256),
};

int encode9(int dest[], int src[], int n) {
    unsigned int busy = 0;
    for (int i = 0; i < n; i++) {
        int p = src[i];
        unsigned int bit = 1 << p;
        //if (busy & bit) return 1;  // optional validity check
        busy |= bit;
        dest[i] = p - bc512[busy & (bit - 1)];
    }
    return 0;
}

/* version for up to 64 positions */
static inline int bitcount64(unsigned long long m) {
    m = m - ((m >> 1) & 0x5555555555555555);
    m = (m & 0x3333333333333333) + ((m >> 2) & 0x3333333333333333);
    m = (m + (m >> 4)) & 0x0f0f0f0f0f0f0f0f;
    m = m + (m >> 8);
    m = m + (m >> 16);
    m = m + (m >> 16 >> 16);
    return m & 0x3f;
}

int encode64(int dest[], int src[], int n) {
    unsigned long long busy = 0;
    for (int i = 0; i < n; i++) {
        int p = src[i];
        unsigned long long bit = 1ULL << p;
        //if (busy & bit) return 1;  // optional validity check
        busy |= bit;
        dest[i] = p - bitcount64(busy & (bit - 1));
    }
    return 0;
}

int main(int argc, char *argv[]) {
    int src[argc], dest[argc];
    int cur, max = 0, n = argc - 1;

    for (int i = 0; i < n; i++) {
        src[i] = cur = atoi(argv[i + 1]);
        if (max < cur)
            max = cur;
    }
    if (max < 9) {
        encode9(dest, src, n);
    } else {
        encode64(dest, src, n);
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", dest[i]);
    }
    printf("\n");
    return 0;
}

核心优化在bitcount()的实现上，您可以根据自己的需要，将其专门化到实际的职位数量上。我在上面发布了针对最多 9 个小数和最多 64 个大数的有效解决方案，但您可以为 12 或 32 个位置制定更有效的解决方案。

在时间复杂度上，一般情况下，我们还是有O(n²)，但是对于较小的值n，它实际上运行在 O(n.Log(n)) 或更好，因为并行执行 bitcount() 可以减少到日志(n) 步或更少 n 最多 64.

您可以查看 http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive 以获得灵感和惊奇。

不幸的是，我仍在寻找使用这个或类似技巧进行解码的方法...

Answer 5

我找到了一个更优雅的解决方案，最多 16 个位置，使用 64 位整数和一个循环进行编码和解码：

#include <stdio.h>
#include <stdlib.h>

void encode16(int dest[], int src[], int n) {
    unsigned long long state = 0xfedcba9876543210;
    for (int i = 0; i < n; i++) {
        int p4 = src[i] * 4;
        dest[i] = (state >> p4) & 15;
        state -= 0x1111111111111110 << p4;
    }
}

void decode16(int dest[], int src[], int n) {
    unsigned long long state = 0xfedcba9876543210;
    for (int i = 0; i < n; i++) {
        int p4 = src[i] * 4;
        dest[i] = (state >> p4) & 15;
        unsigned long long mask = ((unsigned long long)1 << p4) - 1;
        state = (state & mask) | ((state >> 4) & ~mask);
    }
}

int main(int argc, char *argv[]) {
    int naive[argc], compact[argc];
    int n = argc - 1;

    for (int i = 0; i < n; i++) {
        naive[i] = atoi(argv[i + 1]);
    }

    encode16(compact, naive, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", compact[i]);
    }
    printf("\n");

    decode16(naive, compact, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", naive[i]);
    }
    printf("\n");
    return 0;
}

该代码使用 64 位无符号整数来保存 0..15 范围内 16 个值的数组。这样的数组可以单步并行更新，取值简单，删除值麻烦一点，但也只需要几步。

您可以使用不可移植的 128 位整数（gcc 和 clang 都支持 __int128 类型）将此方法扩展到 25 个位置，将每个位置编码为 5 位，利用以下事实5 * 25 < 128，但是魔法常量写起来比较麻烦

Answer 6

在这个回答中，我想展示我自己的一些实现转换的想法以及一些基准测试结果。

您可以找到代码 on Github。这些是我的主机上的结果：

algorithm   ------ total  time ------  ---------- per  call -----------
            decoding encoding total    decoding   encoding   total
baseline    0.0391s  0.0312s  0.0703s    3.9062ns   3.1250ns   7.0312ns
count       1.5312s  1.4453s  2.9766s  153.1250ns 144.5312ns 297.6562ns
bitcount    1.5078s  0.0703s  1.5781s  150.7812ns   7.0312ns 157.8125ns
decrement   2.1875s  1.7969s  3.9844s  218.7500ns 179.6875ns 398.4375ns
bin4        2.1562s  1.7734s  3.9297s  215.6250ns 177.3438ns 392.9688ns
bin5        2.0703s  1.8281s  3.8984s  207.0312ns 182.8125ns 389.8438ns
bin8        2.0547s  1.8672s  3.9219s  205.4688ns 186.7188ns 392.1875ns
vector      0.3594s  0.2891s  0.6484s   35.9375ns  28.9062ns  64.8438ns
shuffle     0.1328s  0.3438s  0.4766s   13.2812ns  34.3750ns  47.6562ns
tree        2.0781s  1.7734s  3.8516s  207.8125ns 177.3438ns 385.1562ns
treeasm     1.4297s  0.7422s  2.1719s  142.9688ns  74.2188ns 217.1875ns
bmi2        0.0938s  0.0703s  0.1641s    9.3750ns   7.0312ns  16.4062ns

实施

baseline 是一种除了读取输入外什么都不做的实现。它的目的是测量函数调用和内存访问开销。
count 是一种“天真的”实现，它存储一个占用图，指示哪些方块上已经有棋子
bitcount 是同一件事，但占用图存储为位图。 __builtin_popcount 用于编码，大大加快了速度。如果改用手写的 popcount，bitcount 仍然是最快的可移植编码实现。
decrement 是第二个简单的实现。它存储棋盘每个方格的编码，在添加一块之后，右边的所有方格数字都会递减。
bin4、bin5 和 bin8 使用 bin 大小为 4、5、和 .
shuffle 基于 Fisher-Yates shuffle 计算略有不同的编码。它的工作原理是重建随机值，这些随机值会进入随机播放，生成我们想要编码的排列。该代码无分支且快速，尤其是在解码时。
vector 使用由建议的五位数向量。
tree使用了一个difference tree，这是我编的一个数据结构。它是一棵深度为 ⌈log₂ n⌉ 的完整二叉树，其中叶子代表每个方块，每个叶子路径上的内部节点总和为该方块的代码（仅添加您向右走的节点）。不存储平方数，导致 n − 1 个字的额外内存。

有了这个数据结构，我们可以在⌈log₂ n⌉ − 1 步中计算每个方块的代码并标记一个正方形占用相同的步数。内部循环是 very simple，包括一个分支和两个动作，具体取决于您是向左下降还是向右下降。在 ARM 上，此分支编译为一些条件指令，从而实现非常快速的实现。在 x86 上，gcc 和 clang 都不够聪明，无法摆脱分支。
treeasm是tree的变体，使用inline assembly实现tree的内循环 小心操作进位标志，没有分支。
bmi2使用BMI2指令集中的pdep和pext指令以非常快速的方式实现算法。

对于我的实际项目，我可能会使用 shuffle 实现，因为它是最快的，不依赖于任何不可移植的扩展（例如 Intel intrinsics）或实现细节（例如 128 位整数的可用性）。

我怎样才能有效地encode/decode压缩职位描述？

How can I effectively encode/decode a compressed position description?

c

encoding

compression

chess

编码

问题

问题澄清

实施