단어 빈도를 사용하여 '상위 목록'을 생성하는 알고리즘

Question

나는 인간이 생성 한 많은 콘텐츠가 있습니다. 가장 자주 발생하는 단어 나 구를 찾고 싶습니다. 이 작업을 수행하는 효율적인 방법은 무엇입니까?

Answer 1

바퀴를 재발 명하지 마십시오. Lucene과 같은 전문 검색 엔진을 사용하십시오.

Answer 2

간단한/쉬운 방법은 해시 테이블을 사용하는 것입니다. 단어를 따라 가면서 카운트를 증가시킵니다.

프로세스가 끝날 때 키/값 쌍을 개수별로 정렬합니다.

Answer 3

기본적인 아이디어는 간단합니다 - 당신이 단어를 산출 반복자에 큰 컬렉션을 설정 어떻게 - 실행 의사에, 물론

from collections import defaultdict 

def process(words): 
    d = defaultdict(int) 
    for w in words: d[w] += 1 
    return d 

, 악마가 세부에있다? 단일 시스템에서 처리 할 수는 없지만 mapreduce 접근 방식이 필요합니다. hadoop을 통해? 기타 등등. NLTK은 언어 적 측면 (언어를 분리하지 않는 언어로 단어 분리)을 도와줍니다.

단일 시스템 실행 (mapreduce 사용)에서 발생할 수있는 한 가지 문제점은 단순한 아이디어가 메모리를 채우는 너무 많은 싱글 톤 또는 그 주변 단어 (한 번 또는 몇 번 발생하는 단어)를 제공한다는 것입니다. 확률 론적 반증은 두 가지 패스를 수행하는 것입니다. 하나는 무작위 샘플링 (10 개에서 한 단어 만, 또는 백 개에서 한 개만 가져옴)으로 최상위 순위의 후보 단어 세트를 만든 다음 두 번째 패스는 후보 집합에 없습니다. 샘플링하는 단어의 수와 결과에 원하는 단어의 수에 따라 중요한 단어를 놓칠 확률에 대한 상한을 계산할 수 있습니다 (합리적인 숫자와 자연어의 경우 , 나는 너에게 잘 될거야.).

사전에 단어를 발생 횟수로 매핑하면 발생 횟수로 상위 N 단어를 선택하기 만하면됩니다. 사전이 너무 커서 전체 항목을 기준으로 정렬 할 수없는 경우 힙 대기열이 도움이됩니다 (예를 들어 내가 가장 좋아하는 실행 가능한 의사 코드에서 heapq.nlargest가이를 수행 할 것입니다).

Answer 4

Apriori algorithm을 살펴보십시오. 빈번한 항목 및/또는 빈번한 항목 집합을 찾는 데 사용할 수 있습니다.

위키 피 디아 문서의 상태와 마찬가지로 같은 효과를내는 더 효율적인 알고리즘이 있지만 이것이 상황에 적용되는지 확인하는 좋은 시작이 될 수 있습니다.

Answer 5

아마도 PATRICIA trie or practical algorithm to retrieve information coded in alphanumeric trie을 사용해 볼 수 있습니까?

Answer 6

단어를 키로하고 값을 카운터로 사용하는 단순한지도가 어떨까요? 높은 값의 카운터를 사용하여 가장 많이 사용되는 단어를 제공합니다. 이것은 단지 O (N) 작업입니다.