问：补充数据链接：
候选：https:
//pan.baidu.com/s/1nvGWbrV bg_db：https : //pan.baidu.com/s/1sllFLAd
每个字符串的长度为23，只要该行的前20个字符，因为数据太大，我只传递了五分之一，众神可以挑战，有一个快速的代码可以粘贴，让小弟读一下，谢谢！
以下是形式问题：
我现在有两个字符串数组，分别称为候选人和bg_db，所有字符串长度均为20，每个字符串的每个字符只有四个可能的ATCG（是的！这是基因组序列！：
candidates = [
'GGGAGCAGGCAAGGACTCTG',
'GCTCGGGCTTGTCCACAGGA',
'...',
65
]
bg_db = [
'CTGCTGACGGGTGACACCCA',
'AGGAACTGGTGCTTGATGGC',
'...',
More, about a billion.
]
我的任务是在bg_db中查找所有小于或等于四个候选候选人差异的记录。
例如：
# The top one is candidate, which is a record of candidates
# 中间|代表相同，*代表不相同
The following record represents bg_db
A T C G A T C G A T C G A T C G A T C G
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The difference is 0
A T C G A T C G A T C G A T C G A T C G
A T C G A T C G A T C G A T C G A T C G
* | | | | | | | | | | | | | | | | | | | | | | | | | | | | The difference is 1
T T C G A T C G A T C G A T C G A T C G
A T C G A T C G A T C G A T C G A T C G
* | | * | | | | | | | | | | | | | | | | | | | | | | | | | | The difference is 2
T T C G T T C G A T C G A T C G A T C G
A T C G A T C G A T C G A T C G A T C G
* | | * | | | | | | | | | | | | | * | | | | | | | | | | | The difference is 3
T T C G T T C G A T C C A T C G A T C G
A T C G A T C G A T C G A T C G A T C G
* | | * | | | | | | | | | | | | | * | | | * | | * | | | # The difference is 4
T T C G T T C G A T C C A T C A A T C G
我的问题是，如果我可以快速找到bg_db中每个候选项的差异小于4的所有记录。
如果使用暴力，请以Python为例：
def align(candidate, record_from_bg_db):
mismatches = 0
for i in range(20):
if candidate[i] != record_from_bg_db[i]:
mismatches += 1
if mismatches >= 4:
return False
return True
candidate = 'GGGAGCAGGCAAGGACTCTG'
record_from_bg_db = 'CTGCTGACGGGTGACACCCA'
Align (candidate, record_from_bg_db) # about 1.24 microseconds
Total time:
10000000 * 1000000000 * 1.24 / 1000 / 1000 / 60 / 60 / 24 / 365
# = 393
10 million candidates and 1 billion bg_db records
It takes about 393 years.
6550
我的想法是bg_db是一个高度有序的字符串（具有固定的长度，每个字符四个可能的字符）。有什么算法可以使求职者快速比较所有bg_db，诸神，以寻求建议？
答：写思路
candidates = [
'GGGAGCAGGCAAGGACTCTG',
'GCTCGGGCTTGTCCACAGGA',
'...',
65
]
bg_db = [
'CTGCTGACGGGTGACACCCA',
'AGGAACTGGTGCTTGATGGC',
'...',
More, about a billion.
]
由于您的数据实际上很有特色，因此可以简化。
因为所有字符串的长度均为20个字符，并且全部由ATCG四个字符组成。然后可以将它们转换为整数以进行比较。
二进制表示如下
A ==> 00
T ==> 01
C ==> 10
G ==> 11
因为字符串的长度是固定的，所以每个字符可以用两位表示，因此每个字符串可以表示为一个。40位的整数。它可以表示为32+8也可以直接使用。64位整形。建议用C语言来做。
让我们谈论比较。
因为我想找到它。All records with a difference of less than or equal to 4 for each candidate in bg_db因此，一次只能做两个整数。^xor运算，结果There are no more than eight binaries with no more than eight binaries, which can only be divided into four groups at most.为可以满足要求（00 ^ 11 = 11，10 ^ 01 = 11）。
结果40每位分为20组，即最多只有一组。4每组是b01 b10 b11这三个值，其余全部是b00。
然后比较算法写得很好。
可以检索每个字节（四个组），其中几个用于三个非零值，以简要介绍整体比较结果。
因为每个字节只有一个256可能的值限定值是3^4=81种类，所以您可以存储结果并获取它们。
在这里，我们给出一个函数来获取结果中的几个非零组。
Generation of table median under *******************
int i;
for( i=0;i<256;++i){
int t =0;
t += (i&0x01 || i&0x02)?1:0;
t += (i&0x04 || i&0x08)?1:0;
t += (i&0x10 || i&0x20)?1:0;
t += (i&0x40 || i&0x80)?1:0;
printf("%d,",t);
if(i%10 ==9){putchar('\n');}
}
********************************************//
int table[] = {
0,1,1,1,1,2,2,2,1,2,
2,2,1,2,2,2,1,2,2,2,
2,3,3,3,2,3,3,3,2,3,
3,3,1,2,2,2,2,3,3,3,
2,3,3,3,2,3,3,3,1,2,
2,2,2,3,3,3,2,3,3,3,
2,3,3,3,1,2,2,2,2,3,
3,3,2,3,3,3,2,3,3,3,
2,3,3,3,3,4,4,4,3,4,
4,4,3,4,4,4,2,3,3,3,
3,4,4,4,3,4,4,4,3,4,
4,4,2,3,3,3,3,4,4,4,
3,4,4,4,3,4,4,4,1,2,
2,2,2,3,3,3,2,3,3,3,
2,3,3,3,2,3,3,3,3,4,
4,4,3,4,4,4,3,4,4,4,
2,3,3,3,3,4,4,4,3,4,
4,4,3,4,4,4,2,3,3,3,
3,4,4,4,3,4,4,4,3,4,
4,4,1,2,2,2,2,3,3,3,
2,3,3,3,2,3,3,3,2,3,
3,3,3,4,4,4,3,4,4,4,
3,4,4,4,2,3,3,3,3,4,
4,4,3,4,4,4,3,4,4,4,
2,3,3,3,3,4,4,4,3,4,
4,4,3,4,4,4
};
int getCount(uint64_t cmpresult)
{
Uint8_t* Pb = & & cmpresult; // Here we assume that it is a small segment mode, and the previous comparison results are low by 40 bits.
return table[pb[0]]+table[pb[1]]+table[pb[2]]+table[pb[3]]+table[pb[4]];
答：提供一种将四个字符简化为00、01、10、11的方法。
比较时，首先执行XOR，因此完全相同的字符变为00；不完全相同的是01、10或11。
那么每个相邻对的XOR结果为OR，因此00变为0、01、10或11变为1。最后，计算1的数目。因为它们是按位运算，所以它们理论上应该很快。
但是，如果我的C学会了炉渣，则无法发布代码。
答:思路如下：
首先：比较四个不同的数据，例如
* * TGACGGGTGACACCCA（删除字符串的四个位置中的字符），将字符的长度更改为16，与完全相同的字符串匹配，
将TGACGGGTGACACCCA保存为键值以及四个差异作为值，例如map。
第二：比较三个差异的数据
在上述基础上，将上述值与比较长度与3完全相同的字符串进行比较
