Tag: 汉明距离

高效地find大集合中汉明距离较低的二进制string

问题： 给定一个大于（〜1亿）的无符号32位整数列表，一个无符号的32位整数input值和一个最大的汉明距离 ，返回在input值的指定汉明距离内的所有列表成员。 列举的实际数据结构是公开的，性能要求决定了内存中的解决scheme，构build数据结构的成本是次要的，查询数据结构的成本低是至关重要的。 例： 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的退化情况，只要使用一个sorting列表并对特定的input值进行二进制search即可。 如果汉明距离只有1，我可以翻转原始input的每一位，重复上述32次。 如何有效地（不扫描整个列表）发现海明距离> 1的列表成员。