Trova la sottostringa del prefisso che offre la migliore compressione

Question

Problema:

Dato un elenco di stringhe, trova la sottostringa che, se sottratta dall'inizio di tutte le stringhe in cui corrisponde e sostituita da un byte di escape, fornisce la lunghezza totale più breve.

Esempio:

" foo " , " fool " , "bar"

Il risultato è: " foo " come stringa di base con le stringhe " \ 0 " , " \ 0l " , " bar " e una lunghezza totale di 9 byte. " \ 0 " è il byte di escape. La somma della lunghezza delle stringhe originali è 10, quindi in questo caso abbiamo salvato solo un byte.

Un algoritmo ingenuo sarebbe simile a:

for string in list
  for i = 1, i < length of string
      calculate total length based on prefix of string[0..i]
      if better than last best, save it
return the best prefix

Questo ci darà la risposta, ma è qualcosa come O ((n * m) ^ 2), che è troppo costoso.

Answer 1

Usa una foresta di alberi prefissi (trie) ...

  f_2    b_1
 /       |
 o_2     a_1
 |       |
 o_2     r_1
 |
 l_1

quindi, possiamo trovare il risultato migliore e garantirlo massimizzando (profondità * frequenza) che verrà sostituito con il tuo carattere di escape. È possibile ottimizzare la ricerca eseguendo prima una ricerca per diramazione e profondità per il massimo.

Sulla complessità: O (C), come menzionato nel commento, per costruirlo e per trovare l'ottimale, dipende. Se ordini la frequenza dei primi elementi (O (A) - dove A è la dimensione dell'alfabeto delle lingue), allora sarai in grado di ritagliare più rami e avere buone probabilità di ottenere un tempo sub-lineare.

Penso che sia chiaro, non ho intenzione di scriverlo - cos'è un compito a casa? ;)

Answer 2

Proverei a iniziare ordinando l'elenco. Quindi vai semplicemente da una stringa all'altra confrontando il primo carattere con il primo carattere della stringa successiva. Una volta che hai una partita, guarderesti il ??prossimo personaggio. Dovresti escogitare un modo per tracciare il miglior risultato finora.

Answer 3

Bene, il primo passo sarebbe quello di ordinare l'elenco. Quindi si passa attraverso l'elenco, confrontando ciascun elemento con il precedente, tenendo traccia delle più lunghe corse di 2 caratteri, 3 caratteri, 4 caratteri ecc. Quindi la figura mostra i 20 prefissi di 3 caratteri migliori dei 15 prefissi di 4 caratteri.