Echo
最近上课有点听不进去,脑子里一直在想一些乱七八糟的东西。
比如这样一个问题。
假设有一个特别大的编号空间,每个东西都有一个对应的编号。如果使用32位整数,那么一共有:
也就是四十多亿种可能。
但是假设其中真正存在的东西只有几十个,甚至几个,那还有没有必要把四十多亿个编号全部检查一遍?
显然没必要。
问题是,不挨个检查,怎么知道究竟是哪几个编号?
我想试着用二进制的办法解决这个问题。
暂时给这个工程取个名字,叫 Echo。
一、把大编号变成小编号
32位一共有四十多亿种可能,直接处理肯定不现实。那能不能先把32位压缩成8位?
8位就只有:
种情况,开一个数组就能存下来。
最简单的办法,可以把32位分成4组,每组8位,然后把它们异或起来。
例如:
int get(unsigned int x) {
return (x ^ (x >> 8) ^ (x >> 16) ^ (x >> 24)) & 255;
}
这样无论原来的编号有多大,最后都只会得到一个0到255之间的数字。
但是这样肯定会出现冲突。
例如:
原来的编号A → 37
原来的编号B → 37
原来的编号C → 102
A和B明明是不同的东西,压缩以后却变成了同一个编号。
所以只压缩一次肯定不行。
我想的是,可以使用不同的异或方式,多压缩几次。
原始32位编号
|
|---- 第1次压缩 → 8位
|
|---- 第2次压缩 → 8位
|
|---- 第3次压缩 → 8位
|
|---- 第4次压缩 → 8位
两个编号在第一次压缩时可能碰撞,但是换一种压缩方式以后,不一定还会碰撞。
如果能把几次结果结合起来,或许就能反推出原来的编号。
不过怎么组合这些结果,目前还没有完全想好。
二、能不能不直接检查编号
即使压缩成256个位置,如果每次还是从0到255挨个检查,好像也没什么意思。
我想到以前学过的异或运算。
假设有两个8位数字 x 和 y,先把它们按位与,再计算结果中1的个数是奇数还是偶数。
int check(int x, int y) {
int t = x & y, cnt = 0;
while (t) {
cnt += t & 1;
t >>= 1;
}
if (cnt % 2)return -1;
return 1;
}
这样无论输入什么,最后只会得到 1 或者 -1。
比如某个目标的编号是 x,我不直接问它的编号,而是给它不同的 y,记录每次得到的结果。
如果把256种 y 全部试一遍,就会得到一组由1和-1组成的数据。
这让我想到了 Walsh-Hadamard 变换。
如果这些数据本来就是按照异或的奇偶关系产生的,那么对它们进行变换,就有可能把原来的编号找出来。
于是我先写了一个简单的 FWHT。
const int maxn = 256;
int a[maxn];
void fwht() {
for (int len = 1; len < maxn; len <<= 1) {
for (int i = 0; i < maxn; i += len * 2) {
for (int j = 0; j < len; j++) {
int x = a[i + j];
int y = a[i + j + len];
a[i + j] = x + y;
a[i + j + len] = x - y;
}
}
}
}
接下来就可以用程序模拟一下。
三、先写个程序试试
暂时不考虑真正的查询设备,也不考虑其他问题,先假设程序知道有哪些目标,并用它们生成查询结果。
主要看看变换以后,能不能找出压缩后的编号。
#include <iostream>
using namespace std;
const int maxn = 256;
int n, a[maxn];
unsigned int x[105];
int get(unsigned int x) {
return (x ^ (x >> 8) ^ (x >> 16) ^ (x >> 24)) & 255;
}
int check(int x, int y) {
int t = x & y, cnt = 0;
while (t) {
cnt += t & 1;
t >>= 1;
}
if (cnt % 2)return -1;
return 1;
}
void fwht() {
for (int len = 1; len < maxn; len <<= 1) {
for (int i = 0; i < maxn; i += len * 2) {
for (int j = 0; j < len; j++) {
int x = a[i + j];
int y = a[i + j + len];
a[i + j] = x + y;
a[i + j + len] = x - y;
}
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> x[i];
for (int i = 0; i < maxn; i++) {
for (int j = 1; j <= n; j++) {
int z = get(x[j]);
a[i] += check(i, z);
}
}
fwht();
for (int i = 0; i < maxn; i++) {
if (a[i])
cout << i << " " << a[i] / maxn << endl;
}
return 0;
}
例如输入:
3
5 17 259
得到:
2 1
5 1
17 1
也就是说,原来输入的三个32位编号,经过压缩和变换以后,在2、5、17这三个位置出现了结果。
如果两个编号压缩以后落到同一个位置,那么那个位置的数值就会累加。
当然,这个程序还没有解决最开始的问题。
因为这里是我自己把目标编号输入进去,再根据这些编号模拟查询结果。程序实际上并没有从四十多亿个未知编号中直接找到目标。
而且得到的只是8位的压缩编号,不是原来的32位编号。
不过至少可以先确认,这种异或关系和FWHT确实可以配合起来使用。
接下来需要解决的就是,怎样使用不同的压缩方式,以及怎样把多次得到的结果对应起来。
四、查询顺序的问题
还有一个问题。
上面的程序是直接计算256次查询结果,实际上默认所有东西都没有变化。
但如果真的把这些查询依次执行,就肯定需要时间。
假设某个目标在查询过程中不断变化,那么第一次得到的结果和最后一次得到的结果就可能不完全一样。
这样直接进行FWHT,得到的结果也可能发生变化。
原来应该集中在某一个位置的数值,可能会分散到其他位置。
那查询顺序是不是也会影响最终结果?
最普通的查询顺序是:
00000000
00000001
00000010
00000011
00000100
...
但是还有一种 Gray Code(格雷码)。
它的特点是相邻两个编号只有一个二进制位不同。
例如3位格雷码:
000
001
011
010
110
111
101
100
生成起来也很简单:
int gray(int x) {
return x ^ (x >> 1);
}
8位格雷码同样可以生成256个不同的编号。
for (int i = 0; i < 256; i++)
cout << (i ^ (i >> 1)) << endl;
我想试试把原来的查询顺序改成格雷码。
一方面,相邻两次查询只需要修改一个二进制位。
另一方面,格雷码的顺序本身也有一定规律。
如果目标的变化和时间有关,那么不同的查询顺序,会不会让最后变换出来的结果出现不同的分布?
我觉得这个可以试一下。
不过需要注意,格雷码只是改变了查询的执行顺序,并不会改变256种查询本身。
如果目标始终不变,那么无论采用哪种顺序,只要把查询结果放回对应的位置,最终变换得到的结果都应该一样。
只有当目标在查询过程中发生变化时,顺序才可能产生影响。
五、关于时间变化
接着前面的想法。
假设一个目标原来经过FWHT,只会在某个位置出现一个明显的值。
但是现在每次查询都发生在不同时间,而目标本身又在慢慢变化。
那么最后的结果可能不再集中在一个位置,而是在其他位置也出现一些数值。
我就在想,能不能通过调整查询顺序,让这些额外出现的数值也具有某种规律?
比如一个目标原来在37号位置。
加入时间变化以后,可能在其他几个位置也出现结果。
如果这些位置和37之间存在某种固定的异或关系,那就比较有意思了。
因为这样或许能够区分:
真正存在的其他目标
和
同一个目标变化后产生的额外结果
当然,现在还不知道格雷码能不能做到这一点。
只不过它本身也是按照二进制规律排列的,所以我想先拿它来试试。
最简单的办法就是给模拟程序加上一个随查询次数变化的数值,然后分别使用普通二进制顺序和格雷码顺序,比较变换结果。
如果结果确实存在某些规律,再继续想办法利用。
六、Echo
这个名字也是随便想到的。
一个目标本来应该只在一个位置出现结果,但是受到时间变化的影响,可能会在其他位置留下额外的数值。
感觉有点像回声,所以就叫 Echo。
目前大概有几个问题还没有解决。
首先,32位压缩成8位以后会发生碰撞,单独一组结果没有办法恢复原来的编号。
其次,多组压缩结果怎么对应起来还没想好。不能前面压缩半天,最后又把四十多亿个编号全部枚举一次,那样就没有意义了。
最后就是查询顺序和时间变化的问题。格雷码能不能让变换后的结果出现某种可以利用的规律,还需要写程序测试。
现在也只是有了一个大概的想法,程序只能验证其中很小的一部分。
先把这些记下来,以后有空再继续折腾。

















这一切,似未曾拥有