큰 파일에서 4-5 바이트 시퀀스 검색

파일이 ~ 1.5GB 이 파일에서 30 억 개의 바이트 시퀀스를 찾아야합니다. 하나의 시퀀스는 4 또는 5 바이트 일 수 있습니다. 첫 번째 위치를 찾거나 파일 번호의 해당 순서를 확인하십시오. 가장 빠른 방법? 컴퓨터큰 파일에서 4-5 바이트 시퀀스 검색

RAM 제한 - 4기가바이트

2012-03-22 turbanoff

무엇보다 빨리? – blueshift

어쩌면 시나리오를 더 확장 할 수 있을까요? ~ 15 억 바이트의 30 억 개의 시퀀스에는 엄청난 중복이있을 수 있습니다. 그 서열의 위치를 찾아야합니까? 아니면 단순히 그들이 존재하는지 아닌지? – deceze

첫 번째 위치 찾기 – turbanoff

사용 grep. 대용량 파일에서 물건을 찾는 데 최적화되어 있습니다.
옵션이 아니라면 Boyer-Moore algorithm에 대한 내용을 읽고 직접 사용하십시오. 그래도 같은 속도 인 grep을 재현하려면 많은 조정이 필요합니다.

2012-03-22 04:51:06 deceze

30 억 독립 실행, 매우 빠른 알고리즘까지도 느려질 수 있습니다. – turbanoff

누가 3 십억 번 실행해야한다고 했습니까? grep은 논리 OR 쿼리를 지원하는 정규식을 지원합니다. 비록 ORing 30 억 용어가 어렵더라도, 당신은 적어도 그것을 조각 낼 수 있습니다. – deceze

전처리를 사용하십시오.

나는 단지 Index을 생성하고 모든 고유 한 4 바이트 시퀀스의 첫 번째 인스턴스를 기록하여 파일을 실행해야한다고 생각합니다. 4 바이트 시퀀스와 첫 번째 발생 위치를 다른 파일에 저장하고 바이트 시퀀스로 정렬합니다.

색인 파일에서 간단한 2 진 검색을 사용하면 효율적으로 시퀀스를 찾을 수 있습니다.

O (1)로 검색을 줄이기 위해 더 영리하고 해시를 사용할 수 있습니다.

2012-03-22 05:04:51 st0le

시퀀스는 5 바이트 일 수있다. 이 경우 4 바이트 시퀀스의 첫 번째 위치가 충분하지 않습니다. – turbanoff

인덱스의 크기는 얼마입니까? – turbanoff

4 ~ 5 바이트 시퀀스가 반복되는 횟수에 따라 다릅니다 ... 반복이 높을수록 인덱스 크기가 작아집니다. 최악의 경우 (모든 시퀀스가있는 경우), 255^5 (~ 4228250625) (길이가 5 인 바이트의 모든 조합). – st0le

서치 라이트 검색 엔진을 확인하십시오.

이 프로그램을 사용하면 최대 10 ASCII 바이트의 여러 시퀀스를 단일 파일에 저장할 수 있습니다. 그런 다음 파일, 디렉토리, 파일 이름의 파일, 디렉토리 이름의 파일, 파일 이름의 arraylist 또는 디렉토리 이름의 arraylist를 지정하면됩니다.

또한 발견 된 각 시퀀스의 파일 바이트 위치/오프셋을보고합니다.

2014-01-31 14:34:11 Mark

답변