光速标记等价构造中ERA与EQ表的初始化问题（Matlab实现）

嘿，刚好对这个算法有点了解，来给你捋清楚~

首先明确结论：ERA和EQ确实需要预先初始化，但绝对不能初始化为零矩阵，否则会直接破坏算法的核心逻辑，你遇到的祖先始终为0、EQ变空的问题完全是初始化错误导致的，肯定不合理。

为什么不能用零矩阵初始化？ #

算法14里的EQ本质是并查集（Union-Find）的父节点数组，用来存储每个等价类的代表元（祖先）；ERA则是相对标签到绝对标签的映射表，初始时每个样本的相对标签和绝对标签是一一对应的。

如果把EQ初始化为全零矩阵：

• 第14行和17行的找祖先操作（带路径压缩的find逻辑）会因为初始父节点是0，一直返回0这个无效的标签索引（一般标签是从1开始的正整数）。
• 后续的合并操作会把所有元素的祖先都指向0，最终导致等价类的逻辑完全混乱，甚至出现EQ“变空”的错误结果，这完全不符合算法的设计初衷。

正确的初始化方式 #

根据算法的逻辑，初始化要满足每个元素初始时属于自己的等价类：

• 假设你的标签范围是1~N（N是样本总数），那么：
  • EQ应该初始化为1:N（用一维数组即可，不需要矩阵，并查集用一维数组更高效），也就是每个元素的初始祖先就是它自己；
  • ERA同样初始化为1:N，因为初始时相对标签和绝对标签完全对应，没有等价合并的情况。

这样初始化后，找祖先的逻辑才能正确执行，后续的合并、更新操作也能按照算法14的流程正常推进。

内容的提问来源于stack exchange，提问作者Fennec