Newsgroup: it.comp.lang.c++
Titolo: PER CHI HA I COGLIONI ALLA "GRINGO"

// \/\//\\/E++
void message () {
DEDICATO A CHI HA TEMPO DA PERDERE!
(per gli altri... ELIMINATE il msg.)
Mi trovo in un bel pasticcio:
Mi hanno chiesto di realizzare un algoritmo di ricerca un po' particolare:
deve individuare in un testo (ma non solo) le sequenze di caratteri più
ripetute e più lunghe possibili, darmene il conto, e poi trovarne altre che
non includano le precedenti... è un po' difficle da spiegare, vi faccio un
esempio:
Questa è una stringa tipo:
abcdefgabcdefgababababababababcdefgabab
Ecco cosa mi dovrebbe trovare:
abab: è la stringa più lunga che comprende li stessi caratteri ripututa
almeno 2 volte, in questo caso 4 volte
La stringa dopo la ricerca è questa: non comprende più le stringhe già
trovate precedentemente...
abcdefgabcdefgcdefg
in questo caso abbiamo tre scelte:
ab = 2 volte
cd = 3v
ef = 3v
g = 3v
oppure
abcdefg = 2v
cdefg = 1v
oppure
ab = 2v
cdefg = 3v
Ecco: a me interessa che trovi il maggior numero possibile di stringhe
uguali, con il maggior numero di caratteri possibili, ed eviti assolutamente
di ripetere la stessa stringa una sola volta! (l'elaborazione darebbe il
terzo es.)
Vorrei evitare di fare diverse scansioni del testo in quanto l'algoritmo
dovrebbe essere il più veloce possibile in quanto deve operare su file di
diverse centinaia di mb!
Sono in alto mare...
ANNEGO! :-))
}
// \/\//\\/E++
// \/\//\\/E_SOFT '98
// 
wave...@freemail.org.mk
 (Permanent account)
// 
wav...@iol.it
 (Fast for really big files: more than 1/2mb!)
// 
members.xoom.com/wave_soft
// Mental-motion;
// Programmer and much more :-))

 diverse centinaia di mb!
uhmm... la vedo dura ;-)
In bocca al lupo
fabio
-- 
Cure the disease and kill the patient.
		-- Francis Bacon

cd = 3v
ecc ecc, insomma stai chiaramente contando anche ripetizioni non
adiacenti.
Sara` difficile, secondo me, che tu possa fare un trattamento
_deterministico_ su di un input di "centinaia di megabyte" per
risolvere con precisione questo problema.  Considera, infatti,
che, per identificare ripetizioni non-adiacenti, tu devi, a un certo
punto della scansione, avere l'elenco di tutte le sottostringhe
(di lunghezza >= 2) che si sono presentate *almeno una volta*
sino a quel punto, giusto "per il caso che" tornino a presentarsi.
Sicuramente potrai (e, penso, dovrai) ottimizzare il caso certo
piu` frequente, "sottostringhe viste una sola volta", ma anche
per tali sottostringhe dovrai pur almeno registrare punto di
partenza nella sequenza, e lunghezza; e, se vuoi evitare di
fare piu` passate sull'input, come puoi allora non registrare
anche la sequenza stessa?  Quindi: "centinaia di megabyte"
di memoria principale per la copia della sequenza; piu`, quando
hai letto N byte, avrai inoltre, almeno:
    una sequenza vista una sola volta di N byte, tutti quelli visti sinora
    due di N-1 byte ciascuna (da 0 a N-2, e da 1 a N-1)
    tre di N-2 byte ciascuna,
ecc, ecc, per un totale di almeno N/2 ("ben" che ti vada, cioe`
se tutte le sequenze piu` corte di N/2 puoi registrarle come
"ripetizioni"); ma 1+2+3+...+N/2 e` quadratico in N -- se N vale
"centinaia di milioni", stiamo parlando di un numero con almeno
una quindicina di zeri.  E dove la registri tutta 'sta roba...?!
Una prima approssimazione che penso ti sara` indispensabile,
per quando mostruosamente gigantesche siano le risorse di
calcolo a tua disposizione, e` dunque la seguente euristica: non
prendere neppure in considerazione le sequenze piu` lunghe di
X, per un qualche X "ragionevole".  Se questo non e` accettabile,
penso che il tuo problema sia dimostrabilmente insolubile entro
le risorse di calcolo attualmente disponibili sul pianeta Terra.
Se l'euristica e` accettabile, mi sembra (ma non ho dimostrato)
che il problema sia ancora quadratico in N; il numero di sequenze
candidate (<=X caratteri) infatti dovrebbe essere lineare in N, e
ogni nuovo carattere comportare un lavoro proporzionale al numero
di sequenze candidate.
Pero` puo` benissimo darsi che esistano ottimizzazioni che
rendono il problema sub-quadratico, e praticamente risolubile;
ad esempio, organizzando le "sequenze candidate" sulla base
del loro "prefisso" (vengono in mente i trie, ad esempio).
Forse puoi scomporre il problema in due parti: anzitutto, trovare
tutte le sequenze fra 2 e X caratteri ripetute almeno 2 volte
nell'input; poi, manipolare, per trovare le "sequenze lunghe molto
ripetute" che cerchi, il solo elenco di sequenze ripetute; se
scegli di evidenziare una data sequenza, l'elenco porta tutte le
informazioni che servono per togliere quelle "ripetizioni di altre
sequenze" che non sono piu` tali (in quanto parzialmente in
sovrapposizione con ripetizioni della sequenza che hai scelto
di "evidenziare"); anche qui, occorrera` una furba organizzazione
dei dati per evitare lavoro almeno quadratico -- e l'organizzazione
non ha nulla a che vedere con quella di cui potrai avere bisogno
per la prima parte, perche` qui il contenuto delle sequenze non ha
piu` importanza ai fini dell'ottimizzazione (mentre prima era l'unica
cosa che contasse) -- contano le posizioni delle ripetizioni, e le
lunghezze delle sequenze, per identificare sovrapposizioni.
Ecco, comunque, il programmino di prova che ho scritto, senza
troppe ottimizzazioni ne` complicazioni, per identificare le sequenze
ripetute (entro una certa lunghezza massima) ed emetterle in
ordine crescente di "fattore di merito".  Dacci un occhio, magari
c'e` qualche idea che puo` farti comodo... sarebbe simpatico che
tu ci chiarissi esattamente quale problema stai cercando di
risolvere con questo "orrendo algoritmo combinatorio", per due
ragioni: (1) ci hai ovviamente incuriosito, (2) le euristiche e le
ottimizzazioni che si possono applicare, i fattori di merito piu`
appropriati, ecc ecc, dipendono chiaramente dal problema...
//
// identifica ed emette le ripetizioni (di >= 2 volte), in una
// sequenza di input, di sottosequenze lunghe fra 2 e X
// caratteri (in questo esempio X==10), in ordine crescente
// di "merito" (lunghezza sottosequenza * numero ripetizioni).
//
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <list>
#include <string>
using namespace std;
class candidata {   // sequenza che stiamo accumulando come candidata a future ripetizioni
    vector<char> sequenza;    // caratteri sinora accumulati
    int indice;                             // indice entro sequenza
public:
    candidata() {} // dummy, x aggirare eventuali problemi del compilatore
    explicit candidata(int lunghezza):    // unico ctor veramente usato
        sequenza(lunghezza),
        indice(0)
    { }
    int len() const {        // accessore alla lunghezza
        return sequenza.size();
    }
    const vector<char>& getSequenza() const {    // accessore alla sequenza
        return sequenza;
    }
    // R true se ha finito di accumulare la sequenza
    bool accumula(char c) {
        sequenza[indice++] = c;
        return indice == sequenza.size();
    }
};
class confermata {  // sequenza gia` successa almeno una volta
    vector<char> sequenza;    // sequenza di caratteri (che si ripete)
    vector<int> partenze;         // indici di partenza della sequenza
    int indice_attuale;               // per verificare altre ripetizioni
public:
    confermata() {} // dummy, x aggirare eventuali problemi del compilatore
    confermata(const candidata& dati, int corrente):    // ctor davvero usato
        sequenza(dati.getSequenza()),
        indice_attuale(0)
    {
        aggiungi_partenza(corrente);
    }
    // i vari accessori
    int len() const {
        return sequenza.size();
    }
    int rep() const {
        return partenze.size();
    }
    int bonta() const {
        return len()*rep();
    }
    vector<int>::iterator begin() {
        return partenze.begin();
    }
    vector<int>::iterator end() {
        return partenze.end();
    }
    string testo() const {
        return string(sequenza.begin(), sequenza.end());
    }
    // mutatore quando si e` trovata una ripetizione
    void aggiungi_partenza(int corrente) {
        partenze.push_back(corrente-len());
    }
    // R true se e` appena terminata un'altra ripetizione
    bool accumula(char c) {
        if(c==sequenza[indice_attuale]) {
            ++indice_attuale;
            if(indice_attuale == len()) {
                indice_attuale = 0;
                return true;
            }
        } else {
            indice_attuale = 0;
        }
        return false;
    }
};
// operatore di confronto, per il sort delle sequenze-confermate
inline bool operator<(const confermata &a, const confermata &b)
{
    return a.bonta() < b.bonta();
}
// funtore di filtro, per togliere sequenze viste 1 sola volta
class pochevolte {
public:
    bool operator()(const confermata& x) const {
        return x.rep() < 2;
    }
};
// coordina la ricerca e l'emissione delle sequenze
class test_frame {
    vector<confermata> sequenze;
    list<candidata> nuove;
    int maxlen;
    int corrente;
public:
    test_frame(int maxlen): maxlen(maxlen), corrente(0) {}
    void nuovo_carattere(char c) {
        ++corrente;
        // registra le sequenze-confermate, di cui una ripetizione
        // e` stata confermata da questo carattere, per evitare di
        // "confermare" candidate gia` presenti con 1+ ripetizioni
        set<int> lunghezze_viste;
        // ciclo fra le sequenze gia` viste in passato
        vector<confermata>::iterator it = sequenze.begin();
        while(it != sequenze.end()) {
            if(it->accumula(c)) {
                // un'altra ripetizione, registriamola
                it->aggiungi_partenza(corrente);
                lunghezze_viste.insert(it->len());
            }
            ++it;
        }
        // ciclo fra le sequenze-candidate che sto accumulando
        list<candidata>::iterator jt = nuove.begin();
        while(jt != nuove.end()) {
            if(jt->accumula(c)) {
                // la candidata ha finito di accumulare caratteri
                set<int>::iterator dove;
                dove = lunghezze_viste.find(jt->len());
                if(dove == lunghezze_viste.end()) {
                    // e` una candidata *nuova*!
                    sequenze.push_back(confermata(*jt, corrente));
                }
                // comunque togliamola dalla lista delle candidate
                jt = nuove.erase(jt);
            } else {
                ++jt;
            }
        }
        // aggiunta di nuove sequenze-candidate
        for(int i=2; i<=maxlen; ++i) {
            nuove.push_back(candidata(i));
            nuove.back().accumula(c);
        }
    }
    // emissione dei risultati alla fine
    void finito() {
        // togliamo le sequenze viste 1 sola volta
        vector<confermata>::iterator ultimo =
            remove_if(sequenze.begin(), sequenze.end(), pochevolte());
        // sortiamo le altre
        sort(sequenze.begin(), ultimo);
        // ciclo di output dei risultati
        vector<confermata>::iterator it = sequenze.begin();
        while(it != ultimo) {
            cout<<"Len="<<it->len();
            cout<<" #r="<<it->rep();
            cout<<" ("<<it->testo()<<")";
            vector<int>::iterator jt = it->begin();
            while(jt != it->end()) {
                cout << ' ' << *jt;
                ++jt;
            }
            cout <<'\n';
            ++it;
        }
    }
};
int main(int argc, char* argv[])
{
    test_frame tf(10);
    const char* str="abcdefgabcdefgababababababababcdefgabab";
    if(argc>1)
        str = argv[1];
    int i = 0;
    while(str[i]) {
        tf.nuovo_carattere(str[i]);
        ++i;
    }
    tf.finito();
    return 0;
}
Alex

 diverse centinaia di mb!
Centinaia di mega? Stai lavorando su sequenze di DNA o cosa?
Comunque sia mi sembra che quello che vorresti fare possa essere
simile alle cose che si fanno sul DNA.....io ho provato a fare una
ricerca su altavista con "DNA sequence search" e le risposte sembrano
promettenti......mai inventare se si puo' copiare :)
In ogni caso mi sembra un bel casino.
Buona fortuna,
Alberto
-- 
Alberto BARSELLA
PGP fingerprint = 13 3F 22 D2 0B 0A D3 25  F1 89 FE B5 82 AD 75 2A
** Beliefs are dangerous. Beliefs allow the mind to stop functioning.
A non-functioning mind is clinically dead.  Believe in nothing... **

// \/\//\\/E++
void message () {
Credo che tu sia riuscito a comprendere meglio il mio probema! Essendo
sequenze anche non adiacenti DEVO sapere quali sono ripetute una sola volta!
Il bello viene qui!
Creando dei puntatori per memorizzare queste informazioni saturo la ram in
men che non si dica! Inoltre dovrei scannare il file diverse volte... e
scannare 100mb per 2/3 o più volte diventa MOSTRUOSAMENTE LUNGO!
Salvare nei file? IMPOSSIBILE, sarebbero altri file di cache da ri-scannare
e so' col disco fisso....
sblob...


scannare 100mb per 2/3 o più volte diventa MOSTRUOSAMENTE LUNGO!
128MB di memoria fisica, veloce, costano, IVAte, 390,000 lire; con circa
un milione si compra dunque 256MB di memoria fisica, e col resto che
avanza un paio di giga di spazio in piu` di buon disco veloce -- il che
rende molto meno spaventoso di una volta il problema di trattare 100Mb
di input: li tieni belli compatti sul disco veloce, te li mappi in memoria
virtuale, e con poche decine dei megabyte fisici a disposizione dovresti
trovarteli tranquilli nel tuo working set.
Purche` tu possa trovare algoritmi O(N), o al massimo NlogN, e NON
quadratici o peggio, il problema e` dunque potenzialmente trattabile;
se richiede algoritmi di costo quadratico o peggio, te lo scordi -- e`
allora, semplicemente, del tutto intrattabile.
Se il problema e` girare il tutto su di una macchina pesantemente
sottodimensionata, siamo egualmente al "puoi scordartelo"; al giorno
d'oggi, per un problema del genere, affrontarlo pensando di avere
meno di 256MB o 384MB di memoria fisica e` poco serio.
Con questo, e gli approcci che ti ho gia` suggerito, dovrebbe essere
possibile identificare sequenze ripetute sino ad una lunghezza
massima rispettabile, diciamo di qualche centinaio di simboli.
Puo` darsi che, sulla base di questa pre-analisi, sia anche poi
possibile in una seconda passata trovare, euristicamente, una
certa possibile varieta` di ripetizioni di sequenze piu` lunghe
ancora; escluderei la possibilita` di farlo deterministicamente (in
modo sub-quadratico e senza limitazione di lunghezza), ma, a
seconda del vero problema che stai cercando di risolvere (e che
continui a non dirci...), parecchie limitazioni euristiche possono
anche essere accettabili.  Ad esempio: se trovi tutte le
sequenze ripetute di lunghezza sino a 100, puoi poi esaminare
quelle di lunghezza esattamente 100, ripetute almeno N volte,
e con una grossa sovrapposizione fra loro, per trovare quelle
piu` lunghe che potrebbero comprenderle entrambe in overlap.
Alex

 Alex
Se il problema e' troppo "generico" rischia di essere davvero
intrattabile,
ma forse puo essere affrontato in maniera piu' efficiente un
sottoproblema piu' 
semplice. Ad esempio se si ha un alfabeto molto limitato (per esempio 4
caratteri 
invece di un centinaio) o ci interessano solo stringhe di una certa
lunghezza
(ad esempio da 5 a 100 caratteri) e' possibile usare dei "truccacci" per
ridurre
l'utilizzo delle risorse.
Ad esempio le stringhe di lunghezza cinque con un  alfabeto di quattro
caratteri sono
"solo" 4^5 = 1024. Quindi potrebbe essere ragionevole inserire in una
map (o altro 
container adatto) tutti gli "inizi" di sequenze e poi elaborare i
"seguiti" un gruppo
 alla volta, (ri)utilizzando magari un albero "quaternario".
Ovviamente un approccio del genere sarebbe assurdo se la stream di input
fosse la 
Divina Commedia, sarebbe invece molto indicato per una sequenza di DNA
;-)
Fabio
-- 
system-independent, adj.:
	Works equally poorly on all systems.

scusate, forse mi sono perso qualcosa, ma mi sembra che manchi ancora
una definizione FORMALE del problema... senza la quale non si può
neanche cominciare a parlarne. 
Cosa sono "le stringhe più lunghe"? La stringa totale (cioè l'input) è
la più lunga di tutte, e viene effettivamente "ripetuta" anche se 1 sola
volta (caso degenere, lo ammetto). nel caso invece si vogliano intendere
"almeno 2 istanze distinte della stessa sottostringa", consideriamo SOLO
quelle lunghe quanto la più lunga (se ce ne sono diverse) o c'è una
finestra ammissibile tipo "la più lunga è di 20, allora voglio trovare
le sottostringhe ripetute almeno 2 volte, lunghe da 18 a 20 caratteri"?
Persino un carattere singolo *E'* una sottostringa ripetuta (altro caso
degenere, lo riammetto...)
Se è come credo si può fare con una sola passata e senza troppi
problemi, certo il problema della memoria ci sarà sempre ma non si può
volere tutto...
riparliamone più "formalmente" (non per puntiglio accademico, ma perché
se qualcuno si è sbattuto sulla teoria dei linguaggi formali tanto vale
approfittarne, no? :)
ciao
S

;-)
Ce l'avete su con questa storia del DNA eh? EH? >>EH??<<
E' un algoritmo di ricerca... non vi posso dire altro ;-) Mi appello alla
legge della privacy!
Comunque, come al solito, non sono SOLO 4 caratteri, ma il set completo e
l'esteso dei caratteri ascii! Sarebbe stato troppo bello. In ogni caso
dovrebbe funzionare ANCHE sui testi tipo la divina commedia! E non è finita,
se possibile anche sui file binari! Ma forse quello che stai dicendo non è
sbagliato, forse converrebbe davvero ridurre il numero dei caratteri a 4/5,
ma sarebbe un'altro algoritmo dell'algoritmo!
Tutto sommato però ci potrei guadagnare in semplicità... fatemi riflettere:
stream o non stream, questo è il problema! =-))
