Effizienteres Speichern von Worten

[b1zarRe]

Hi,

Folgender Pseudocode:

//Lese Text einer Textdatei zeilenweise ein
(...)

//Zerstückel einzelne Wörter, welche einen Trenner wie (" .,;: etc") haben
(...)

//Solange noch Tokens vorhanden
//Füge Token in eine ArrayList
while(st.hasMoreTokens()) {
  String token = st.nextToken();
  al.add(token);
}

Meine Frage ist nun, ob es effizienter wäre mithilfe einer HashMap ODER eines
Hashsets und eine Liste zu arbeiten: Würde dies nicht speichersparender sein?
Ungefähr so:

//Lese Text einer Textdatei zeilenweise ein
(...)

//Zerstückel einzelne Wörter, welche einen Trenner wie (" .,;: etc") haben
(...)

//Solange noch Tokens vorhanden
//Prüfe ob Token in Hashmap ist
//Falls ja, adde diesen der Arraylist
//Falls nein, erzeuge eine neue Schlüssel-Wert Beziehung und füge den Wert ein
while(st.hasMoreTokens()) {
   String token = st.nextToken();
   if(hm.containsKey(token) {
      al.add(hm.get(token));
   } else {
     hm.put(token, token);
     al.add(token);
  }
}

Denke ich da korrekt? Vorher wurden einfach nur Tokens in die Arraylist abgelegt...
nun aber, werden quasi alle tokens mit einer hashmap zugewiesen: Sprich: Wenn
ein token bereits zugewiesen wurde, dann war dieser in genau der Form schonmal
im Text vorhanden, also kann ich doch einfach eine Referenz an die Stelle stellen?

Ist dies korrekt gedacht, oder unfug?

 

[Tente]

Ich denke es ist deine absicht bereits vorhandene Wörter nochmals hinzuzufügen, sonst macht es keinen Sinn was du geschrieben hast!?

Trotzdem ist deine Methode so äußerst ineffizient. Du hälst dir den String in deiner HashMap, um zu prüfen ob Wörter die auftreten bereits einmal aufgetreten sind, um dann die gleiche Referenz in die ArrayList schreiben zu können. Daraus ergeben sich 2 Fragen:

1. Ist es so wichtig, dass es die gleiche Referenz ist? Wenn man sauber mit equals prüft sollte das doch eigentlich immer nahezu egal sein.. Gleiche Buchstaben sind gleiche Buchstaben.

2. Warum speicherst du überhaupt doppelt? Ich kenne jetzt natürlich nur den Ausschnitt deines Codes. Ich verstehe es aber so, dass du das Wort brauchst und das eben so häufig wie es aufgetreten ist. Da wäre es viel sinnvoller das Wort als Key in der HashMap zu verwenden und als Value die Anzahl.. über das EntrySet kannst du iterieren und du kommst über HashMap-Methoden effizient an deine String Referenzen. So sparst du dir das doppelte Speichern der Strings.

 

[b1zarRe]

Naja, dass hat, denke ich folgenden Vorteil:
(Es geht darum Textdateien mit Sätzen auszulesen)

Wenn ich nur eine ArrayList benutze, dann wird jeder Token gespeichert UND
die Reihenfolge bliebe erhalten. NUR: Es kann natürlich sein, dass ein Wort wie
"und" oder "der" etc. x-mal im Satz vorkommen.

Deshalb die Frage, ob es nicht speichereffizienter wäre, mit
einer HashMap zu prüfen, ob das Wort bereits aufgenommen wurde, falls
nein, dann eine Zuordnung zu schaffen, falls ja, genau die Referenz (und nicht neuen String)
in die ArrayListe abzulegen.

Ein Set würde demnach wegfallen weil ich ja den Satz rekonstruieren/lesen möchte... Gleiches
für eine reine HashMap.


Anders ausgedrückt: Ich möchte einen Text in Wörtertokens zerlegen, speichereffizienter als
bei einer reinen ArrayListe, aber sodass man diese Sätze rekonstruieren kann !

 

[Tente]

Die Reihenfolge ist natürlich ein schlagendes Argument. Es ist schwer zu sagen ob es speichereffizieter ist. Ich würde es einfach ausprobieren und das Speicherverhalten beobachten.

 

[freez]

Da du die Sätze rekonstruieren möchtest, brauchst du die Information wo das Wort steht. Somit könntest du einerseits ein HashSet verwenden mit dem Wort, welches nur einmal vorhanden wäre und eine Liste / Array, wo du die Referenz zu dem Wort aus dem HashSet in die richtige Reihenfolge bringst. Allerdings hast du hier eine Liste mit Referenzen als Overhead und je nach Text kann es sein, dass du Speicher sparst, oder mehr Speicher brauchst. Bei einfachen Texten mit vielen Wiederholungen und einfachen Wörtern hast du Spareffekte und bei komplizierter Fachliteratur wirst du wohl wenig sparen, oder sogar drauflegen. Ein Test mit verschiedenen Texten könnte es zeigen.

Du könntest auch versuchen den Text vorher an bestimmten Stellen zu analysieren und daraufhin die entsprechende Speichertechnik verwenden.