[Algoritmi] Domanda su compressione LZW

[minavagante1]

Ciao a tutti,
date queste stringhe d'ingresso devo scrivere la sequenza di codici in uscita e il contenuto della tabella dato l'ingresso di questi valori numerici scritti su 8 bit:
11,137,11,137,250,11,137,250,11,137
Come scrivo la tabella e i codici e l'uscita??
Grazie a tutti

[apatriarca]

Se ti è stato dato questo esercizio immagino ti abbiano mostrato un esempio del funzionamento dell'algoritmo. Comunque se non ricordo male dovrebbe funzionare nel modo seguente:

Stringa letta: 11
Commento: 11 è già contenuto nella tabella (viene normalmente inizializzata con tutti i singoli caratteri).
Output:
Tabella (oltre ai singoli caratteri di base): {}

Stringa letta: 11, 137
Commento: [11, 137] non è contenuto nella tabella, viene visualizzato il codice per il primo carattere, aggiunta la stringa [11, 137] nella tabella e si considera la stringa che inizia con 137
Output: 11
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137]}

Stringa letta: 11, 137, 11
Commento: [137, 11] non è contenuto nella tabella, viene visualizzato il codice per il primo carattere, aggiunta la stringa [137, 11] nella tabella e si considera la stringa che inizia con 11
Output: 11, 137
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11]}

Stringa letta: 11, 137, 11, 137
Commento: [11, 137] è contenuto nella tabella e si prosegue a leggere caratteri
Output: 11, 137
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11]}

Stringa letta: 11, 137, 11, 137, 250
Commento: [11, 137, 250] non è contenuto nella tabella, si aggiunge alla tabella e si visualizza il codice per il prefisso
Output: 11, 137, 256
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11], 258 = [11, 137, 250]}

Stringa letta: 11, 137, 11, 137, 250, 11
Commento: [250, 11] non è contenuto nella tabella
Output: 11, 137, 256, 250
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11], 258 = [11, 137, 250], 259 = [250, 11]}

Stringa letta: 11, 137, 11, 137, 250, 11, 137
Commento: [11, 137] è contenuto nella tabella
Output: 11, 137, 256, 250
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11], 258 = [11, 137, 250], 259 = [250, 11]}

Stringa letta: 11, 137, 11, 137, 250, 11, 137, 250
Commento: [11, 137, 250] è contenuto nella tabella
Output: 11, 137, 256, 250
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11], 258 = [11, 137, 250], 259 = [250, 11]}

Stringa letta: 11, 137, 11, 137, 250, 11, 137, 250, 11
Commento: [11, 137, 250, 11] non è contenuto nella tabella
Output: 11, 137, 256, 250, 258
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11], 258 = [11, 137, 250], 259 = [250, 11], 260 = [11, 137, 250, 11]}

Stringa letta: 11, 137, 11, 137, 250, 11, 137, 250, 11, 137
Commento: [11, 137] è contenuto nella tabella e la stringa è completa
Output: 11, 137, 256, 250, 258, 256
Tabella (oltre ai singoli caratteri di base): {256 = [11, 137], 257 = [137, 11], 258 = [11, 137, 250], 259 = [250, 11], 260 = [11, 137, 250, 11]}

Dovrebbe essere corretto. Ma non l'ho controllato.

[minavagante1]

ciao,
innanzitutto grazie della risposta e della disponibilità, ma non ho capito in base a cosa vengano scelti i caratteri da inserire nella tabella e gli output. Ad esempio per i caratteri, ho capito che vengono inserite nuove stringhe se ancora non si sono presentate, ma in questa situazione:
11,137,11,137,250 ad esempio perchè la stringa nuova inserita nella tabella è 11,137,250 e non ad esempio 137,250 che ancora non compare oppure anche la stringa intera??
Gli output non ho veramente capito in base a cosa vengano inseriti

[apatriarca]

Ad ogni turno viene mantenuta una stringa già contenuta nella tabella (che chiamo ad esempio w) e un nuovo carattere letto (che chiamo c). Allora se w + c non è ancora contenuto nella tabella lo aggiungo, visualizzo il codice per w e setto w = c. In caso contrario aggiorno w = w + c

[minavagante1]

mmmm
ma con c intendi il carattere che leggo??
Allora io ricevo 11, è già contenuto. Ricevo 137, quindi ho 11,137 che è nuovo e lo vado ad inserire nella tabella. Quando ricevo il secondo 11, quindi ricevo 11,137,11 perchè non inserisco 11,137,11 nella tabella???

[apatriarca]

Perché quando inserisco una nuova stringa nella tabella considero solo il nuovo carattere letto come parte della stringa w. Se cerchi con google troverai comunque parecchie descrizione dell'algoritmo con esempi.

[minavagante1]

Ora ho capito finalemente
Grazie mille