Java: Datenstruktur, um viele Wörter zu speichern

Ich muss viele Wörter (+ 200k) in einem Java-Programm speichern, und ich möchte sehr schnell darauf zugreifen. Ich muss nur wissen, ob ein bestimmtes Wort zu meinem "Wörterbuch" gehört. Ich brauche kein Paar wie <word, smthg>. Wenn möglich suche ich eine Lösung in der Standardbibliothek.Java: Datenstruktur, um viele Wörter zu speichern

PS: Vielleicht ist die Verwendung einer Datenstruktur nicht der bessere Weg, dies zu tun? Lesen Sie jedes Mal, wenn die Datei mit den Wörtern effizienter ist?

edit: Es ist ein kleines Projekt. Ich muss mit der Wirksamkeit und dem Speicher umgehen

Last Edit: Ich wähle schließlich HashSet.

Quelle

2013-04-18 DouglasAdams

Klingt wie ein [HashSet] (http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html) könnte eine gute Passform sein. – Keppil

Haben Sie eine Idee über die Verwendung von [Lucene] (http://lucene.apache.org/) – SenthilPrabhu

@Keppil Das Problem in HashSet ist, dass es nicht sortiert ist. Also wird die Suche langsamer sein. –

Verwenden Sie Java-Sets, weil Sets linear sortierte Datenstruktur wie TreeSet sind. Für die Suche können Techniken wie die binäre Suche implementiert werden und sie sind schnell ohne Wiederholung.

Dies ist die Struktur eines Java-Sets.

enter image description here

Auch wird es keine Duplizierung damit Redundanz zu reduzieren gehen zu lassen und Ihr Gedächtnis speichern.

Wenn Sie verschiedene komplexe Komplexitäten von Suchalgorithmen wissen möchten, verweisen Sie auf diesen Link. Hier ist

http://bigocheatsheet.com/

Quelle

2013-04-18 10:21:51

Sets verschwenden viel Speicherplatz. Für diese Art von Aufgaben gibt es spezielle Datenstrukturen. –

@IvayloStrandjev 200k Wörter von durchschnittlich 10 Zeichen, die in einem HashSet gespeichert sind, benötigen vielleicht 5 bis 10MB im Speicher. Das ist nicht viel ... – assylias

Ausprobiert, es ist näher an 20MB, aber immer noch nicht viel. – assylias

Verwenden Sie entweder Trie oder Patricia tree, abhängig von der Verteilung der Wörter. Ich würde persönlich mit Patricia Tree gehen, da es mehr für die Speichernutzung optimiert ist (obwohl es schwieriger zu implementieren ist).

Quelle

2013-04-18 10:20:47

Für eine kleine Anzahl von Objekten, wie im Anwendungsfall des OP, würde ein HashSet gut funktionieren.Es ist auch erwähnenswert, dass es im Standard-JDK keine Trie/Patricia Tree-Implementierungen gibt. – assylias

Vielleicht möchten Sie meine TrieMap oder TrieSet Implementierungen testen (found here)? Ich habe sie speziell für solche Fälle geschrieben. Bisher habe ich Versuche für String und byte[] Schlüssel implementiert.

TrieSet<String> t = Tries.newStringTrieSet(); 

    t.add("hello"); 
    t.add("help"); 
    t.add("hell"); 
    t.add("helmet"); 
    t.add("hemp"); 

    List<String> resultsA = new ArrayList<>(); 
    t.findElements("hel", true, resultsA); // search for prefix 

    List<String> resultsB = new ArrayList<>(); 
    t.findElements("ell", false, resultsB); // search for substring 

    System.out.println("A: " + resultsA); 
    System.out.println("B: " + resultsB);

Dieser Druck würde:

, Diese

A: [hell, hello, helmet, help] 
B: [hell, hello]

Quelle

2013-04-18 11:36:02

> 1,5 KLOC und kein einziger Test? –

sieht ganz ok zu mir, ich weiß nicht, ob ich aus irgendeinem Grund falsch bin:

//put all your words to an ArrayList and sort the list. 
List <String> arr = new Arraylist<>(); 
while(there is next) 
    arr.add(theWord) 
Collections.sort(arr); 

//this is your search method 
boolean mysearch(keyword){ 
    return Collections.binarySearch(arr, keyword) 
}

Die Leistung ist: O(n*log_n) für Einfügen von Daten und Suche ist O(log_n)

Lassen Sie uns sagen, jede Zeichenfolge ist 20B, auf der a Verage. 20B *200000 = 4MB Platz.

Quelle

2013-04-18 11:41:26 smttsp

Java: Datenstruktur, um viele Wörter zu speichern

Antwort

Verwandte Themen