PDA

Visualizza la versione completa : ComplessitÓ computazionale algoritmo


zar1978
26-03-2010, 09:53
Ho il seguente problema legato all'identificazione all'interno di un testo di un indirizzo. Per me un indirizzo Ŕ composto dalla presenza, in contemporanea, entro una finestra di "n" caratteri di un <DUG> + <CIVICO> + <CAP> + <COMUNE> + <PROVINCIA>
(con dug identifico stringhe del tipo, via, piazza, strada, corso etc, etc)
per intenderci qualcosa del genere deve essere riconosciuto come un indirizzo:
Es: Corso Mazzini, 13 87100 Cosenza (CS)
Supponiamo di avere dei riconoscitori per ciascun "pezzo" della stringa indirizzo, riconoscitori basati su:
1) su espressioni regolari
2) su file (tipo lista dei comuni delle province etc etc)
riconoscitori che restituiscono liste di possibili candidati, e di iterare su queste liste scrivendo qualcosa del genere:



while (dugIter.hasNext()) {
dug = (Street) dugIter.next();
while (capIter.hasNext()) {
cap = (Cap) capIter.next();
if (!finestra(cap) continue;
while (comuneIter.hasNext()) {
comune = (Comuni) comuneIter.next();
if (!finestra(comune) continue;
while (civicoIter.hasNext()) {
civico = (Civico) civicoIter.next();
if (!finestra(civico) continue;
while(provIter.hasNext()) {
provincia = (Province) provIter.next();
if (!finestra(provincia) continue;
// OK HO TROVATO UN POSSIBILE INDIRIZZO
// VERIFICO CORRETTEZZA DATI ANNOTATI
if(verificaOK) ---> ANNOTO INDIRIZZO
else ---> PROSEGUI
}//END PROVINCIA
}//END CIVICO
}//END COMUNI
}//END CAP
}//END DUG


Il metodo boolean finestra(stringa) ritorna TRUE se la stringa annotata rientra nella finestra di "n" caratteri, mentre nel ciclo pi¨ interno si eseguono una serie di controlli per validare l'indirizzo candidato (ES coerenza tra comune e provincia o tra cap e comune).
Ora su una pagina contenente del testo specifico, il numero di iterazioni che ciascun ciclo pu˛ compiere ha i seguenti valori MEDI:

CICLI SUI DUG: 2
CICLI SUL CIVICO: 10
CICLI SUL CAP: 1
CICLI SULLA PROVINCIA: 8
CICLI SUL COMUNE:5

Ora un CIVICO, una PROVINCIA, oppure un COMUNE, annotati molto spesso non risultano tali infatti sempre facendo una MEDIA risulta che effettivamente si hanno:

SU 2 DUG ANNOTATI 2 SONO EFFETTIVAMENTE DEI DUG
SU 10 CIVICI ANNOTATI 2 SONO EFFETTIVAMENTE DEI CIVICI
SU 1 CAP ANNOTATO 1 E' EFFETTIVAMENTE UN CAP
SU 8 PROVINCE ANNOTATE 4 SONO EFFETTIVAMENTE DELLE PROVINCE
SU 5 COMUNI ANNOTATI 3 SONO EFFETTIVAMENTE DEI COMUNI

I tempi di esecuzione, soprattutto quando in una pagina ci sono parecchie annotazioni, sono molto elevati.Premesso che conto di migliorare il riconoscimento dei CIVICI e delle PROVINCE, c'Ŕ un modo per diminuire la complessitÓ e ottimizzare l'algoritmo? magari innestando in maniera diversa i cicli?

Grazie mille!

Loading