큰 단어 시퀀스에서 상위 K 개의 빈번한 단어를 찾는 가장 효율적인 방법
입력 : 양의 정수 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 힙을 사용하여 효율적으로 해결하십시오.
당신이 추구 하는 것이 실제 k 와 자연어 에 대한 텍스트에서 가장 자주 사용되는 k 단어 목록이라면 알고리즘의 복잡성은 관련이 없습니다.
그냥 샘플 어떤 알고리즘을 것을, 말, 텍스트에서 몇 백만 단어, 공정 초 만에 , 그리고 가장 자주 카운트 매우 정확합니다.
참고로 더미 알고리즘의 복잡성 (1. 모두 계산 2. 계산 정렬 3. 최선을 다함)은 O (n + m * log (m))이며, 여기서 m은 사용자의 다른 단어 수입니다. 본문. log (m)은 (n / m)보다 훨씬 작으므로 O (n)으로 유지됩니다.
실제로 긴 단계가 중요합니다.
- 메모리 효율적인 데이터 구조를 활용하여 단어 저장
- MaxHeap을 사용하여 자주 사용되는 상위 K 단어를 찾습니다.
다음은 코드입니다.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import com.nadeem.app.dsa.adt.Trie;
import com.nadeem.app.dsa.adt.Trie.TrieEntry;
import com.nadeem.app.dsa.adt.impl.TrieImpl;
public class TopKFrequentItems {
private int maxSize;
private Trie trie = new TrieImpl();
private PriorityQueue<TrieEntry> maxHeap;
public TopKFrequentItems(int k) {
this.maxSize = k;
this.maxHeap = new PriorityQueue<TrieEntry>(k, maxHeapComparator());
}
private Comparator<TrieEntry> maxHeapComparator() {
return new Comparator<TrieEntry>() {
@Override
public int compare(TrieEntry o1, TrieEntry o2) {
return o1.frequency - o2.frequency;
}
};
}
public void add(String word) {
this.trie.insert(word);
}
public List<TopK> getItems() {
for (TrieEntry trieEntry : this.trie.getAll()) {
if (this.maxHeap.size() < this.maxSize) {
this.maxHeap.add(trieEntry);
} else if (this.maxHeap.peek().frequency < trieEntry.frequency) {
this.maxHeap.remove();
this.maxHeap.add(trieEntry);
}
}
List<TopK> result = new ArrayList<TopK>();
for (TrieEntry entry : this.maxHeap) {
result.add(new TopK(entry));
}
return result;
}
public static class TopK {
public String item;
public int frequency;
public TopK(String item, int frequency) {
this.item = item;
this.frequency = frequency;
}
public TopK(TrieEntry entry) {
this(entry.word, entry.frequency);
}
@Override
public String toString() {
return String.format("TopK [item=%s, frequency=%s]", item, frequency);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + frequency;
result = prime * result + ((item == null) ? 0 : item.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
TopK other = (TopK) obj;
if (frequency != other.frequency)
return false;
if (item == null) {
if (other.item != null)
return false;
} else if (!item.equals(other.item))
return false;
return true;
}
}
}
다음은 단위 테스트입니다.
@Test
public void test() {
TopKFrequentItems stream = new TopKFrequentItems(2);
stream.add("hell");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("hero");
stream.add("hero");
stream.add("hero");
stream.add("hello");
stream.add("hello");
stream.add("hello");
stream.add("home");
stream.add("go");
stream.add("go");
assertThat(stream.getItems()).hasSize(2).contains(new TopK("hero", 3), new TopK("hello", 8));
}
자세한 내용은 이 테스트 케이스를 참조하십시오.
해시 테이블을 사용하여 전체 단어 시퀀스를 순회하면서 모든 단어의 빈도를 기록합니다. 이 단계에서 키는 "단어"이고 값은 "단어 빈도"입니다. O (n) 시간이 걸리며 위에서 설명한 모든 작업과 동일합니다.
hashmap에 삽입하는 동안 상위 10 개 자주 사용되는 단어를 유지하기 위해 크기 10 (k = 10)의 Treeset (Java에만 해당되며 모든 언어에 구현이 있음)을 유지합니다. 크기가 10 미만이 될 때까지 계속 추가하십시오. 크기가 10이면 삽입 된 요소가 최소 요소, 즉 첫 번째 요소보다 큰 경우. 그렇다면 제거하고 새 요소를 삽입하십시오.
트리 세트의 크기를 제한하려면 이 링크를 참조하십시오.
"ad" "ad" "boy" "big" "bad" "com" "come" "cold"라는 단어 시퀀스가 있다고 가정합니다. 그리고 K = 2. "단어의 첫 글자를 사용하여 파티션 나누기"를 언급했듯이 ( "ad", "ad") ( "boy", "big", "bad") ( "com" "come" "cold") "then k 개의 단일 단어 세트를 가질 때까지 다음 문자를 사용하여 가장 큰 다중 단어 세트를 분할합니다. " 파티션 ( "boy", "big", "bad") ( "com" "come" "cold"), 첫 번째 파티션 ( "ad", "ad")은 누락되고 "ad"는 실제로 가장 빈번한 단어.
아마도 나는 당신의 요지를 오해 할 것입니다. 파티션에 대한 프로세스를 자세히 설명해 주시겠습니까?
이 문제는 O (n) 알고리즘으로 해결할 수 있다고 생각합니다. 즉석에서 정렬을 할 수 있습니다. 즉,이 경우 정렬은 해시 테이블에 액세스 할 때마다 하나의 카운터 만 하나씩 증가하기 때문에 기존 정렬 문제의 하위 문제입니다. 처음에는 모든 카운터가 0이므로 목록이 정렬됩니다. 해시 테이블에서 카운터를 계속 증가시키면서 다음과 같이 빈도별로 정렬 된 해시 값의 또 다른 배열을 기록합니다. 카운터를 증가시킬 때마다 순위 배열에서 인덱스를 확인하고 해당 개수가 목록의 이전 항목을 초과하는지 확인합니다. 그렇다면이 두 요소를 바꿉니다. 따라서 우리는 최대 O (n)의 해를 얻습니다. 여기서 n은 원본 텍스트의 단어 수입니다.
나는 이것으로도 어려움을 겪었고 @aly에서 영감을 얻었습니다. 나중에 정렬하는 대신 사전 정렬 된 단어 목록 ( List<Set<String>>)을 유지 관리 할 수 있으며 단어는 X 위치에서 집합에있게됩니다. 여기서 X는 단어의 현재 개수입니다. 일반적으로 작동 방식은 다음과 같습니다.
- 각 단어에 대해 발생지도의 일부로 저장합니다 :
Map<String, Integer>. - 그런 다음 카운트를 기반으로 이전 카운트 세트에서 제거하고 새 카운트 세트에 추가합니다.
이것의 단점은 목록이 클 수 있다는 TreeMap<Integer, Set<String>>것입니다.- 를 사용하여 최적화 할 수 있지만 이것은 약간의 오버 헤드를 추가합니다. 궁극적으로 우리는 HashMap 또는 자체 데이터 구조를 혼합하여 사용할 수 있습니다.
코드
public class WordFrequencyCounter {
private static final int WORD_SEPARATOR_MAX = 32; // UNICODE 0000-001F: control chars
Map<String, MutableCounter> counters = new HashMap<String, MutableCounter>();
List<Set<String>> reverseCounters = new ArrayList<Set<String>>();
private static class MutableCounter {
int i = 1;
}
public List<String> countMostFrequentWords(String text, int max) {
int lastPosition = 0;
int length = text.length();
for (int i = 0; i < length; i++) {
char c = text.charAt(i);
if (c <= WORD_SEPARATOR_MAX) {
if (i != lastPosition) {
String word = text.substring(lastPosition, i);
MutableCounter counter = counters.get(word);
if (counter == null) {
counter = new MutableCounter();
counters.put(word, counter);
} else {
Set<String> strings = reverseCounters.get(counter.i);
strings.remove(word);
counter.i ++;
}
addToReverseLookup(counter.i, word);
}
lastPosition = i + 1;
}
}
List<String> ret = new ArrayList<String>();
int count = 0;
for (int i = reverseCounters.size() - 1; i >= 0; i--) {
Set<String> strings = reverseCounters.get(i);
for (String s : strings) {
ret.add(s);
System.out.print(s + ":" + i);
count++;
if (count == max) break;
}
if (count == max) break;
}
return ret;
}
private void addToReverseLookup(int count, String word) {
while (count >= reverseCounters.size()) {
reverseCounters.add(new HashSet<String>());
}
Set<String> strings = reverseCounters.get(count);
strings.add(word);
}
}
이 문제에 대한 다른 해결책을 찾았습니다. 그러나 나는 그것이 옳다고 확신하지 못한다. 해결책:
- 해시 테이블을 사용하여 모든 단어의 빈도 T (n) = O (n) 기록
- 해시 테이블의 처음 k 요소를 선택하고 하나의 버퍼 (공간 = k)로 복원합니다. T (n) = O (k)
- 매번, 먼저 버퍼의 현재 최소 요소를 찾고 버퍼의 최소 요소를 해시 테이블의 (n-k) 요소와 하나씩 비교해야합니다. 해시 테이블의 요소가이 버퍼의 최소 요소보다 크면 현재 버퍼의 최소를 삭제하고 해시 테이블의 요소를 추가합니다. 따라서 버퍼에서 최소값을 찾을 때마다 T (n) = O (k)가 필요하고 전체 해시 테이블을 탐색하려면 T (n) = O (n-k)가 필요합니다. 따라서이 프로세스의 전체 시간 복잡도는 T (n) = O ((nk) * k)입니다.
- 전체 해시 테이블을 순회 한 후 결과는이 버퍼에 있습니다.
- 전체 시간 복잡도 : T (n) = O (n) + O (k) + O (kn-k ^ 2) = O (kn + n-k ^ 2 + k). 왜냐하면 k는 일반적으로 n보다 실제로 작습니다. 따라서이 솔루션의 경우 시간 복잡도는 T (n) = O (kn) 입니다. k가 정말 작은 선형 시간입니다. 맞아? 정말 잘 모르겠습니다.
이런 종류의 문제에 접근하기 위해 특별한 데이터 구조를 생각해보십시오. 이 경우 문자열을 특정 방식으로 저장하려는 시도와 같은 특별한 종류의 트리는 매우 효율적입니다. 또는 단어 세기와 같은 자체 솔루션을 구축하는 두 번째 방법입니다. 이 TB의 데이터는 영어로 작성되고 일반적으로 약 600,000 단어가 있으므로 해당 단어 만 저장하고 반복되는 문자열을 세는 것이 가능할 것입니다.이 솔루션은 일부 특수 문자를 제거하기 위해 정규식이 필요합니다. 첫 번째 해결책은 더 빠를 것입니다.
http://en.wikipedia.org/wiki/Trie
이것은 검색하기에 흥미로운 아이디어이며 Top-K https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pd f 와 관련된이 문서를 찾을 수 있습니다.
가장 자주 사용되는 단어를 가져 오는 가장 간단한 코드입니다.
function strOccurence(str){
var arr = str.split(" ");
var length = arr.length,temp = {},max;
while(length--){
if(temp[arr[length]] == undefined && arr[length].trim().length > 0)
{
temp[arr[length]] = 1;
}
else if(arr[length].trim().length > 0)
{
temp[arr[length]] = temp[arr[length]] + 1;
}
}
console.log(temp);
var max = [];
for(i in temp)
{
max[temp[i]] = i;
}
console.log(max[max.length])
//if you want second highest
console.log(max[max.length - 2])
}
이러한 상황에서는 Java 내장 기능을 사용하는 것이 좋습니다. 왜냐하면 그들은 이미 잘 테스트되고 안정적입니다. 이 문제에서는 HashMap 데이터 구조를 사용하여 단어의 반복을 찾습니다. 그런 다음 결과를 객체 배열에 푸시합니다. Arrays.sort ()로 객체를 정렬하고 상위 k 단어와 그 반복을 인쇄합니다.
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class TopKWordsTextFile {
static class SortObject implements Comparable<SortObject>{
private String key;
private int value;
public SortObject(String key, int value) {
super();
this.key = key;
this.value = value;
}
@Override
public int compareTo(SortObject o) {
//descending order
return o.value - this.value;
}
}
public static void main(String[] args) {
HashMap<String,Integer> hm = new HashMap<>();
int k = 1;
try {
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("words.in")));
String line;
while ((line = br.readLine()) != null) {
// process the line.
//System.out.println(line);
String[] tokens = line.split(" ");
for(int i=0; i<tokens.length; i++){
if(hm.containsKey(tokens[i])){
//If the key already exists
Integer prev = hm.get(tokens[i]);
hm.put(tokens[i],prev+1);
}else{
//If the key doesn't exist
hm.put(tokens[i],1);
}
}
}
//Close the input
br.close();
//Print all words with their repetitions. You can use 3 for printing top 3 words.
k = hm.size();
// Get a set of the entries
Set set = hm.entrySet();
// Get an iterator
Iterator i = set.iterator();
int index = 0;
// Display elements
SortObject[] objects = new SortObject[hm.size()];
while(i.hasNext()) {
Map.Entry e = (Map.Entry)i.next();
//System.out.print("Key: "+e.getKey() + ": ");
//System.out.println(" Value: "+e.getValue());
String tempS = (String) e.getKey();
int tempI = (int) e.getValue();
objects[index] = new SortObject(tempS,tempI);
index++;
}
System.out.println();
//Sort the array
Arrays.sort(objects);
//Print top k
for(int j=0; j<k; j++){
System.out.println(objects[j].key+":"+objects[j].value);
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
For more information, please visit https://github.com/m-vahidalizadeh/foundations/blob/master/src/algorithms/TopKWordsTextFile.java. I hope it helps.
**
C++11 Implementation of the above thought
**
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}
vector<int> res;
// we use the priority queue, like the max-heap , we will keep (size-k) smallest elements in the queue
// pair<first, second>: first is frequency, second is number
priority_queue<pair<int,int>> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
// onece the size bigger than size-k, we will pop the value, which is the top k frequent element value
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
};
'program tip' 카테고리의 다른 글
| 중복되지 않는 목록 구현이 있습니까? (0) | 2020.10.08 |
|---|---|
| 몽고의 외래 키? (0) | 2020.10.08 |
| CanExecute가 처음 호출 될 때 WPF CommandParameter가 NULL입니다. (0) | 2020.10.08 |
| 목록의 요소 쌍 결합-Python (0) | 2020.10.08 |
| strict를 사용할 때 익명 함수에서 "this"가 정의되지 않은 이유는 무엇입니까? (0) | 2020.10.08 |