问题:
给定一个大的(~1亿)无符号32位整数列表,无符号32位整数输入值和最大汉明距离,返回在输入值的指定汉明距离内的所有列表成员.
保持列表的实际数据结构是开放的,性能要求决定了内存中的解决方案,构建数据结构的成本是次要的,查询数据结构的低成本是至关重要的.
例:
For a maximum Hamming Distance of 1 (values typically will be quite small)
And input:
00001000100000000000000001111101
The values:
01001000100000000000000001111101
00001000100000000010000001111101
should match because there is only 1 position in which the bits are different.
11001000100000000010000001111101
should not match because 3 bit positions are different.
到目前为止我的想法:
对于汉明距离为0的退化情况,只需使用排序列表并对特定输入值进行二分搜索.
如果汉明距离只有1,我可以翻转原始输入中的每一位并重复上述32次.
如何有效地(不扫描整个列表)发现汉明距离> 1的列表成员.
algorithm bit-manipulation bitwise-operators hamming-distance
对于我正在研究的问题,找到两个序列之间的距离来确定它们的相似性,序列顺序非常重要.但是,我所拥有的序列长度并不完全相同,所以我用空点填充任何不足的字符串,使得两个序列的长度相同,以满足汉明距离要求.我这样做是否有任何重大问题,因为我所关心的只是换位次数(不是像Levenshtein那样的插入或删除)？
我发现汉明距离比Levenshtein快得多,作为长度较长的序列的距离度量.何时应该使用Levenshtein距离(或Levenshtein距离的导数)而不是更便宜的汉明距离？汉明距离可以被认为是两个序列之间可能的Levenshtein距离的上限,因此如果我将两个序列进行比较以获得有序偏差的相似性度量而不是绝对最小的移动数量以匹配序列,则没有明显的我之所以选择Levenshtein而不是Hamming作为指标,是吗？
给定主题图像的散列"100111..10",我们希望在汉明距离为8的 Elasticsearch索引中找到所有相似的图像散列.
当然,查询可以返回距离大于8的图像,Elasticsearch或外部的脚本可以过滤结果集.但总搜索时间必须在1秒左右.
每个文档都有images包含图像哈希的嵌套字段:
{
"images": {
"type": "nested",
"properties": {
"pHashFingerprint": {"index": "not_analysed", "type": "string"}
}
}
}
事实: Elasticsearch模糊查询仅支持最大2的Levenshtein距离.
我们使用自定义标记生成器将64位字符串拆分为4组16位,并使用4个模糊查询进行4组搜索.
分析:
{
"analysis": {
"analyzer": {
"split4_fingerprint_analyzer": {
"type": "custom",
"tokenizer": "split4_fingerprint_tokenizer"
}
},
"tokenizer": {
"split4_fingerprint_tokenizer": {
"type": "pattern",
"group": 0,
"pattern": "([01]{16})"
}
}
}
}
然后新的字段映射:
"index_analyzer": "split4_fingerprint_analyzer",
然后查询:
{
"query": {
"filtered": {
"query": {
"nested": {
"path": "images",
"query": {
"bool": …我的数据库中有一个表,我将SHA256哈希存储在BINARY(32)列中.我正在寻找一种方法来计算列中条目的汉明距离到提供的值,即:
SELECT * FROM table
ORDER BY HAMMINGDISTANCE(hash, UNHEX(<insert supplied sha256 hash here>)) ASC
LIMIT 10
(如果您想知道,字符串A和B的汉明距离定义为BIT_COUNT(A^B),其中^是按位XOR运算符,BIT_COUNT返回二进制字符串中的1的数量).
现在,我知道^运算符和BIT_COUNT函数都只能在INTEGER上运行,所以我想说可能唯一的方法就是分解子字符串中的二进制字符串,将每个二进制子字符串转换为整数,计算汉明距离子串,然后添加它们.这个问题是它听起来非常复杂,效率不高,绝对不优雅.因此,我的问题是:你能提出更好的建议吗？(请注意我在共享主机上,因此我无法修改数据库服务器或加载库)
编辑(1):显然在PHP中加载整个表并进行计算是可能的,但我宁愿避免它,因为这个表可能会变得非常大.
编辑(2):数据库服务器是MySQL 5.1
编辑(3):我的答案包含我刚才描述的代码.
编辑(4):我刚刚发现使用4个BIGINT来存储哈希而不是BINARY(32)会产生大量的速度提升(速度提高100倍以上).请参阅下面的评论.
*这是一个简短的介绍,具体问题在最后一段以粗体显示.
我正在尝试生成具有给定汉明距离的所有字符串,以有效地解决生物信息学分配.
这个想法是,给定一个字符串(即'ACGTTGCATGTCGCATGATGCATGAGAGCT'),搜索单词的长度(即4)和在字符串中搜索该单词时可接受的不匹配(即1),返回最常用的单词或'突变'的话.
要清楚,给定字符串中的长度为4的单词可以是这个(在'[]'之间):
[ACGT]TGCATGTCGCATGATGCATGAGAGCT #ACGT
这个
A[CGTT]GCATGTCGCATGATGCATGAGAGCT #CGTT
或这个
ACGTTGCATGTCGCATGATGCATGAG[AGCT] #AGCT
我所做的是(并且它的效率非常低,而且当单词需要有10个字符时它真的很慢)会生成具有给定距离的所有可能的单词:
itertools.imap(''.join, itertools.product('ATCG', repeat=wordSize))
如果生成的单词(或其变异)出现在循环中,则搜索并比较给定字符串中的每个单词:
wordFromString = givenString[i:i+wordSize]
mismatches = sum(ch1 != ch2 for ch1, ch2 in zip(wordFromString, generatedWord))
if mismatches <= d:
#count that generated word in a list for future use
#(only need the most repeated)
我想要做的是,而不是生成所有可能的单词,只生成给定字符串中出现的具有给定数量的不匹配的单词的突变,换句话说,给定汉明距离和单词,返回所有可能的具有该(或更小)距离的变异单词,然后使用它们在给定的字符串中进行搜索.
我希望我很清楚.谢谢.
对于Data Structures项目,我必须找到两个单词之间的最短路径(例如"cat"和"dog"),一次只能更改一个字母.我们给出了一个拼字游戏单词列表,用于查找我们的路径.例如:
cat -> bat -> bet -> bot -> bog -> dog
我已经使用广度优先搜索解决了这个问题,但我正在寻找更好的东西(我用trie代表字典).
请给我一些更有效的方法(在速度和记忆方面)的想法.有些荒谬和/或挑战是首选.
我问过我的一个朋友(他是一名大三学生),他说这个问题没有有效的解决办法.他说我会学习为什么我参加算法课程.对此有何评论？
我们必须一个接一个地移动.我们不能去cat -> dat -> dag -> dog.我们还必须打印出遍历.
我想从汉明距离为(例如)1 的单词列表中构建一个图形,或者换句话说,如果它们只与一个字母(lo l - > lo t)不同,则连接两个单词.
所以给定
words = [ lol, lot, bot ]
图表将是
{
'lol' : [ 'lot' ],
'lot' : [ 'lol', 'bot' ],
'bot' : [ 'lot' ]
}
简单的方法是将列表中的每个单词与其他单词进行比较并计算不同的字符; 遗憾的是,这是一种O(N^2)算法.
我可以使用哪种algo/ds /策略来获得更好的性能？
另外,我们假设只有拉丁字符,并且所有单词都具有相同的长度.
我有一些存储在mysql中的哈希值,我将通过汉明距离进行比较.
存储的哈希值如下:
qw 1 ffe71b001820a1fd
qw 2 ffffb81c1c3838a0
qw 3 fff8381c1c3e3828
qw 4 fffa181c3c2e3920
qw 5 fffa981c1c3e2820
qw 6 ff5f1c38387c1c04
qw 7 fff1e0c1c38387ef
qw 8 fffa181c1c3e3820
qw 9 fffa381c1c3e3828
我通常会像:
SELECT product_id, HAMMING_DISTANCE(phash, 'phashfromuserinput') ;
但是在mysql汉明距离是按位运算符,如果字符串只是数字,我可以这样做:
SELECT pagedata,BIT_COUNT(pagecontent^'$encrypted')searchengine WHERE pagecontent > 2 ; ")
它仅适用于整数(数字),但我的要求是使用数字和字母,例如:
74898fababfbef46 and 95efabfeba752545
从我的小研究中我知道,首先我必须将字段转换为binary然后使用或bitcount使用:CASTCONVERT
SELECT BIT_COUNT( CONV( hash, 2, 10 ) ^
0b0000000101100111111100011110000011100000111100011011111110011011 )
要么
SELECT BIT_COUNT(CAST(hash AS BINARY)) FROM data;
这可以将数据转换为binary和使用bitcount.现在问题出现了该varbinary存储在字符/哈希值mysql …
考虑长度为n的所有二进制向量的集合S,其中每个包含正好m个; 所以每个载体都有nm零.
我的目标是从S构造一个数量k的向量,使得这些向量尽可能彼此不同.
举一个简单的例子,取n = 4,m = 2和k = 2,那么可能的解是:[1,1,0,0]和[0,0,1,1].
这似乎是编码理论文献中的一个开放性问题(？).
有没有办法(即算法)找到一个次优但好的解决方案？
汉明距离是在这种情况下使用的正确性能指标吗？
一些想法:
在本文中,作者提出了几种算法来找到向量子集,使得成对汉明距离> =某个值 d.
我已经实现了如下随机方法:取一个 SS,它由 S中的任何向量初始化.然后,我考虑 S中的剩余向量.对于这些矢量中的每一个,我检查该矢量相对于 SS中的每个矢量是否至少具有距离 d.如果是,则将其添加到 SS.
通过取最大可能 d,如果 SS的大小> = k,那么我将 SS视为最优解,并且我从 SS中选择 k个向量的任何子集.使用这种方法,我认为导致 SS将取决于初始向量的识别 SS ; 即有多种解决方案(？).
但是如果 SS的大小< k,怎么办？
从本文提出的算法中,我只理解了随机算法.我对二进制词典搜索(第2.3节)感兴趣,但我不知道如何实现它(？).
algorithm combinatorics binary-data hamming-distance data-structures
我有n(8位)字符串,所有字符串都具有相同的长度(比方说m),另一个字符串s长度相同.我需要计算汉明距离s到其他每个字符串的距离.在普通的C中,类似于:
unsigned char strings[n][m];
unsigned char s[m];
int distances[n];
for(i=0; i<n; i++) {
int distances[i] = 0;
for(j=0; j<m; j++) {
if(strings[i][j] != s[j])
distances[i]++;
}
}
我想使用带有gcc的SIMD指令来更有效地执行这样的计算.我已经读过PcmpIstrI在SSE 4.2中有用并且我的目标计算机支持该指令集,所以我更喜欢使用SSE 4.2的解决方案.
编辑:
我编写了以下函数来计算两个字符串之间的汉明距离:
static inline int popcnt128(__m128i n) {
const __m128i n_hi = _mm_unpackhi_epi64(n, n);
return _mm_popcnt_u64(_mm_cvtsi128_si64(n)) + _mm_popcnt_u64(_mm_cvtsi128_si64(n_hi));
}
int HammingDist(const unsigned char *p1, unsigned const char *p2, const int len) {
#define MODE (_SIDD_UBYTE_OPS | _SIDD_CMP_EQUAL_EACH | _SIDD_BIT_MASK | …