Echo

最近在折腾一个有点奇怪的问题。

假设有一个非常大的编号空间，每个目标都有一个32位编号。

那么理论上一共有：

$$ 2^{32} $$

种可能。

也就是四十多亿，但是实际真正出现的目标可能非常少，比如只有几十个。

最直接的办法当然是一个编号一个编号去找，但是这样显然很蠢，如果真正有用的东西只有那么几个，为什么还要把四十多亿个位置全部扫一遍？

我第一反应还是OI里面那套东西：

状态太大
↓
想办法压

真正有用的状态很少
↓
不要围着所有状态转

于是开了一个 C++ 工程。

暂时叫：

Echo

先把32位压成8位

32位太大，那就先压小。

把一个32位编号记成：

通过一些二进制异或关系，把它映射成一个8位编号：

可以先写成：

$$ z=Mq $$

这里全部放在二进制里面理解。

矩阵 M 的每一行，其实就是：

从原来的32个 bit 里面挑一些出来异或，最后得到新的一个 bit。

这样原来：

$$ 2^{32} $$

个位置，在当前这一组映射里面就变成了：

$$ 2^8=256 $$

个位置。

一下就小很多了，当然，这样一定会碰撞，因为四十多亿个东西硬塞进256个位置，不可能一一对应。

两个完全不同的32位编号可能会得到同一个：

但是碰撞本身也不是不能处理。

换一组 M 再看一次就行。

比如某个编号第一组被映射成：

10110110

第二组可能变成：

00101101

第三组又会落到另一个地方。两个编号在某一组里面撞到一起很正常，但是如果连续很多组都撞在一起，就没有那么容易了，所以可以多做几组不同的映射，然后把结果放在一起判断。

这样原来的问题：

怎么在四十多亿个编号里面
找到几十个目标？

就变成了：

每次只看256个位置
↓
多看几次
↓
最后把原来的32位编号拼回来

这个看起来舒服多了。

256个位置也不想一个个问

但是如果每一组还是把：

0
1
2
...
255

一个一个问一遍，其实还是有点笨。

只是把：

一个大暴力

拆成：

很多个小暴力

而已。

既然编号本来就是二进制，我就在想：

能不能不要直接问位置，而是问一些二进制关系？

假设现在局部编号是：

我不直接问：

你是不是137号？

而是给它一个二进制向量：

让它回答：

$$ (-1)^{u^Tz} $$

这里：

u^T z

全部按照二进制来算。

所以最后只有：

0
或
1

然后再变成：

+1
或
-1

刚开始看这个东西可能会觉得挺绕。

但把所有 u 都跑一遍以后，会得到一整组很规整的：

+1
-1
+1
+1
-1
...

模式。

然后直接做：

Walsh-Hadamard Transform

或者：

FWHT

如果这一组里面只有一个目标，那么经过变换以后，它会在自己的局部编号位置形成很明显的峰。

大概就是：

一组二进制查询
        ↓
得到 +1 / -1 响应
        ↓
       FWHT
        ↓
得到256个位置
        ↓
某个位置出现峰
        ↓
得到局部编号

这个就开始有意思了。

因为整个过程中，我其实从来没有直接问：

你到底是几号？

而只是问了一堆：

二进制问题

最后通过变换，编号自己从结果里面出来了。

如果同时存在几个目标，那么结果里面就会出现几个峰。

只要真正存在的目标数量远远小于256，结果仍然是比较稀疏的。

所以最开始那个：

$$ 2^{32} $$

大小的空间，根本没有必要真的展开。

多看几组，再把编号拼回来

一组8位肯定不够。

因为：

32 bit
↓
8 bit

一定存在大量碰撞。

所以很自然的办法就是换不同的 M，做很多组。

32位编号
   ↓
第1组 → 8位
第2组 → 8位
第3组 → 8位
第4组 → 8位
   ...

每一组只告诉我：

这一组里面
哪些局部位置可能有目标

然后再把不同组的结果放到一起，看哪些局部结果能够共同对应到同一个32位编号。

这里有个很重要的问题。

绝对不能做到最后又开一个：

$$ 2^{32} $$

大小的数组，然后把四十多亿个候选重新检查一遍。

那样前面压半天就完全没意义了。

整个程序最好从头到尾都只围着：

真正出现的目标
+
少量候选

转。

我挺喜欢这种感觉。

问题表面上特别大，但真正需要工作的地方其实很小。

然后时间把事情弄乱了

前面的东西如果只放在数学里面，其实挺干净。

但继续往实际执行方向想，很快就碰到一个问题：

256个查询并不是同时发生的。

它们必须：

一个
一个
一个
...

顺序执行。

第一个查询发生在最开始。

等到第两百多个查询的时候，已经过去了一段时间。

如果目标在整个查询周期里面完全不变化，那当然没问题。

但是只要目标的：

相位
幅度

之类的东西随着时间慢慢变化，那么同一个目标在前面的响应和后面的响应就已经不是完全一样的了。

再直接做 FWHT，原来应该集中在一个位置的峰就会开始往旁边散。

理想情况下：

             |
             |
-------------|-------------
           target

发生时间变化以后可能变成：

          |  |
       |  |  | |
------|-|-|--|-|--------

一开始我的想法当然是：

怎么把这个误差消掉？

但是想了一会又感觉不太对。

因为查询顺序本来就是：

我自己安排的。

既然时间变化躲不掉，那为什么一定要把时间当成一个完全不受控制的误差？

于是问题变成了：

能不能反过来安排查询顺序，让时间本身也有规律？

Gray Code

8位一共有：

个状态。

最普通的顺序当然是：

但是我后来把：

Gray Code

拿了过来。

Gray Code 最明显的特点就是：

相邻两个状态只变化一个 bit。

例如3位：

这个东西在竞赛里面本身不算什么特别稀奇的东西。

但是放到这里突然变得挺好玩。

首先，每一次查询状态切换只改变一位。

不像普通二进制加一：

01111111
↓
10000000

这种情况会一下翻很多位。

但我更在意的其实不是这个。

我开始想：

如果查询顺序本身有这么强的二进制结构，那么“第几个被查询”这件事情，在 Walsh 变换里面会不会也留下某种结构？

如果执行顺序完全乱排，那么时间变化造成的东西应该也会比较乱。

但是 Gray Code 本身不是乱的。

所以我现在的想法是，如果目标随时间只是比较平滑地变化，那么这种变化经过变换以后，可能不会完全随机地铺满整个空间，而会沿着一些和查询顺序有关的异或方向扩散。

大概像：

原来的位置：

z

发生时间变化：

z
├── z xor s1
├── z xor s2
├── z xor s3
├── z xor s1 xor s2
└── ...

于是问题又变了一次。

一开始我想的是：

怎么把时间造成的误差消掉？

后来变成：

既然一定会漏，能不能让它只往我知道的地方漏？

我觉得后一个问题明显更有意思。

一个峰后面拖出一串回声

这样一来，一个真正的目标做完变换以后，就不一定还是孤零零的一个点。

如果它在这一轮查询里面发生变化，原来的峰旁边可能会出现一些额外分量。

我暂时把这些东西理解成：

回声

所以这个工程就先叫：

Echo

这些东西和普通噪声感觉又不太一样。

噪声是真的乱。

但是这种尾巴虽然很烦，如果查询顺序是自己设计的，那么它至少有可能带着一些结构。

也就是说，可以先找：

比较明显的主峰

然后再看附近那些东西里面，有哪些可能其实不是新的目标，而是：

同一个目标
+
时间变化

产生出来的。

到这里，这个问题已经和一开始那个简单的：

怎么从巨大空间里面找几个编号？

不太一样了。

因为原本看起来只是麻烦的：

时间变化

现在也开始变成设计的一部分。

时间为什么会落到这些位置

继续往下想，可以把某个查询真正执行的时间记成：

τ(u)

如果一个目标的相位随着时间比较稳定地变化，可以先很粗地写成：

$$ h(u)=e^{j\Omega\tau(u)} $$

这里最麻烦的其实就是：

τ(u)

如果查询顺序完全乱，那么这个时间函数扔进 Walsh 域以后应该也会很难看。

但如果：

τ(u)

自己就带着某种比较简单的二进制结构，那么时间造成的变化也有可能只落到有限的一些方向上。

至少现在程序里面看到的现象让我觉得这个方向值得继续试。

我暂时没打算先把所有公式都证明得特别漂亮。

对我来说先做到：

把模型写出来
↓
跑起来
↓
改变查询顺序
↓
看看频谱到底怎么变

已经够有意思了。

如果现象根本不存在，那再漂亮的推导也没用。

C++先跑起来

最后还是先用 C++ 把整个流程写出来。

因为局部只有：

个状态，所以 FWHT 本身基本没有什么压力。

真正麻烦的反而是：

映射怎么生成？

多组之间怎么避免一直碰撞？

局部峰怎么找？

多个目标撞在一起怎么办？

时间变化以后，
多远的东西还能算同一个目标？

最后怎么把不同组重新对应起来？

现在程序大概是：

生成少量目标
↓
给每个目标一个32位编号
↓
生成多组8位映射
↓
生成查询状态
↓
按照指定顺序执行
↓
给响应加入时间变化
↓
每组做FWHT
↓
寻找局部峰值
↓
处理峰旁边的“回声”
↓
把多组结果重新拼起来
↓
和原始编号比较

最开始几次结果当然挺难看，有时候一个目标拖出来的东西已经快比主峰还高了，有时候两个目标刚好碰到一起，还有时候参数只改一点点，整个结果突然就乱掉。但是这种东西反而比做一道已经知道答案的题更有意思。

OI 题做完：

AC

基本就结束了。

这里没有标准答案告诉我：

最后应该长什么样

甚至连问题本身都可以继续改。

一开始我想的是：

怎么从巨大空间里面找几个编号？

然后变成：

怎么把编号压小？

接着：

碰撞怎么办？

后来又发现：

查询不是同时发生的

最后甚至开始想：

能不能反过来设计时间顺序？

问题会自己往外长。

为什么不直接扫

如果编号空间只有：

几千
几万

其实完全没必要搞这么复杂。

直接扫一遍可能还更快。

Echo 真正让我感兴趣的是这种情况：

可能空间特别大

真正存在的目标特别少

每次查询有成本

所有查询还必须按照时间顺序完成

这时候一个一个问：

你是不是这个？
你是不是这个？
你是不是这个？

就变成了最没意思的办法。

我更想做的是：

设计问题本身。

不是问四十多亿次：

你是不是编号 x？

而是只问一批经过设计的二进制问题，然后从答案里面把真正存在的编号反推出去。

而且不只是：

问什么

重要。

连：

先问什么
后问什么

也会影响最后得到的结果。

顺序本身也是算法的一部分。

还有一堆问题

现在这个东西当然还很粗，目标数量继续增加以后，碰撞肯定会越来越严重。不同目标强弱差得太大的时候，小的可能直接被大的盖掉，时间变化如果越来越快，原本还能看出结构的尾巴也可能越来越散。

还有一个更现实的问题。

程序里面：

响应是什么
噪声多大
相位怎么变

全部都可以自己随便生成，真的物理东西肯定不会这么听话。

到时候还会有：

噪声
状态切换误差
采样误差
不同通道之间的差异

之类的东西继续塞进来，不过我现在也不急着一次把它弄完，至少这个问题已经足够好玩了。

这种问题比：

这题应该套哪个模板？

有意思多了。

先写到这里。