如何从汉明球中的一个字节计算所有最近的邻居

Question

我想从给定字节计算所有可能的汉明邻居，并具有最大汉明距离。

对于 1 的汉明距离，我创建了这个函数：

public static ArrayList<Byte> hammingNeighbours(byte input, int maxDistance){
    ArrayList<Byte> neighbours = new ArrayList<>();
    neighbours.add(input);
    byte value;;
    byte mask = 1;


        for (int i = 0; i < 8; i++) {
            value = (byte) (input ^mask);
            neighbours.add(value);
            mask = (byte) (mask << 1);

        }
    return neighbours;
}

但是如何添加距离 > 1 的邻居？有人可以帮我解决这个问题吗？

此致

Answer 1

好的，经过简单的考虑，我可以使用我的第一个代码 post 并通过简单的递归扩展它来计算所有邻居：

public static HashSet<Byte> hammingNeighbours(byte input, int maxDistance){
    HashSet<Byte> neighbours = new HashSet<>();
    neighbours.add(input);
    byte value;;
    byte mask = 1;


        for (int i = 0; i < 8; i++) {
            value = (byte) (input ^mask);
            if(maxDistance > 1){
            neighbours.addAll(hammingNeighbours(value,maxDistance -1));
            }
            else{
                neighbours.add(value);
            }
            mask = (byte) (mask << 1);

        }
    return neighbours;
}

您可以使用此示例代码对其进行测试：

 HashSet<Byte> bset = hammingNeighbours((byte) 0, 2);
    System.out.println(bset.size());
    for (Byte b : bset) {
        System.out.println(String.format("%8s", Integer.toBinaryString(b & 0xFF)).replace(' ', '0'));;
    }

Answer 2

正如我在评论中所说，所有没有距离 == 1 或 0 的 byte 都是有效的。但是如果你想要一个算法，它会给你最多 maxDist 的所有字节，你可以这样做一个递归方法：

public static void getNeighbours(ArrayList<Byte> nbrs, byte input, int bit, int maxDist) {
    if(maxDist == 0 || bit == 8) {
        nbrs.add(input);
    } else {
        getNeighbours(nbrs, (byte) (input^(1<<bit)), bit+1, maxDist-1);
        getNeighbours(nbrs, input, bit+1, maxDist);
    }
}

如果您只想要恰好 maxDist 的字节，则只需添加 if(maxDist == 0) 并终止分支 if(bit == 8)

如何从汉明球中的一个字节计算所有最近的邻居

how to calculate all nearest neighbours from a byte in a hamming ball

java

nearest-neighbor

hamming-distance