Locura número 1 :D ( XD )
-
Hola, les presento un prototipo de modelo matemático que estoy desarrollando para poder comprimir información (como el WinRar, por ejemplo, pero usando mi propio método). Les advierto que esto va a ser demasiado largo.Y digo prototipo porque todavía no está terminado, falta mucho por hacer (este proyecto lo dejé hace tiempo atrás porque tenía que ocuparme en otras cosas, pienso retomarlo). Es un proyecto experimental y bastante jodido, escribo todo esto para descargar un poco la tensión (estoy enloqueciendo mas de lo normal). xDEsto va a ser excesivamente largo, no es necesario que lo lean. (supongo que me sirve de guía, y ya que estoy lo postéo acá)Introducción:-------------La compresión de datos tiene por objetivos usar menos espacio de memoria en el disco rígido a costa de modificar los datos en cuestión. Obviamente los datos comprimidos no pueden ejecutarse como un .exe, y como están alterados no sirven para nada hasta que se los descomprima.Supongamos que tenemos una cadena de caracteres: $A.$A podría ser, por ejemplo: [ A48^*S¨"=GKA?"¨RA::>¨!?·)VK"?DA ]Pero podriamos guardar esa cadena en un archivo txt, y leer el archivo de forma binaria, obteniendo ceros y unos.$A quedaría algo así:[ 0110100101010010101010010101010001010100101010101001 ]Mucho más larga por supuesto, ya que para cada caracter necesitamos más de un bit (dependiendo del tipo de codificación, pero no viene al caso, supongamos que necesitamos 8 bits).Exceso de bits:---------------Si cada caracter toma información de 8 bits, a nosotros no nos interesa. Nosotros vamos a tomar de a 10 caracteres (1024 posibilidades)Si la cadena binaria tiene, por ejemplo, 13 dígitos, entonces van a sobrar 3 dígitos (o a faltar 7 dígitos). Lo que se hace en ese caso es apartar esos 3 bits y registrarlos por ahi. La idea es que esos 3 bits no van a ser comprimidos.Un archivo podría tener 450137463 bits, de modo que 3 bits definitivamente no hacen la diferencia.Números decimales:------------------Para simplificar MUCHO la tarea de entender cómo funciona todo, vamos a representar las 1024 posibilidades de los 10 bits como números decimales. Siempre trabajaríamos con números binarios, pero los representamos en decimal.Y los números que tienen ceros a la izquierda, se quedan tal y como están: con ceros a la izquierda.Ejemplos: 0012 0003 0628 1024 0000 0391Esto lo hacemos así porque en realidad estamos trabajando con cadenas, aunque se vea como números.El 0082 podría estar representando la letra "R" por ejemplo. Noten que tomo siempre de a 4 caractéres.Si tuvieramos una cadena de caractéres asi: "0371037510120092"la dividiríamos así: 0371 0375 1012 0092A cada grupo de 4 dígitos, llamemoslé código.
-
Reordenamiento:---------------Supongamos que tenemos un archivo de 832 códigos. Entonces tomemos bloques de a 100 códigos (esta vez en vez de descartar bits, descartamos CONJUNTOS de 10 bits). Descartamos 32 (los registramos por ahi, y no lo comprimimos).De nuevo, si el archivo tendría 70987132 códigos, 32 códigos no son nada.Entonces tenemos 8 bloques de 100 códigos, cada código con 10 bits. Si al final le concatenamos los códigos descartados y los bits descartados, obtenemos el archivo entero.El compresor que intento diseñar comprime a cada uno de estos 8 grupos por separado.Así que cada vez que hablemos de comprimir, vamos a hablar de comprimir 100 códigos.Lo primero que hace el compresor es ordenar los códigos como si fueran números (recuerden que en realidad son cadenas).Si tenemos los códigos:1º 02042º 10023º 01104º 09125º 0362Entonces los reordenamos así:1º 01102º 02043º 03624º 09125º 1002Pero para no perder el orden original, entonces anexamos a cáda código el número de orden original.3º 01101º 02045º 03624º 09122º 1002En el ejemplo son solo 5 códigos, pero se supone que ordenaríamos los códigos de los bloques de 100 códigos.El ordenamiento agrega un dígito más a cáda código, a ese nuevo dígito lo vamos a llamar Posicionador.Por lo tanto las posiciones se anexan a cada código, antecediendo al código.Ejemplo: 70294 indica que 0294 está en la posición 7 del bloque en cuestión.Como tenemos 100 códigos en el bloque, necesitamos 2 dígitos Posición.Un ejemplo sería: 991024 que indica que 1024 está en la posición 99.Ahora bien, para tener un posicionador que indique la posición número 100 se necesitan 3 digitos.Pero tomemos al 00 como la posición 1, con lo que el 99 quedaría representando la posición número 100.Y ya tenemos nuestro bloque de 100 códigos ordenado (aunque con mucho mas peso, porque se les agregó 2 dígitos a cada bloque).Si teníamos 800 códigos, con 8 bloques de 100, entonces agregamos un posicionador de 2 dígitos por cada bloque (estaríamos agregando 2 dígitos cada 10 dígitos, con lo cual el tamaño aumenta en un 20%).Pero están ordenados, he ahí el santo grial de mis esperanzas.Y fín, se terminó. ^_^Jajajaj , no mentira xD.
-
Compresión simple.------------------La idea principal es esta: la derivada. Si dibujaramos nuestros 100 códigos en una función XY, entonces podríamos sacar las distancias parciales de un punto a otro, sin tener que representar numéricamente cada punto desde el Eje X. (la derivada es un número que indica pendiente, pero en este caso lo interpretamos como la variación que existe entre un código y otro).Para ponerles un ejemplo, si tenemos 4 códigos ordenados así:3º 09231º 09292º 09364º 0945Entonces podemos representarlo así:3º 09231º anterior + 62º anterior + 74º anterior + 9A estos nuevos códigos les llamarémos códigos relativos, (a los anteriores: códigos absolutos). Los códigos relativos tienen la ventaja de usar menos dígitos, de forma variable (según ajustemos ciertos parámetros y según los datos).Podríamos representar los códigos relativos así:Posicionador Código Relativo3º 09231º 62º 74º 9Con la consiguiente pérdida de 9 dígitos entre los 4 códigos. La información se puede reconstruir a partir de los códigos relativos, pero falta una pequeña cosa: Habría que indicar qué longitud tiene cada código relativo, ya que como vemos, tienen distinta longitud, y cuando uno lee secuencialmente el archivo que vamos a comprimir, debe saber cuándo empieza y cuándo termina cada código relativo, porque tienen distinta longitud.Eso lo hago con algo que llamo "Indicador de Longitud", otro maravilloso dígito anexado D:Supongamos el ejemplo anterior con la siguiente notación:C = CódigoP = PosicionadorL = LongitudLa manera de comprimir esos datos sería generar la cadena:LPCLPCLPCLPCLPC....Conformada de subcadenas LPC.Así que sin más preámbulos, vayamos a la práctica y probemos si funciona. ^_^
-
Ejemplo de Compresión Simple.-----------------------------Tenemos el archivo. Tiene 1437 bits.Tomemos códigos de 20 bits cada uno.Para eso descartamos 17 bits sobrantes. (Recuerden que para archivos grandes eso no importa)Ahora tenemos 71 códigos (con 1420 bits).Elejimos el tamaño de cada bloque: 10 códigos por bloque.Descartamos 1 código sobrante. Nos quedan 7 bloques de 10 códigos cada uno, de 20 bits cada uno.Y trabajamos en cada uno de los 10 bloques, comprimiendo uno a uno de la siguiente forma:1. Reordenamos los códigos dentro de cada bloque.2. Generamos los Posicionadores (P).3. Generamos los códigos relativos (C) con las derivadas parciales a partir de los códigos absolutos ordenados.4. Calculamos la longitud (L) de cada código relativo.5. Anexamos todo en secuencias LPC.6. Almacenamos el archivo.Supongamos que estamos comprimiendo el primer bloque. Los datos seguirán una especie de distribución aleatoria, pero el ejemplo está vilmente manipulado para obtener datos favorables, esto no funciona para todos los casos, pero sí funciona para ciertos casos (para muy pocos casos). El fin de esto es demostrar si el algoritmo funciona o no, para saber si es viable avanzar desarrollándo nuevas técnicas.Supongamos que el límite máximo de (2 ^ 20) es de 1.000.000 (asi no nos complicamos tanto).Cargamos el primer bloque de 10 códigos.Bloque 1:092831092839240351240396240484491337491382603948603983603994Bloque 1 (editando):092831-092839-240351-240396-240484-491337-491382-603948-603983-603994Cargamos los Códigos Absolutos.Posicionador Código Absoluto1º 2403962º 4913823º 0928314º 6039485º 2403516º 6039947º 2404848º 4913379º 60398310º 092839Ordenamos los Códigos Absolutos y Generamos los Posicionadores.Posicionador Código Absoluto3º 09283110º 0928395º 2403511º 2403967º 2404848º 4913372º 4913824º 6039489º 6039836º 603994
-
Generamos los Códigos Relativos y Calculamos los Indicadores de Longitud.Longitud Posicionador Código Relativo6 3º 0928311 10º 86 5º 1475122 1º 452 7º 886 8º 2508532 2º 456 4º 1125662 9º 352 6º 11Total 35Anexamos todo en secuencias LPC (Longitud, Posicionador, Código).LPCCCCCC-LPC-LPCCCCCC-LPCC-LPCC-LPCCCCCC-LPCC-LPCCCCCC-LPCC-LPCC62092831-198-64147512-2045-2688-67250853-2145-63112566-2835-2511Guardamos el archivo.6209283119864147512204526886725085321456311256628352511Bien, ahora si queremos recuperar el archivo, tenemos que decodificar el código, tenemos que revisar el protocolo de información.Sacamos el primer número, lo usamos como Longitud: 6Sacamos el segundo número y le sumamos 1, lo usamos como Posicionador: 2 + 1 = 3ºCargamos tantos números como diga la Longitud al primer código relativo.Cargamos: "092831"Sacamos el segundo Indicador de Longitud: 1Sacamos el segundo Posicionador y le sumamos 1: 9 + 1 = 10ºCargamos tantos números como diga la Longitud al segundo código relativo.Cargamos "8"Y así sucesivamente hasta obtener el bloque de 10 códigos entero.Después tendríamos los posicionadores y los códigos relativos, con los cuales se pueden generar los códigos absolutos y darles el orden correcto.Generamos los Códigos Absolutos a partir de los Códigos Relativos extraidos.Posicionador Código Rel. Código Abs.3º +092831 09283110º +8 0928395º +147512 2403511º +45 2403967º +88 2404848º +250853 4913372º +45 4913824º +112566 6039489º 35 6039836º 11 603994
-
Reordenamos los Códigos Absolutos según los Posicionadores.Posicionador Código Absoluto1º 2403962º 4913823º 0928314º 6039485º 2403516º 6039947º 2404848º 4913379º 60398310º 092839Concatenamos los Códigos Absolutos desde el 1º hasta el 10º.092831092839240351240396240484491337491382603948603983603994Y obtenemos el bloque original. Si aplicamos este proceso a cada uno de los bloques, podemos comprimir y recuperar cada uno de sus 7 bloques.Queda demostrado que en este método es factible recuperar la información "comprimida". Y pongo "comprimida", entre comillas, porque todavía no sabemos si se comprimieron los datos o si solo agregamos información basura.En retrospectiva (después de tanto circo, vamos a lo importante): ¿Se comprimieron los datos?Si sumamos los 35 dígitos que usamos para los códigos relativos, más los 10 dígitos que usamos para los posicionadores, más los 10 dígitos que usamos para los indicadores de longitud, obtenemos 55.El bloque original tenía 10 códigos de 6 dígitos decimales cada uno, por lo tanto tenía 6 x 10 = 60 dígitos en total.Y como 35 + 10 + 10 = 55 < 60 = 6 x 10Entonces no queda más opción que concluir que es matemáticamente posible reducir la cantidad de dígitos de un número, usando una menor cantidad de dígitos del mismo tipo. Los datos SI se comprimieron, en un 8,3% periódico.Eso quiere decir que determinados números N (de X cantidad de dígitos), pueden representarse con Y dígitos, siendo Y < X. (WTF)¿Qué tal? :DAhora -sabemos- que es posible. Pero de posibilidad a probabilidad hay un largo trecho. XD
-
Obviamente hay muchos tipos de amalgamación, no es tan simple, lo que da lugar a términos como amalgamación múltiple, o amalgamación parcial, amalgamación incremental, etc.La pregunta del millón.-----------------------¿Cuáles son los parámetros correctos?Hay que establecer los parámetros como el tamaño de los códigos absolutos, el tamaño de los bloques, el tipo de amalgamación (hay muchos tipos), etc. La cosa no es nada fácil, además no siempre funciona (pocas veces comprime datos).Siempre depende de los datos que se le ingrese.Entonces opté por formalizar matemáticamente todo lo que pueda, incluir los parámetros en un algoritmo, y buscar la mejor solución con métodos de inteligencia artificial.Y ahí estoy, dejé ese proyecto creo que hace más de un año ya, todavía tengo que seguirlo.La idea es construir un programa que anexe a cada bloque unos indicadores que indiquen los parámetros de compresión utilizados.Por una parte es malo, agrega algunos indicadores a cada bloque, pero por otra parte es muy bueno, porque permite una flexibilidad muy alta para poder comprimir cada bloque, el algoritmo de inteligencia artificial buscaría una y otra vez distintos métodos hasta dar con uno que comprima los datos, a prueba y error.Me pregunto si habrá alguna semi-heurística para poder determinar qué parámetros usar... En fín, tengo mucho por hacer, tengo que formalizar el proceso de amalgamación y registrar todas las posibles alteraciones a los datos originales antes de ser procesados, incluso estaba pensando en algún tipo de entreveración..Dentro de unos meses me voy a programar a lo hardcore, asi que quiero preparar bien los diseños del modelo matemático. Va a ser un trabajo descomunal. ^_^Saludos chicos :) , les dije que era largo. XDPD: No me hago responsable de ninguno los efectos psicologicos secundarios (daninos por supuesto) que les haya provocado leer esto. :D
-
Obviamente hay muchos tipos de amalgamación, no es tan simple, lo que da lugar a términos como amalgamación múltiple, o amalgamación parcial, amalgamación incremental, etc.La pregunta del millón.-----------------------¿Cuáles son los parámetros correctos?Hay que establecer los parámetros como el tamaño de los códigos absolutos, el tamaño de los bloques, el tipo de amalgamación (hay muchos tipos), etc. La cosa no es nada fácil, además no siempre funciona (pocas veces comprime datos).Siempre depende de los datos que se le ingrese.Entonces opté por formalizar matemáticamente todo lo que pueda, incluir los parámetros en un algoritmo, y buscar la mejor solución con métodos de inteligencia artificial.Y ahí estoy, dejé ese proyecto creo que hace más de un año ya, todavía tengo que seguirlo.La idea es construir un programa que anexe a cada bloque unos indicadores que indiquen los parámetros de compresión utilizados.Por una parte es malo, agrega algunos indicadores a cada bloque, pero por otra parte es muy bueno, porque permite una flexibilidad muy alta para poder comprimir cada bloque, el algoritmo de inteligencia artificial buscaría una y otra vez distintos métodos hasta dar con uno que comprima los datos, a prueba y error.Me pregunto si habrá alguna semi-heurística para poder determinar qué parámetros usar... En fín, tengo mucho por hacer, tengo que formalizar el proceso de amalgamación y registrar todas las posibles alteraciones a los datos originales antes de ser procesados, incluso estaba pensando en algún tipo de entreveración..Dentro de unos meses me voy a programar a lo hardcore, asi que quiero preparar bien los diseños del modelo matemático. Va a ser un trabajo descomunal. ^_^Saludos chicos :) , les dije que era largo. XDPD: No me hago responsable de ninguno los efectos psicologicos secundarios (daninos por supuesto) que les haya provocado leer esto. :D
-
Una sugerencia: ¿por que una vez que generaste los códigos relativos, no los volves a comprimir usando el mismo algoritmo? Se me ocurre que este algoritmo se puede re-aplicar varias veces.Digamos: separas la base original de los relativos a esta, los ordenas de menor a mayor, y al menor lo usas como una nueva base. Y de todos los restantes calculas el delta con respecto a este (como venias haciendo antes).Vamos a dividir los bloques en Base (B) y No Base (NB). Una vez que aplicas el algoritmo por primera vez, te queda 1 Base y 9 No Base (o relativos). Ahora tomas los 9 NB, los ordenas, al menor lo haces Base y los 8 NB restantes los transformas en códigos relativos del Base nuevo. Ahora de los 8 NB, los ordenas, al menor lo haces Base, etc...Al final te quedarían 9 B y 1 NB (o 10 NB, habria que analizarlo bien). ¿Entonces que hacemos con todas esas bases? Reaplicamos el algoritmo :PClaro que se necesitarían más bits de información extra (no se cuantos ni donde :P )... pero bueno.
-
Tengo una gran sospecha que en todo esto juegan un papel importante los logaritmos... voy a hacer ciertas investigaciones y volveré con más :D
-
Había probado hacer lo que dijiste, pero es inusual que el método por sí solo (Ordenar y sacar códigos relativos) comprima.Comprimir 10 códigos, despues 9, despues 8, etc, solo lleva el problema a otra instancia, pero sin beneficio para la compresión.Tengo que encontrar una buena manera de amalgamar los datos para lograr juntarlos lo más posible. Las amalgamaciones pueden ser múltiples (aplicar más de una amalgamación sobre los datos), y algunas veces vale la pena amalgamar más de una vez. Tengo que formalizar, unificar y sistematizar el proceso de amalgamación.
-
Tengo una teoría (o un concepto, o una idea, nose)... que me viene carcomiendo la cabeza desde hace un tiempo.
Según el ejemplo que puse acá, paso a paso, se obtiene que los dos siguientes números representan el mismo número.
6209283119864147512204526886725085321456311256628352511{ } WTF XD092831092839240351240396240484491337491382603948603983603994Mi teoría es que la información extraida del segundo número, la información que falta en el primer número, está acá: en los parámetros pre-establecidos del Compresor, como el número de compresiones hechas (si es que comprimimos recursivamente), el tamaño de los bloques, el tamaño de los códigos, la cantidad de amalgamaciones, etc.¿Y esto es magia? No. Significa que todos los archivos que comprimamos van a tener información compartida, gracias a que comparten el mismo tipo de codificación, el mismo protocolo.Toda cadena de información tiene un protocolo asociado, incluso un número normal como 84 (8 decenas 4 unidades).Dado un Compresor con sus parámetros establecidos, es natural pensar que representa la información de otra forma, y que por alguna extraña razón que desconocemos para algunos números se necesita más digitos que en el sistema decimal, y para otros números menos.Lo que hace a un compresor un Compresor es: que si los datos comprimidos son mayores que los originales: NO comprime. Esa es una decisión, que recorta las posibilidades en 2. Por un lado tenemos los datos comprimidos, y por otro lado los datos NO comprimidos (en vez de los datos que aumentaron de tamaño). Esa decisión selectiva es, en parte, información agregada.Supongo que cuanta más información comparta un archivo con otros, en un protocolo, más se va a poder comprimir el archivo.La información expresada en una cadena de datos de longitud N debería tener biunicidad con cualquier otra cadena de tamaño variable M (como los archivos que se intentaron comprimir).-Por lo tanto, suena gracioso, pero creo que tiene MUCHO que ver con la fórmula que presentaste en el post "Sumatoria de Rangos". Si te fijas bien, es el post creado anterior a este. Eso es porque por alguna razón tu post me inspiro para crear este. Ahora veo el porqué de la corazonada. -
Maldita sea... ¡Yo sabia! ¡Yo sabia!:P
Howdy, Stranger!
It looks like you're new here. If you want to get involved, click one of these buttons!