Sar*_*dar 12 sorting pattern-matching hamming-distance
有一个包含N个固定长度字符串的数据库.有一个相同长度的查询字符串.问题是从数据库中获取具有最小汉明距离的第k个字符串到q.
N很小(约400),弦长,长度固定.数据库不会更改,因此我们可以预先计算索引.查询变化很大,缓存和/或预计算不是一种选择.每秒有很多.我们总是需要k结果,即使k-1结果匹配0(在汉明距离上排序并取第一个k,因此局部敏感散列和类似方法不会这样做).kd-tree和类似的空间分区可能比线性搜索表现更差(字符串可能很长).BK树目前是最好的选择,但它仍然比它需要的慢和复杂.
感觉就像有一个算法,它将构建一个索引,它将在很少的步骤中丢弃大多数条目,留下k <= t << N个条目来计算实际的汉明距离.
人们建议基于Levenstein距离的模糊字符串匹配 - 谢谢,但问题要简单得多.基于广义距离度量的方法(如BK树)是好的,但也许有利用上述事实(小DB /长固定大小的字符串,简单的汉明距离)
链接,关键字,论文,想法？=)
tbi*_*hel 11
这似乎是一个Vantage Point(VP树)可能工作的任务......因为汉明距离应该满足三角不等式定理,你应该能够应用它...它也有利于识别k-nearest.我已经看到了它在图像索引数据库设置...你可能要检查第5 本文正如我正在谈论的(尽管在不同的领域)的例子.