Ricerca di prefissi comuni per un set di stringhe

Question

Ricerca di prefissi comuni per un set di stringhe

#1 da (3 voti)
#2 da (-2 voti)

2

Sto cercando di trovare prefissi comuni per un insieme ordinato di stringhe. Ad esempio, se vengono fornite le seguenti stringhe:

AB123456
AB123457
ABCDEFGH
ABCDEFGX1
ABCDEFGY
XXXX

allora la mia funzione dovrebbe restituire tre prefissi e i loro suffissi:

AB12345  6,7
ABCDEFG  H,X1,Y
XXXX     (no suffixes)

Alcune informazioni di base: sto provando a comprimere una grande quantità di stringhe ordinate. Un'implementazione tradizionale della compressione del prefisso memorizzerebbe semplicemente la differenza di ogni stringa con la stringa precedente. Ciò non consente inserimenti o ricerche casuali veloci, poiché tutte le stringhe precedenti devono essere prima decompresse. Ecco perché voglio trovare prefissi comuni. Ogni stringa memorizzerà la differenza con questo prefisso comune. Quindi ottengo un rapido accesso casuale per il costo di alcuni byte aggiuntivi (rispetto all'implementazione tradizionale).

Non ho ancora una buona idea di come implementarlo. Nei miei sogni immagino una finestra che scivoli sul flusso di input, cercando di trovare il miglior risultato. Questo odora di programmazione dinamica, un argomento con cui non sono stato in contatto dall'università (molto tempo fa).

Se, tuttavia, il calcolo del risultato "migliore" risulta estremamente intensivo in termini di prestazioni, sono disposto a utilizzare il secondo risultato migliore. Le prestazioni sono importanti.

EDIT: Dopo aver letto le prime poche risposte, capisco che forse la mia domanda non è stata sufficientemente precisa. Forse posso riformularlo un po ':

Sto cercando il costo più basso (= utilizzo dello spazio minimo) in un grafico. Il grafico inizia con un insieme ordinato di stringhe univoche. (Non sono compressi e quindi richiedono lo spazio massimo.) Ora voglio trovare prefissi comuni delle stringhe, in modo che lo spazio utilizzato possa essere ridotto. Dovrebbe esserci un solo livello di prefissi, cioè nessuna gerarchia di prefissi (come sarebbe assunta in un trie).

algorithms computer-science trie dynamic-programming

posta cruppstahl 09.11.2014 - 22:45

fonte

2 risposte

Leggi altre domande sui tag algorithms computer-science trie dynamic-programming

Entity Framework Code Prima implementazione del database centralizzata DDD: memorizzazione di dati aggiuntivi con il modello

score 3 · Answer 1

Vuoi memorizzare stringhe in forma compressa (per risparmiare spazio, immagino), ma vuoi una ricerca veloce, vero? Se fossi in te, andrei per la velocità e userei un trie (per il primo pochi personaggi). Ha la ricerca O (log n) e condenserà automaticamente i prefissi comuni.

Molto dipende dalle statistiche delle stringhe, come quante ce ne sono e dalla loro lunghezza tipica.

AGGIUNTO: per le stringhe che hai dato, il trie avrebbe avuto questo aspetto:

- A B - 1 2 3 4 5 - 6 .
  |     |           |
  |     |           7 .
  |     |           
  |     C D E F G - H .
  |                 |
  |                 X 1 .
  |                 |
  |                 Y .
  |
  X X X X .

Ogni nodo del trie contiene un piccolo "dizionario" di "parole", inizialmente lungo 1 lettera, e ogni "parola" punta a un sub-nodo. Se quel sottonodo contiene solo una "parola" nel proprio "dizionario", allora quella "parola" può essere assorbita nella "parola" del suo genitore, ed è così che si costruiscono i prefissi.

score -2 · Answer 2

-2

Dovresti essere in grado di usare una sottostringa della stringa che vuoi controllare a meno che la lunghezza del prefisso non vari. Puoi usare un'istruzione if per assicurarti che la stringa sia sufficientemente lunga da avere il prefisso.

risposta data 10.11.2014 - 02:53

fonte