From 66f873a3de4adb65bbad6fb09cd57272216d332f Mon Sep 17 00:00:00 2001
From: Ricardo Markiewicz <gazer.arg@gmail.com>
Date: Mon, 28 Jun 2004 06:38:27 +0000
Subject: [PATCH]  Subo BS (Merge con exito!)

---
 doc/InformeTP3.lyx | 138 ++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 137 insertions(+), 1 deletion(-)

diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx
index 18a17ec..2978894 100644
--- a/doc/InformeTP3.lyx
+++ b/doc/InformeTP3.lyx
@@ -411,6 +411,143 @@ Especificaciones
 \layout Subsection
 
 Block Sorting
+\layout Standard
+
+La técnica de Block Sorting
+\begin_inset Foot
+collapsed true
+
+\layout Standard
+
+desde ahora lo llamaremos BS, para minimizar la notación.
+\end_inset 
+
+ tiene su principal desventaja en que es un algoritmo que consume muchos
+ recursos, y para ser una solución práctica debe ser trabajada para dar
+ resultados coherentes.
+\layout Standard
+
+En una implementación simple, el BS debe crear una matriz y crear todos
+ los desplazamientos sobre ella.
+ Esto hace que se necesito O(n^2) en memoria, donde n es la longitud del
+ vector sobre el cual se quiere operar.
+ Claramente es un problema, ya que para una página pequeña, digamos 1kb,
+ se necesita una matriz de 1Mb.
+\layout Standard
+
+El otro problema es el tiempo de ordenamiento de los desplazamientos, que
+ debe ser lo menor posible.
+ Una posibiliad es utilizar un método de ordenamiento de bajo órden, como
+ el Quick Sort
+\begin_inset Foot
+collapsed true
+
+\layout Standard
+
+Se ha optado por utilizar el qsort de la libc por ser ANSI-C y tener una
+ técnica de selección del pivot aceptable.
+\end_inset 
+
+ utilizado en esta implementación.
+ Otra posible opción hubiera sido el Heap Sort, pero dada la complejidad
+ de su implementación no se creyó que diera una mejora factible y suficiente
+ apreciable como para implementarlo.
+\layout Standard
+
+Como última opción se estudió el Radix Sort, ya que justamente nuestro dato
+ a ordenar es de longitud fija n y se cuenta con un conjunto de L=255 elementos
+ posibles a aparecer en el dato.
+ El orden de éste método sería O(n*L), pero para que realmente el Radix
+ Sort sea efectivo, se requiere que L < log2(n) = 15, por lo que no convenía
+ tampoco.
+\layout Standard
+
+Para solucionar el problema del consumo de memoria se plateó un esquema
+ como el que se indica a continuación :
+\layout LyX-Code
+
+                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 
+\layout LyX-Code
+
+Dato            | | | | | | | | | | | | | | | | | | | | | | | | | |
+\layout LyX-Code
+
+                +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+\layout LyX-Code
+
+                 ^ ^                                             ^
+\layout LyX-Code
+
+Desplazamientos  | |                                             |
+\layout LyX-Code
+
+     +-+         | |                                             |
+\layout LyX-Code
+
+     | |---------+ |                                             |
+\layout LyX-Code
+
+     +-+           |                                             |
+\layout LyX-Code
+
+     | |-----------+                                             |
+\layout LyX-Code
+
+     +-+                                                         |
+\layout LyX-Code
+
+     
+\backslash 
+/
+\backslash 
+                                                         |
+\layout LyX-Code
+
+     +-+                                                         |
+\layout LyX-Code
+
+     | |---------------------------------------------------------+
+\layout LyX-Code
+
+     +-+
+\layout Standard
+
+El vector desplazamiento es una estructura de control que almacena :
+\layout Itemize
+
+La posición inicial de la palabra desplazada i en el Dato
+\layout Itemize
+
+La posición final de la palabra desplazada en el Dato ( se calcula como
+ (pos_inicial+n-1)%n)
+\layout Standard
+
+La ganancia de este método es que se utilizan 2*n bytes de memoria solamente,
+ es decir, que se bajo a O(n) el orden en memoria del algoritmo.
+\layout Standard
+
+Luego de inicializar el vector Desplazamiento (esta parte es O(n) en tiempo)
+ se ordena el vector utilizando el qsort, que es del orden de O(n*log(n))
+\begin_inset Foot
+collapsed true
+
+\layout Standard
+
+En realidad es del orden de O(1.44*n*log2(n)), para el caso promedio.
+\end_inset 
+
+.
+ Y como último paso se obtiene la salida recurriendo el vector Desplazamiento
+ ordenado y emitiendo el último byte de cada posición.
+ Si se detecta la posición donde la posición inicial sea 0, se obtiene el
+ k para retornar.
+\layout Standard
+
+Se debe aclara que los órdenes estimados más arriba se basan en la suposición
+ de que el orden de una comparación en O(1).
+ En el caso de tener que comprimir archivos donde los desplazamientos queden
+ iguales o solo cambien sobre el final, los órdenes se ven muy afectados.
+ Sin embargo, para el caso promedio no se comporta tan mal.
 \layout Subsection
 
 Move to Front (MTF)
@@ -886,7 +1023,6 @@ Se prueba el set de Calgary utilizando nuestro compresor, y enfrentandolo
  Los resultados se dan a continuación, para dos configuraciones de PC distintas:
 \layout Standard
 
-
 \begin_inset Float table
 placement H
 wide false
-- 
2.43.0