큰 파일에서 검색하는 가장 좋은 방법은 무엇입니까?

Question

KMP (또는 유사한) 검색을 큰 파일 (> 4GB)에 적용하려고합니다.

나는 이것을 나에게 문제를 줄 것으로 기대하고 있습니다. 공간이 충분하지 않기 때문에 모든 것을 메모리에 복사 할 수는 없습니다.

내 질문은이 검색을 수행하는 가장 좋은 방법은 무엇입니까? 단순히 파일*을 만들고 파일에서 직접 검색 해야하는 경우 블록 (4K)을 메모리에 복사하여 그 것들 또는 다른 것을 완전히 검색해야합니까?

Answer 1

지원하는 플랫폼을 사용하는 경우 mmap ()를 사용할 수 있습니다. 파일의 페이지 매김도 가능성이 있지만, 버퍼를 최대한 크게 유지하여 IO 오버 헤드를 줄이고 두 페이지의 경계를 조심해야합니다 (문자열이 일치하지만 페이지 경계에 의해 분리되어 있다고 가정합니다).

또는 어떤 종류의 색인을 구축하고 색인을 사용하여 검색을 제한하는 것이 좋습니다. KMP 검색은 특별히 효율적이지 않습니다. 물론 이것은 파일의 특성, 그것이 어떻게 생성되는지에 달려 있습니다. 등.

Answer 2

파일 액세스의 경우 데이터 사본을 피하기 위해 메모리 매핑 파일을 사용하는 것이 좋습니다. 유닉스 머신에서는 사소한 일입니다. 파일 매핑을 한 블록으로 할당 할 수없는 경우 파일 매핑을 작은 블록으로 분할해야 할 수도 있습니다. 관심이 있으시면 몇 가지 코드를 제공 할 수 있습니다.

검색을 위해 사용하는 것이 좋습니다 보이어 더 많은 검색 알고리즘.

Answer 3

버퍼링을 사용하면 파일에서 직접 검색하는 것이 매우 느립니다. 그러나 버퍼는 검색하는 것보다 커야합니다 (SearchLength), 물론, 당신은있을 때 버퍼를 새로 고침해야합니다. SearchLength 끝이 끝나기 전에 바이트.

Answer 4

가장 좋은 방법은 블록으로 읽고 검색하는 것입니다. 블록 크기를 매개 변수로 만들어야하므로 최상의 성능을 제공하는 것을 실험 할 수 있습니다.

그러나 전체 파일을 통해 선형으로 검색 할 필요가 없도록 파일을 어떤 식 으로든 시도하고 인덱싱하는 것이 일반적으로 더 효율적입니다. 예를 들어, KMP는 문자열 검색 알고리즘입니다. 단어의 경우를 찾고 있습니까? 그런 다음 파일에 단어와 해당 위치의 해시 테이블 (디스크에)을 만들고 매우 효율적인 검색을 할 수 있습니다.