Ridurre al minimo l'archiviazione di sequenza mediante prefissi sovrapposti

Question

Oggi mi sono imbattuto in questo problema, e dopo un po 'di riflessione, io pensare Ho una soluzione in $ O (n^3) $, che è meglio di nessuna soluzione o un $ O (n!) $ Soluzione, ma la mia risposta non è ancora eccezionale. Puoi battere la mia migliore risposta?

L'impeto del mondo reale

Dato un insieme di dati $ C $ che consiste in non sovrapposizione, non vuoto, unico sequenze $ S_1, s_2, s_3, ... $ di valori atomici. Ogni sequenza tende ad avere molti valori ripetuti.

Ad esempio, nel codice in cui mi sono imbattuto nel problema, le sequenze erano inizialmente qualcosa del genere:

    9, 1, 1, 1, 1, 1;
    5, 5, 5, 3, 2;
    1, 1, 1, 1, 4;
    1, 7, 5, 5;
    4, 4, 4;
    ...

Per accedere ai dati, c'è una tabella secondaria di offset nei dati complessivi per mostrare dove inizia ogni sequenza: cioè sequenza $ S_1 $ inizia a 1, e $ S_2 $ a 7, e $ S_3 $ a 13 anni, e così via. Ma questo significa che il Le sequenze possono verificarsi in qualsiasi ordine, e possono anche sovrapposizione.

Dato che i dati potrebbero sovrapporsi, mi è venuto in mente che riordinando le sequenze, potrei ridurre la memoria richiesta. Ad esempio, nei dati di cui sopra, posso ridurre le dimensioni dell'archiviazione richiesta riordinando le sequenze come $ S_1, s_3, s_5; S_4, S_2 $:

    9, 1, 1, 1, 1, 1, 4, 4, 4;
    1, 7, 5, 5, 5, 3, 2;
    ...

Sovrapponendo i prefissi e i suffissi, possiamo archiviare 16 valori anziché l'originale 23, un notevole risparmio.

La dichiarazione del problema

Generalizzando questo, il problema, quindi, è trovare un algoritmo per ordinare un insieme arbitrario di sequenze, in modo che l'ordine risultante abbia il massimo Sovrapposizione complessiva dei prefissi e dei suffissi di tali sequenze.

(E per quello che vale, io no in realtà Devo risolverlo per il codice a cui stavo lavorando: questa è puramente una questione di interesse accademico a questo punto.)

La mia migliore risposta

È facile "vedere" una risposta ottimale per esempi banali come quello sopra, ma nel generale Caso di un gran numero di sequenze di valori arbitrari, diventa rapidamente. Un algoritmo avido potrebbe probabilmente dare almeno una risposta accettabile in tempo polinomiale, ma questa non sarebbe la vera risposta minima. E ovviamente, puoi semplicemente provare ogni possibile ordinamento, ma $ O (n!) $ Non è neanche una soluzione molto bella.

Mi è venuto in mente una possibile soluzione potrebbe esistere come variazione su un problema più longevo-through-a-ponderato. Consideri ogni sequenza $ S_1, s_2, s_3, ... $ come nodo in un grafico e costruisci un bordo diretto ovunque $ S_n $ ha un prefisso che corrisponda a un suffisso di $ S_m $ per tutti $ n $ e $ m $, ponderato dalla lunghezza della partita. Ciò si traduce in una soluzione in due fasi:

• Calcola tutti i pesi del bordo. I pesi del bordo possono essere calcolati banalmente in $ O (n^2) $, o forse anche dentro $ O (n) $ Utilizzando un trie costruito tramite programmazione dinamica.

• Quindi per ogni vertice, usa l'algoritmo più corto di Dijkstra (o simile), invertito, per trovare il percorso più lungo per quel vertice. Di tutti i percorsi più lunghi possibili, quindi prendi il più lungo. Questo è $ O (n^3) $, o forse $ O (n^2 log n) $ utilizzando code prioritarie.

io pensare Questo potrebbe funzionare, con un tempo complessivo di $ O (n^3) $ o forse $ O (n^2 log n) $, ma non ho tentato di dimostrarlo per il vero (o implementarlo). Potrebbe anche esserci una tecnica migliore dell'algoritmo di Dijkstra per "il percorso più lungo nel grafico quando non ti interessa quale nodo inizia o finisce".

Puoi fare di meglio?

Ecco di nuovo l'affermazione del problema:

Trova un algoritmo in grado di ordinare in modo efficiente un insieme di sequenze $ S_1, s_2, s_3, ... $ in modo tale che vi sia massima sovrapposizione globale dei loro prefissi e suffissi.

Buona fortuna; Sono curioso di vedere se riesci a risolverlo meglio di me!