한 단어에 대한 25GB 자료 검색

Question

한 단어에 대해 위키 백과의 25GB 코퍼스를 검색해야합니다. grep을 사용했지만 시간이 많이 걸립니다. 빠르고 쉽게 검색 할 수있는 효율적이고 쉬운 표현이 있습니까? 또한 정확한 일치를 찾고 싶습니다.

감사합니다.

Answer 1

단어 목록 (바이트 코드 오프셋)에 대한 매핑 색인을 원할 수 있습니다. 단어 목록은 사전 순으로 정렬됩니다. 그런 다음이 큰 목록의 단어에서 특정 문자가 시작되는 위치의 2 차 색인을 가질 수 있습니다.

Lazy hash   | Word index    | Corpus 
aaa starts at X | aaa      | lorem ipsum dolor 
aab starts at Y | ...      | sit amet ..... 
aac ...   | and 486, 549, 684, ... | ... 
... ...   |       | 
zzz ...   |       | 

이

내 부서에서 자연 언어 교수에 의해 주창 방법이다 (우리는 알고리즘 과정에서 실험실로이 운동을했다).

Answer 2

Boyer-Moore 알고리즘과 그 simplified version으로 성공했습니다. 웹을 둘러싼 다양한 언어에 대한 구현이 있습니다.

Answer 3

인덱싱 엔진을 사용해 보셨습니까 ... Nutch와 Lucene을 사용하셨습니까? Lucene은 색인 엔진입니다. Nutch는 웹 크롤러입니다. 힘을 합치십시오!

나는

Answer 4

@aloobe이 위치에 단어를 매핑 인덱스 파일을 사용하는 대답을했다 ... CouchDB를 (http://couchdb.apache.org/를) 언급하는 것을 잊었다. 저는 OP가 찾고있는 대답이 Boyer-Moore일지도 모른다고 생각하지만 이것에 대해서 설명하려고합니다.

인덱스 파일 (사람이 읽을 수있는 2 자리 숫자를 사용하는 간체)과 같을 것이다 :

53 17 89 03 
77 79 29 39 
88 01 05 15 
... 

위의 각 항목은 당신이 충분히 중요한 것으로 간주 한 단어 나 문자의 바이트 오프셋입니다 색인. 실제로, 당신은 당신의 코퍼스보다 큰 인덱스 파일을 사용하지 않을 것입니다! 이 수

and and are as 
ate bad bat bay 
bear best bin binge 

당신이에 Binary Search을 할 수있는 : 당신은 위치와 그 위치에서 단어를 대체한다면

트릭은, 색인 파일은 신체의 알파벳 순으로 정렬 된 버전이 될 것입니다 코퍼스는 인덱스 파일을 통해. 위의 "best"단어를 검색하는 경우 색인 파일에서 중간 항목을 가져옵니다. 79 그런 다음 코퍼스에서/byte 79 위치로 이동하여 단어가 무엇인지 확인합니다. bad입니다. 알파벳순으로 best > bad을 알고 있기 때문에 색인 파일의 두 번째 절반에 위치해야합니다.

중간 색인은 79 (6th) ~ 15 (12th) 사이이며, 예를 들어 01입니다. 그런 다음 우리는 bear을 찾기 위해 코퍼스에서 위치/바이트 88 (9 번째)을 봅니다. best > bear 그래서 다시 시도해보십시오. 중간 색인은 이제 어떻게 반올림했는지에 따라 01 (10 번째) 또는 05 (11 번째) 중 하나입니다. 그러나 분명히 우리는 best을 1 또는 2 개의 더 많은 검색에서 찾을 것입니다. 예를 들어 12 개의 단어가있는 경우 최악의 경우 최대 4 회의 검색을 수행합니다. 25GB 파일의 경우 평균 단어 길이는 문자와 공백 사이에 5 글자이며 공백은 약 40 억 단어입니다. 그러나 최악의 시나리오에서는 ~ 32 번만 검색합니다. 이 시점에서 프로그램 검색에 소요되는 시간은 실제로 검색하는 것보다 디스크를 회전시키고 입력을 버퍼하는 데 소비됩니다.

이 방법은 중복 단어에도 적용됩니다.the이라는 단어의 위치를 ​​모두 찾으려면 색인을 찾을 때까지 the에서 이진 검색을 수행하십시오. 그런 다음 매번 값을 사용하여 코퍼스를 조사하여 색인 파일의 위치에서 1을 반복해서 뺍니다. 해당 위치의 단어가 여전히 the 인 경우 계속하십시오. 마침내 중지하면 인덱스 파일에 가장 이른 인덱스가 the으로 매핑됩니다.

색인 파일을 만드는 것이 어려운 부분입니다. 코퍼스의 각 단어를 거쳐 단어와 색인의 데이터 구조를 구축해야합니다. 길을 따라 가면서 "a", "I", "the", "and", "is"등과 같이 너무 많거나 짧게 나열된 단어는 건너 뛰십시오. 끝나면 해당 데이터 구조를 사용할 수 있습니다 그것을 인덱스 파일로 변환하십시오. 25GB 파일의 경우 인덱스가 32 비트 이상이어야합니다. 불행히도 long (자바) 또는 long long (C)을 사용하십시오. 사람이 읽을 수 있어야 할 이유가 없으므로 색인을 문자열이 아닌 64 비트 값으로 작성하십시오.

내가 권장하는 구조는 self-balancing binary search tree입니다. 각 노드는 문자열 값 (단어)과 색인입니다. 그러나 트리는 문자열만을 기준으로 노드를 비교합니다. 이렇게하면 순서 순회 (왼쪽, 노드, 오른쪽)가 색인 파일을 정확하게 제공합니다.

희망이 도움이됩니다. 몇 년 전 휴대 전화 사전을 개발 한 예는 Jim Breen's EDICT입니다. EUC 인코딩 및 일본어 문자 때문에 픽업하기가 어려울 수 있지만 의도는 같습니다.