简洁的序列预测算法

简介:

计算机和人的最大区别在于,人具备彻底的学习和强大的联想能力,而计算机则不同,只能在程序员给定的框架内进行简单的学习(与其说是学习,不如说是参数微调)。
人类可以很容易的发现特有的模式,比如看下面几个例子:

image

然而,如此简单的模式,计算机却无法发现,但如果能让计算机学习这种模式,那无疑是非常有价值的。
我们的目标,是给定一串序列:

image

找出其中的规律,并能够推断之后的序列sn,直到无穷,或是序列结束。本文是笔者独立思考得到的,没有参考其他学术论文,如果有更好的方法,欢迎批评指正。


如果不限制模式的长度,那么这个问题可能是无解的,即使出现一长串的A,我们也不能就只认定这就是A的重复序列,很有可能后面会出现B。因此,必须给问题增加限制条件。

模式是递归定义的,对ID=2的例子,是ABC的重复,内部又是一个递增数组。ID=1的例子,则外部是递增数组,内部是重复。若是ABCCBAABCCBA, 则是重复,重复结构是ABCCBA。 如果要求更高,可以发现内部是一个回环。

重复

重复是最基本,最常见的模式,例如AAAAA,ABCABCABC。处理起来也非常容易:

从起始长度n=1为起点,判断之后的结构是否满足重复条件,如果满足,则算法终止,否则n++,直到n=min(MAXREPEATLEN,len(S)),此时序列不存在重复模式。

我们通常需要对重复段的长度增加限制,比如不超过10。

发现重复后,其表达就是数组[Mode]+ ,Mode为子序列,此时即可推导之后的元素。

值递增递减

考虑这样的序列:


ABCDEF...
ABCCDEEFG...
ABCEFGIJK...

它们没有重复模式,但存在子结构,子结构之间有递增和递减关系。我们的思路,是尽可能地将这种模式退化为重复模式,即可使用重复的方法。
聪明的读者可能已经想到,既然是递增递减,则可使用差分。
对第一个序列,后一个元素减去前面的元素,可得:


11111111....

第二个序列:


110110110....

第三个序列:


112112112...

之后,即可调用重复模式的分析思路,解决问题。


我们似乎还没有讨论这样的序列:


AA AB AC AD....

差分求解后,得到的是0,0,1,-1,2,-2,3,-3....这并不是一个重复的序列。
但如果按照相隔一个元素求差分,则顿时开朗:


0101010101...

因此,我们可总结值递增递减的模式分析方法:

从起始差分步进长度n=1为起点,判断之后的结构是否满足值递增递减条件,如果满足,则算法转换为处理重复模式,否则n++,直到n=min(MAXLEN,len(S)),此时序列不存在递增递减模式。

长度递增递减

这种模式,分析起来更为复杂,看下面的例子:


A AB ABC ABCD...
B EF IJK NOPQ...
1 12 112 1112 11112...

(中间的空格,是手工加上便于看清规律的)
这种规律很明显,但并不是重复,也不是值递增递减,它的子结构发生了长度上的变化。
按照上一节的思路,从左到右依次差分计算:


0,1,-1,1,1,-2,1,1,1,-3,1,1,1,1,-4....
2,1,2,1,1,2,1,1,1,1...
0,1,-1,0,0,1,-1,0,0,0,1,-1....

我想尽办法,试图能通过某种变换,获得像刚才那样简单有效的转换,发现无果。换一个思路,通过类似概率的手段来分析。仔细观察会发现, 出现最多的数字是步进值,第一行和第二行都是1,第三行是0。之后按照步进值分割,就成了下面的增减/重复序列:


0,-1,-2,-3....
1,-1,1,-1,1,-1...

而且,步进值出现的次数,也是一个递增,递减序列:


1 | 1,1 | 1,1,1 | 1,1,1,1| ....
0 | 0,0 | 0,0,0....

又可以按照增减,重复序列的方式处理。

总结一下这种方式的伪代码:
原始序列S1从左到右依次差分,得到的序列S2,求取出现次数最多的数字,以此为特征分隔符,即可将序列S2分割为两个序列:

image

其中SA和SB分别为增减/重复序列。

其他更复杂的序列

大家看了以上的处理思路,是不是希望让计算机去求解公务员考试题目?不好意思,复杂的序列非常多,比如下面的序列:

image

image

这个问题靠计算机搜索,几乎是不可解的。如果硬要处理,最终会变成一个离散的多项式拟合问题,到了那个时候就一点都不酷了。

好在,现实世界的流程和结构一般没有那么复杂,比如网页的结构,消息出现的样式,重复占据了绝大多数情况。可能最多出现递增递减和重复嵌套的情况。如果是复杂的序列,上面的检测方法最少能告诉我们,这个序列不是重复/递增递减序列,可能需要用更复杂的方式来处理。对于一般的情形,这样的思路基本够用了。
另外要注意的问题是相等性。我们简化了问题的描述,将序列简化为有明确标示和序号的串。看下面的例子:


<name>zhao</name>
<job>coding</job>
<name>wang<name>
<job>eating</job>
...

这是个name,job不断重复的xml文档,在解决模式推断之前,你需要一些手段告诉计算机,第一行和第三行,在一定程度上是相等的。如果不相等,这事没戏了。

额外的有益讨论

从刚才那个例子,可以看出文法推断在自动解析上的好处:

  • 如果能够发现序列的规律,就能自动将其结构化
  • 能在一定程度上预测下一条数据是什么类型,从而提升命中效率
  • 能够发现隐含在数据结构中的规律

文法推断是一项相当复杂的命题,即使序列有特定的规律,即使能找到问题的解,解的数量可能也是非常庞大的。通常使用奥卡姆剃刀原理,即认为正确的文法总是最简单的那个。本文描述的,也只是文法推断中一个最为简单的命题,即序列的模式发现。
更多的真实情况,是序列有规律,但却是符合概率的。下面的例子:


AAC AAC AAD AAC AAC AAC AAD...

多数情况出现的是AAC,但有较低的可能性出现AAD,如果能从其中找出规律并推算概率,那么也能解决相当多的问题。不过,就需要大量的数学知识和技巧了,笔者望洋兴叹,只能感慨于造物主对人类大脑的恩赐。

一方面,在表面上看起来毫无意义的噪声,经过某种特定的数学变换,却能从中发现稳定的规律。
只要愿意,任何一串序列都能转换为一个特定的整数,而整数处理起来比序列更为简单和纯粹。序列的分解,可以对应为整数的分解。质数为什么如此重要?因为质数提供了乘法计算中不可分解的“元”。

有任何问题,欢迎各位随时讨论。 


相关文章
|
2月前
|
存储 算法 索引
模拟算法题练习(二)(DNA序列修正、无尽的石头)
模拟算法题练习(二)(DNA序列修正、无尽的石头)
|
3月前
|
编解码 算法 定位技术
GEE时序——利用sentinel-2(哨兵-2)数据进行地表物候学分析(时间序列平滑法估算和非平滑算法代码)
GEE时序——利用sentinel-2(哨兵-2)数据进行地表物候学分析(时间序列平滑法估算和非平滑算法代码)
99 3
|
14天前
|
机器学习/深度学习 人工智能 运维
人工智能平台PAI 操作报错合集之请问Alink的算法中的序列异常检测组件,是对数据进行分组后分别在每个组中执行异常检测,而不是将数据看作时序数据进行异常检测吧
阿里云人工智能平台PAI (Platform for Artificial Intelligence) 是阿里云推出的一套全面、易用的机器学习和深度学习平台,旨在帮助企业、开发者和数据科学家快速构建、训练、部署和管理人工智能模型。在使用阿里云人工智能平台PAI进行操作时,可能会遇到各种类型的错误。以下列举了一些常见的报错情况及其可能的原因和解决方法。
|
15天前
|
算法 数据安全/隐私保护 数据格式
基于混沌序列的图像加解密算法matlab仿真,并输出加解密之后的直方图
该内容是一个关于混沌系统理论及其在图像加解密算法中的应用摘要。介绍了使用matlab2022a运行的算法,重点阐述了混沌系统的特性,如确定性、非线性、初值敏感性等,并以Logistic映射为例展示混沌序列生成。图像加解密流程包括预处理、混沌序列生成、数据混淆和扩散,以及密钥管理。提供了部分核心程序,涉及混沌序列用于图像像素的混淆和扩散过程,通过位操作实现加密。
|
16天前
|
编解码 算法 数据可视化
【视频】时间序列分类方法:动态时间规整算法DTW和R语言实现
【视频】时间序列分类方法:动态时间规整算法DTW和R语言实现
|
1月前
|
存储 算法
从动态规划到贪心算法:最长递增子序列问题的方法全解析
从动态规划到贪心算法:最长递增子序列问题的方法全解析
107 2
|
3月前
|
算法 测试技术 C++
【动态规划】【C++算法】801. 使序列递增的最小交换次数
【动态规划】【C++算法】801. 使序列递增的最小交换次数
|
2天前
|
算法 数据安全/隐私保护 计算机视觉
基于二维CS-SCHT变换和LABS方法的水印嵌入和提取算法matlab仿真
该内容包括一个算法的运行展示和详细步骤,使用了MATLAB2022a。算法涉及水印嵌入和提取,利用LAB色彩空间可能用于隐藏水印。水印通过二维CS-SCHT变换、低频系数处理和特定解码策略来提取。代码段展示了水印置乱、图像处理(如噪声、旋转、剪切等攻击)以及水印的逆置乱和提取过程。最后,计算并保存了比特率,用于评估水印的稳健性。
|
3天前
|
存储 算法 数据可视化
基于harris角点和RANSAC算法的图像拼接matlab仿真
本文介绍了使用MATLAB2022a进行图像拼接的流程,涉及Harris角点检测和RANSAC算法。Harris角点检测寻找图像中局部曲率变化显著的点,RANSAC则用于排除噪声和异常点,找到最佳匹配。核心程序包括自定义的Harris角点计算函数,RANSAC参数设置,以及匹配点的可视化和仿射变换矩阵计算,最终生成全景图像。
|
3天前
|
算法 Serverless
m基于遗传优化的LDPC码NMS译码算法最优归一化参数计算和误码率matlab仿真
MATLAB 2022a仿真实现了遗传优化的归一化最小和(NMS)译码算法,应用于低密度奇偶校验(LDPC)码。结果显示了遗传优化的迭代过程和误码率对比。遗传算法通过选择、交叉和变异操作寻找最佳归一化因子,以提升NMS译码性能。核心程序包括迭代优化、目标函数计算及性能绘图。最终,展示了SNR与误码率的关系,并保存了关键数据。
12 1