대용량 파일에서 n-gram 주파수 액세스하기

Question

저는 자연어 처리와 자바 프로그래밍에 새로운 것을 알고 있습니다. ngrams 및 관련 주파수 (aaprox, 250MB)가 포함 된 매우 큰 텍스트 파일이 있습니다. 프로그램 런타임에 ngram이 주어지면 주파수 값을 얻어야합니다. N- 그램 주파수가 파일에 다음과 같은 (예를 전용) 제공됩니다

the quick 445 
quick brown 458 
brown fox 11 
fox jumped 123 

나는 HashSet의를 채워 시작시 파일을 읽는 시도 ...하지만 그것은 18메가바이트 파일에 대해 약 1500 밀리했다 (시스템을 사용하여 테스트 .currentTimeMillis()). 이제는 n-gram 수를 정렬하고 250MB의 파일을 작은 덩어리로 나누고 목록을 채우고 별도의 색인에 파일 세트를 색인화하고 참조하여 주문형 주파수를 얻으려고합니다.

하지만 더 쉽고 효율적인 방법이 있는지 확실하지 않습니다. 더 좋은 방법이 있는지 알려 주시기 바랍니다. (스크립트 나 라이브러리를 사용하지 않는 것이 좋습니다 ...). 다들 감사 해요.

Answer 1

로드 시간이 일반적으로 가장 중요한 최적화 대상이 아닌 @mbatchkarov에 동의합니다. 하지만 런타임은 종종 메모리 사용량과 밀접한 상관 관계가 있습니다 (메모리 액세스 속도가 느리므로 캐시에 저장할 수있는 작업 집합이 많을수록 좋습니다).

각 bigram을 Integer 수 (아마도 java.util.HashMap)에 매핑하는 초기 접근법은 합리적이지만 매우 많은 메모리를 필요로합니다. 카운트 파일에는 수백만 개의 바이 그램이 포함되어 있으며 각각은 별도의 String으로 표시되어야합니다. 이러한 문자열은 (최소) 약 40 바이트의 메모리를 사용하며 각 객체는 Integer 객체를 필요로합니다. 대부분의 JVM 구현에서 약 20 바이트입니다. 내 거친 back-of-the-envelope 추측은 데이터 구조를 기가 바이트 이상으로 만듭니다.

그러나 bigram은 파일 (및 데이터 구조)에서만 한 번 발생하지만 대부분의 개별 단어가 여러 번 반복되는 것을 관찰하면 더 잘 수행 할 수 있습니다. 반복적으로 저장하지 않고 도망 갈 수 있습니다.

예를 들어, 예제에서 = 0, quick = 1, brown = 2 등의 단어부터 정수 인덱스까지의 맵부터 시작합니다. 어휘집의 크기는 모르지만 영어 단어를 자주 사용하는 경우에는 수십 또는 수십만 단어가 포함될 수 있습니다. 따라서 문자열 저장소는 더 작아야합니다.

카운트를 저장하려면 이러한 정수 단어 인덱스를 복합 키에 결합하여 해당 키를지도에 사용할 수 있습니다. 하나의 쉬운 '결합'방법은 단순히 첫 번째 단어의 색인을 비트 시프트하고 두 번째 색인의 OR을 비트 시프트하는 것입니다. 의사에서

:

HashMap<String, Integer> lexicon = new HashMap<String, Integer>(); 

// Iterate through the file, mapping each word to 
for (String file line) { 
    ... Parse out word1 and word2 
    if (!lexicon.containsKey(word1)) { 
     lexicon.put(word1, lexicon.size()); 
    } 
    if (!lexicon.containsKey(word2)) { 
     lexicon.put(word2, lexicon.size()); 
    } 
} 

지금, 별도의 카운트지도로 카운트를 추가, 다시 파일을 반복. 당신의 카운트지도에서 두 단어의 인덱스를 검색 키를 생성하고 조회 - 음절 수를 액세스

는

HashMap<Long, Integer> countMap = new HashMap<Long, Integer>(); 

for (String file line) { 
    ... Parse out word1, word2, and count 
    int i1 = lexicon.get(word1); 
    int i2 = lexicon.get(word2); 
    long key = (i1 << 32) | i2; 
    countMap.put(key, count); 
} 

를 매핑하는 유사합니다. 그렇게하면 저장 공간이 상당히 줄어 듭니다. 그러나 한 걸음 더 나아가 야하고 일반 HashMaps를 FastUtil 또는 Trove 같은 형식의 특정 맵으로 대체하십시오. 원시 데이터 구조는 데이터 맵에서 Long 및 Integer 각각에 대해 ~ 12-20 바이트의 오버 헤드를 많이 제거합니다.

위 의사 코드는 단어 색인에 32 비트 int를 사용하고 64 비트 long으로 결합한다고 가정합니다. 어휘집이 충분히 작 으면 16 비트 단락과 32 비트 int를 대신 사용할 수 있으며 더 많은 공간을 절약 할 수 있습니다.

편집 : 전체 n-gram 언어 모델 (trigram, 4-gram 등)을 구현하려면 더 효율적인 표현이 있고 n-gram 모델이 잘 처리된다는 것이 분명해야합니다. 여러 도서관 (나는 OpenGRM과 Lingpipe을 보길 권합니다.) 그러나 위의 의사 코드는 간단한 bigram 모델을 만드는 데 쉽고 상대적으로 효율적인 방법입니다.

Answer 2

Ngram을 처리하기위한 특수 라이브러리 인 BerkeleyLM을 살펴보십시오.