这是一篇翻译向的文章,笔者整理了一些有关 Berlekamp–Massey 算法的笔记,还增加了一些自己的理解。

下面列出了笔者写此文时所参考的一些资料:

线性递推式

对于一个数列 ${S_i}$,它的 $m$阶递推式 ${\Lambda_i}$应该始终满足

$$\Lambda_1S_{i+m-1}+\cdots+\Lambda_{m-1}S_{i+1}+\Lambda_mS_i-S_{i+m}=0$$

这里和 wikipedia 上介绍的略有不同。

BM 算法简要介绍

我们记 $C(x)$是一个递推式,它的阶数为 $L$。BM 算法的目的就是对于给定的一个数列 ${S_i}$,找到一个递推式 $C(x)$满足,对于每个指针 $k$

$$C_1S_{k-1}+\cdots+C_{L-1}S_{k-L+1}+C_LS_{k-L}-S_k=0$$

记 $d$为上式的值,$B(x)$是上次失配时 $C(x)$的副本,$b$为上次失配时 $d$的副本,$m$为上次失配后成功迭代的次数

BM 算法将通过计算 $d$,以逐一检验当前递推式的正确性:

若 $d=0$,则成功迭代,检验下一项。
若 $d\not=0$,则失配,调整新的递推式为 $C'(x)=C(x)-\frac d bx^mB(x)$,则这一位的 $d’=d-\frac d b b=0$,匹配成功。

请注意,在最优递推式阶数小于等于给定数列长度的一半时,BM 算法才能保证求出的递推式最短,否则只能保证求出可行解。

原理

BM 算法更像是一个贪心算法,它的正确性在于,我们每次调整当前递推式时,可以保证新的递推式对于以前的项依然满足 $d=0$,我们无须再重新开始验证这个新递推式。

把式子展开,则正确性即可证明。

Code

很抱歉,代码咕咕咕了

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注