ejemplos_bs_mtf.txt

   1
   2
   3
   4 Los siguientes son algunos de los ejemplos dados en la clase práctica 20040531
   5 Los mismos no reemplazan a la explicación; son publicados únicamente con el objeto de evitar la necesidad de copiar los ejemplos en clase.
   6
   7 ----------------------------------------------------------------
   8
   9 1) El proceso es:
  10
  11 Datos originales --BS--> D' --MTF--> D'' ---Compresión Aritmética---> Datos comprimidos
  12
  13 ----------------------------------------------------------------
  14
  15 2) Ejemplo de Block Sort
  16
  17
  18 Datos originales: ABRACADABRA
  19
  20 Generamos las rotaciones:
  21
  22 ABRACADABRA
  23 BRACADABRAA
  24 RACADABRAAB
  25 ACADABRAABR
  26 CADABRAABRA
  27 ADABRAABRAC
  28 DABRAABRACA
  29 ABRAABRACAD
  30 BRAABRACADA
  31 RAABRACADAB
  32 AABRACADABR
  33
  34 Las ordenamos lexicográficamente:
  35
  36 AABRACADABR
  37 ABRAABRACAD
  38 ABRACADABRA
  39 ACADABRAABR
  40 ADABRAABRAC
  41 BRAABRACADA
  42 BRACADABRAA
  43 CADABRAABRA
  44 DABRAABRACA
  45 RAABRACADAB
  46 RACADABRAAB
  47
  48 Nos quedamos con la última columna:
  49
  50 V = RDARCAAAABB
  51
  52 Determinamos cuál de las rotaciones es la original:
  53
  54 K = 3
  55
  56 Resultado del algoritmo BlockSort:
  57 * V = RDARCAAAABB
  58 * K = 3
  59
  60
  61 ----------------------------------------------------------------
  62
  63
  64 3) Inversa del BlockSort:
  65
  66 Datos:
  67 * V = RDARCAAAABB
  68 * K = 3
  69
  70 Numeramos los elementos del vector V:
  71
  72 1   2   3   4   5   6   7   8   9  10  11
  73 R   D   A   R   C   A   A   A   A   B   B
  74
  75 Ahora ordenamos el vector V arrastrando también al orden los números:
  76
  77 3   6   7   8   9  10  11   5   2   1   4   // orden original
  78 A   A   A   A   A   B   B   C   D   R   R   // elementos ordenados
  79
  80 A continuación volvemos a numerar los elementos del V ordenado:
  81
  82 1   2   3   4   5   6   7   8   9  10  11   // nuevo orden
  83 3   6   7   8   9  10  11   5   2   1   4   // orden original
  84 A   A   A   A   A   B   B   C   D   R   R   // elementos ordenados
  85
  86 Luego empezamos por el elemento que tiene el número K en el nuevo orden. Lo emitimos, y el siguiente será el indicado por el número viejo del elemento emitido.
  87
  88 K = 3
  89
  90 Emitimos A, siguiente = 7
  91 Emitimos B, siguiente = 11
  92 Emitimos R, siguiente = 4
  93 Emitimos A, siguiente = 8
  94 Emitimos C, siguiente = 5
  95 Emitimos A, siguiente = 9
  96 Emitimos D, siguiente = 2
  97 Emitimos A, siguiente = 6
  98 Emitimos B, siguiente = 10
  99 Emitimos R, siguiente = 1
 100 Emitimos A, siguiente = 3 (3 era el original => fin)
 101
 102 Resultado: ABRACADABRA
 103
 104 ----------------------------------------------------------------
 105
 106
 107 4) Ejemplo de MTF
 108
 109 Datos originales:
 110
 111 RDARCAAAABB
 112
 113 Vector Z original: ABCDR
 114 (todos los caracteres posibles)
 115
 116 ABCDR //datos del vector Z
 117 01234 //numeración de las posiciones (empezamos del cero)
 118
 119 Dato  Emitimos  El vector Z queda:
 120  R      4           RABCD
 121  D      4           DRABC
 122  A      2           ADRBC
 123  R      2           RADBC
 124  C      4           CRADB
 125  A      2           ACRDB
 126  A      0             =
 127  A      0             =
 128  A      0             =
 129  B      4           BACRD
 130  B      0             =
 131
 132
 133 Resultado del algoritmo MTF:
 134 4 4 2 2 4 2 0 0 0 4 0
 135
 136
 137 ----------------------------------------------------------------
 138
 139
 140 5) Inversa del MTF:
 141
 142 Dato:
 143 4 4 2 2 4 2 0 0 0 4 0
 144
 145 Vector Z original:
 146 ABCDR
 147
 148 Dato  Emitimos  El vector Z queda:
 149  4      R           RABCD
 150  4      D           DRABC
 151  2      A           ADRBC
 152  2      R           RADBC
 153  4      C           CRADB
 154  2      A           ACRDB
 155  0      A             =
 156  0      A             =
 157  0      A             =
 158  4      B           BACRD
 159  0      B             =
 160
 161
 162 Resultado:
 163 RDARCAAAABB
 164
 165
 166
 167
 168
 169
 170
 171
 172
 173
 174
 175
 176
 177
 178
 179