큰 바이너리 파일에서 문자열 검색

Question

큰 바이너리 파일 (1 MB < 크기 < 50MB)이 있습니다. 문자열을 검색하고 후속 4 바이트 (다른 ​​파일의 실제 데이터의 {size, offset})를 추출해야합니다. 검색을 가장 빨리 수행 할 수있는 가장 효율적인 방법은 무엇입니까?

EDIT : 인덱스 파일의 문자열은 정렬 된 순서입니다.

Answer 1

{string, size, offset} 튜플을 정렬 된 순서 (문자열 기준)로 저장하고 문자열에 대해 이진 검색을 사용합니다.

파일의 시작 부분에 문자열의 첫 글자마다 오프셋을 저장할 수도 있습니다. 예를 들어, 'a'로 시작하는 문자열이 120 위치에서 시작하고 'b'로 시작하는 문자열이 파일에서 2000 위치에서 시작된 경우 120, 2000, ...

Answer 2

인코딩이 고정 된 경우 (ASCII) 비교적 간단합니다. 바이너리 스트림을 열고 바이트를 읽고 목표 문자열의 첫 번째 문자와 일치시킵니다.

다른 (UTF-8) 인코딩을 사용하는 문자열이 있으면 더 까다로워집니다.

Answer 3

과 같은 파일을 시작할 수 있습니다. Boyer–Moore string search algorithm을 찾으십시오.

Answer 4

먼저 파일의 메모리 매핑을 사용하십시오. RAM에 읽는 것보다 훨씬 효율적입니다. 두 개의 복사본 (프로그램에 하나, 파일 캐시에 하나) 대신에 복사본이 하나뿐이기 때문입니다.

각 문자열이 고정 길이이면 메모리를 문자 배열의 배열로 처리 할 수 ​​있기 때문에 이진 검색이 매우 쉽습니다.

각 문자열이 가변 길이이지만 종료가 0 인 경우 문자열 목록의 중간으로 건너 뛰고 다음 0을 검색 한 다음이 다음 문자열을 테스트하는 이진 검색 변형을 사용할 수 있습니다. 그런 다음 앞으로 또는 뒤로 이동하여 문자열 목록의 1/4 또는 3/4으로 이동하고 반복하십시오.

각 문자열이 파스칼 스타일로 가변 길이 인 경우 시작 부분에 바이트 수가 더 까다 롭습니다. 처음부터 선형 검색은 검색 속도가 너무 느리지 않습니다. 정확한 문자열 일치를 찾으려면 길이가 일치하지 않는지 확인하여 대부분의 문자열을 건너 뛸 수 있다는 것을 잊지 마십시오.

자주 목록을 검색해야한다면 문자열 목록에 대한 char 포인터의 배열을 만드는 것이 다시 바이너리 검색을 매우 쉽게 만듭니다. 이 파일이 정말로 빠른 검색을위한 인덱스 파일이라면 파일을로드하는 동안 디자이너가 char 포인터 배열을 만들려고하지 않는 한 이미 어딘가에이 파일이있을 것입니다.