원시 데이터에서 패턴 발견

Question

원시 데이터 (비 ASCII)에서 반복 패턴을 검색하기위한 알고리즘을 구성하고자합니다.

구성 가능한 가장 짧은 패턴 크기와 가장 큰 패턴 크기. 검색 할 데이터의 크기는 수만 바이트입니다.

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

겠습니까 출력 반복 패턴이 발생 될 횟수 : 다음 데이터 주어진 예를 들어

. 이 경우 :

ABCD x2 
02EF x3 

나는 접미어 트리와 같은 몇 가지 알고리즘을 보았지만 일반적으로 문자열 기반 인 것으로 보입니다.

이것은 파이썬으로 작성 될 예정이지만 실제 구현보다는 관련된 개념에 더 관심이 있습니다.

많은 도움에 감사드립니다.

Answer 1

난 패턴 문자열을 보유 할 Lempel-Ziv-Welch

알고리즘의 내부 사전 같은 알고리즘 갈 것, 출력 (즉, 압축 된 데이터)는 해당 문자열의 위치를 ​​나타내는 것이다. 데이터로부터 카운트를 얻는 것은 간단하며, 알고리즘은 구현하기가 쉽습니다.

데이터 압축 컨텍스트의 "문자열"은 텍스트를 의미하지 않습니다. 이진 데이터는 단지 256 개의 다른 바이트 값의 알파벳을 사용합니다.