단어 빈도 추적/계산

Question

단어 빈도 수를 저장하고 쿼리 할 수있는 좋은 디자인에 대한 공동체 의견을 제시하고자합니다. 나는 텍스트 입력을 구문 분석하고 단어가 몇 번 나왔는지 (시간이 지남에 따라) 저장해야하는 응용 프로그램을 만들고 있습니다. 그래서 주어진 다음 입력 :

• "조롱 조류를 죽일 놈"

다음 값 저장겠습니까 "피아노 플레이어 도발"

:

Word Count 
------------- 
To  1 
Kill 1 
A  2 
Mocking 2 
Bird 1 
Piano 1 
Player 1 

그리고 나중에 일을 주어진 임의 단어의 카운트 값을 신속하게 쿼리 할 수 ​​있습니다.

내 현재 계획은 단순히 단어와 카운트를 데이터베이스에 저장하고 단어 수 값 캐싱에 의존하는 것입니다.하지만이 방법을 장기적으로 실행하기에 충분한 캐시 적중률을 얻지 못할 것으로 생각됩니다.

누구나 알고리즘이나 데이터 구조 또는이를 잘 구현할 수있는 다른 아이디어를 제안 할 수 있습니까? 내가하지이 그것을 할 수있는 방법은 이라고 말하고

void map(String name, String document): 
    for each word w in document: 
    EmitIntermediate(w, "1"); 

void reduce(String word, Iterator partialCounts): 
    int result = 0; 
    for each pc in partialCounts: 
    result += ParseInt(pc); 
    Emit(AsString(result)); 

, 그러나 그것은 확실히이다 :

Answer 1

왜 데이터베이스가 적합한 솔루션이 아니라고 생각하는지 이해할 수 없습니다. 당신은 아마도 약 100000 개의 열만 가질 것이고 작은 테이블 크기는 메모리에 전체적으로 저장 될 수 있음을 의미합니다. 단어를 기본 키로 만들고 조회가 매우 빠릅니다.

Answer 2

워드 카운트는 MapReduce 프로그램 (의사 위키 백과의 코드)의 표준 예입니다 옵션은 뚜렷한 단어의 수가 하나의 컴퓨터에서 사용 가능한 메모리를 초과하는 경우 잘 확장되는 것을 필요로 할 때 필요합니다. 메모리 제한을 초과 할 수없는 한 해시 테이블을 업데이트하는 간단한 루프가 트릭을 수행해야합니다.

Answer 3

hash table을 사용하십시오.

Answer 4

해결책은 괜찮습니다. 캐시가 최근 사용 횟수를 기반으로하는 경우 가장 빈번한 단어에 대한 단어 수가 유지됩니다. (단어 배포는 처음 100 단어가 단어 인스턴스의 90 %를 차지하므로) 매우 큰 캐시가 필요하지 않습니다.

성능을 향상시키고 db를 삭제하려는 경우 단어를 trie로 인코딩하고 리프 노드에 사용 횟수를 저장할 수 있습니다. 본질적으로, 그것은 단어 텍스트에 색인을 붙이는 경우 데이터베이스가하는 일이므로, 실제로는 db 대기 시간 만 피할 수 있습니다. 그것이 목표라면, 병렬 검색을 사용하는 것과 같이 db 대기 시간을 피할 수있는 다른 방법이 있습니다.

Answer 5

성능이 가장 중요한 목표 인 경우 해시 기반 또는 트라이 기반 구조를 RAM에만 사용할 수 있습니다. 어쨌든 유용한 필터링을한다고 가정 할 때 (단어가 아닌 문자를 포함하지 않는 용어), 테이블의 최대 단어 수는 106 개에서 107 개 (여러 언어가 포함 된 경우에도)이므로 쉽게 현재 PC의 메모리에 적합하게 (그리고 모든 데이터베이스 처리를 완전히 피하십시오).

반면에 해싱 테이블에 대한 세부 정보를 직접 구현해야하는 경우 데이터베이스 사용자가 코드를 최대로 수정 한 동안 잘못 처리 할 수있는 코드가 더 있습니다. 따라서 구현시 사소한 세부 사항조차도 성능 손실을 다시 초래할 수 있습니다.

이 딜레마는 최적화의 첫 번째와 두 번째 규칙을 명확하게 보여줍니다. 1. 조기에 최적화하지 마십시오. 2. 최적화하기 전에 측정하십시오.

: