有一个包含N个固定长度字符串的数据库.有一个相同长度的查询字符串.问题是从数据库中获取具有最小汉明距离的第k个字符串到q.
N很小(约400),弦长,长度固定.数据库不会更改,因此我们可以预先计算索引.查询变化很大,缓存和/或预计算不是一种选择.每秒有很多.我们总是需要k结果,即使k-1结果匹配0(在汉明距离上排序并取第一个k,因此局部敏感散列和类似方法不会这样做).kd-tree和类似的空间分区可能比线性搜索表现更差(字符串可能很长).BK树目前是最好的选择,但它仍然比它需要的慢和复杂.
感觉就像有一个算法,它将构建一个索引,它将在很少的步骤中丢弃大多数条目,留下k <= t << N个条目来计算实际的汉明距离.
人们建议基于Levenstein距离的模糊字符串匹配 - 谢谢,但问题要简单得多.基于广义距离度量的方法(如BK树)是好的,但也许有利用上述事实(小DB /长固定大小的字符串,简单的汉明距离)
链接,关键字,论文,想法？=)
在ruby中,计算两个无符号整数之间的位差(例如汉明距离)的最有效方法是什么？
例如,我有一个整数a = 2323409845和b = 1782647144.
他们的二进制表示是:
a = 10001010011111000110101110110101
b = 01101010010000010000100101101000
a和b之间的位差是17 ..
我可以对它们进行逻辑XOR,但这会给我一个不同的整数!= 17,然后我必须迭代结果的二进制表示并计算#s的1.
计算位差的最有效方法是什么？
现在,答案是否会改变以计算许多整数序列的比特差异？例如,给定2个无符号整数序列:
x = {2323409845,641760420,509499086....}
y = {uint,uint,uint...}
计算两个序列之间的比特差异的最有效方法是什么？
你会迭代序列,还是有更快的方法来计算整个序列的差异？
汉明距离:
例如,两个二进制数:1011和1000的HD(汉明距离)是2.
10000和01111的HD是5.
这是代码:
有人可以向我解释一下吗？
谢谢!
short HammingDist(short x, short y)
{
short dist = 0;
char val = x^y;// what's the meaning?
while(val)
{
++dist;
val &= val - 1; // why?
}
return dist;
}
输入:图G输出:几个独立的集合,因此节点对所有独立集的成员资格是唯一的.因此,节点与其自己的集合中的任何节点都没有连接.这是一个示例路径.
由于在这里要求澄清另一个改写:
将给定的图形划分为多个集合
我可以通过集合中的成员资格告诉所有其他节点节点,例如,如果节点i仅存在于集合A中,则集合A中不应存在其他节点
如果节点j出现在集合A和B中,则集合A和B中不应存在其他节点.如果节点的成员资格由位模式编码,则这些位模式的汉明距离至少为1
如果图中有两个节点相邻,则它们不应出现在同一个集合中,因此是一个独立的集合
示例:B没有相邻节点D => A,A => D.
解:
A具有位模式10并且其集合中没有相邻节点.B有位模式11,没有相邻节点,D有01,因此所有节点的汉明距离至少为1,没有相邻节点=>正确
错了,因为D和A连接在一起:
A在其集合中具有位模式10和D,它们是相邻的.B具有位模式11而没有相邻节点,D具有11和B一样,因此在该解决方案中存在两个错误,因此不被接受.
当然,随着图表中节点数量的增加,这应该扩展到更多集合,因为您至少需要log(n)集合.
我已经在MAX-SAT中编写了一个转换,为此使用了一个sat-solver.但条款的数量只是很大.更直接的方法会很好.到目前为止,我有一个近似值,但我想要一个精确的解决方案或至少更好的近似.
我尝试过一种方法,我使用粒子群从任意解决方案优化到更好的解决方案.然而,运行时间非常糟糕,结果远非如此.我正在寻找动态算法或其他东西,但我无法理解如何划分和征服这个问题.
问题:
我有N(~100k-1m)个字符串,每个D(例如2000个)字符长,字母低(例如3个可能的字符).我想对这些字符串进行排序,使得相邻字符串之间的可能变化很少(例如,汉明距离较低).解决方案不一定是最好的,但越接近越好.
例
N=4
D=5
//initial strings
1. aaacb
2. bacba
3. acacb
4. cbcba
//sorted so that hamming distance between adjacent strings is low
1. aaacb
3. acacb (Hamming distance 1->3 = 1)
4. cbcba (Hamming distance 3->4 = 4)
2. bacba (Hamming distance 4->2 = 2)
关于这个问题的想法
我有一种不好的感觉,这是一个非常重要的问题.如果我们将每个字符串视为一个节点并将其他字符串的距离视为边缘,那么我们就会看到一个旅行商问题.大量的字符串意味着预先计算所有成对距离可能是不可行的,我认为将问题转化为更像加拿大旅行者问题.
目前我的解决方案是使用VP树来找到问题的贪婪最近邻类型解决方案
curr_string = a randomly chosen string from full set
while(tree not empty)
found_string = find nearest string in tree
tree.remove(found_string)
sorted_list.add(curr_string)
curr_string = found_string
但初步结果似乎很差.散列字符串使更多类似的字符串更接近可能是另一种选择但我对这将提供的解决方案有多好或者它将如何扩展到这种大小的数据知之甚少.
我有一个表A,其中有一个列'template_phash'.我存储了400K图像生成的phash.
现在我拍摄一张随机图像并从该图像生成一个镜头.
现在我如何查询,以便我可以从表A获得汉明距离差小于阈值的记录,比如说20.
我在SQL中看到了二进制字符串的汉明距离,但无法弄明白.
我想我发现我需要制作一个功能来实现这个但是怎么做？
我的两个phash都在BigInt中,例如:7641692061273169067
请帮我制作这个功能,以便我可以查询
SELECT product_id, HAMMING_DISTANCE(phash1, phash2) as hd
FROM A
WHERE hd < 20 ORDER BY hd ASC;
我有一组位串：（{'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 …我有一个包含大约100万个文档的MongoDB.这些文档都有一个字符串,表示一个1位和0位的256位bin,如:
0110101010101010110101010101
理想情况下,我想查询近二进制匹配.这意味着,如果两个文件具有以下数字.是的,这是汉明距离.
Mongo目前不支持此功能.所以,我不得不在应用程序层中这样做.
因此,鉴于此,我试图找到一种方法来避免在文档之间进行单独的汉明距离比较.这使得时间基本上不可能完成.
我有很多内存.并且,在ruby中,似乎有一个伟大的宝石(算法)可以创建许多树,我似乎没有任何工作(还)可以减少我需要做的查询数量.
理想情况下,我想制作100万个查询,找到接近重复的字符串,并能够更新它们以反映这一点.
任何人的想法将不胜感激.
如果您有n二进制字符串,每个长度m,是否有更快的方法来确定任何一对之间的最小汉明距离,而不是比较所有O(n^2)对和每个以计算其汉明距离？
那可以在不到一定的
O(n^2m)时间内完成吗？
除了其他任何东西,如下所述,汉明距离是一个适当的距离函数,因此满足三角不等式,这让我觉得应该有一个更快的解决方案.
我读了关于汉明重量的维基百科文章,并注意到一些有趣的东西:
因此它等同于
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 …