我希望构建一种算法来发现原始数据(非 ASCII)中的重复模式。
可配置的最短和最大图案尺寸。要搜索的数据大小将达到数万字节。
例如,给定以下数据:
AB CD 01 AB CD 02 EF 03 02 EF 04 02 EF
将输出遇到重复模式的次数。在这种情况下:
ABCD x2
02EF x3
我看过后缀树等几种算法,但大体上好像都是基于字符串的。
这将用 Python 编写,但我更感兴趣的是所涉及的概念,而不是实际的实现。
非常感谢您的帮助。
最佳答案
我会选择像 Lempel-Ziv-Welch 这样的算法
算法的内部字典将保存模式字符串,输出(即压缩数据)将表示这些子字符串的位置。从数据中获取计数很简单,算法也很容易实现。
请注意,数据压缩上下文中的“字符串”并不表示文本。二进制数据只是使用 256 个不同字节值的字母表。
关于algorithm - 原始数据中的模式发现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15454688/