搜索bitstring最不像一组位串

Question

我有一组位串：qazxsw poi（一组中的所有位串都具有相同的长度）。

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

{'0011', '1100', '1110'}

我知道我可以迭代该长度的所有可能的位串，计算每个位的最大相似度，最后保持这些迭代中的最小值。但这解决了O（2 ^ n）中的问题。我想知道是否有人看到任何更快的替代方案。

我一直在玩Pythons XOR：

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

（函数int2bin从

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

被盗）

但我发现它适用于某些输入，而不适用于其他输入。在上面的测试中，它找到了bitset2的正确解决方案，但不是bitset1。任何低于O（2 ^ n）的解决方案都可用？

Answer 1

这个问题部分是算法（什么是获得解决方案的最佳算法），部分是Python问题（关于Python的哪些部分用于高效实现最佳算法）。

在算法上：您将位串的最大距离定义为一组（相同大小）位串，这是目标位串与该组中任何字符串不同的最大位数。该算法的目标是找到一个新的位串，其长度与具有最低最大距离的集合中的字符串相同。

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

生成正确长度的所有可能位串并计算到每个起始字符串的最大距离是强制问题，可以使用回溯优化（*）（一旦候选位超过最低当前最大值就丢弃结果）串）。

（*：对于想要纠正我的拼写的人，请考虑我使用英国英语，而不是美国英语的事实 - 随意提出改进意见）

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

对于长度为1的位串，字符串的整个空间只有两个选项，here。这可以看作是{'0', '1'}和'0'，它们位于长度为1的线段的两端，两者之间的距离都是1。

对于长度为2的位串，字符串的整个空间有4个选项，即0到3的位表示'1' 0距离1和2的距离1，两者距离3的距离为1。当可视化时，它们形成一个正方形的四个角落，它们都不会超过任何其他两个步骤。

对于长度为3的位串，整个空间有8个选项，即0到7的位表示。当可视化时，形成立方体的8个角，它们中的任何一个都不超过3个步。

这种模式继续（进入4D超立方体，5D等）并找到问题的答案有效地转换为：给定这些图形中的一个角上的一组角，找到与它们中的任何一个具有最小最大距离的点。

一个找到这样一个点的算法，给出一个像这样的图：

1. 从他们自己的集合中的点列表开始;如果只有一个，这是微不足道的答案。
2. 将当前距离设置为1。
3. 对于所有集合，只需距离集合中已有的点一步即可添加任何点。
4. 相交所有结果集;如果交叉点不为空，则这些是距离起始点集当前距离（或更小）的所有点;否则，将当前距离增加1并转到步骤3。

这可能通过跟踪被访问的点（因为它们被添加到集合中（对于长位字符串）而进一步优化，以避免反复添加相同的点，从而快速减慢给定的算法。即而不是将{'00', '01', '10', '11'}变成{'001'}，你可以从{'001', '101', '011', '000'}到[{'001'}] - 集合的联合仍然可以获得所有在1步或更少步骤内可达到的点，但是系列的下一步将更容易计算，通过找到所有更远一点的点，但不包括上一个方向的点。

找到一步实际上是非常简单的，如果你将字符串转换成代表的数字并计算独占的位或数字与所有具有相同位串长度的单个'1'位数，即找到距离[{'001'}, {'101', '011', '000'}]一步之遥的所有点，你可以用'001'，1和4 xor 2，产生1，匹配正确的点。

将所有这些放在Python中（没有针对更长字符串的优化）：

{5, 3, 0}

请注意，

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}

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

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

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))

Answer 2

这是一个成本为

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]}

的算法，其中O(n * b)是集合的大小，n是固定的比特长度。

该算法的直觉是检查每个位索引（0或1）的多数位位置，并相应地得分。

得分越高意味着给定的位串具有与大多数时间相比大多数位的位位置。虽然，我没有处理过关系。

b

另外注意，我传递的是一个列表而不是一个集合，因为python集的排序是非确定性的。

用法：

import operator

def max_hamming(bitstrings):
    n_bits = len(bitstrings[0])
    # Track bit set/unset for each bit position
    scores = {
        n: {'0': [], '1': []} for n in range(n_bits)
    }
    # Increment on each bit position if not with the majority
    total = {b: 0 for b in bitstrings}

    # O(b * n)
    for n in range(n_bits):
        n_set = 0
        for b in bitstrings:
            is_set = b[n]
            scores[n][is_set].append(b)
            if is_set:
                n_set += 1

        # If majority have this bit set, give a point to those with unset or vice versa
        outliers = scores[n]['0'] if n_set > len(bitstrings) else scores[n]['1']
        for s in outliers:
            total[s] += 1

    return max(total.items(), key=operator.itemgetter(1))[0]

Answer 3

我可以使用

bitset1 = [
    '0011',
    '1100',
    '1110'
]
bitset2 = [
    '01001',
    '11100',
    '10111'
]
print(max_hamming(bitset1))
print(max_hamming(bitset2))

或者这应该是算法吗？让我们假设一切都像你拥有的numpy。

bitstring

现在我知道你说

import numpy as np

def bitstring2np(bitstring):
    """
    Convert a bitstring to np.array
    i.e. '0011' to np.array([0, 0, 1, 1])
    """
    return np.array([int(bit) for bit in bitstring], dtype=int)

def unlike(bitset):
    """
    Gets the most 'unlike' string between a bitset.
    Accomplishes this by creating a 2D array from the bitsets,
    figuring out the number of 1s in a column, and if that
    number of 1s is >=50%, then gives it a 0 in that place, otherwise
    gives it a 1.
    """
    bset = list(bitset)
    # Create an empty 2D array to store the bitsets into
    arr = np.empty((len(bset), len(bset[0])), dtype=int)
    for idx in range(len(bset)):
        # Store that bitset into the row of our array
        arr[idx,:] = bitstring2np(bset[idx])

    # Count the number of 1's in each column
    nonzero = np.count_nonzero(arr, axis=0)
    total = len(bset) # how many to compare against
    # Since you want the most unlike and since we are counting
    # number of 1s in a column, if the rate is >=.5 give it a 0, otherwise 
    # 1
    most_unlike = ''.join('0' if count/total >=.5 else '1' for count in nonzero)

    return most_unlike


>>> print(unlike(bitset1))
0001
>>> print(unlike(bitset2))  
00010

不是0001的正确解决方案，但我很确定它是除非我没有正确理解这个问题。