python - 搜索最不像一组位串的位串

Question

我有一组位串:{'0011', '1100', '1110'}(一组中的所有位串都具有相同的长度)。

我想快速找到与集合最大相似度最小的相同长度的位串。最大相似度可以这样计算:

def max_similarity(bitstring, set):
    max = 0
    for item in set:
        temp = 0
        for i in range(len(bitstring)):
            if bitstring[i] == item[i]:
                temp += 1
        if temp > max:
            max = temp
    return max

我知道我可以遍历该长度的所有可能的位串，计算每个位的最大相似度，最后保留最小的迭代次数。但这解决了O(2 ^ n)中的问题。我想知道是否有人看到任何更快的选择。

我一直在玩Pythons XOR:

def int2bin(integer, digits):
    if integer >= 0:
        return bin(integer)[2:].zfill(digits)
    else:
        return bin(2**digits + integer)[2:]


def XOR(bitset):  
    intset = [int('{}'.format(bitstring), 2) for bitstring in bitset]

    digits = len(bitset.pop())

    if len(intset) == 1:
        return int2bin(~intset.pop(), digits)        
    else:
        curr = 0    
        while intset:
            curr = curr ^ intset.pop()

        return int2bin(curr, digits)

if __name__ == '__main__':
    bitset1 = {'0011', '1100', '1110'}
    bitset2 = {'01001', '11100', '10111'}
    print(XOR(bitset1))
    print(XOR(bitset2))

>>> python test.py
0001
00010

(从intt_a盗取的函数int2bin)

但是我发现它仅适用于某些输入，不适用于其他输入。在上面的测试中，它找到了bitset2的正确解决方案，但没有找到bitset1的正确解决方案。是否有低于O(2 ^ n)的解决方案？

Answer 1

这个问题部分是算法上的(什么是解决方案的最佳算法)，部分是Python问题(要使用Python的哪些部分然后有效地实现该最佳算法)。

关于算法:将一个位串到一组(相同大小)位串的最大距离定义为目标位串与该组中的任何字符串所不同的最大位数。该算法的目标是找到一个新的位串，其长度与集合中具有最小最大距离的字符串的长度相同。

假设所有的起始位串都是不同的(因为它被定义为一个集合，而不是一个列表)。您正在计算的距离称为汉明距离，因此您正在寻找的新位串的汉明距离到一组起始字符串的最小距离。

生成所有合适长度的可能的位串并计算到每个起始串的最大距离是蛮力解决的问题，可以使用回溯来优化(*)(一旦超过候选位的最低电流最大值，则丢弃结果)字符串)。

(*:对于希望更正我的拼写的人，请考虑以下事实:我使用的是英国英语，而不是美国英语-请随时提出改进建议)

但是，该问题也可以如下看待。

对于长度为1的位字符串，字符串的整个空间只有两个选项{'0', '1'}。可以看到'0'和'1'位于长度为1的线段的任一端，彼此之间的距离为1。

对于长度为2的位串，字符串的整个空间具有4个选项，即0到3的位表示{'00', '01', '10', '11'} 0距离1距离1和2，两者都距离1距离3。当可视化时，它们形成正方形的四个角，彼此之间的距离不得超过2步。

对于长度为3的位串，整个空间有8个选项，即0到7的位表示形式。可视化时，形成一个立方体的8个角，彼此之间的距离都不超过3步。

这种模式继续存在(变成4D超立方体，5D等)，找到问题的答案有效地转化为:给定这些图之一上的一组角，找到距它们中最大距离最小的点。

给定这样的图形，找到这样一个点的算法将是:

从一个集合中的点列表开始。如果只有一个，那是微不足道的答案。

将当前距离设置为1。

对于所有集合，将其添加到距集合中已有点仅一步之遥的任何点上。

相交所有结果集；如果交点不为空，则所有这些点都是距起始点集的当前距离(或小于)的当前点；否则，将当前距离增加1并转到步骤3。

可以通过跟踪将访问的点添加到集合中(对于长位字符串)来跟踪访问的点，以避免重复重复添加相同的点，从而快速减慢给定算法的速度，从而进一步优化此过程。 IE。您可以将 {'001'}转换为 {'001', '101', '011', '000'}，而不是将 [{'001'}]转换为 [{'001'}, {'101', '011', '000'}]-集的并集仍然可以使您在1步或更少的步骤内就可以达到所有点，但是通过查找所有步骤，该系列中的下一步将更易于计算距离较远的点，但不包括前一个方向的点。

实际上，找到一个步骤很简单，如果将字符串转换为表示形式的数字，然后按位字符串长度计算具有相同位字符串长度的所有单个“1”位数字，即按位或计算所有数字的异或，即要查找距 '001'一步之遥的所有点，可以将 1， 4和 2与 1异或，生成 {5, 3, 0}，匹配正确的点。

将所有内容放在一起使用Python进行压缩(无需对较长的字符串进行优化):

def closest(strings):
    if len(strings) == 1:
        return next(iter(strings))

    size = len(next(iter(strings)))
    points = [{int(s, 2)} for s in strings]
    powers = {1 << n for n in range(size)}

    d = 0
    while True:
        d += 1
        points = [{n ^ p for p in powers for n in nums} | nums for nums in points]
        intersection = set.intersection(*points)
        if len(intersection) > 0:
            return d, {f"{n:b}".zfill(size) for n in intersection}


print(closest({'1000', '0001', '0011'}))

请注意， closest返回实际距离和所有最佳答案，而不仅仅是一个。输出:

(2, {'0000', '0010', '1001', '0001', '1011'})

将讨论的优化添加到 closest中:

def closest_optimised(strings):
    if len(strings) == 1:
        return next(iter(strings))

    size = len(next(iter(strings)))
    points = [({int(s, 2)}, {int(s, 2)}) for s in strings]
    powers = {1 << n for n in range(size)}

    d = 0
    while True:
        d += 1
        new_points = [{n ^ p for p in powers for n in rp} - ap for ap, rp in points]
        points = [(ap | np, np) for (ap, _), np in zip(points, new_points)]
        intersection = set.intersection(*[ap for ap, _ in points])
        if len(intersection) > 0:
            return d, {f"{n:b}".zfill(size) for n in intersection}

请注意，对于这些设置，通过事件探查器运行此代码可使优化的代码平均运行大约一半的时间:

from random import randint

s = 10
x = 500
numbers = [randint(0, 2**s-1) for _ in range(x)]
number_strings = {f"{n:b}".zfill(s) for n in numbers}
print(number_strings)
print(closest_optimised(number_strings))
print(closest(number_strings))

编辑:出于好奇，我将示例与问题中给出的原始示例进行对比，发现它经常返回的结果远非最佳。我没有试图找出原因，但我认为值得一提。

有人指出，OP可能实际上想要与所有提供的位串具有最大汉明距离的点。使用类似的方法:

def farthest(strings):
    s = next(iter(strings))
    size = len(s)
    if len(strings) == 1:
        return ''.join(['0' if c == '1' else '1' for c in s])

    all_visited = {int(s, 2) for s in strings}
    visited = [set(), all_visited]
    powers = {1 << n for n in range(size)}

    d = 0
    while True:
        d += 1
        visited.append({n ^ p for p in powers for n in visited[-1]} - all_visited)
        all_visited = all_visited | visited[-1]
        if len(all_visited) == 2**size:
            return d, {f"{n:b}".zfill(size) for n in visited[-1]}