本文共 2720 字，大约阅读时间需要 9 分钟。
计算机和人的最大区别在于，人具备彻底的学习和强大的联想能力，而计算机则不同，只能在程序员给定的框架内进行简单的学习（与其说是学习，不如说是参数微调）。
人类可以很容易的发现特有的模式，比如看下面几个例子:然而，如此简单的模式，计算机却无法发现，但如果能让计算机学习这种模式，那无疑是非常有价值的。
我们的目标，是给定一串序列：找出其中的规律，并能够推断之后的序列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分割为两个序列：其中SA和SB分别为增减/重复序列。
大家看了以上的处理思路，是不是希望让计算机去求解公务员考试题目？不好意思，复杂的序列非常多，比如下面的序列:
这个问题靠计算机搜索，几乎是不可解的。如果硬要处理，最终会变成一个离散的多项式拟合问题，到了那个时候就一点都不酷了。
好在，现实世界的流程和结构一般没有那么复杂，比如网页的结构，消息出现的样式，重复占据了绝大多数情况。可能最多出现递增递减和重复嵌套的情况。如果是复杂的序列，上面的检测方法最少能告诉我们，这个序列不是重复/递增递减序列，可能需要用更复杂的方式来处理。对于一般的情形，这样的思路基本够用了。
另外要注意的问题是相等性。我们简化了问题的描述，将序列简化为有明确标示和序号的串。看下面的例子:zhao coding wang eating ...
这是个name,job不断重复的xml文档，在解决模式推断之前，你需要一些手段告诉计算机，第一行和第三行，在一定程度上是相等的。如果不相等，这事没戏了。
从刚才那个例子，可以看出文法推断在自动解析上的好处：
文法推断是一项相当复杂的命题，即使序列有特定的规律，即使能找到问题的解，解的数量可能也是非常庞大的。通常使用奥卡姆剃刀原理，即认为正确的文法总是最简单的那个。本文描述的，也只是文法推断中一个最为简单的命题，即序列的模式发现。
更多的真实情况，是序列有规律，但却是符合概率的。下面的例子：AAC AAC AAD AAC AAC AAC AAD...
多数情况出现的是AAC,但有较低的可能性出现AAD，如果能从其中找出规律并推算概率，那么也能解决相当多的问题。不过，就需要大量的数学知识和技巧了，笔者望洋兴叹，只能感慨于造物主对人类大脑的恩赐。
一方面，在表面上看起来毫无意义的噪声，经过某种特定的数学变换，却能从中发现稳定的规律。
只要愿意，任何一串序列都能转换为一个特定的整数，而整数处理起来比序列更为简单和纯粹。序列的分解，可以对应为整数的分解。质数为什么如此重要？因为质数提供了乘法计算中不可分解的“元”。有任何问题，欢迎各位随时讨论。
转载地址：http://oajta.baihongyu.com/