Java: Datastructure per l'archiviazione di molte parole

Question

Devo immagazzinare molte parole (+ 200k) in un programma Java e voglio accedervi molto velocemente. Ho solo bisogno di sapere se una parola data appartiene al mio "dizionario". Non ho bisogno di un paio come <word, smthg>. Se possibile, sto cercando una soluzione nella libreria standard.

PS: Forse l'utilizzo di una struttura dati non è il modo migliore per farlo? Leggendo ogni volta il file contenente le parole sarà più efficiente?

modifica: è un piccolo progetto. Ho a che fare con l'efficacia e la memoria

Ultima modifica: Finalmente scelgo HashSet.

Answer 1

Usa set java perché i set sono strutture di dati ordinati lineari come TreeSet. Quindi per la ricerca, tecniche come la ricerca binaria possono essere implementate e sono veloci senza ripetizioni.

Questa è la struttura di un set java.

Inoltre non sarà intenzione di consentire la duplicazione di conseguenza riducendo la ridondanza e salverà la memoria.

Se si desidera conoscere vari algoritmi di ricerca, consultare questo collegamento. Ecco

http://bigocheatsheet.com/

Answer 2

Utilizzare uno Trie o Patricia tree a seconda della distribuzione delle parole. Vorrei personalmente andare con Patricia tree in quanto è più ottimizzato per l'utilizzo della memoria (anche se è più difficile da implementare).

Answer 3

Forse volete testare le mie TrieMap o TrieSet implementazioni (found here)? Li ho scritti appositamente per casi come questo. Finora ho implementato Tries per le chiavi String e byte[].

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); 

Ciò stampare:

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

Answer 4

questo sguardo abbastanza ok per me, non so se ho sbagliato per qualche motivo:

//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) 
} 

La performance è: O(n*log_n) per inserimento dati e ricerca è O(log_n)

Diciamo che ogni stringa è 20B, sulla a verage. 20B *200000 = 4MB spazio.