Strings nach häufigkeit sortieren -aber wie?

[Bastie]

Hi,

ich parse eine XML-Datei und will zählen wie oft jedes der Tags vorkommt. die tags sollen als strings zusammen mit ihrer häufigkeit in einer liste gespeichert werden. Das parsen ist kein Problem, aber wie mache ich folgendes: jedesmal wenn der tag gefunden wird, wird seine häufigkeit in einer liste um eins erhöht.
Ich habe zuerst eine hashmap mit der häufigkeit als value-feld genommen, aber es muss doch auch schöner gehen.

vielen dank!
LENA

 

[Gast2]

Hm, was ist daran unschön (siehe code)?
Ansonsten kannste das ganze auch noch als Objekt kapseln dem du einfach den String übergibst und dann später nur noch ne Methode getWordCount hast die dir die Anzahl des gesuchten Wortes zurückgibt.

	private Map<String, Integer> stringCounter = new HashMap<String, Integer>();

	public void count(String word) {
		if (stringCounter.containsKey(word)) {
			int wordCount = stringCounter.get(word);
			stringCounter.put(word, wordCount+1);
		} else {
			stringCounter.put(word, 0);
		}
	}
	
	public int getCount(String word) {
		int wordCount = 0;
		if (stringCounter.containsKey(word)) {
			wordCount = stringCounter.get(word);
		}
		return wordCount;
	}

 

[Bastie]

aber nach der häufigkeit sortiert sind sie jetzt nicht.
ich kann mir nicht ganz vorstellen, dass es nicht geschickterr geht. vielleicht mit 2 listen? oder kann man danach eine map erstellen in der die häufigkeiten die keys sind und die aufsteigend geordnet sind (wie ein minheap). was passiert dann wenn mehrere tags gleich oft vorkommen?
trotzdem danke eratmal für die hilfe!
LENA

 

[lenafrag]

Eine Map ist die effizienteste Datenstruktur für diese Aufgabe. Klar, ist auch anderes denkbar, wie (verknüpfte) Listen z.B. oder, wenn die Wortlänge begrenzt ist, riesengroße Arrays, aber ersteres dauert lange, zweiteres ist speicherintensiv...

 

[Gast2]

Oh, das mit der Sortierung hab ich überlesen, ich poste gleich nochmal nen neuen Code.

 

[tfa]

@Bastie
Versuch's mal mit einer SortedMap, z.B. der TreeMap.

 

[Gast2]

Ja, SortedMaps kann man natürlich auch nutzen.

Hier mal was "manuelles":

import java.util.List;

public class Main {

	public static void main(String[] args) {
		String text = "Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat. Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi. Nam liber tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat. uis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, At accusam aliquyam diam diam dolore dolores duo eirmod eos erat, et nonumy sed tempor et et invidunt justo labore Stet clita ea et gubergren, kasd magna no rebum. sanctus sea sed takimata ut vero voluptua. est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat.   Consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus.   Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.   Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat.   Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat. Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi.   Nam liber tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat.   Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis.   At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, At accusam aliquyam diam diam dolore dolores duo eirmod eos erat, et nonumy sed tempor et et invidunt justo labore Stet clita ea et gubergren, kasd magna no rebum. sanctus sea sed takimata ut vero voluptua. est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat.   Consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus.   Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.   Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat.   Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat. Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis at vero eros et accumsan et iusto odio dignissim qui blandit praesent luptatum zzril delenit augue duis dolore te feugait nulla facilisi.   Nam liber tempor cum soluta nobis eleifend option congue nihil imperdiet doming id quod mazim placerat facer possim assum. Lorem ipsum dolor sit amet, consectetuer adipiscing elit, sed diam nonummy nibh euismod tincidunt ut laoreet dolore magna aliquam erat volutpat. Ut wisi enim ad minim veniam, quis nostrud exerci tation ullamcorper suscipit lobortis nisl ut aliquip ex ea commodo consequat.   Duis autem vel eum iriure dolor in hendrerit in vulputate velit esse molestie consequat, vel illum dolore eu feugiat nulla facilisis.   At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, At accusam aliquyam diam diam dolore dolores duo eirmod eos erat, et nonumy sed tempor et et invidunt justo labore Stet clita ea et gubergren, kasd magna no rebum. sanctus sea sed takimata ut vero voluptua. est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat.   Consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus.   orem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero";
		StringCounter counter = new StringCounter(text);
		
		List<StringCounter.StringCount> wordList = counter.getSortedList();
		
		for (StringCounter.StringCount sc : wordList) {
			System.out.println("Das Wort " + sc.getString() + " kommt " + sc.getCount() + " mal vor.");
		}
	}
}

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

public class StringCounter {

	private Map<String, StringCount> stringCounter;

	public StringCounter(String text) {
		stringCounter = new HashMap<String, StringCount>();
		
		String[] words = text.split(" +");
		
		
		for (String word : words) {
			addWord(word);
		}
	}

	private void addWord(String word) {
		if (stringCounter.containsKey(word)) {
			stringCounter.get(word).inkrementCount();
		} else {
			stringCounter.put(word, new StringCount(word));
		}
	}
	
	public int getWordCount(String word) {
		if (stringCounter.containsKey(word)) {
			stringCounter.get(word).getCount();
		}
		return 0;
	}
	
	public List<StringCount> getSortedList() {
		List<StringCount> wordList = new ArrayList<StringCount>(stringCounter.values());
		Collections.sort(wordList);
		
		return wordList;
	}

	public class StringCount implements Comparable<StringCount> {
		private String string;
		private int count;

		public StringCount(String string, int count) {
			this.string = string;
			this.count = count;
		}
		
		public StringCount(String string) {
			this(string, 1);
		}

		public String getString() {
			return string;
		}

		public int getCount() {
			return count;
		}
		
		public void inkrementCount() {
			count++;
		}

		@Override
		public int compareTo(StringCount o) {
			return o.count - this.count;
		}
	}
}

 

[lenafrag]

@Bastie
Versuch's mal mit einer SortedMap, z.B. der TreeMap.

Und dann jedes mal, wenn erhöht werden soll, die ganze Datenstruktur durchsuchen

Außerdem geht das nicht, denn Elemente mit gleichem Gewicht sind nicht möglich in einer TreeMap

 

[Marco13]

TreeMap geht natürlich nicht direkt - zumindest bräuchte man eine TreeMap<String,Integer>, und die wäre erstmal nach den Keys sortiert. Wenigstens war das ein Anlass, endlich mal zumindest diesen kleinen Punkt von meiner TODO-Liste zu streichen - siehe http://www.java-forum.org/codeschnipsel-u-projekte/64510-map-treemap-sorted-values.html#post736137

 

[Blakh]

	private Map<String, Integer> stringCounter = new HashMap<String, Integer>();

	public void count(String word) {
		if (stringCounter.containsKey(word)) {
			int wordCount = stringCounter.get(word);
			stringCounter.put(word, wordCount+1);
		} else {
			stringCounter.put(word, 0);
		}
	}

Hab dazu eine kleine Frage. Ist das garantiert, dass das mit dem containsKey bei zwei Strings funktioniert? Bei einem int ja sicherlich, bei Objekten sicher nicht (bei gleichen Eigenschaften). Wie ist das jetzt bei Strings?

 

[Marco13]

Hab dazu eine kleine Frage. Ist das garantiert, dass das mit dem containsKey bei zwei Strings funktioniert?

JA.

Bei einem int ja sicherlich, bei Objekten sicher nicht (bei gleichen Eigenschaften). Wie ist das jetzt bei Strings?

Es funktioniert auch bei Objekten, wenn sie "equals" sind (und wenn die Bedinungen der Implementierung von Comparabl bzw. dem Comparator erfüllt sind, die in der API-Doku bei "...consistent with equals" zusammengefasst sind).