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).