입력 : 양의 정수 K와 큰 텍스트. 텍스트는 실제로 단어 시퀀스로 볼 수 있습니다. 그래서 우리는 그것을 단어 순서로 나누는 방법에 대해 걱정할 필요가 없습니다.
출력 : 텍스트에서 가장 빈번한 K 단어.
제 생각은 이렇습니다.
-
해시 테이블을 사용하여 전체 단어 시퀀스를 순회하면서 모든 단어의 빈도를 기록합니다. 이 단계에서 키는 “단어”이고 값은 “단어 빈도”입니다. O (n) 시간이 걸립니다.
-
(단어, 단어 빈도) 쌍을 정렬하십시오. 핵심은 “단어 빈도”입니다. 일반 정렬 알고리즘에서는 O (n * lg (n)) 시간이 걸립니다.
-
정렬 후 처음 K 단어 만 가져옵니다. 이것은 O (K) 시간이 걸립니다.
요약하면 총 시간은 O (n + n lg (n) + K) ， K는 N보다 확실히 작기 때문에 실제로는 O (n lg (n))입니다.
우리는 이것을 개선 할 수 있습니다. 사실 우리는 상위 K 단어를 원합니다. 다른 단어의 빈도는 우리에게 중요하지 않습니다. 따라서 “부분 힙 정렬”을 사용할 수 있습니다. 2) 및 3) 단계에서는 정렬 만 수행하지 않습니다. 대신, 우리는 그것을
2 ‘) “단어 빈도”를 키로 사용하여 (단어, 단어 빈도) 쌍의 힙을 작성하십시오. 힙을 빌드하는 데 O (n) 시간이 걸립니다.
3 ‘) 힙에서 상위 K 단어를 추출합니다. 각 추출은 O (lg (n))입니다. 따라서 총 시간은 O (k * lg (n))입니다.
요약하면,이 솔루션은 시간 O (n + k * lg (n))을 소모합니다.
이것은 단지 내 생각입니다. 1 단계를 개선 할 방법을 찾지 못했습니다.
일부 정보 검색 전문가가이 질문에 대해 더 많은 정보를 얻을 수 있기를 바랍니다.
답변
이것은 O (n) 시간 내에 수행 될 수 있습니다.
해결책 1 :
단계 :
-
단어를 세고 해시하면 다음과 같은 구조가됩니다.
var hash = { "I" : 13, "like" : 3, "meow" : 3, "geek" : 3, "burger" : 2, "cat" : 1, "foo" : 100, ... ... -
해시를 탐색하여 가장 자주 사용되는 단어 (이 경우 “foo”100)를 찾은 다음 해당 크기의 배열을 만듭니다.
-
그런 다음 해시를 다시 탐색하고 단어 발생 수를 배열 인덱스로 사용할 수 있습니다. 인덱스에 아무것도 없으면 배열을 만들고 배열에 추가합니다. 그런 다음 다음과 같은 배열로 끝납니다.
0 1 2 3 100 [[ ],[cat],[burger],[like, meow, geek],[]...[foo]] -
그런 다음 끝에서 배열을 횡단하고 k 단어를 수집합니다.
해결책 2 :
단계 :
- 같은 상기와
- 최소 힙을 사용하고 최소 힙의 크기를 k로 유지하고 해시의 각 단어에 대해 단어 발생을 최소와 비교합니다. 1) 최소값보다 크면 최소값을 제거합니다 (최소 힙은 k와 같음) 최소 힙에 숫자를 삽입합니다. 2) 간단한 조건을 쉬십시오.
- 배열을 순회 한 후 최소 힙을 배열로 변환하고 배열을 반환합니다.
답변
설명한 솔루션보다 일반적으로 더 나은 런타임을 얻을 수는 없습니다. 모든 단어를 평가하기 위해 최소한 O (n) 작업을 수행 한 다음 상위 k 개 용어를 찾기 위해 O (k) 추가 작업을 수행해야합니다.
문제 세트가 정말 큰 경우 map / reduce와 같은 분산 솔루션을 사용할 수 있습니다. n 명의지도 작업자가 각각 텍스트의 1 / n에서 빈도를 세게하고 각 단어에 대해 단어의 해시를 기반으로 계산 된 m 개의 감속기 작업자 중 하나에게 전송합니다. 감속기는 카운트를 합산합니다. 감속기의 출력에 대한 병합 정렬은 인기순으로 가장 인기있는 단어를 제공합니다.
답변
솔루션의 작은 변형 은 상위 K 순위에 신경 쓰지 않으면 O (n) 알고리즘을 생성 하고 O (n + k * lg (k)) 솔루션을 생성합니다. 나는이 두 경계가 일정한 요인 내에서 최적이라고 믿습니다.
여기에서 최적화는 목록을 실행하여 해시 테이블에 삽입 한 후 다시 발생합니다. 중앙값 알고리즘 의 중앙값을 사용 하여 목록에서 K 번째로 큰 요소를 선택할 수 있습니다 . 이 알고리즘은 증명할 수있는 O (n)입니다.
K 번째로 작은 요소를 선택한 후 퀵 정렬에서와 마찬가지로 해당 요소를 기준으로 목록을 분할합니다. 이것은 분명히 O (n)입니다. 피벗의 “왼쪽”에있는 모든 것은 K 요소 그룹에 있으므로 완료되었습니다 (계속 진행하면서 다른 모든 것을 버릴 수 있음).
따라서이 전략은 다음과 같습니다.
- 각 단어를 살펴보고 해시 테이블에 삽입합니다. O (n)
- K 번째로 작은 요소 선택 : O (n)
- 해당 요소 주변의 파티션 : O (n)
K 요소의 순위를 매기려면 O (k * lg (k)) 시간에 효율적인 비교 정렬로 정렬하면 총 실행 시간이 O (n + k * lg (k))가됩니다.
O (n) 시간 제한은 각 단어를 한 번 이상 검사해야하기 때문에 상수 요인 내에서 최적입니다.
O (n + k * lg (k)) 시간 제한은 k * lg (k) 시간 미만으로 k 요소를 정렬하는 비교 기반 방법이 없기 때문에 최적입니다.
답변
“큰 단어 목록”이 충분히 크면 간단히 샘플링하여 견적을 얻을 수 있습니다. 그렇지 않으면 해시 집계를 좋아합니다.
편집 :
샘플을 통해 일부 페이지 하위 집합을 선택하고 해당 페이지에서 가장 자주 사용되는 단어를 계산합니다. 합리적인 방법으로 페이지를 선택하고 통계적으로 유의미한 샘플을 선택했다면 가장 빈번한 단어에 대한 추정치는 합리적이어야합니다.
이 접근 방식은 데이터가 너무 많아 모든 것을 처리하는 것이 어리석은 경우에만 합리적입니다. 메그가 몇 개 밖에 없다면 추정값을 계산하는 데 신경 쓰지 않고 데이터를 찢고 정확한 답을 계산할 수 있어야합니다.
답변
단어의 첫 글자를 사용하여 분할 한 다음 k 개의 단일 단어 세트를 가질 때까지 다음 문자를 사용하여 가장 큰 다중 단어 세트를 분할하여 시간을 더 줄일 수 있습니다. 리프에 부분 / 완전 단어 목록이있는 일종의 256-way 트리를 사용합니다. 모든 곳에서 문자열을 복사하지 않도록 매우주의해야합니다.
이 알고리즘은 O (m)이며, 여기서 m은 문자 수입니다. k에 대한 의존성을 피합니다. 이것은 큰 k에 매우 좋습니다. [게시 된 실행 시간이 잘못 되었기 때문에 O (n * lg (k)) 여야하며, 그게 무엇인지 잘 모르겠습니다. 미디엄].
두 알고리즘을 나란히 실행하면 점근 적으로 최적 인 O (min (m, n * lg (k))) 알고리즘을 얻을 수 있지만 관련이 없기 때문에 평균적으로 더 빠릅니다. 해싱 또는 정렬.
답변
설명에 버그가 있습니다. 계산에는 O (n) 시간이 걸리지 만 정렬에는 O (m * lg (m))가 걸립니다. 여기서 m은 고유 한 단어 의 수입니다 . 이것은 일반적으로 총 단어 수보다 훨씬 적으므로 해시 작성 방법을 최적화해야합니다.
답변
귀하의 문제는 http://www.geeksforgeeks.org/find-the-k-most-frequent-words-from-a-file/ 과 동일합니다
.
Trie 및 min 힙을 사용하여 효율적으로 해결하십시오.
