私もこれに苦労していて、@aly に触発されました。後で並べ替える代わりに、事前に並べ替えられた単語のリスト ( ) を維持するだけでList<Set<String>>、その単語はセット内の位置 X に配置されます。ここで、X は単語の現在のカウントです。一般的には、次のように機能します。
- 単語ごとに、その出現のマップの一部として保存します:
Map<String, Integer>。
- 次に、カウントに基づいて、前のカウント セットから削除し、新しいカウント セットに追加します。
これの欠点は、リストが大きくなる可能性があることです.aを使用して最適化できます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);
}
}