m****y
发帖数: 28 | 1 问题其实很简单
我的程序要维护一个集合
集合里的每个元素都是一个64bits的二进制数
要支持对这个集合进行插入，删除，查找三种操作
插入和删除就不说了
查找的要求是这样的：
给一个64bits的数作为input
要求找出集合里跟input的二进制差异最小的数，
可以是一个或者多个
甚至可以不要求最优的精确查找，返回次优的结果也可以接受
举个例子
比如集合里有{1100, 1011}
查找1010的话，应该返回1011，因为他们之间只有一个bit的差异
请问，该采用什么样的数据结构和算法呢？ |
c*****t
发帖数: 1879 | 2 我觉得应该看你有多少数字，具体是什么 pattern，然后决定用什么算法。
否则 brute force 虽然慢，但是如果数量少的话，而且注意 optimization
的话，速度其实还是应该可以接受的。
如果只是 1-2 个错的话，trie 应该可以很快。如果把问题分成两个 32-bit
部分，处理 3-4 也估计可以。多的话，这方法就估计很麻烦了。
另外 hash table + extend （类似 BLAST 的办法）估计也可以，但是也是
对数据的 pattern 要做些假设的。
【在 m****y 的大作中提到】
: 问题其实很简单
: 我的程序要维护一个集合
: 集合里的每个元素都是一个64bits的二进制数
: 要支持对这个集合进行插入，删除，查找三种操作
: 插入和删除就不说了
: 查找的要求是这样的：
: 给一个64bits的数作为input
: 要求找出集合里跟input的二进制差异最小的数，
: 可以是一个或者多个
: 甚至可以不要求最优的精确查找，返回次优的结果也可以接受
|
X****r
发帖数: 3557 | 3 没错，因为brute force查找也只不过是O(n)而已，要再快的通用方法不太容易，
如果有些假设才好做。另外也取决于哪种操作更多些。
【在 c*****t 的大作中提到】
: 我觉得应该看你有多少数字，具体是什么 pattern，然后决定用什么算法。
: 否则 brute force 虽然慢，但是如果数量少的话，而且注意 optimization
: 的话，速度其实还是应该可以接受的。
: 如果只是 1-2 个错的话，trie 应该可以很快。如果把问题分成两个 32-bit
: 部分，处理 3-4 也估计可以。多的话，这方法就估计很麻烦了。
: 另外 hash table + extend （类似 BLAST 的办法）估计也可以，但是也是
: 对数据的 pattern 要做些假设的。
|
t****t
发帖数: 6806 | 4 你这查找不就是generalized channel code decoding问题的翻版嘛
如果集合没有什么特征, 是没什么搞头的, 直接O(N)得了
要是你万一想出什么搞头, 直接投稿到Trans IT估计可以拿年度最佳paper奖不在话下
如果集合是个linear space, 那就是linear code, 请去计算syndrome和coset leader
如果还有别的特征in addition, 请参见channel code的参考书
【在 m****y 的大作中提到】
: 问题其实很简单
: 我的程序要维护一个集合
: 集合里的每个元素都是一个64bits的二进制数
: 要支持对这个集合进行插入，删除，查找三种操作
: 插入和删除就不说了
: 查找的要求是这样的：
: 给一个64bits的数作为input
: 要求找出集合里跟input的二进制差异最小的数，
: 可以是一个或者多个
: 甚至可以不要求最优的精确查找，返回次优的结果也可以接受
|
