프로젝트의 "찾기 기능"을 수행해야합니다. 나는 동일한 문자열 (물론 운영자가 작성한 하나의 문자열)을 모두 검색해야하며 가능한 한 가장 빠른 방법으로 거대한 파일에 얼마나 많은 문자열을 검색해야 하는지를 알아야합니다. 해시 테이블과 연결된 트리에 대해 생각했지만 올바른지 여부는 알 수 없습니다.파일에서 문자열을 검색하는 가장 빠른 방법
문자열로 할 수있는 방법은 무엇입니까?
사용하기에 가장 적합한 데이터 구조는 무엇입니까 (복잡성)?
가정 최악의 경우 :
/usr/share/dict/words을 가져 가자. 반복하고 그것을 섞는다.알고리즘의 선택은
에 따라 달라집니다 입력 및/또는별로 메모리를 사용할 수 없습니다 당신은 그것을 선형 적으로 검색 할 수 있습니다 (Boyer-Moor (Horspool), Rabin-Karp, Apostolico-Giancarlo, Knuth-Morris-Pratt).
당신은 입력과 메모리를 많이 사용할 수 있습니다. 먼저 파일을 색인 생성하고 (O (n), 분명히) 색인을 생성하고 O (1)에서 해시 테이블 또는 O (log n) tree (가능한 여러 가지 최적화가 있지만 간단하게 유지합시다).
별로 메모리가 필요하지 않습니다. 당신이하는 일, 해시 테이블이나 트리가 무엇이든 관계없이 어딘가에 위치를 유지해야하며 4 개 이상의 Gibibytes가 있기 때문에 64 비트 카운터가 필요합니다. 8 바이트는 1.1mio의 테이블 크기를 곱한 것 : 단 8 메가 바이트. 단어 자체 (하나의 Mebibyte가 내 /usr/share/dict/words)보다 작거나 해시 테이블에 대한 색인 (짧은 단어 목록으로 큰 정수가 필요하지 않기 때문에 조금 적음).
큰 파일의 개별 단어 인덱스를 유지 관리하는 데 약간의 오버 헤드가 있습니다. 바이너리 검색 트리는 메모리 오버 헤드가 상당히 빠르지 만 빠르고 신속하게 빌드됩니다. 색인을 검색 할 필요가없는 경우 : 간단한 배열에 색인을 넣으십시오.
tl; dr : 파일에 색인을 붙이십시오. 단어와 그 위치를 hastable하게 만듭니다. 한 번에 모든 것이 필요할 경우 간단한 배열에 장소를 두십시오 (64 비트 정수가 필요할 수도 있음).이 색인을 검색해야하는 경우 (2 진) 검색 트리를 사용하십시오. 완벽한 해시를 만드는 방법을 알고 있다고 가정합니다.
이것은 질문에서 명확하지 않은 많은 것들에 달려 있습니다. 예를 들어 파일의 내용은 무엇입니까? –
파일에서 가장 일반적인 ** 문자열을 찾아야합니까? ** 발생하는 모든 문자열 * x * times **? ** 특정 문자열 **이 몇 번이나 나옵니까? –
지금 원하는대로 정확하게 코드화되었지만 꼭 필요한 것은 아닙니까?(시작하기에 좋은 장소 일 수 있습니다.) –