Newsgroup: it.comp.lang.visual-basic
Titolo: Algoritmo di string match su stringhe lunghe lunghe

Ciao a tutti, rinnovo la mia richiesta...
nessuno di voi ha per caso sviluppato un algoritmo per calcolare il match di
due stringhe lunghe? (per lunghe intendo sui 10000 caratteri al massimo...)
Io ho trovato in giro Levhenstein Distance, edit Distance, ma vanno tutti in
memoria e come si discuteva con Albe utilizzando l'implementazione standard
di quegli algoritmi mi serve un pc con un tera di ram...
Grassie!
-- 
Stay Cool, Stay Free, and then You will see.
It's Best to Stay Mellow!
http://www.assandshirt.com
Venerate anche voi il dio Flying Spaghetti Monster, andate su
http://www.venganza.org

 di quegli algoritmi mi serve un pc con un tera di ram...
Puoi postarmi la vostra discussione .. non l'ho seguita .. e sarei 
interessato a questa discussione ... visto che mi servirebbe poter 
trattare stringhe .. e operazioni su di esse :)
-- 
                                  [CapoBecchino]
| --------------------------------------------- |
| hotmail/msn: capobecchino [@] hotmail [.] com |
| yahoo: capo_becchino [@] yahoo [.] it         |
| icq: 217325174                                |
| --------------------------------------------- |
!!! SODDISFATTI O RIMBORSATI !!!
Nessuno si è mai lamentato della nostra offerta 2x1. Morire in 2 e 
pagare per 1.

 di quegli algoritmi mi serve un pc con un tera di ram...
In realtà non sapevo quale fosse la tua necessità.
Cioè, tu avevi due array di long da 50.000 elementi, e volevi costruire 
una matrice dei due array, per cui avevi 10GB di richiesta Ram.
Ma per i due array monodimensionali, o se scendi a 10.000 elementi, o 
meglio ancora se passi da long a byte (che per i caratteri non unicode 
va benissimo), riduci di tanto la necessità, al punto da riuscire a 
stare dentro i 4GB e quindi riuscire a fare girare tutto.
Parallelamente, potresti anche tentare di studiare le potenzialità text 
di strumenti dbms come Sql-Server, che offrono tante cose già pronte e 
particolarmente efficienti (beh, ci vuole comunque un certo server, 
mica un symbian...).
Ciao
Alberto
-- 
Si è visto di meglio,
ma si è scopato di peggio,
qualche volta a pago
e non erano neanche sempre donne
[Paolo]

Ciao, la questione non si era dilungata di molto:
Sul 
http://www.merriampark.com/ld.htm
 ci sono alcuni esempi (VB,JAVA,C) per
il calcolo della Distanza di Levenshtein.
Queste funzioni funzionano (:-|) solo con stringhe corte (corte per me - ho
provato con 1000 caratteri e andava ancora).
Un brandello di codice dalla pagina:
Public Function LD(ByVal s As String, ByVal t As String) As Integer
Dim d() As Integer ' matrix
Dim m As Integer ' length of t
Dim n As Integer ' length of s
Dim i As Integer ' iterates through s
Dim j As Integer ' iterates through t
Dim s_i As String ' ith character of s
Dim t_j As String ' jth character of t
Dim cost As Integer ' cost
 
  ' Step 1
 
  n = Len(s)
  m = Len(t)
  If n = 0 Then
    LD = m
    Exit Function
  End If 
  If m = 0 Then
    LD = n
    Exit Function
  End If 
  ReDim d(0 To n, 0 To m) As Integer
Guardando l'ultima riga, viene dimesionato un vettore 2D
come vedi n e m sono il valore della lunghezza delle strighe che si vogliono
confrontare.
Supponendo di avere n=30000 e m=20000
30.000 * 20.000 = 600.000.000
Dato che un intero sono 4 byte
600.000.000 * 4 = 2.400.000.000 byte (Circa 2,3 GB)
Comunque, ache utilizzando stringhe più corte (2000 caratteri), il calcolo
della distanza risulta lento, lento... lento!
Questo era il sugo della discussione...


 mica un symbian...).
Ci avevo pensato, solo che la strada non è praticabile... purtroppo (o per
fortuna) la scelta del dbms è caduta su mysql, che non ha funzioni per la
manipolazione delle stringhe...
Cazzu Cazzu IU IU!


 
-- 
                                  [CapoBecchino]
| --------------------------------------------- |
| hotmail/msn: capobecchino [@] hotmail [.] com |
| yahoo: capo_becchino [@] yahoo [.] it         |
| icq: 217325174                                |
| --------------------------------------------- |
!!! OFFERTA IRRIPETIBILE !!!
Muori oggi avrai uno sconto del 50%.

 manipolazione delle stringhe...
Sono curioso di capire dove stia la 'fortuna'.
MySql in produzione non è gratuito (MSDE sì), quanto a performance c'è 
pochissima differenza (dovuta comunque al fatto di una minore 
ridondanza della gestione degli accessi al disco, con conseguente 
minore affidabilità a fronte dei crash), i provider disponibili sono 
pochi e obsoleti (l'unico provider serio è addirittura un ODBC), 
l'amministrazione è sicuramente più complessa e meno intuitiva, i NG di 
supporto sono tristissimi e sicuramente valgono zero rispetto a quelli 
disponibili per Sql-Server.
Nel tuo caso specifico, poi, dove manipoli grossi testi, le 
funzionalità Text di Sql-Server ti sarebbero servite immensamente.


> Sono curioso di capire dove stia la 'fortuna'.
Semplicemente che MSDE non gira su linux ... siccome di server linux ne ho
in giro un po'... magari il dbms lo mettiamo su linuz... tutto qua.



Magari osservando la "alegbra" di tali funzioni.... forsi trovi un algoritmo 
di calcolo distanza stringhe che rispetta la proprietà associativa del tipo:
F(s) = F(Left(s,Len(s)\2)) + F(Right(s,Len(s)\2))
e puoi dividere l'algoritmo fino ad ottenere una divisione di stringhe 
accettabili in termini di compromesso ram/velocità....
????
Adesso riguardo il post e mi ristudio la definizione di String Match 
Score... in base a quella forse si può creare qualcosa di semplice....
Ti serve proprio il risultato esatto del String Match Score? O è solo un 
valore indicativo per optare una scelta?
Perché in questo caso potresti fare un preanalizzatore che lavora sulle 
stringhe lunghe e decide se è il caso di calcolare il valore... se è il caso 
magari elimina anche la parte di stringhe in cui non c'è bisgono di 
calcolare il valore e memorizza distanza 0 * la percentuale di stringa 
scartata...
Magari ho detto solo un mucchio di sciocchezze... magari no... sappimi dire 
se ti sono stato
d'aiuto...
Riccardo 

 valore indicativo per optare una scelta?
Diciamo che, per il mio scopo, lo score serve per optare una scelta: se le
stringhe differiscono di [tot], allora le considero diverse, altrimenti
fingo che siano uguali...
spero di essermi spiegato correttamente visto che torno da un pranzo un po'
alcolico...


 Grassie!
nel sito dove hai trovato l'algoritmo in VB c'e' questo:
# Chas Emerick has written an implementation in Java, which avoids an 
OutOfMemoryError which can occur when my Java implementation is used 
with very large strings.
che ti manda qui: 
http://www.merriampark.com/ldjava.htm
c'e' lo stessto algoritmo che pero' usa *solo* 3 vettori uguali
e' in java ma puoi tradurlo!
bye
r

Grazie Nerone, ho dato un'occhiata e ho già tradotto:
Private Function Minimum(ByVal a As Long, _
                         ByVal b As Long, _
                         ByVal c As Long) As Long
Dim mi As Long
 
  mi = a
  If b < mi Then
    mi = b
  End If
  If c < mi Then
    mi = c
  End If
 
  Minimum = mi
 
End Function
Function LD(ByVal s As String, ByVal t As String) As Long
    Dim n, m, i, j, cost As Long
    Dim p() As Long
    Dim d() As Long
    Dim dd() As Long
    Dim t_j As String
    n = Len(s)
    m = Len(t)
    If n = 0 Then
        LD = m
        Exit Function
    Else
        If m = 0 Then
            LD = n
            Exit Function
        End If
    End If
 
    ReDim p(n + 1)
    ReDim d(n + 1)
    For i = 0 To n
        p(n) = i
    Next
 
    For j = 1 To m
        t_j = Mid(t, j, 1)
        ReDim d(0)
        d(0) = j
 
        For i = 1 To n
            If Mid(s, i, 1) = t_j Then cost = 0 Else cost = 1
            ReDim Preserve d(i)
            d(i) = Minimum(d(i - 1) + 1, p(i) + 1, p(i - 1) + cost)
        Next
 
        dd = p
        p = d
        d = dd
    Next
 
    LD = p(n)
End Function
Ora non schianta +, però è lento (72 secondi su due stringhe di 6000
caratteri)...
Se si potesse ottimizzare...


Adorno Scagaceto ha scritto:

Mi posti anche le stringhe che hai usato .. cosi lo provo e vediamo .. :)


 
Beh, ho fatto un progetto con 2 textbox multiline e ci incollavo di volta in
volta stringhe diverse, poi cambiavo qualche letterina qua e là nella
seconda stringa.
devo zippare e metterlo da qualche parte?


 
yes .. mandalo tranquillamente a e.scognamillo [@] marcorelations [.] it
-- 
                                  [CapoBecchino]
| --------------------------------------------- |
| hotmail/msn: capobecchino [@] hotmail [.] com |
| yahoo: capo_becchino [@] yahoo [.] it         |
| icq: 217325174                                |
| --------------------------------------------- |
!!! SODDISFATTI O RIMBORSATI !!!


 
come inizio io farei:
         ReDim d(n) As Long
         d(0) = j
         For i = 1 To n
             If Mid(s, i, 1) = t_j Then cost = 0 Else cost = 1
             ''''''ReDim Preserve d(i)
perche redim preserve e' un po lento ;-)
magari ci sono altre cose ma questa e' la prima che vedo.
bye
r

Per tutti il progetto di test è qua:
http://www.assandshirt.com/projects/testld.zip
Ciao!


Allora ecco eventuali ottimizzazioni al codice che gia hai .. :)
Nel primo for questo
[CODE]
  For j = 1 To m
         RaiseEvent OnProgress(j, m)
         t_j = Mid(t, j, 1)
         'ReDim d(0) <- č inutile visto che tanto viene ricalcolato ogni 
volta
[/CODE]
nel secondo for
[CODE]
    If Mid(s, i, 1) = t_j Then cost = 0 Else cost = 1
             'ReDim Preserve d(i) <- Anche qui č inutile, in quanto č 
gia stata dimensionata su ed n non cambia mai.
[/CODE]
Nello swap degli array
[CODE]
   'dd = p <---|
    p = d      |--- Sono inutili in quanto d verrą sempre ricalcolata e 
               |    quindi eliminata
   'd = dd <---|
[/CODE]
Spero di esserti stato un po di aiuto ..
sul mio P4 3,2 1 gb ram con il tuo una stinga di 6000 caratteri, con la 
differenza di 1 solo carattere alla fine impiegava 57 secondi con le mie 
ottimizzazioni 44
-- 
                                  [CapoBecchino]
| --------------------------------------------- |
| hotmail/msn: capobecchino [@] hotmail [.] com |
| yahoo: capo_becchino [@] yahoo [.] it         |
| icq: 217325174                                |
| --------------------------------------------- |
!!! OFFERTA IRRIPETIBILE !!!


Grazie 1000 a tutti ragazzi...
adesso proverò a tradurre in C e a ficcarlo in una dll... magari guadagno
qualche secondo ancora... :-)
