原始数据中的模式发现

我期待构建一种发现原始数据（非ASCII）重复模式的算法。原始数据中的模式发现

可配置的最短和最大模式大小。要搜索的数据的大小将在成千上万的字节中。

例如，给定以下数据：

AB CD 01 AB CD 02 EF 03 02 EF 04 02 EF

将输出的次数的重复图案将被遇到的数量。在这种情况下：

ABCD x2 
02EF x3

我已经看过几种算法，如后缀树，但通常看起来是基于字符串的。

这将用Python编写，但我更关心涉及的概念，而不是实际的实现。

非常感谢您的帮助。

2013-03-16 Jon

阅读压缩算法。很多都基于这个想法。关于“基于字符串”的算法的说明毫无意义。没有任何理由说明为什么“基于字符串”的算法不能像原样那样处理数据，或者进行微小的更改。 – 2013-03-16 21:26:50

+1是因为“对涉及的概念更感兴趣，而不是实际的实现”。 – Dukeling 2013-03-16 21:53:05

我会去的算法像Lempel-Ziv-Welch

该算法的内部字典将保持模式串，并输出（即，压缩数据）将代表那些子串的位置。从数据中获得计数是微不足道的，算法也相当容易实现。

请注意，数据压缩上下文中的“字符串”并不意味着文本。二进制数据仅使用256个不同字节值的字母表。

2013-03-16 22:40:57

回答