原始数据中的模式发现

Question

我正在寻找构建一种算法来发现原始数据（非 ASCII）中的重复模式。

可配置的最短和最大图案尺寸。要搜索的数据大小将达到数万字节。

例如，给定以下数据：

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

将输出遇到重复模式的次数。在这种情况下：

ABCD x2
02EF x3

我看过几种算法，例如后缀树，但通常似乎是基于字符串的。

这将用 Python 编写，但我对所涉及的概念而不是实际实现更感兴趣。

非常感谢您的帮助。

Answer 1

我会选择像Lempel-Ziv-Welch这样的算法

算法的内部字典将保存模式字符串，输出（即压缩数据）将表示这些子字符串的位置。从数据中获取计数很简单，算法也很容易实现。

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