快速汉明距离评分

Question

有一个包含N个固定长度字符串的数据库。 有一个相同长度的查询字符串。 问题是从数据库中获取与q的汉明距离最小的前k个字符串。

N很小（约为400），字符串很长，长度固定。数据库不会改变，因此我们可以预先计算索引。查询变化很大，缓存和/或预计算不是一个选项。每秒有大量查询。我们始终需要k个结果，即使k-1个结果匹配0（按汉明距离排序并取前k个，因此局部敏感哈希等方法行不通）。kd树和类似的空间划分可能比线性搜索表现更差（字符串可能非常长）。BK树目前是最佳选择，但它仍然比必要的慢和复杂。

感觉有一种算法，可以构建一个索引，在很少的步骤中丢弃大多数条目，留下k <= t << N个条目来计算实际的汉明距离。

人们建议基于Levenstein距离的模糊字符串匹配 - 谢谢，但问题要简单得多。基于广义距离度量的方法（如BK树）很好，但也许有些东西利用了上述事实（小型DB /长固定大小字符串，简单的汉明距离）

链接，关键词，论文，想法？=）

- Sardar

---

有关有界汉明距离方法，请参见此答案：https://dev59.com/KmHVa4cB1Zd3GeqPlUcT#47487949 - Philippe Ombredanne

Answer 1

这似乎是一个可以使用Vantage Point (VP tree) 的任务......由于汉明距离应满足三角不等式定理，所以您应该能够运用它......它也适用于识别k个最近的点。我在图像索引数据库设置中看到过它... 您可以查看这篇论文第5节作为我所说的示例（尽管在不同的领域）。

- tbischel

---

汉明距离是一种度量标准，因此您可以使用它构建VP树。 - mu is too short

Answer 2

所有汉明距离可以使用下面的Python代码在O（K^2/D）中生成。
在某些情况下，这比简单的O（N*K）代码更快。
其中，N是固定长度字符串的数量
K是每个字符串的长度
D是字典的大小。

# DATABASE is a tuple of the strings
# eg. ('asdfjjajwi...', 'hsjsiei...', ...)

# SINGLE is the string you are matching
# eg. 'jfjdkaks...'

SIZE_OF_STRING = 5000
NUMBER_OF_STRINGS = 400
FIRST_K_REQUIRED = 100

def setup_index():
  index = []
  for x in xrange(SIZE_OF_STRING):
    index_dict = {}
    for y in xrange(NUMBER_OF_STRINGS):
      temp = index_dict.get(DATABASE[y][x], [])
      temp.append(y)
      index_dict[DATABASE[y][x]] = temp
    index.append(index_dict)
  return index

index = setup_index()

output = []
for x in xrange(NUMBER_OF_STRINGS):
  output.append([SIZE_OF_STRING, x])

for key, c in enumerate(SINGLE):
  for x in index[key][c]:
    output[x][0] -= 1

output.sort()
print output[:FIRST_K_REQUIRED]

只有在 SIZE_OF_STRING / DICTIONARY_SIZE < NUMBER_OF_STRINGS 时，这是一种更快的方法。

希望这可以帮到您。

---

编辑： 上述代码的复杂度不正确。

平均情况下，可以在 O(N*K/D) 的时间内生成汉明距离。
这比平凡的 O(N*K) 代码更快 所有 情况下。

其中 N 是固定长度字符串的数量
K 是每个字符串的长度
D 是字典的大小。

- threenplusone

Answer 3

据我所知，BK树非常适合查找与查询字符串最多有K个“差异”的所有字符串。这是一个不同于寻找X个最接近的元素的问题。这可能是性能问题的原因。

我的第一直觉是，如果速度真的很重要，那么最终目标应该是构建一个确定性有限自动机（DFA）来处理此问题。唐纳德·克努斯曾经研究过相关问题，并开发了一种称为Trie的方法来模拟DFA。当你需要搜索字典中许多可能单词时，这种方法特别好用。我认为你的问题可能是这项工作的有趣扩展。在他最初的工作中，DFA的目标是尝试将输入字符串与字典中的单词匹配。我相信对于这个问题也可以做类似的事情，但是返回查询的K个最接近的项目。本质上，我们正在扩展可接受状态的定义。

这取决于需要包括的接受状态数量是否实际可行。我认为关键的想法是兼容集合。例如，在数轴上，我们有元素1、2、3、4、5，并且对于任何查询，都希望获得最接近的两个元素。元素2可以在两个可能的集合(1,2)或(2,3)中，但2永远不会与4或5一起成为一个集合。现在还不确定构建这样的DFA的最佳方法。看起来答案中可能会有一篇不错的论文。

- Samsdram

Answer 4

这个问题似乎与 Knuth 的“trie”算法密切相关，有几种高度优化的特殊解决方案 - 主要与它们的缓存一致性和 CPU 指令辅助加速（位 trie）有关。

Trie 是一个解决相关问题的绝佳方案 - 字符串开头的相似性，当然也使它成为从任何起点开始找到最小唯一字符串解集的完美解决方案。在这种情况下，位 trie 的平均性能实际上是 O(1)，最坏情况下是 O(m)，其中 M 是键长度。总体而言，它的搜索、插入和删除性能与哈希相同，只是没有纯哈希数组的碰撞问题。

我之所以遇到这个问题，是因为我正在搜索有关位 trie 的信息，并意识到它们与某些汉明算法的相似之处，因此也许这类算法对您来说是一个富有成果的研究领域。祝你好运。

- eris