2014-05-19 1 views
0

큰 텍스트 파일 (몇 MB에서 GB)을 임의의 텍스트로 구성하고 소문자 만 공백없이 구성한다고합시다. 그러나 누군가는 영어의 단어 중간에 어딘가에 문자열을 추가합니다 (소문자 만 포함하고 공백은 포함하지 않음).알고리즘은 어떻게 대형 파일 내에서 구문을 검색합니까?

문자열이 무엇인지, 무엇을 말하고 있는지, 문자열이 말해야 할 것이 무엇인지 모를 때 (단지 영어로되어 있고 완전히 임의의 텍스트가 아님) 어떻게 알 수 있습니까? 영어 단어 사전을 사용할 수 있습니다.

+1

hsctf는 힘든 친구입니다 – Rush2sk8

+0

사실은 아주 구별 할 수있는 단어가 없으면 실제 영어를 소음, 특히 짧은 단어에 대해 말하기 어려울 것입니다 ... – awksp

+0

파일이 10MB이고 아무 것도 없습니다 공백 – Rush2sk8

답변

0

사전을 트라이에 빌드하고 파일을 탐색하십시오. O (n) 시간 (O (파일 크기 * trie 깊이) 최악의 경우) 및 O (1) 메모리 (사전 크기를 고정하고 작은 단어가 가장 큰 것으로 가정). 이것은 스트리밍 가능하며 매우 RAM 효율적이기 때문에 1 기가 바이트의 RAM으로 테라 바이트의 데이터까지 확장 할 수 있습니다.

관련 문제