Newsgroup: it.comp.java
Titolo: Ottimizzazione algoritmo ricerca su array

Devo eseguire un algoritmo di string matching tra una stringa ed un array di 
stringhe. L'array allo stato attuale contine circa 200.000 elementi, ma in 
fase di produzione si dovrebbero superare i 2 milioni di stringhe......
Mi stavo chiedendo quali fossero i vantaggi nel dividere l'array in n sotto 
array, ed eseguire n ricerche simultanee con n thread separati, magari in 
relazione produttore/consumatore, (tutti i thread inseriscono in un array 
comune i gradi di similitudine ad ogni iterazione)
Secondo voi come procedimento e' valido?
Supponendo di avere una macchina dual core, 2 thread sono ottimali, ovvero 
ogni thread su un core? (e quindi con 4 thread non dovrei avere 
significativi incrementi delle prestazioni, giusto?) 


Metterlo in database relazionale no?
Lo string matching è fatto su una sottostringa, sulla stringa intera, o 
sull'inizio della stringa?
A seconda della risposta ha senso indicizzare l'elenco in modi diversi.
-- 
Andrea Francia
http://www.andreafrancia.it/

Quali strutture dati e algoritmi intendi usare?
L'array delle stringhe è ordinato?

 diversi.
Su tutta la stringa. Pensavo di applicare il confronto fra tutte le stringhe 
a disposizione (peggiore caso, quando non viene inserita la località 
dll'indirizzo) 

 L'array delle stringhe è ordinato?
No, non e' ordinato.
Come algoritmi stavo testando  la distanza di Levenshtein, QGrams e 
Smith-Waterman-Gotoh per vedere la migliore approssimazione tra tempi di 
calcolo e bonta' dei risultati (tutti implmentati in java nella libreria 
stringmetrics 
http://www.dcs.shef.ac.uk/~sam/stringmetrics.html
) 

 i dati vengono da database
Scusa, ma lo string matching non puoi farlo fare direttametne al database?
Y.

 dll'indirizzo) 
Così ci metti troppo tempo, devi prima indicizzare.
Ti crei una tabella con due campi
    Parola: Stringa
    Indirizzo che la usa: ID dell'Indirizzo.
Fai un ciclo che indicizza tutti gli indirizzi, per ogni indirizzo vai 
ad aggiungere un record alla tabella indice. Per esempio se trovi un 
indirizzo con
    Id=2143
    Text=P.zza mazzini, 31
Aggiungi alla tabella indice le seguenti tuple (Parola, Indirizzo_ID):
    ("P.zza", 2143)
    ("Mazzini", 2143)
    ("31", 2143)
Quando devi fare la ricerca parti dalla tabella indice.
Se l'utente ricerca Piazza mazzini, tu scomponi in
	- Piazza
   	- Mazzini
Poi aggiungi i sinomini conosciuti e ottieni
	- Piazza
	- P.zza
   	- Mazzini
Fai una SELECT FROM Indirizzi
		LEFT JOIN Indice
		ON Indice.Indirizzo_ID = Indirizzi.ID
	WHERE
		Indice.Parola IN ('Piazza', 'P.zza', 'Mazzini')
E ottieni il tuo indirizzo a tempo zero.


 stringmetrics 
http://www.dcs.shef.ac.uk/~sam/stringmetrics.html
) 
sul sito che hai linkato c'e' gia' il test fatto su tutti gli algoritmi...
Ciao Jack
-- 
http://motoko.dyndns.org
http://jack471.labrute.fr


boh, non saprei...mysql non ha funzioni per lo string matching (like non 
basta, soundex non funziona).
Stored procedure? Dovrei riscrivere degli algoritmi gia' 
implementati...quale potrebbe essere l'effettivo miglioramento di far 
eseguire l'analisi al db piuttosto che ad un programma esterno (a parte 
spreco memoria che non "costa") 


Per scoprire cosa è meglio e cosa non lo è (ad es. riguardo l'uso di 2
thread piuttosto che 4 etc.) ti consiglio di usare un profiler.
In tal modo potrai analizzare le tue prove, sia dal punto di vista
della cpu che dal punto di vista del consumo di memoria.
----
Articoli ed Esempi su
[Java EE, EJB, Servlet, JSP, WebService, Glassfish, Java ME etc]
http://programmaremobile.blogspot.com


Mmmh, non ci avevo pensato...
ma il problema e' cono gli errori di scrittura, cioe' non e' tanto p.zza o 
piazza a creare problemi (basterebbe anche creare regole di sostituzione in 
fase di insrimento...) , ma mazini mazzini mazzzini mazzinini che devono 
essere riconosciute e ritornate entrambe, in ordine di somiglianza, come 
mazzini....poi forse non ho capito a fondo la soluzione che mi hai 
proposto.... 

 eseguire l'analisi al db piuttosto che ad un programma esterno
Cambia che il RDBMS serve proprio a restituirti nel modo più efficiente
possibile e scrivendo meno codice possibile (SQL) soltanto i dati che ti
servono.
Se devi caricare tutte le righe in memoria e poi ravanarci sopra con
Java tanto vale averle in un file di testo, no?
Prova con le regexp o altrimenti cambia RDBMS.
Y.


No, mi sa che mi sono spiegato male....
Ho una tabbellona in mysql che non posso cambiare che contiene degli 
indirizzi. Un utente esterno mi passa una stringa (chiamiamola input) che 
contiene un indirizzo, io devo ritornare dal db n stringhe con n variabile 
che ordinate per "somiglianza" alla stringa input...
es: input = viale marcillo antonio 23
output:
viale Antonio Marcello -> 95%
viale Antonio Murcilla  -> 83 %
via le mani dal naso  -> 3%
Ora, che io sappia l'sql non permette di ricercare stringhe "simili", 
l'operatore like non fa questo tipo di ricerche, o sbaglio? (ad esempio se 
cerco ..where nome like "via casiolina" non mi ritorna via casilina, che 
invece e' l'unica strada possibile)
Il fatto di caricare le stringhe in memoria e' solo per evitare di far 
passare n MB di dati in rete tra applicazione che implementa l'algoritmo e 
db...cioe', le leggo tutte prima e sicuramente l'applicazione va piu' veloce 
(lan = collo di bottiglia)
pero' pero' mi avete messo la pulce nell'orecchio di implementare un 
algoritmo direttamente come stored procedure, solo che non ne ho 
eperienza... 

Ah, comunque grazie a tutti per l'interessamento!!! 

 (lan = collo di bottiglia)
Ovvero tutte le volte che fai una ricerca sul db fai passare in rete 
tutto il db? Stile access?
Mi sembra che ci sia un difetto di analisi.
-- 
Dr.Ugo Gagliardelli,Modena,ItalyCertifiedUindoscrasherAñejoAlcoolInside
Spaccamaroni andate a cagare/Spammers not welcome/Spammers vão à merda
Spamers iros a la mierda/Spamers allez vous faire foutre/Spammers loop
schijten/Spammers macht Euch vom Acker/Spamerzy wypierdalac'

 Mi sembra che ci sia un difetto di analisi.
Devo confrontare una stringa con TUTTE le stringhe presenti nel database...o 
le stringh del db vengono da me per farsi confrontare, o la stringa va al 
database per farsi confrontare...
la seconda opzione non sembra essere fattibile (mysql non espone metodi per 
trovare stringhe simili che io sappia) per cui le stringhe del db devono 
arrivare ad un algoritmo esterno, no?
Ora, all'avvio dell'applicazione si scaricano tutte le stringhe, e 
l'algoritmo effettua tutte le sue belle ricerchine....proprio per evitare 
che ogni volta che si devono fare dei confronti riscarico tutti i dati 
necessari dal db, no? (no, i dati non cambiano mai, e se cambiano deve 
essere resettata tutta l'applicazione) 


Ancora meglio, se vuoi usere più thread (e mi sembra un'ottima cosa), di 
una collection del package concurrent:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/package-summary.html
che hanno meno overhead nella gestione della sincronizzazione.
Oppure un meccanismo di lock stripping.

 Devo eseguire un algoritmo di string matching tra una stringa ed un array di 
Se non è un esercizio e ti serve per un progetto reale prova a cercare 
con goole "java full text search" in particolare se non ricordo male il 
progetto "Apache Lucene", si occupa di indicizzare i dati, e risponde in 
base ad una percentuale di "somiglianza" alla parola cercata, quindi 
credo che dovrebbe fare proprio al caso tuo.

ogni thread su un core? 
Non verrebbero necessariamente schedulati a questo modo. Tieni
presente che con una JVM ci sono sempre dei daemon thread che occupano
tempo CPU. Dovresti provare.


Prima cosa ringrazio tutti per gli aiutini...
ho fatto un poco di prove, ho trovato in 8 thread il minor tempo di 
esecuzione.... 

 che invece e' l'unica strada possibile)
Se il tuo database supporta funzioni definite dall'utente, potresti 
provare a implementare la distanza di Levensthein su tale funzione.
Per MySql ho trovato questo: 
http://codejanitor.com/wp/2007/02/10/levenshtein-distance-as-a-mysql-
stored-function/
Parlano addirittura di percentuali..dovrebbe fare al caso tuo.

 proposto.... 
Probabilmente non sono stato chiaro, ho scritto di fretta perché dovevo 
tornare subito al mio lavoro.
Leggiti questo che magari spiega meglio: 
http://en.wikipedia.org/wiki/Inverted_index
E poi cerca su internet questa cosa: "text indexing".
Di più non posso aiutarti perché ne so poco.
-- 
Andrea Francia
http://andreafrancia.blogspot.com/2008/07/colinux-linux-dentro-windows.html

il 17/10/2008 17.00, Scrive toto 43711712:

Io indicizzerei gli indirizzi su un motore di ricerca, tipo lucene, e 
farei le query su quello, proponendo all'utente i risultati piu' favorevoli.
Probabilmente e' piu' efficiente che confrontare centinaia di migliaia 
di stringhe, con risultati analoghi se non migliori.


 wrote:
<snip>
Ma non eri tu quello che raccomandava di quotare decentemente?


Mah, non saprei...adesso con circa 150.000 stringhe ritrovo quello ch mi 
serve in media in 500ms, il che e' buono...poi ho trovato il modo di ridurre 
il set di ricerca, dal milione e passa iniziale ha sub-set da max 200.000 
stringhe..
Ho dato un'occhiata a lucene, mi e' sembrato troppo "grande" per quello che 
serve a me....
Poi gli indici mi sembrano troppo "bloccati" e meno interpretativi rispetto 
ad un algoritmo, imho 


Io predico bene, mica razzolo bene ...
Di solito lo faccio solo quando trovo i messaggi top-quotati, o che non 
riportano i messaggi di risposta che sono i piu' difficili da leggere.


 
Cmq la prossima volta quoterň meglio, grazie della segnalazione.


 Per MySql ho trovato questo: 
IMHO Levenshein su quela mole di dati è troppo costoso. Oltretutto
un'implementazione in questo coso mi pare essere veramente poco
efficiente. Ogni volta che in C si farebbe un pointer dereference qua va
a chiamare una SUBSTRING. 
Bisogna capire *esattamente* cosa deve fare, ma in generale un O(mn)
sommato su qualche migliaio di m non è proprio un granchè. Potrebbe
provare qualcosa di fuzzy... che so, il bitap.
O davvero a quel punto meglio usare Lucene e non reinventare la ruota. 
Se invece deve solo cercare una stringa in un bloccazzo di altre
stringhe (quindi match esatto) ci sarebbero il classico
knuth-morris-pratt o il boyer-moore (bisogna vedere chi se la cava
meglio per gli input tipici). E si, Java dovrebbe cavarsela benone in
ambo i casi.
Ecco, complessivamente *io* farei in modo tale che all'utente vengono
presentate mano mano possibili scelte (di modo tale che in ogni momento
ci sia solo input valido -- o si sappia che l'input è invalido --).
Questo si fa efficientemente con una trie o qualcosa del genere.
In pratica si tratta solo di andare a cercare nelle varie stringhe a
disposizione una che abbia l'input per prefisso (e si propongono queste
come completamento). Appena meno efficiente ammettere anche match di
sottostringa al centro. 
Ammettere la cosa più generale (e quindi Levenshtein o bitap e simili)
potrebbe essere troppo costoso. Vale la pena comunque di andare ad
indagare negli algoritmi che usano in biologia per chiappare dna et
similia che dovrebbero gestire bene cose "simili" *e* match su dati
enormi. Io purtroppo non sono esperto in materia.
-- 
-riko

 serve a me....
In effetti é forse anche il migliore, prova a dare un'occhiata qui
http://en.wikipedia.org/wiki/List_of_search_engines
c'è n'e' una bella lista.



Gli algoritmi che mi hai suggerito mi sembra siano riferiti essenzialemente 
alla ricerca esatta, almeno di sottostringhe, o sbaglio?
Comunque mi hai fatto pensare che posso ridurre l'insieme nel quale vado a 
cercare le stringhe (che sono indirizzi stradali) dividendoli per localita', 
suggerendola all'utente per evitare errori in fase di inserimento della 
localita.
Ora sono sotto i 100 ms per ogni ricerca con algoritmi piu' costosi di 
Levenshtein, come QGrams 

 alla ricerca esatta, almeno di sottostringhe, o sbaglio?
Si. Per la maggior parte si. 
-- 
-riko