Un ejemplo concreto de utilización de Filtros (Linux)

En la actualidad existen una gran cantidad de problemas que solo son abordables gracias a la tecnología. Tipicamente, científicos se encuentran con el problema de tener un archivo resultante de un experimento que posee millones de líneas, de las cuales la gran mayoría no es relevante y se hace necesario filtrar la información. Afortunadamente, Linux posee una gamma de comandos filtradores y además, la posibilidad de crear nuevos filtros. En este post veremos un ejemplo de la gran utilidad que tienen la combinación de estos comandos al momento de filtrar información y para esto, abordaremos un caso particular del siguiente problema matemático: “Supongamos que tenemos un tablero de ajedrez de dimensiones n\times n y n reinas, ¿De cuántas formas diferentes se pueden disponer las n reinas sobre el tablero de tal modo que ninguna pueda comerse en el siguiente turno?”.

Este problema es un problema matemático sin solución analítica (es decir, no se conoce la solución en función de la dimensión), por lo tanto, solo es posible conocer la solución (para cada caso) modelando el problema teoricamente y montando un programa algebraico numérico que mediante múltiples iteraciones calcule todos los casos posibles, relevantes y no relevantes, y sea capaz de discriminar los casos no relevantes. Tal programa es demasiado complejo para realizarse y realmente no vale la pena montarlo por un concepto de costos… es por esto que nos aprovechamos de otros programas ya montados (mucho más amplios respecto a utilidades), de teorías matemáticas que nos permitirán modelar el problema de tal modo que sea natural la extensión de este a dimensiones mayores y de los útiles filtros. Como no son interesantes (en este post) las teorías utilizadas para la resolución del “Problema de las Reinas“, nos limitaremos a explicar como fue obtenido el arhivo de datos que filtraremos. Existe un tipo de grafo conocido como “Red de Petri” capaz de modelar matemáticamente el problema para cada caso dimensional (la red es naturalmente generalizable para dimensiones mayores) y existe un programa (llamado INA) capaz de trabajar sobre la información de tal grafo y hacer lo que se conoce como “análisis de alcanzabilidad”… Un grafo, como seguramente sabrán, es una malla geométrica con ciertas propiedades y reglas; un grafo capaz de representar la información del “Problema de las Reinas” 3-dimensional es el siguiente:

…que codificado (para que INA lo entienda) es

     P   M   PRE,POST  NETZ  1:ej
     0   1    11:3,    1
     1   0    1,   2   3   4
     2   0    1,   5   6   7
     3   0    1,   8   9  10
     4   0    2,  11
     5   0    3,  11
     6   0    4,  11
     7   0    5,  11
     8   0    6,  11
     9   0    7,  11
    10   0    8,  11
    11   0    9,  11
    12   0   10,  11
    13   0    1,   2   5   8
    14   0    1,   3   6   9
    15   0    1,   4   7  10
    16   0    1,   5   8
    17   0    1,   6   9
    18   0    1,   7  10
    19   0    1,   3   5
    20   0    1,   4   6   8
    21   0    1,   6   8
    22   0    1,   7   9
    23   0    1,   2   6  10
    24   0    1,   3   7
    25   0    1,   5   9
    26   0    1,   6  10
    
    @
    

El análisis de alcanzabilidad entregado por INA en forma de un archivo de datos es el siguiente: (en el caso de trabajar con dimensiones mayores, este arhivo de datos crece exponencialmente)

    State nr.    1
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
        :  0  0  0  0
    State nr.    2
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  1  1  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1
        :  1  1  1  1
    State nr.    3
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  1  1  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1
        :  0  1  1  1
    State nr.    4
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  0  1  1  0  0  0  0  1  0  0  0  0  1  0  1  1  0  1  1  1  0
        :  0  0  1  1
    State nr.    5
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  0  1  0  0  0  0  0  0  1  0  0  0  1  1  0  1  1  1  1  0
        :  0  1  0  1
    State nr.    6
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  1  0  1  0  0  0  0  0  0  0  1  0  1  1  1  1  0  1  1  1
        :  1  0  1  1
    State nr.    7
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  0  0  1  0  0  0  0  1  0  0  0  0  1  0  1  1  0  0  0  1
        :  1  0  1  1
    State nr.    8
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  0  0  1  0  0  0  0  0  0  1  1  0  0  1  1  0  0  1  1  1
        :  0  0  1  0
    State nr.    9
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  1  0  0  1  0  0  0  0  0  0  1  1  0  1  1  1  1  0  1  1
        :  1  1  1  1
    State nr.   10
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  0  1  0  0  1  1  0  0  0  0  0  0  1  0  0  1  1  0  0  1  1
        :  1  1  0  1
    State nr.   11
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  0  1  0  0  0  1  0  0  0  0  1  0  1  0  0  1  0  1  1  0  1  0
        :  1  1  0  1
    State nr.   12
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  0  1  0  0  0  1  0  0  0  0  0  0  1  1  0  1  1  0  1  1  1
        :  1  1  0  1
    State nr.   13
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  0  0  0  0  0  1  0  0  0  0  1  0  1  0  0  1  0  0  1  1  1
        :  0  1  0  0
    State nr.   14
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  0  1  0  0  0  0  1  0  0  0  0  1  0  1  1  0  1  1  0  0  1
        :  0  1  1  0
    State nr.   15
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  0  1  0  0  0  0  0  1  0  0  0  1  1  0  1  1  0  1  1  1  0
        :  1  0  1  1
    State nr.   16
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  0  0  0  0  0  0  0  1  1  0  0  0  1  0  0  1  0  1  0  0  0
        :  1  0  1  1
    State nr.   17
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  1  0  0  0  0  0  0  0  1  0  0  0  1  1  0  1  1  1  0  0  1
        :  1  1  1  1
    State nr.   18
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  1  0  0  0  0  0  0  0  0  1  0  1  0  1  1  0  1  1  1  1  0
        :  1  1  0  1
    State nr.   19
    P.nr:  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
        : 23 24 25 26
    toks:  0  1  1  0  0  0  0  0  0  0  0  0  1  1  1  0  1  1  0  1  1  1  1
        :  0  1  1  0
    

Supongamos que el nombre de este archivo es “datos.dat”. Notemos que cada “place” (es un nodo del grafo) esta enumerado desde el 1 al 26; en realidad lo único que nos interesa de este archivo son los places y la cantidad de “tokens” en ellos (el número de estado “State nr.” no es importante). Notamos que la cantidad de estados que se generaron fueron solo 19, pero ¿qué pasaría si fueran 1000 estados?… es por esto que supondremos además que no es posible leer el archivo línea por línea, por lo que nos veremos en la necesidad de filtrar. Para filtrar las líneas del documento que nos interesa (las que comienzan con “toks”-tokens) usamos el comando en consola “grep toks: datos.dat > datos1.dat“; esta línea de comando solo extrae las líneas del archivo “datos.dat” que comienzan con “toks:” y las guarda de un nuevo archivo llamado “datos1.dat”. Veamos el contenido del archivo generado “datos1.dat”:

    toks:  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
    toks:  0  1  1  1  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  1
    toks:  0  0  1  1  1  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1
    toks:  0  0  0  1  1  0  0  0  0  1  0  0  0  0  1  0  1  1  0  1  1  1  0
    toks:  0  0  1  0  1  0  0  0  0  0  0  1  0  0  0  1  1  0  1  1  1  1  0
    toks:  0  0  1  1  0  1  0  0  0  0  0  0  0  1  0  1  1  1  1  0  1  1  1
    toks:  0  0  1  0  0  1  0  0  0  0  1  0  0  0  0  1  0  1  1  0  0  0  1
    toks:  0  0  1  0  0  1  0  0  0  0  0  0  1  1  0  0  1  1  0  0  1  1  1
    toks:  0  0  1  1  0  0  1  0  0  0  0  0  0  1  1  0  1  1  1  1  0  1  1
    toks:  0  0  0  1  0  0  1  1  0  0  0  0  0  0  1  0  0  1  1  0  0  1  1
    toks:  0  0  1  0  0  0  1  0  0  0  0  1  0  1  0  0  1  0  1  1  0  1  0
    toks:  0  1  0  1  0  0  0  1  0  0  0  0  0  0  1  1  0  1  1  0  1  1  1
    toks:  0  1  0  0  0  0  0  1  0  0  0  0  1  0  1  0  0  1  0  0  1  1  1
    toks:  0  1  0  1  0  0  0  0  1  0  0  0  0  1  0  1  1  0  1  1  0  0  1
    toks:  0  1  0  1  0  0  0  0  0  1  0  0  0  1  1  0  1  1  0  1  1  1  0
    toks:  0  1  0  0  0  0  0  0  0  1  1  0  0  0  1  0  0  1  0  1  0  0  0
    toks:  0  1  1  0  0  0  0  0  0  0  1  0  0  0  1  1  0  1  1  1  0  0  1
    toks:  0  1  1  0  0  0  0  0  0  0  0  1  0  1  0  1  1  0  1  1  1  1  0
    toks:  0  1  1  0  0  0  0  0  0  0  0  0  1  1  1  0  1  1  0  1  1  1  1
    

Es importante explicar lo que significan todos estos 1’s y todos estos 0’s.. y es que la respuesta depende de la posición donde esten. Por ejemplo, la columna 6 a la columna 14 de datos corresponden a cada una de las 9 posiciones posibles del tablero de ajedrez de 3\times 3, donde un 0 significa que no hay reina y un 1 significa que hay una reina en esa posición. Nuevamente notamos que el resto de la información en este archivo es irrelevante, por lo que nuevamente debemos filtrar la información, y lo haremos con la línea de comando “cut -b 19-46 datos1.dat > datos2.dat“; este comando corta desde la columna 19 del documento (OJO! esta columna no es de datos! cada columna corresponde al espacio de un caracter) a la columna 46 del archivo “datos1.dat” y guarda la información en un nuevo archivo llamado “datos2.dat”, cuya información guardada es la siguiente:

    0  0  0  0  0  0  0  0  0
    0  0  0  0  0  0  0  0  0
    1  0  0  0  0  0  0  0  0
    1  0  0  0  0  1  0  0  0
    1  0  0  0  0  0  0  1  0
    0  1  0  0  0  0  0  0  0
    0  1  0  0  0  0  1  0  0
    0  1  0  0  0  0  0  0  1
    0  0  1  0  0  0  0  0  0
    0  0  1  1  0  0  0  0  0
    0  0  1  0  0  0  0  1  0
    0  0  0  1  0  0  0  0  0
    0  0  0  1  0  0  0  0  1
    0  0  0  0  1  0  0  0  0
    0  0  0  0  0  1  0  0  0
    0  0  0  0  0  1  1  0  0
    0  0  0  0  0  0  1  0  0
    0  0  0  0  0  0  0  1  0
    0  0  0  0  0  0  0  0  1
    

Estamos considerando que este archivo es imposible leerlo línea por línea (por lo supuestamente grande que es). Como sabemos, para tener una solución al problema, debemos tener 3 reinas en 3 de las 9 posiciones del tablero… para saber cuales son posibles soluciones, basta sumar todas las filas de datos y las filas cuya suma nos de 3 será una solución. Para hacer esta suma basta usar el comando “awk ‘{print $1+$2+$3+$4+$5+$6+$7+$8+$9}’ datos2.dat > datos3.dat“; esta línea de comandos suma las columnas de datos que van desde la primera a la novena para cada fila del archivo “datos2.dat” y guarda tal suma en un nuevo archivo “datos3.dat”, cuya información guardada es la siguiente:

    0
    0
    1
    2
    2
    1
    2
    2
    1
    2
    2
    1
    2
    1
    1
    2
    1
    1
    1
    

Este archivo suele ser muy grande, por lo que comunmente se usa el comando “grep 3 datos3.dat > datos4.dat” y luego se cuentan la cantidad de filas que tiene el archivo “datos4.dat” (que tendrá solo 3’s en cada fila) para saber la cantidad de soluciones diferentes que tiene nuestro problema 3-dimensional. Como pudimos instuírlo desde el principio, la respuesta es 0 soluciones y es consecuente con la cantidad de soluciones que obtenemos con este método un poco complicado, pero muy útil para archivos enormemente grandes. Para el caso n-dimensional de este mismo problema, lo que se hace es un programa que genere el grafo (para INA), puesto que es demasiado grande el archivo de grafo como para ser generado manualmente. Evidentemente, hacer todo esto y separar en varios archivos “datosj.dat” es muy poco engorroso, por lo que se suelen identificar las operaciones que se deben hacer y suelen aplicarse todas juntas en una sola línea de comando, lo que resume bastante lo hecho, pero que no explica para nada lo que se hace. Para finalizar este pequeño ejemplo, debo decir que existen muchos más comandos “filtros” en Linux con otras utilidades y que los comandos ya vistos también hacen otras operaciones (solo hay que cambiar un poco la sintaxis de los argumentos que le entregamos a cada comando), por lo que ser experto en filtrado de archivos requiere mucho tiempo de estudio y muchas veces ingenio 🙂

Anuncios

Si te gustó el post, por favor dejanos tu comentario!!

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s