[JAVA] Estrazione parole da file

[tagibo]

Devo estrarre da un file di testo tutte le parole contenute, per poi riversarle man mano in una hash table contandone la frequenza.
Per ora mi interessa solo l'estrazione delle parole dal file; io ho scritto questo codice:

public static void ExtractAndAdd(String s){
	int i=0;
	String r="",c="";
	while (i<s.length()){
		r=""; c=s.substring(i,i+1);
		while(!utility.isDelim(c)){
			r=r+c;
			i++;
			c=s.substring(i,i+1);
		}
		if (utility.isDelim(s.substring(i,i+1))) i++;
		add(r); //aggiungo ad hash table
	}

	public static boolean isDelim(String s) {
		char c = s.charAt(0);
		if (c == ' '
			|| c == ','
			|| c == '.'
			|| c == ';'
			|| c == ':'
			|| c == '?'
			|| c == '!'
			|| c == '\"'
			|| c == '\''
			|| c == '#'
			|| c == '('
			|| c == ')')
			return true;
		return false;
	}
}

Prima di continuare a scrivere il resto del codice, volevo chiedere se secondo voi una cosa del genere è abbastanza efficiente (considerando che devo controllare una serie di file di almeno 10mb), o se devo utilizzare altri metodi.
Aspetto le vostre risposte!
Ciao!

[pinok]

Non potevi usare un readLine per leggere le righe del file una ad una, e su ogni riga invocare lo stringTokenizer passandogli come delimitatori tutti quelli che ti vengono in mente ?
Mi pare che l'aggiunta alla hashtable sia ancora da scrivere, vero ?

[franksisca]

usa uno StringTokenizer, secondo me è meglio......MOLTO

[tagibo]

Originariamente inviato da pinok

Non potevi usare un readLine per leggere le righe del file una ad una, e su ogni riga invocare lo stringTokenizer passandogli come delimitatori tutti quelli che ti vengono in mente ?

Sì, il metodo ExtractAndAdd lo invoco dentro un metodo read dove leggo una ad una le righe del file.

Originariamente inviato da franksisca

usa uno StringTokenizer, secondo me è meglio......MOLTO

Non conosco però questo stringTokanizer. Mi potreste dare più informazioni?

Originariamente inviato da pinok

Mi pare che l'aggiunta alla hashtable sia ancora da scrivere, vero ?

Sì, faccio un passo per volta, intanto penso all'estrazione delle parole.... piano piano spero di arrivare alla fine!
Grazie a tutti e due!

[pinok]

Originariamente inviato da tagibo

Non conosco però questo stringTokanizer. Mi potreste dare più informazioni?

Ecco qua: http://java.sun.com/j2se/1.4.2/docs/...Tokenizer.html

C'è anche l'esempio

StringTokenizer st = new StringTokenizer("this is a test");
while (st.hasMoreTokens()) 
{
   System.out.println(st.nextToken());
}

Produce
this
is
a
test

Perchè di default lo spazio è coniderato come delimitatore.
Puoi costruirlo con

StringTokenizer st = new StringTokenizer("this is a test", "\t;.:-_");

per considerare tutto quello che c'è nella seconda stringa come delimitatore (ci aggiungi quello che vuoi)

[tagibo]

GRAZIE! Ora provo subito.
Ciao!

[sottovento]

Ciao,
beh, ti hanno dato degli ottimi suggerimenti, per cui non ci sarebbe bisogno di aggiungere altro.
Solo due cose:
1 - il tuo codice potrebbe portarti, in alcuni casi, a sfondare la dimensione massima della stringa, ottenendo un'eccezione di Out of Bounds: infatti prima controlli che la variabile i stia nei limiti, poi la incrementi. Non e' detto che il suo valore incrementato stia ancora nei limiti, no? (magari ho visto male,correggimi se sbaglio);

2 - Prova ad usare gli alberi binari invece della hash table. Ovviamente li devi implementare, ma se il tuo problema e' l'efficienza ne potrebbe valere la pena


High Flying
Sottovento

[tagibo]

Originariamente inviato da sottovento

1 - il tuo codice potrebbe portarti, in alcuni casi, a sfondare la dimensione massima della stringa, ottenendo un'eccezione di Out of Bounds: infatti prima controlli che la variabile i stia nei limiti, poi la incrementi. Non e' detto che il suo valore incrementato stia ancora nei limiti, no? (magari ho visto male,correggimi se sbaglio);

2 - Prova ad usare gli alberi binari invece della hash table. Ovviamente li devi implementare, ma se il tuo problema e' l'efficienza ne potrebbe valere la pena


High Flying
Sottovento

1 - Non ho fatto il controllo pensando che ogni file debba sempre terminare con un . o comunque con delimitatore (in italiano non ho mai visto terminare frasi senza un . o un ? o un !) e quindi non avrei problemi con l'OutOfBounds.
E' un po' rischioso, ma se uno rispetta la grammatica italiana....
2 - intanto fammi cimentare con le hash table, visto che l'ho usate poche volte.... Sicuramente può essere interessante implementare entrambi i metodi per poi confrontarli e vedere qual'è la diff. di efficenza. Quasi quasi lo faccio....
Grazie a tutti!

[pinok]

Originariamente inviato da tagibo

Sicuramente può essere interessante implementare entrambi i metodi per poi confrontarli e vedere qual'è la diff. di efficenza. Quasi quasi lo faccio....
Grazie a tutti!

La hashtable dovrebbe già essere ottimizzata per le operazioni di ricerca e inserimento.
Se vuoi testare dei miglioramenti, potresti anche prendere in considerazione l'idea di farti tante hashtable quante sono le lettere dell'alfabeto più i numeri 0-9, in modo da allegerire i controlli con il crescere del numero di parole

[tagibo]

Originariamente inviato da pinok

La hashtable dovrebbe già essere ottimizzata per le operazioni di ricerca e inserimento.
Se vuoi testare dei miglioramenti, potresti anche prendere in considerazione l'idea di farti tante hashtable quante sono le lettere dell'alfabeto più i numeri 0-9, in modo da allegerire i controlli con il crescere del numero di parole

Quindi fare una specie di vocabolario??

[pinok]

Originariamente inviato da tagibo

Quindi fare una specie di vocabolario??

Se lo vuoi chiamare così, diciamo di si.
O un'enciclopedia, che rende meglio l'idea.
Se hai una parola che inizia per L, pensa cosa vuol dire andarla a cercare dentro un libro di 24.000 pagine (per esempio) o piuttosto dentro al libro L con solo 1000 pagine.
Fai meno fatica a sollevarlo e a consultarlo, no?
Ovviamente, dipende dal numero di parole. Se sono poche, non avrai grosse ricerche da fare. Se sono tante, si

[sottovento]

Originariamente inviato da pinok

La hashtable dovrebbe già essere ottimizzata per le operazioni di ricerca e inserimento.
Se vuoi testare dei miglioramenti, potresti anche prendere in considerazione l'idea di farti tante hashtable quante sono le lettere dell'alfabeto più i numeri 0-9, in modo da allegerire i controlli con il crescere del numero di parole

Scusate l'intervento, spero che non sia di disturbo. Volevo semplicemente dire che gli algoritmi di inserimento e ricerca in tabella hash sono ottimi, specialmente se hai tanta memoria e non troppi dati. Al crescere del numero di dati, la complessita' non potra' che tendere a O(n).
Gli alberi binari saranno sempre O(log(n)).
E' estremamente probabile che con pochi dati le tabelle hash diano prestazioni superiori, ma al crescere del numero delle parole la situazione si ribalti.

Naturalmente il linguaggio implementa gia' le hash table e non implementa i bintree, ed anche questo e' un fattore da tenere in considerazione. Cmq per quanto ottimizzate per ricerca ed inserimento, la hash verra' superata in prestazioni dai bintree.

Chiedo scusa ancora per questo intervento sicuramente poco pratico

High Flying
Sottovento

[tagibo]

Originariamente inviato da pinok

Se lo vuoi chiamare così, diciamo di si.
O un'enciclopedia, che rende meglio l'idea.
Se hai una parola che inizia per L, pensa cosa vuol dire andarla a cercare dentro un libro di 24.000 pagine (per esempio) o piuttosto dentro al libro L con solo 1000 pagine.
Fai meno fatica a sollevarlo e a consultarlo, no?
Ovviamente, dipende dal numero di parole. Se sono poche, non avrai grosse ricerche da fare. Se sono tante, si

L'unica cosa che non mi torna è come richiamare la tabella hash giusta dove poter inserire la parola. Ad esempio:

        
        nextStr = filebuf.readLine();     
        while (nextStr != null){
            st = new StringTokenizer(nextStr,delim);
            .............
            metodi.addHash(mappa_giusta,st);
            nextStr = filebuf.readLine(); 
        } 
        filebuf.close();

Cosa ci metto al posto dei puntini??

Originariamente inviato da Sottovento

Scusate l'intervento, spero che non sia di disturbo. [....] Chiedo scusa ancora per questo intervento sicuramente poco pratico
High Flying
Sottovento

E che disturbo dai?? I forum sono nati apposta per scambiare idee e suggerimenti nella reciproca correttezza verbale!!
Anzi, ti ringrazio del tuo intervento perchè agli alberi di ricerca non ci avevo proprio pensato, dopo averlo implementato con le tabelle hash voglio provare a farlo anche con gli alberi!

Grazie e ciao a tutti!

[pinok]

Per richiamare la tabella giusta, potresti farti un array di hash e un metodo, ad es:

int indiceFromLettera(String iniziale) { .... }

in cui scrivi un qualche algoritmo che dalla lettera ti dà la posizione (ad es., A=0, B=1 ecc).
Quindi la hash nella posizione 0 dell'array è quella per la A, nella pos. 1 è quella per la B ecc.

[crick_pitomba]

Originariamente inviato da sottovento

Al crescere del numero di dati, la complessita' non potra' che tendere a O(n).
Gli alberi binari saranno sempre O(log(n)).
E' estremamente probabile che con pochi dati le tabelle hash diano prestazioni superiori, ma al crescere del numero delle parole la situazione si ribalti.

Non sono perfettamente d'accordo.
le hash table sono nate per compiere le operazioni di ricerca e inserimento in tempo O(1): è per quello che hanno bisogno di tanta memoria.


In ogni caso i due algoritmi non sono confrontabili: uno è basato sui confronti, l'altro su operazioni matematiche che ti danno l'accesso ai dati.

l'O(log(n)) degli alberi binari è riferito al numero di confronti necessario per individuare la chiave cercata.

Le tabelle di hash non effettuano confronti: la funzione di hash ti dice "in che cella inserire il valore" a meno che non ci siano collisioni: per questo sono in tempo costante.

potrebbe tendere ad o(n) solo se la funzione di hash fa particolarmente pena e praticamente tutti i dati vanno a finire in nella stessa cella ed utilizzi un sistema di gestione delle collisioni basate su concatenazioni: tutti i dati vanno a finire nello stesso slot e crei una catena lunga n elementi in cui fare la ricerca...

ma a questo punto un banale albero binario presenta lo stesso identico problema se inserisci n elementi ordinati ed ottieni un albero fortemente sbilanciato: puoi risolvere questo problema usando alberi rb o b alberi.

[sottovento]

Ciao
ottima osservazione.
Mi riferivo appunto al fatto di ottenere O(n) al crescere del numero di elementi, visto il problema in esame. E, sempre per il problema in esame, e' poco probabile che un albero sia sbilanciato.

High Flying
Sottovento

[tagibo]

E l'esercizio continua.... QUI!