Suche passende Datenstruktur

[MFM]

Hi, hoffentlich kann mir einer helfen:

Ich möchte aus einer Datei Wörter auslesen, welche ich in einer Datenstruktur mit begrenztem Speicherplatz ablege, mit dem Ziel, die Wörter nach der ganzen Aktion

1) Nach Häufigkeitet
2) alphabetisch geordnet

auszugeben.

Kennt jemand dazu schon eine passende DS? Ich persönlich habe mir mal die Klasse TreeMap ins Auge gefasst.

Diese ist ja nach den Keys natürlich geordnet. Dazu würde ich alle Werte hinter den Keys mit dem zu einfügenden Wort vergleichen, falls es dabei ist, den Eintrag löschen und mit einem um 1 höheren key abspeichern.

Dennoch gäbe es noch einige Probleme, die sich damit nicht lösen lassen ...

Gibts dazu schon eine passende Datenstruktur?

MFM

 

[0x7F800000]

für die Häufigkeit würde ich eine "counting map" vorschlagen, eine datenstruktur, die als wrapper um eine beliebige Map<String,Integer> gelegt ist, und dann einfach beim jedem weiteren hinzugefügten wort den Integer-Zähler erhöht. In der Standardbibliothek ist das ding nicht drin, ist aber keine große Sache, kannst man schnell selbst basteln. Um viele Wörter zu sortieren, dürfte der Radix sort "ziemlich gut abgehen", wobei es möglicherweise mit irgendwelchen abgefahrenen Bäumen evtl. sogar schneller geht, aber der Radixsort ist unschlagbar einfach zu implementieren. Und vielleicht gibt's den schon irgendwo.

 

[Landei]

1) Ich glaube, das hieß MultiMap (z.B. bei GoogleCollections)
2) TreeSet (kein nachträgliches Sortieren nötig)

 

[MFM]

danke erstmal.

Ich habe es mit einer hashmap für die counting map mal versucht, komm aber noch nicht wirklich zu dem erwünschten ergebnis.

Alphabetisch sortieren ist kein problem, da lege ich einfach eine treeMap von der hashMap an ... das ganze wird dann alphabetisch sortiert ^^

Codemäßig sieht das so aus:

import java.util.*;

public class Test {

	public void countWords() {
		int numwords;
		String text = "für die Häufigkeit würde ich eine counting map vorschlagen, eine datenstruktur, die als wrapper um eine beliebige Map<String,Integer> gelegt ist, und dann einfach beim jedem weiteren hinzugefügten wort den Integer-Zähler erhöht. In der Standardbibliothek ist das ding nicht drin, ist aber keine große Sache, kannst man schnell selbst basteln. Um viele Wörter zu sortieren, dürfte der Radix sort ziemlich gut abgehen, wobei es möglicherweise mit irgendwelchen abgefahrenen Bäumen evtl. sogar schneller geht, aber der Radixsort ist unschlagbar einfach zu implementieren. Und vielleicht gibt's den schon irgendwo.";

		// HashMap mit Wort als Key und int Zählvariable als value
		Map<String, Integer> hashMap = new HashMap<String, Integer>();

		String[] words = text.split("[ 1234567890.;,!?\\n-]");
		numwords = words.length;
		System.out.println("Wortanzahl: " + numwords);

		for (int i = 0; i < words.length; i++) {
			if (words[i].length() > 1) {
				if (hashMap.get(words[i]) != null) {
					int value = hashMap.get(words[i]).intValue();
					value++;
					hashMap.put(words[i], value);
				} else
					hashMap.put(words[i], 1);
			}
		}
		// So sind die Daten momentan abgespeichert
		System.out.println(hashMap);
		// Dazugehörigen values
		System.out.println(hashMap.values());

		// Lege treeMap der hashMap an
		Map<String, Integer> treeMap = new TreeMap<String, Integer>(hashMap);
		// Dadurch kann ich, wenn ich die treeMap ausdrucke,
		//diese in alphabetischer Reihenfolge und ihrer values ausgeben
		System.out.println("\nAusgabe der Woerter und deren Anzahl in "
				+ "aufsteigender, alphabetischer Reihenfolge");
		System.out.print(treeMap);

	}

	public static void main(String[] args) {

		Test test = new Test();
		test.countWords();
	}

}

Mir fehlt der richtige Gedanke, wie sich das eben kombinieren lässt.

Ich schaue mir mal noch die Landei Vorschläge an