12

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

N很小（约400），字符串很长，长度固定。数据库不会改变，所以我们可以预先计算索引。查询差异很大，缓存和/或预计算不是一种选择。每秒有很多。我们总是需要 k 个结果，即使 k-1 个结果匹配 0（按汉明距离排序并取第一个 k，因此局部敏感散列和类似方法不会这样做）。kd-tree 和类似的空间分区可能会比线性搜索执行得更差（字符串可能很长）。BK-tree 目前是最好的选择，但它仍然比它需要的慢和复杂。

感觉就像有一个算法，它将建立一个索引，它将在很少的步骤中丢弃大部分条目，留下 k <= t << N 个条目来计算真正的汉明距离。

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

链接、关键词、论文、想法？=)

4

4 回答 4

11

这似乎是一个有利点（VP树）可能工作的任务......因为汉明距离应该满足三角形不等式定理，你应该能够应用它......它也有利于识别k-closest。我已经在图像索引数据库设置中看到了它......您可以查看本文的第 5 节作为我正在谈论的示例（尽管在不同的领域）。

于 2010-06-23T01:01:13.703 回答
4

All hamming distances can be produced in O(K^2/D) using the python code below.
This is faster in some cases than the trivial code which is O(N*K).

Where N is the number of fixed length strings
K is the length of each string
and D is the size of the dictionary. 

# 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]

This is a faster method only when SIZE_OF_STRING / DICTIONARY_SIZE < NUMBER_OF_STRINGS.

Hope this helps.

EDIT: The complexity of the above code is incorrect.

The Hamming Distances can be produced in O(N*K/D) on average.
This is faster in ALL cases than the trivial code which is O(N*K).

Where N is the number of fixed length strings
K is the length of each string
and D is the size of the dictionary.

于 2010-12-30T13:41:51.153 回答
1

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

我的第一个倾向是，如果速度真的很重要，那么最终目标应该是构建一个确定性有限自动机(DFA) 来处理这个问题。Donald Knuth 研究了一个相关问题，并开发了一种名为Trie的方法来模拟 DFA。当您在起始字典中有许多可能的单词要搜索时，此方法特别好。我认为你的问题可能是这项工作的一个有趣的延伸。在他最初的工作中，DFA 的目标是尝试将输入字符串与字典中的单词进行匹配。我相信对于这个问题可以做同样的事情，而是将 K 最接近的项目返回给查询。本质上，我们正在扩展接受状态的定义。

这是否可行取决于需要包含的接受状态的数量。我认为关键思想是兼容集。例如，假设在数轴上我们有元素 1、2、3、4、5，并且对于任何查询都需要两个最接近的元素。元素 2 可以在两个可能的集合 (1,2) 或 (2,3) 中，但 2 永远不能是具有 4 或 5 的集合。为时已晚，所以我不确定构建诸如 DFA 之类的最佳方法片刻。似乎答案中可能有一篇不错的论文。

于 2010-12-31T08:35:40.773 回答
0

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

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

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

于 2012-02-08T16:28:44.267 回答