标签: hamming-distance

我读了关于汉明重量的维基百科文章,并注意到一些有趣的东西:

因此它等同于Hamming distance来自相同长度的全零字符串.对于最典型的情况,一串位,这是字符串中1的数字.在这个二进制的情况下,它也被称为人口数popcount或横向总和.

[强调我的]

所以有些事发生在我身上.我可以XOR通过它们计算两个弦之间的汉明距离,然后取得结果弦的汉明重量(POPCOUNT)吗？

有点像这样的东西(使用gcc内在函数):

#include <stdint.h>

int hammingDistance (uint64_t x, uint64_t y) {
        uint64_t res = x ^ y;
        return __builtin_popcountll (res);
}

现在,至于为什么我想要这样做,好吧,在某些平台上,是的,这只会转换为gcc发出对计算函数的调用popcount.例如,在没有的x64上popcnt,gcc吐出(Godbolt的GCC Online):

hammingDistance:
    sub rsp, 8
    xor rdi, rsi
    call    __popcountdi2
    add rsp, 8
    ret

OTOH,如果你有一个支持POPCOUNT的平台,比如x64模型包括nehalem和之后(有POPCNT),你得到(Godbolt的GCC Online):

hammingDistance:
    xor rdi, rsi
    popcnt  rax, rdi
    ret …

我有两个相同长度的numpy数组包含二进制值

import numpy as np
a=np.array([1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0])
b=np.array([1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1])

我想尽可能快地计算它们之间的汉明距离,因为我有数以百万计的这样的距离计算.

一个简单但缓慢的选择(取自维基百科):

%timeit sum(ch1 != ch2 for ch1, ch2 in zip(a, b))
10000 loops, best of 3: 79 us per loop

我已经提出了更快的选项,灵感来自堆栈溢出的一些答案.

%timeit np.sum(np.bitwise_xor(a,b))
100000 loops, best of 3: 6.94 us per loop …

在为计算机网络课程学习时,教授谈到了示例代码中2个有效代码字之间的汉明距离.我已经读过关于汉明距离的内容,从描述两个字符串之间的距离差异的角度来看它是有意义的.例如:

Code Word 1 = 10110 

发送方发送代码字1,并且引入了错误,接收方接收10100.因此您看到第4位已损坏.这将导致汉明距离为1,因为:

Valid Code Word: 10110
Error Code Word: 10100
                 -----
XOR              00010

2个字符串的XOR结果为1,因此汉明距离为1.我理解它到那一点.但是教授要求:

• 标准CRC-16位协议的汉明距离是多少？
• 标准CRC-32位协议的汉明距离是多少？

我有点困惑,想知道是否有人可以提供帮助.谢谢.

我一直在Go中使用汇编语言,我写了一个Hamming Weight函数作为练习.

我在这个SO答案上建立了一个原生的Go版本,而汇编版本是基于AMD的这个文档(第180页).在对两个函数进行基准测试后,我发现本机Go版本比汇编版本快1.5倍 - 2倍,尽管手写的汇编版本几乎与输出版本完全相同go tool 6g -S popcount.go.

输出来自 go test -bench=.

PASS
BenchmarkPopCount       100000000               19.4 ns/op 
BenchmarkPopCount_g     200000000                8.97 ns/op
ok      popcount   4.777s

popcount.go

package popcount

func popCount(i uint32) uint32 // Defined in popcount_amd64.s

func popCount_g(i uint32) uint32 {
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> …

我正在寻找一个数据结构来处理包含512个二进制值的二进制字符串.

我的目标是向结构发送查询并获取包含距离较远的所有数据的结果集.

我的第一个想法是使用kd树.但是这些树木的高度非常慢.我的第二个想法是使用lsh方法(minHash/superbit)lsh.但为此,我还必须有一个结构来执行有效的搜索

任何想法如何处理这些大数据？

**更新**一些细节说明:

• 汉明距离只存在一个上限,可能是128.但是我及时不知道上限
• 插入或删除会很好,但我也可以重建图形(数据库只更新一周)
• 结果集必须包含所有相关节点(我不是在寻找knn)

设a和b是具有8位整数(0-255)的相同大小的向量.我想计算这些向量不同的位数,即通过串联这些数字的二进制表示形成的向量之间的汉明距离.例如:

a = [127,255]
b= [127,240]

使用numpy库

np.bitwise_xor(a,b)
# Output: array([ 0, 15])

我现在需要的是二进制表示上述数组的每个元素,并在数组的所有元素中计数1的数量.上面的例子将给出汉明距离0 + 4 = 4.在Python中任何快速而优雅的解决方案？

我现在刚刚学习 python 3。\n\'\'\'它要求用户提供两个字符串并找到字符串之间的汉明距离。输入序列应该只包含核苷酸 \xe2\x80\x98A\ xe2\x80\x99、\xe2\x80\x99T\xe2\x80\x99、\xe2\x80\x98G\xe2\x80\x99 和 \xe2\x80\x98C\xe2\x80\x99。如果用户输入无效字符，程序应要求用户重新输入序列。程序应能够比较字符串的长度是否相同。如果字符串长度不同，程序应要求用户再次输入字符串。用户应该能够输入大写、小写或两种情况作为输入 \'\'\'

该程序应按以下格式打印输出：

please enter string one: GATTACA\nplease enter string two: GACTATA\nGATTACA\n|| || |  \nGACTATA\nThe hamming distance of sequence GATTACA and GACTATA is 2\nSo the Hamming distance is 2.\n

我已经在下面尝试过，但无法得到答案。

def hamming_distance(string1, string2):\n    string1 = input("please enter first sequence")\n    string2 = input("please enter second sequence")\n    distance = 0\n     L = len(string1)\n    for i in range(L):\n        if string1[i] != string2[i]:\n            distance += 1\n    return distance\n

我有一个可能性列表和所需的输入:

possibles = [20, 30, 40, 50, 60, 70, 80, 100]
desired = [20, 30, 40]

我想通过列表生成close.例:

# Distance of 1 (i.e. 1 element changes to a close-by)
[30, 30, 40]
[20, 40, 40]
[20, 30, 30]
[20, 30, 50]

# Distance of 2:
[40, 30, 40]
[30, 30, 50]
[30, 40, 40]
...

我当前的版本一次只改变一个元素,因此,一旦距离超过1,我就会错过很多组合.

def generate_close_by(possibles, desired):
    for k in range(1, 4):
        for i, elt in enumerate(desired):
            id = possibles.index(elt)

            new = desired[:]
            if id < len(possibles)-k-1:
                new[i] = …

我有一组n(~1000000)字符串(DNA序列)存储在列表trans中.我必须找到列表中所有序列的最小汉明距离.我实施了一个天真的暴力算法,它运行了一天多,还没有给出解决方案.我的代码是

dmin=len(trans[0])
for i in xrange(len(trans)):
    for j in xrange(i+1,len(trans)):
            dist=hamdist(trans[i][:-1], trans[j][:-1])
            if dist < dmin:
                    dmin = dist

有没有更有效的方法来做到这一点？Hamdist是我写的一个函数,用于查找汉明距离.它是

def hamdist(str1, str2):
    diffs = 0
    if len(str1) != len(str2):
        return max(len(str1),len(str2))
    for ch1, ch2 in zip(str1, str2):
        if ch1 != ch2:
          diffs += 1
    return diffs

我发现了一个有趣的算法来计算这个站点的汉明距离:

def hamming2(x,y):
    """Calculate the Hamming distance between two bit strings"""
    assert len(x) == len(y)
    count,z = 0,x^y
    while z:
        count += 1
        z &= z-1 # magic!
    return count

关键是这个算法只适用于位串,我试图比较两个二进制字符串,但它们是字符串格式,如

'100010'
'101000'

如何使它们与此算法一起使用？