简单说就是一个检测是否为Uniquely decodable codes的方法。做法是保存每轮中dangling suffix的集合,并检查是否包含了空串($\epsilon$),以及是否和之前的集合相同。若为前者,表示找到了一个证明不是Uniquely decodable codes的反例。若为后者,可证明是Uniquely decodable codes,因为如果某两轮集合相同,根据迭代公式,所有之后的集合都是这两轮之间部分的重复,所以都不含空串。但是假如存在反例,一定会有一轮集合包含空串。所以没有反例。

这个算法一定会停,因为dangling suffix的长度不可能超过最长的编码的长度,所以dangling suffix的集合的个数是有限的。

Links: