Implementación de "quiso decir" similar al de google

Uno de los avances más importantes que hizo que la utilidad de google como buscador es el apartado "quiso decir".

Si nos equivocamos en una palabra se nos indica (con bastante acierto) lo que queríamos decir, es más, muchas veces no nos preocupamos de escribir bien la consulta sabiendo que se nos va a corregir bien.

¿Cómo se implementa algo así? Pues realmente no es algo muy complejo.

Primero necesitamos una medida de cómo de lejana es una palabra con respecto a otra, se puede usar la distancia de Levenshtein, en el enlace a la wikipedia hay también implementaciones de esta medida en numerosos lenguajes.

En php además tenemos la ventaja de tener implementada ya la función.

Veamos un ejemplo de como usarla.

<?php

$input='peujot';

$dictionary=array('seat','ford','honda','mercedes',
        'bmw','citroen','peugeot','fiat','ferrari');

$shortest=-1;

foreach($dictionary as $word){
        $lev=levenshtein($input, $word);

        if($lev==0){
                $closest=$word;
                $shortest=0;
                break;
        }

        if($lev<=$shortest || $shortest<0){
                $closest=$word;
                $shortest=$lev;
        }
}

echo "Ha introducido: $input <br/>";
if($shortest==0){
        echo "Palabra correcta <br/>";
}
else{
        echo "Quiso decir: $closest <br/>";
}

En este código se toma como entrada $input y se busca la palabra conocida más cercana (según la distancia Levenshtein).

Problema pasando parámetros por referencia en perl

En esta ocasión voy a explicar un problema existente en el paso de parámetros por referencia en perl cuando estamos trabajando con hebras. Probado en la versión 5.8.8.

En perl el paso de parámetros por referencia se hace de la siguiente forma.

#!/usr/bin/perl

use threads;

sub funcion{
        my $p=shift;
        ${$p}=2;
        print "Vale ${$p}\n";
}

my $var=1;

funcion(\$var);

print "En la hebra principal vale $var\n";

Obtenemos el valor 2 en los dos casos, es decir, se ha producido un cambio real de la variable al pasarla por referencia. Si intentamos hacer exactamente lo mismo pero en lugar de con una función normal con una hebra resulta lo siguiente.

#!/usr/bin/perl

use threads;

sub hebra{
        my $p=shift;
        ${$p}=2;
        print "Vale ${$p}\n";
}

my $var=1;

$t=threads->new(\&hebra, \$var);

$t->join();

print "En la hebra principal vale $var\n";

En este caso pese a ser el código calcado al anterior no se produce cambio en la variable. ¿Por qué sucede esto?
Cuando creamos una hebra esperamos compartir el espacio de direcciones del proceso, sin embargo en perl con cada hebra se realiza una copia de este espacio de direcciones. Así, aunque pasemos el parámetro por referencia se modifica una copia y no el original.

En C se puede comprobar que sí se modifica la variable en una situación similar.

#include <pthread.h>
#include <stdio.h>

void *hebra(void *param){
        int *p=(int *)param;
        *p=2;
        printf("Vale %d\n",*p);

        pthread_exit(NULL);
}

int main(int argc, char *argv[]){
        pthread_t threads[1];
        void *status;
        int var=1;

        pthread_create(&threads[0], NULL, hebra, (void *) &var);
        pthread_join(threads[0], &status);

        printf("En la hebra principal vale %d\n", var);

        pthread_exit(NULL);
}

Para compartir variables en perl entre hebras la única solución que nos queda es usar share.

#!/usr/bin/perl

use threads;
use threads::shared;

share($var);

sub hebra{
        $var=2;
        print "Vale $var\n";
}

$var=1;

$t=threads->new(\&hebra);

$t->join();

print "En la hebra principal vale $var\n";

En esta ocasión la variable funciona como una variable global y por tanto no hay que pasarla como parámetro.

Tratamiento de excepciones en python

En la mayoría de lenguajes de programación tenemos herramientas para manejar las excepciones que se produzcan, paso a comentar las existentes en python.

Si ejecutamos el siguiente programa se producirá una execpción debida a la división entre cero.

#!/usr/bin/python

a=10/0;
print a;

Se puede controlar la excepción de la siguiente forma.

#!/usr/bin/python

try:
        a=10/0;
        print a;

except:
        print "Problema dividiendo";

Se pueden tratar los errores por separado.

#!/usr/bin/python

try:
        a=10/0;
        print a;

except ZeroDivisionError:
        print "El divisor es cero";

except:
        print "Otro error";

Se puede ejecutar código si no se produce la excepción, será lo representado por la cláusula else.

#!/usr/bin/python

try:
        a=10/0;

except ZeroDivisionError:
        print "El divisor es cero";

else:
        print a;

O incluso se puede ejecutar código tanto si se produce la excepción como si no, con la cláusula finally.

#!/usr/bin/python

try:
        a=10/0;

except ZeroDivisionError:
        print "El divisor es cero";

finally:
        print "Necesitamos seguir aunque cometamos errores";

Podemos también definir nuestras propias excepciones, para ello debemos crear una clase que herede de Exception. La excepción se lanzará con raise.

#!/usr/bin/python

class MiExcepcion(Exception):
        def __init__(self, valor):
                self.valor = valor

        def __str__(self):
                return str(self.valor) + ": se ha cometido al intentar realizar la operacion"

var=2;
if var < 10:
        raise MiExcepcion("Valor enano");

Por supuesto las excepciones que lancemos también se pueden capturar y tratar.

#!/usr/bin/python

class MiExcepcion(Exception):
        def __init__(self, valor):
                self.valor = valor

        def __str__(self):
                return str(self.valor) + ": se ha cometido al intentar realizar la operacion"

try:
        var=2;
        if var < 10:
                raise MiExcepcion("Valor enano");

except:
        print "Tranquilidad que lo podemos solucionar todavia";

Función zip the python

zip es una función para reorganizar listas en python. Como parámetros admite un conjunto de listas. Lo que realmente hace es tomar el elemento iésimo de cada lista y unirlos en una tupla, después une todas las tuplas en una lista.

No es tan difícil como parece, se entiende mejor con un ejemplo.

#!/usr/bin/python

lista=[1,2,3,4,5,6,7,8,9];

l2=filter(lambda n : n%2==0, lista);

print l2;

l3=zip(lista,l2);

print l3;

En este caso construimos la lista "l2" usando una función lambda, esta lista contiene los números pares de "lista", es decir [2, 4, 6, 8].

Posteriormente ejecutamos zip sobre las dos listas, obtenemos [(1, 2), (2, 4), (3, 6), (4, 8)], una lista de tuplas combinando las dos listas, primero "lista" y después "l2".

En el ejemplo anterior hemos combinado dos listas, pero puede hacerse con más a la vez, si por ejemplo obtenemos una lista de nombres, y otras dos con los apellidos de una base de datos podríamos combinarlas de la siguiente forma.

#!/usr/bin/python

nombres=["Francisco", "Jose", "Fernando"];
apellidos1=["Fernandez", "Rodriguez", "Jimenez"];
apellidos2=["Jimenez", "Rodriguez", "Fernandez"];

nombresCompletos=zip(nombres, apellidos1, apellidos2);

for i in nombresCompletos:
        print i;

Compartir conexión a internet entre windows vista y xp

Para explicar el proceso vamos a suponer un escenario. Tenemos un cable de red que nos da conexión a Internet y queremos conectar dos portátiles, uno con windows vista y otro con windows xp.

Podemos conectar el portátil con windows vista a la red, después ejecutamos:

Inicio->Conectar->Configurar una conexión a internet

Nos aparece esta pantalla.



Elegimos la opción de configurar una red ad-hoc y llegamos aquí.



Elegimos el nombre de la red (el que queramos), el tipo de encriptación a utilizar y la contraseña.

Finalmente llegamos aquí.



Y elegimos Activar conexión compartida a Internet.

Finalmente en el equipo con windows xp nos conectamos a la red inalámbrica que hemos creado (debería aparecer) y ya tendremos acceso a Internet.

Alineamiento de memoria

Cuando accedemos a un dato en memoria en la arquitectura x86 podemos referenciarlo por bytes, sin embargo, la mínima cantidad de información que puede traer de memoria el procesador es una palabra (4 bytes). ¿Cuál es el problema?

Imaginemos la situación en la que queremos acceder a una palabra que está en la dirección de memoria 100, el procesador traerá correctamente desde la dirección 100 a la 103 (inclusive).
Sin embargo, si la palabra a la que queremos acceder empieza en la dirección 101, tendremos que acceder dos veces, 100-103 y 104-107. Dos accesos de memoria para traer tan solo una palabra, la mitad de la información traída de memoria en este caso no es útil.

¿Qué hacer para solucionarlo? La mayoría de las veces no debemos preocuparnos por este hecho, el compilador se encarga de solucionar el tema. Veamos el siguiente código en C.

#include <stdio.h>

int main(int argc, char **argv){
        char x[5];

        printf("%d\n", sizeof(x));
}

No hace mucho, simplemente declara un array y llama a la función printf. Si dejamos que el compilador (gcc en este caso) lo traduzca a ensamblador obtendremos esto.

.file   "prog.c"
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $24, %esp
        andl    $-16, %esp
        movl    $0, %eax
        addl    $15, %eax
        addl    $15, %eax
        shrl    $4, %eax
        sall    $4, %eax
        subl    %eax, %esp
        subl    $8, %esp
        pushl   $5
        pushl   $.LC0
        call    printf
        addl    $16, %esp
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.0.2 20050901 (prerelease) (SUSE Linux)"
        .section        .note.GNU-stack,"",@progbits

En el código podemos ver el prólogo y el epílogo habitual de una función, la llamada a printf, algunos ajustes en la pila, y 3 instrucciones que en principio no tienen mucho sentido, andl, shrl, sall.

Estas tres instrucciones se utilizan en esta ocasión para hacer el alineamiento de memoria, en primer lugar andl $-16,%esp es lo mismo que and $0xfffffff0,%esp, es decir, mantiene la dirección de %esp haciendo los últimos 4 bits a cero.

Las instrucciones shrl y sall hacen lo mismo, si primero dseplazamos el valor de un registro 4 bits a la derecha y luego 4 hacia la izquierda, lo que realmente estamos haciendo es poniendo los últimos 4 bits a cero. Evidentemente se pueden cambiar estas dos instrucciones por un andl como el anterior. El siguiente programa es el mismo ahorrándonos unas cuantas instrucciones.

.file   "prog.c"
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl main
        .type   main, @function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $24, %esp
        andl    $-16, %esp
        movl    $30, %eax
        andl    $-16, %eax
        subl    %eax, %esp
        subl    $8, %esp
        pushl   $5
        pushl   $.LC0
        call    printf
        addl    $16, %esp
        leave
        ret
        .size   main, .-main
        .ident  "GCC: (GNU) 4.0.2 20050901 (prerelease) (SUSE Linux)"
        .section        .note.GNU-stack,"",@progbits

Actualizar webs cada X segundos

En muchas ocasiones nos encontramos esperando a la actualización de una web para ver unas notas, alguna noticia, etc.
El caso se agrava cuando esa página no tiene sindicación (RSS, Atom...) y es entonces cuando se produce el "síndrome del F5", vamos, que nos pasamos todo el día dándole a actualizar.

Pues me acabo de fabricar un scrip en perl que hace justamente eso, actualizar cada cierto tiempo y mostrar los cambios en la página que le indiquemos.

#!/usr/bin/perl
use LWP::Simple;
use Digest::MD5 qw(md5_hex);

unless(@ARGV > 1){ die "Uso: $0 url sleeptime" }
my $url=shift(@ARGV);
my $sleeptime=shift(@ARGV);

my $page = get $url;
die "No se encuentra: $url" unless defined $page;

my $lastPage=$page;
my $last=md5_hex($page);
my $new=$last;

while(1){
        $page = get $url;
        die "No se encuentra: $url" unless defined $page;

        $new=md5_hex($page);
        if($last ne $new){
                open(LAST, ">lastPage.html");
                print LAST $lastPage;
                close(LAST);
                open(PAGE, ">page.html");
                print PAGE $page;
                close(PAGE);
                system("diff -bBiw lastPage.html page.html");
                system("rm lastPage.html page.html");
                $lastPage=$page;
                $last=$new;
        }

        sleep($sleeptime);
}

Se ejecuta de la siguiente forma: ./update url tiempo_entre_actualizaciones

Ejecutar el mismo comando repetidas veces con distintos parámetros

Aquí os dejo un "one-line" en perl, ejecuta $orden sobre los ficheros que le vayamos pasando como parámetro.

perl -e '$orden="ls";while(<>){chomp($_);system "$orden $_"}'

Se puede combinar con el uso de netcat de la entrada anterior e ir mandando ficheros a otro pc con tan solo escribir su ruta.

Enviando ficheros comprimidos por red

Para enviar archivos en red local puntualmente sin tener que abrir un servicio de ftp se puede usar netcat. Si se trata de archivos grandes podemos comprimir el archivo al vuelo para disminuir el tiempo que tarda la transferencia.

En la máquina que tiene el archivo:

cat ARCHIVO | gzip --fast | netcat -l -p PUERTO

En la máquina a la que queremos enviarlo:

netcat HOST PUERTO | gunzip > ARCHIVO

Generadores en python

Python es un lenguaje multiparadigma que soporta gran cantidad de conceptos de programación, pero uno del que nunca había oido hablar y me ha llamado la atención son los generadores.

Un generador es una función especial que va creando valores sobre los que iterar.

Supongamos que queremos iterar sobre el conjunto de los números primos.

#!/usr/bin/python

from math import sqrt

def esPrimo(n):
        root=int(sqrt(n));
        for i in range(2,root+1):
                if n%i==0:
                        return False;
        return True;


def generadorPrimos(n):
        for i in filter(esPrimo, range(2,n+1)):
                yield i


for i in generadorPrimos(100):
        print i;

Primero debemos definir la función esPrimo que no tiene ningún misterio, en la función generadorPrimos usamos filter, este comando produce una lista a partir de la que le pasamos como parámetro, pero tan solo con los elementos que cumplen la condición pasada en el primer parámetro.

Es decir, en el ejemplo devolvería una lista con los números primos entre 2 y n (inclusive), posteriormente iteramos sobre la lista de números primos y devolvemos cada uno de ellos. En el caso de los generadores se devuelve el valor con yield.

Ahora cada vez que queramos iterar sobre los números primos podemos usar el método generadorPrimos.

Al principio puede que cueste encontrar una utilidad práctica a los generadores, sin embargo pueden ayudar en multitud de ocasiones, unos ejemplos que se me ocurren, generar n números aleatorios entre a y b.

#!/usr/bin/python

from math import sqrt
import random

def generadorAleatorios(a,b,n):
        for i in range(0,n):
                yield random.randint(a, b);

for i in generadorAleatorios(1,100,10):
       print i;

O incluso se pueden ir generando IPs aleatorias válidas.

#!/usr/bin/python

from math import sqrt
import random

def generadorIPs(n):
        for i in range(0,n):
                a=random.randint(0,255);
                b=random.randint(0,255);
                c=random.randint(0,255);
                d=random.randint(0,255);
                yield str(a)+"."+str(b)+"."+str(c)+"."+str(d);

for i in generadorIPs(10):
       print i;

Cifrando los datos de un pendrive

Acostumbramos a llevar en nuestros pendrives información privada. El problema es que estos dispositivos tienen una tendencia especial a perderse :P.

Una posible solución es cifrar el sistema de ficheros del pendrive, desgraciadamente la mayoría los tenemos formateados en FAT y este sistema no admite cifrado.

Ningún problema para nosotros, si no admite cifrado el sistema de ficheros, pues nos hacemos un programa que lea el dispositivo en linux y lo cifre todo haciendo a los datos XOR con nuestra clave.

#include<stdio.h>

#define PENDRIVE "/dev/sdb1"
#define BUFFERSIZE 4096

int main(){
        int i, j, leido, nBytes;
        FILE *fichero;
        int buffer[BUFFERSIZE];

        fichero=fopen(PENDRIVE, "rw+");

        //Hallar el tamanio del fichero
        fseek(fichero, 0, SEEK_END);
        nBytes=ftell(fichero);
        fseek(fichero, 0, SEEK_SET);

        //Leer,escribir y encriptar el fichero/dispositivo
        for(i=0;i<nBytes;i+=BUFFERSIZE){
                leido=fread(buffer, 1, BUFFERSIZE, fichero);
                fseek(fichero, -leido, SEEK_CUR);

                for(j=0;j<leido;j++) buffer[j]=buffer[j]^0x12345678;

                fwrite(buffer, leido, 1, fichero);

                if(i%(BUFFERSIZE*1000)==0){
                    printf("%.1f%\n",(i*100.0)/nBytes);
                }
        }

        fclose(fichero);
}

En este caso la clave es 0x12345678 (en hexadecimal), y el dispositivo /dev/sdb1.
Sirve tanto para pendrives, disquetes, ficheros, todo en linux es un fichero.
Para desencriptarlo tan solo hay que volver a ejecutar el programa.

Si alguien intenta leer los datos del pendrive cuando están cifrados, simplemente parecerá que el pendrive no tiene formato ya que también se encripta la tabla FAT.

Evidentemente el algoritmo de encriptación se puede mejorar, tan solo es una idea.