如何有效地编码/解码压缩的位置描述？ [英] How can I effectively encode/decode a compressed position description?

问题描述

我正在为日本象棋变体编写一个表库。为了索引表基，我将每个象棋位置编码为整数。在编码步骤之一中，我对棋子在板上的位置进行编码。由于实际方法有点复杂，所以让我以一种简化的方式来解释问题。

I am writing a tablebase for a Japanese chess variant. To index the table base, I encode each chess position as an integer. In one of the encoding steps, I encode where the pieces are on the board. Since the actual method is a bit complicated, let me explain the problem in a simplified manner.

在残局表库中，我有（假设）我要在9个正方形的棋盘上分配六个不同的棋子。我可以用六元组（ a ， b ， c ， d ， e ， f ），其中每个变量 a 到 f 的数字都是0到8之间的数字（包括0和8）

In the endgame tablebase, I have (let's say) six distinct chess pieces that I want to distribute over a board with 9 squares. I can naïvely represent their positions by a six-tuple (a, b, c, d, e, f ) where each of the variables a to f is a number in the range 0 to 8 inclusive indicating where the corresponding chess piece is located.

但是，这种表示不是最佳的：没有两个棋子可以占据相同的正方形，但是前面提到的编码很高兴允许这样做。我们可以用六元组[ a 相同的来对相同的位置进行编码[ a，b'，c'，d'，e'，f'] > a 和以前一样， b'是一个介于0到7之间的数字，表示第二个片段所在的正方形的编号。通过为第一个未打开的每个正方形分配一个从0到7的数字来工作。例如，如果第一块在正方形3上，则第二块的正方形数字为：

However, this representation is not optimal: no two chess pieces can occupy the same square but the aforementioned encoding happily allows this. We can encode the same position by a six-tuple [a, b', c', d', e', f' ] where a is the same a as before, b' is a number from 0 to 7 inclusive indicating the number of the square the second piece is on. This works by assigning a number from 0 to 7 to each square the first piece is not on. For example, if the first piece is on square 3, the square numbers for the second piece are:

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到5的数字，等等。例如，朴素的编码（5，2，3，0 ，7、4）产生紧凑编码（5、2、2、0、3、1）：

the other pieces are encoded similarly, c' as a number from 0 to 6, d' as a number from 0 to 5, etc. For example the naïve encoding (5, 2, 3, 0, 7, 4) yields the compact encoding (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

在我的实际编码中，我要编码的片段数不是固定的。但是，板上的平方数是。

In my actual encoding, the number of pieces I want to encode is not fixed. The number of squares on the board however is.

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

How can I efficiently convert the naïve representation to the compact representation and vice versa? I use standard C99 for the program. In the context of this question, I am not interested in answers that use non-standard constructs, inline assembly or intrinsics.

As这个问题似乎有些混乱：

As there seems to be some confusion about the question:

• 问题是找到一种切实有效的方法来实现天真之间的转换>和 compact 位置表示形式


• 这两种表示形式都是 n 个在一定范围内的整数元组。问题不在于如何将这些表示形式编码成其他形式。


• 在我遇到的一种情况下，平方数是25，而块数则是12。但是，我对适用于合理参数空间（例如，最多64个平方和最多32个片段）的实现感兴趣。


• 我对替代表示形式或编码（尤其是表示形式或并不是最理想的编码。


• 我也不感兴趣的是，紧凑表示形式不值得您付出努力。

• The question is to find a practically efficient way to implement the conversion between the naïve and the compact position representations
• Both representations are n-tuples of integers in certain ranges. The question is not about how to encode these representations into anything else.
• In one of the cases I have, the number of squares is 25 and the number of pieces is up to 12. I am however interested in an implementation that works for a reasonable parameter space (e.g. up to 64 squares and up to 32 pieces).
• I am not interested in alternative representations or encodings, especially representations or encodings that are not optimal.
• Nor am I interested in remarks that the compact representation isn't worth the effort.

推荐答案

我发现了一个更为优雅的解决方案，可使用64位整数以及一个用于编码和解码的单个循环来处理多达16个位置：

I have found a more elegant solution for up to 16 positions using 64-bit integers with a single loop for both encoding and decoding:

#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位无符号整数将16个值的数组保存在范围 0..15 。这样的数组可以在一个步骤中并行更新，提取值很简单，而删除值则​​比较麻烦，但仅需几个步骤。

The code uses 64-bit unsigned integers to hold arrays of 16 values in the range 0..15. Such an array can be updated in parallel in a single step, extracting a value is straightforward and deleting a value is a bit more cumbersome but still only a few steps.

您可以使用不可移植的128位整数（gcc和clang都支持类型 __ int128 ）将该方法扩展到25个位置，利用5位编码每个位置 5 * 25< 128 ，但是不可思议的常量编写起来比较麻烦。

You could extend this method to 25 positions using non-portable 128-bit integers (type __int128 is supported by both gcc and clang), encoding each position on 5 bits, taking advantage of the fact that 5 * 25 < 128, but the magical constants are more cumbersome to write.

这篇关于如何有效地编码/解码压缩的位置描述？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！