马尔可夫预测器：基于 D 阶马尔可夫模型的预测方法

假设待测样本数据为 S={s1,....,sL}, 其包含 L 个样本, 其中 L=10^6, 每个样本 s 属于 {x1,....xk}。其中, A 为样本空间, k 为样本空间的大小, 对于二元序列, k 为 2, A 属于 {0,1}; 对于 D 阶马尔可夫模型, 基于马尔可夫预测器的估计计算过程如下。

a) 初始化参数 D=16, N=L-2, wimmer=1。分别创建包含 D 个值的列 subpredict, scoreboard, entries 来记录 D 个子预测器的预测值、预测正确的次数以及已经记录的不同模板的个数, 并分别初始化为 Null, 0, 0。其中, entries 的最大值为 maxEntries=100000。创建数组 correct 包含 N 个值, 初始化为全 0, 用来记录马尔可夫预测器 N 次预测的结果。

b) 将 d 的值从 1 取到 D 分别代表 16 个不同的子预测器。设置 Md, 是一组计数器, Md[x,y] 记录模板为 x，其后一个输出为 y 的元组 (x，y) 的出现次数。

c) For i=3 to L :

For d =1 to D : If d=1: 将 s[i-2] 作为模板, 将 s[i-1] 作为 Md[1,s[i-2]] 的下一个输出值, 并将 Md[1,s[i-2]] 的计数器加 1。如果 Md[1,s[i-2]] 已经存在, 则将 s[i-1] 添加到 Md[1,s[i-2]] 的下一个输出值中。
如果 d>1: 将 s[i-d:i-1] 作为模板, 将 s[i] 作为 Md[d,subpredict[d]] 的下一个输出值, 并将 Md[d,subpredict[d]] 的计数器加 1。如果 Md[d,subpredict[d]] 已经存在, 则将 s[i] 添加到 Md[d,subpredict[d]] 的下一个输出值中。
对于每个子预测器 d, 计算 subpredict[d]。如果 Md[d,subpredict[d]] 存在, 则将 subpredict[d] 设置为 Md[d,subpredict[d]] 的下一个输出值中的最大值。否则, 将 subpredict[d] 设置为随机的样本。
对于每个子预测器 d, 如果 subpredict[d]=s[i], 则将 scoreboard[d] 加 1。
如果 entries<maxEntries, 则将模板 s[i-d:i-1] 添加到 entries 中。如果 entries>=maxEntries, 则从 entries 中随机选择一个模板并将其替换为 s[i-d:i-1]。

d) 对于每个 i=1 to N, 使用马尔可夫预测器对 s[i+2] 进行预测。如果预测值等于 s[i+2], 则将 correct[i] 加 1。

e) 计算正确率 acc=sum(correct)/N。返回 acc 作为预测器的准确率。