Сумма всех расстояний Хэмминга данной строки A от подстрок длины | A | другой строки B

Question

Для двух двоичных строк a и b найдите сумму расстояний Хэмминга между a и всеми смежными подстроками b длины | a |.

inputCopy:

01

00111

outputCopy:

3

Объяснение: Для первого примера выборки существует четыре смежных подстроки b длины | a |: «00», «01», «11» и «11». Расстояние между «01» и «00» составляет | 0 - 0 | + | 1 - 0 | = 1. Расстояние между «01» и «01» составляет | 0 - 0 | + | 1 - 1 | = 0. Расстояние между «01» и «11» равно | 0 - 1 | + | 1 - 1 | = 1. Последнее расстояние учитывается дважды, так как есть строка вхождения «11». Сумма этих расстояний редактирования составляет 1 + 0 + 1 + 1 = 3.

В этом вопросе я думаю только о решении грубой силы со временной сложностью O (| a |. | B |) как алгоритм сопоставления строк ... Есть ли быстрее al go для решения этой проблемы

Answer 1

Вы можете сделать это в линейном времени и в постоянном пространстве.

Каждый бит в a будет сравниваться с |b| - |a| + 1 битами в b, и каждое несовпадение добавит 1 к сумме всех Расстояния Хэмминга.

Кроме того, для каждого бита a нам не нужно знать всю битовую последовательность, с которой она будет сравниваться, начиная с b. Нам нужно только знать, сколько нулей и сколько их. По мере продвижения вперед на один бит в a соответствующий диапазон сдвигается вперед на один бит в b, и мы можем легко обновить эти значения в постоянное время.

Вот реализация в python:

def HammingSum(a,b):
    # compare initial range in b to first bit in a
    range0 = len(b)-len(a)+1
    numZeros = 0
    numOnes = 0
    for i in range(range0):
        if b[i]=='0':
            numZeros += 1
        else:
            numOnes += 1
    total = numOnes if a[0]=='0' else numZeros

    #adjust the range as we compare to the other bits

    for i in range(len(b)-range0):
        #count the bit we're adding to the end of the range
        if b[range0+i]=='0':
            numZeros += 1
        else:
            numOnes += 1

        #uncount the bit we remove from the start of the range
        if b[i]=='0':
            numZeros -= 1
        else:
            numOnes -= 1

        #compare range with bit in a
        total += numOnes if a[i+1]=='0' else numZeros

    return total

Answer 2

Поскольку вы вычисляете сумму расстояний Хэмминга, это можно сделать очень быстро:

H := sum of Hamming distances
compute array A and B such as the following:
    A[i]: the number of zeros up to i-th element of b
    B[i]: the number of ones up to i-th element of b

iterate over elements of a for i <- 0:|a|-1:
    as a[i] should be compared with all elemetns of b[i] .. b[|b|-|a|+i]
    its effect over the value of summing distances is:
        if a[i] == 0:
            H += B[|b|-|a|+i] - B[i-1]
        else: 
            H += A[|b|-|a|-1] - A[i-1]

В приведенном выше псевдокоде B[|b|-|a|+i] - B[i-1] означает количество единиц между i -ым элементом и |b|-|a|+i -й элемент b тоже самое для A[|b|-|a|-1] - A[i-1]). Это элементы, с которыми i -й член a должен сравниваться для вычисления суммы расстояний Хэмминга. Следовательно, временная сложность этого алгоритма составляет \Theta(|a| + |b|).