Collections Word-Frequenzen zählen

[Landei]

Ich habe einmal darüber meditiert, wie man performant die Word-Frequenzen eines Textes ermittelt, wobei aber der aktuelle Stand jederzeit geordnet abrufbar sein soll (ansonsten ist das Problem trivial). Ich bin nur auf ein umständliches Hin und Her mit zwei Maps gekommen. Denke ich hier zu kompliziert?

public class WordCount {

    private final Map<String, Integer> wordFreq = new HashMap<String, Integer>();
    private final SortedMap<Integer, Set<String>> freqWord = new TreeMap<Integer, Set<String>>();

    public void add(String word) {
        int freq = 1;
        if (wordFreq.containsKey(word)) { //wir müssen den alten Eintrag löschen
            freq = wordFreq.get(word);
            Set<String> set = freqWord.get(freq);
            set.remove(word);
            if(set.isEmpty()) { //Einträge mit leeren Sets vermeiden
                freqWord.remove(freq);
            }
            freq++;
        }
        wordFreq.put(word, freq);
        Set<String> set = freqWord.get(freq);
        if (set == null) { //Eintrag mit neuem Set anlegen
            set = new TreeSet<String>();
            freqWord.put(freq, set);
        }
        set.add(word);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Entry<Integer, Set<String>> entry : freqWord.entrySet()) {
            sb.append(entry.getKey()).append(":").append(entry.getValue()).append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        WordCount wc = new WordCount();
        wc.add("a");
        wc.add("b");
        wc.add("a");
        wc.add("a");
        wc.add("c");
        System.out.println(wc);
        System.out.println();
        wc.add("d");
        wc.add("d");
        System.out.println(wc);
    }
}

 

[bERt0r]

Du könntest das ganze gleich in einer SortedMap <String, Integer> speichern und der Map einen Comparator geben, der eben aufgrund der Values, nicht der Keys sortiert.
Ob das dann performanter ist als deine zwei Maps kann ich nicht sagen.

 

[Gast2]

Hm, so eine "geschummelte" Lösung suchst du nicht oder?

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class WordCount {
	private final Map<String, WordFrequency> wordFrequencies;

	private boolean isSorted = false;
	private List<WordFrequency> sortedWordFrequencies;

	public WordCount() {
		wordFrequencies = new HashMap<String, WordFrequency>();
	}

	public void add(String word) {
		if (!wordFrequencies.containsKey(word)) {
			wordFrequencies.put(word, new WordFrequency(word));
		} else {
			wordFrequencies.get(word).increaseFrequencyByOne();
		}

		isSorted = false;
	}

	@Override
	public String toString() {
		if (!isSorted) {
			sortWordFrequencies();
		}

		StringBuilder sb = new StringBuilder();
		for (WordFrequency wf : sortedWordFrequencies) {
			sb.append(wf.word).append(" : ").append(wf.frequency).append("\n");
		}
		return sb.toString();
	}

	private void sortWordFrequencies() {
		sortedWordFrequencies = new ArrayList<WordFrequency>(
				wordFrequencies.size());

		for (Entry<String, WordFrequency> entry : wordFrequencies.entrySet()) {
			sortedWordFrequencies.add(entry.getValue());
		}

		Collections.sort(sortedWordFrequencies);
		isSorted = true;
	}

	private static class WordFrequency implements Comparable<WordFrequency> {
		private final String word;
		private int frequency;

		public WordFrequency(String word) {
			this.word = word;
			this.frequency = 1;
		}

		public void increaseFrequencyByOne() {
			frequency++;
		}

		@Override
		public int compareTo(WordFrequency o) {
			return o.frequency - frequency;
		}
	}

	public static void main(String[] args) {
		WordCount wc = new WordCount();
		wc.add("a");
		wc.add("b");
		wc.add("a");
		wc.add("a");
		wc.add("c");
		System.out.println(wc);
		System.out.println();
		wc.add("d");
		wc.add("d");
		System.out.println(wc);
	}

}

 

[Landei]

Du könntest das ganze gleich in einer SortedMap <String, Integer> speichern und der Map einen Comparator geben, der eben aufgrund der Values, nicht der Keys sortiert.
Ob das dann performanter ist als deine zwei Maps kann ich nicht sagen.

Das nützt aber nichts, wenn sich die Frequenz eines Wortes dauernd ändert.

@EikeB: In der Praxis könnte so ein "gemogeltes" Vorgehen durchaus sinnvoll sein, aber mir geht es eher um die theoretische Frage, wie man mein Vorgaben "datenstrukturtechnisch" umsetzen könnte.

 

[Gast2]

Wenn sich das Sortierkriterium laufend ändert seh ich so auf die schnelle keinen anderen Weg als die Datensätze jedesmal neu einzuordnen. Das könnte man z.b. mit ner SortedMap lösen, die das neu ordnen für einen erledigt.

EDIT:
Oder nen SortedSet, wär vielleicht ein wenig schlauer

EDIT2:
So vielleicht, auf Anhieb fällt mir da keine schlauere Datenstruktur ein.

public class WordCount2 {
	private final SortedSet<WordFrequency> wordFrequencies;
	
	public WordCount2() {
		wordFrequencies = new TreeSet<WordFrequency>();
	}
	
	public void add(String word) {
		WordFrequency wordFrequency = getAndRemoveWordFrequency(word);
		
		if (wordFrequency == null) {
			wordFrequency = new WordFrequency(word);
		} else {
			wordFrequency.increaseFrequencyByOne();
		}
		
		wordFrequencies.add(wordFrequency);
	}
	
	private WordFrequency getAndRemoveWordFrequency(String word) {
		Iterator<WordFrequency> iterator =  wordFrequencies.iterator();
		while (iterator.hasNext()) {
			WordFrequency wf = iterator.next();
			if (wf.getWord().equals(word)) {
				iterator.remove();
				return wf;
			}
		}
		
		return null;
	}
	
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (WordFrequency wf : wordFrequencies) {
			sb.append(wf.word).append(" : ").append(wf.frequency).append("\n");
		}
		return sb.toString();
	}
	
	private static class WordFrequency implements Comparable<WordFrequency> {
		private final String word;
		private int frequency;

		public WordFrequency(String word) {
			this.word = word;
			this.frequency = 1;
		}

		public void increaseFrequencyByOne() {
			frequency++;
		}

		public String getWord() {
			return word;
		}

		@Override
		public int compareTo(WordFrequency o) {
			if (o.frequency == frequency) {
				return o.word.compareTo(word);
			} else {
				return o.frequency - frequency;
			}
		}
	}
	
	public static void main(String[] args) {
		WordCount2 wc = new WordCount2();
		wc.add("a");
		wc.add("b");
		wc.add("a");
		wc.add("a");
		wc.add("c");
		System.out.println(wc);
		System.out.println();
		wc.add("d");
		wc.add("d");
		System.out.println(wc);
	}
}

 

[bERt0r]

Das nützt aber nichts, wenn sich die Frequenz eines Wortes dauernd ändert.

@EikeB: In der Praxis könnte so ein "gemogeltes" Vorgehen durchaus sinnvoll sein, aber mir geht es eher um die theoretische Frage, wie man mein Vorgaben "datenstrukturtechnisch" umsetzen könnte.

Genau das gleiche machst du doch auch, nur eben mit einer zweiten Collection, die man bei meinem Ansatz nicht braucht. Wenn sich der Wert erhöht, wird gegebenenfalls gelöscht (bin mir nicht sicher ob es mit einfachem überschreiben richtig sortiert wird) und neu eingefügt. Der Comparator sorgt dafür, dass die Wörter nach der Häufigkeit sortiert, richtig eingefügt werden.

 

[Marco13]

Ich finde, das ist eigentlich schon eine sehr kompakte und elegante Lösung. Man könnte sich eine Klasse machen, die das wegkapselt und wie eine normale Map aussieht ... oder nimm einfach Scala! :joke: Nee im Ernst: bezieht sich die Frage auf die "Menge des Codes", oder auf das etwas unhandliche Einfügen, weil man die Sortierung nachträglich nicht mehr ändern kann? Um das zu vermeiden bräuchte man irgendeinen Heap, dem man sagen kann: "heap.sortValueChanged(element, newValue)", und der dann die Sortierung auf Basis des neuen Wertes wiederherstellt - aber wenn das effizient sein soll (und man diesen Anspruch an sich selbst hat ) sollte das ein Fibonacci-Heap sein. Den schüttelt man nicht einfach aus dem Ärmel...

 

[tagedieb]

Mich erinnert das Problem an das Bag Interface (von Apache Commons Collections und von Goolgle implementiert) siehe TreeMultiset (Google Collections Library 1.0 (FINAL))

Allerdings hab ich auf anhieb nichs gefunden um die Collection nach Anzahl der Members zu sortieren, aber eventiel laesst dich die Klasse ja erweitern.