Condición de parada

Si ya hemos elegido nuestro algoritmo favorito y la función fitness que vamos a usar, lanzamos nuestro programa y surge un problema ¿Cuando páramos?.

Lo fácil sería decir que cuando alcancemos el resultado deseado, pero eso no es siempre posible o al menos no en un tiempo que sea razonable. Así que tendremos que quedarnos con una buena aproximación. ¿Pero cual es una buen aproximación? Hay veces que lo sabemos, sabemos que resultado nos tiene que dar al función fitness para que la solución sea suficiente para nosotros. ¿Pero que pasa si no sabemos cuando ha llegado al máximo o al mínimo de la misma?. Con las metaheurísticas siempre nos quedaremos con la duda. No podemos saber si hemos encontrado el punto optimo o nos hemos quedados atrapados en un máximo/mínimo local. Todo dependerá de nuestras necesidades y conocimiento del espacio de búsqueda.

Para reducir este problema hay que intentar explorar lo máximo posible el espacio de búsqueda. El punto optimo puede esconderse en cualquier rincón que nos dejemos sin mirar. Pero claro si estamos usando una metaheurística es porque no conocemos el espacio de búsqueda y es muy grande como para que lo exploremos.

Una de las condiciones más usadas en el caso de desconocimiento total es fijar de antemano un número de iteracciones. Es útil cuando tenemos un tiempo o recursos limitados para calcular la solución. Sin embargo puede darse el caso de que el tiempo no sea tan limitante, aunque tampoco nos apetezca tener al algoritmo iterando durante varias veces la vida del universo. En ese caso se puede fijar un umbral de «mejora». De tal manera que si durante un número determinado de iteracciones el resultado no ha mejorado la solución por encima de ese umbral se para la ejecución ya que se considera que el tiempo invertido no compensa la mejora obtenida.

Por último la que me atrevería a decir que es la condición más usada pero que ningún libro habla de ella. Ir mostrando datos en pantalla y que el usuario decida cuando terminar la ejecución. Puede parecer una solución «poco inteligente» pero durante las pruebas de un algoritmo para ver qué tal se comporta con un problema o viendo si se puede afinar su configuración puede ahorrar mucho de tiempo.

De todas formas muchas veces nos obsesionamos con encontrar el resultado optimo y en la vida real muchas veces basta con una aproximación que ni siquiera sea muy buena.
 

Descenso del gradiente

Si hay una metaheurística de ascender montañas tiene que haber otra de bajarlas. El descenso del gradiente se basa en usar el gradiente de guía para encontrar el mínimo de una función. El gradiente indica la pendiente máxima en un punto y hacia donde tenemos que dirigirnos para ascender (a favor del gradiente) o descender (en contra del gradiente). Sabiendo eso solo hay que moverse en la dirección indicada por el gradiente. ¿Cuanto? Ahí está el problema. Si el paso es muy grande podrías pasarte el mínimo y si es muy corto puedes acabar dando un gran número de pasos. Cómo lo de dar un gran número de pasos solo es un problema cuando lo haces con papel y lápiz y los ordenadores no se cansan de caminar (siendo cada paso una iteración del algoritmo) es preferible el segundo caso. Cada vez que se llega a un nuevo punto se calcula el gradiente en ese punto y se avanza en esa nueva dirección.

Supongamos que aún con nuestras precauciones de dar pasitos pequeños nos pasamos del mínimo. ¿Cómo podemos saberlo?. En la imagen de debajo se puede ver un ejemplo. Primero empezamos a «rebotar» de un lado a otro de la función, mientras el valor decrezca vamos bien. El problema surge si el valor aumenta (en la imagen el paso del punto f al g) . En ese caso hemos de volver al punto anterior, reducir el tamaño del paso y seguir probando hasta que se obtenga un valor fitness menor.

descensoGradienateProblema

 

Lo ideal sería llegar a un punto donde la pendiente sea 0 (eso indica que es un máximo o un mínimo). Pero en la practica no siempre es posible y al final hemos de depender de las condiciones habituales, llegar a una solución lo suficientemente próxima a la ideal, alcanzar cierto numero de iteraciones o llegar a un tamaño de paso tan pequeño que no merezca la pena continuar.

Ya hemos visto como calcular de forma numérica la derivada y el gradiente. Ahora hemos de aplicar ese conocimiento para calcular el gradiente de la función fitness. Como el descenso del gradiente esta pensado para minimizar, hemos de elegir una función fitness que a menor valor mejor resultado.

Cada nueva coordenada seria la antigua coordenada menos el valor de la derivada de la funcion para esa coordenada multiplicado por el tamaño del paso Kstep.

cordX = cordX – (Kstep * dF/dx)

O lo que es lo mismo en código:

var grad = diff.grad(cords, this.model.calculateFitness);
for(var i = 0; i < this.parameters.dimensions; ++i){
  cords[i] -= this.parameters.step*grad[i];
}

Si el nuevo valor de fitness es menor adoptamos esas coordenadas como nueva solución, si es mayor reducimos el tamaño del paso y volvemos a probar:

if(newFitness < this.fitness){
this.cords = newCords;
this.fitness = newFitness;
} else {
this.parameters.step *= this.parameters.reduceStep;
}

El código completo puede verse aqui.

 

 

Imagen integral

La imagen integral es una técnica para acelerar el calculo de operaciones que incluyan la suma del valor de los pixeles de un área. Para calcular la imagen integral hay que reemplazar cada píxel por la suma de todos pixeles contenidos en un rectángulo cuya esquina superior izquierda es el vértice 0,0 de la imagen . Y cuya esquina inferior derecha es el propio pixel.

Veamoslo con un ejemplo, partimos de una imagen de 4×4 con lo siguientes pixeles:

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

La forma más intuitiva de verlos es como un proceso en dos iteraciones. en la primera se suman todas las celdas de cada fila de izquierda a derecha:

1 1+1=2 2+1=3 3+1=4
2 2+2=4 4+2=6 6+2=8
3 3+3=6 6+3=9 9+3=12
4 4+4=8 8+4=12 12+4=16
1 2 3 4
2 4 6 8
3 6 9 12
4 8 12 16

Luego sumamos las columnas de arriba hacia abajo:

1 2 3 4
2+1=3 4+2=6 6+3=9 8+4=12
3+3=6 6+6=12 9+9=18 12+12=24
4+6=10 8+12=20 12+18=30 16++24=40

El resultado:

1 2 3 4
3 6 9 12
6 12 18 24
10 20 30 40

Vale, tenemos una imagen con la suma de los valores de los pixeles. ¿Para qué nos sirve?. Para obtener con solo cuatro operaciones el total de la suma de de todos los pixeles de cualquier rectángulo de la imagen. Su uso es muy sencillo. Tomamos las cuatro esquinas A-B-C-D. El valor del pixel D en la imagen integral es el valor del área desde la esquina superior izquierda hasta el punto D. Le restamos el valor del área C (valor del punto C en la imagen integral) y el valor del área B (valor del punto B en la imagen integral). El problema es que ahora hemos restado una parte dos veces, por fortuna esa parte corresponde con el valor del área de A (seguro que ya sabes lo que va en estos paréntesis) solo hay que sumarlo. En resumen:

Valor del área ABCD = D – C – B + A

 

ABCD BD BD 4
CD D D 12
CD D D 24
10 20 30 40

¿Para qué sirve esto?. Se usa generalmente cuando tenemos algoritmos de ventana deslizante que necesitan calcular el valor de la suma del área comprendida por la ventana. Por ejemplo que necesiten el valor medio de un área o algún otro valor estadístico. No es necesario que lo que se sume sea el valor del pixel puede ser su cuadrado o simplemente 0 y 1 si es blanco o negro.

Es una herramienta útil para reducir los cálculos de distintos algoritmos, sobre todo de los que usan ventana deslizante.

Ventana deslizante y pirámide de imágenes

Se llama venta deslizante a seleccionar un rectángulo dentro de la imagen (la ventana) aplicar sobre él un conjunto de operaciones y luego desplazar (deslizar) la ventana un pixel y repetir el proceso, cuando llega al final de la linea se vuelve al principio y se baja una fila de pixels. Con un ejemplo se ve fácilmente, siendo los cuadros rojos la ventana seleccionada.

* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *
* * * *

Se usa principalmente para la búsqueda de características. O para aplicar algoritmos que solo tiene en cuenta la vecindad. La convolución seria un ejemplo.

Es habitual su uso con una pirámide de imágenes que no es más que usar la misma imagen pero escalandola en cada paso para reducir su tamaño. Se usa cuando el algoritmo que se aplica en la ventana deslizante es dependiente de la escala, por ejemplo un histograma no lo es, pero un detector de caras si que lo es (no se lo mismo que la ventana abarque toda la cara que que abarque solo media cara). Cada iteración de la pirámide la imagen se reduce en un porcentaje pequeño y sobre la imagen resultante se aplica la ventana deslizante.

Una explicación más visual, con una reducción del 50% (generalmente es más pequeña)

8×8

* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *
* * * * * * * *

4×4

* * * *
* * * *
* * * *
* * * *

2×2

* *
* *

Estos algoritmos suelen ser buenos candidatos a ser optimizados usando una o varias imágenes integrales.

Regresión Lineal en Arduino

La regresión lineal es útil cuando tenemos dos variables relacionadas linealmente o cuya relación se puede aproximar a la ecuación de un línea. La forma habitual de verlo es como una nube de puntos donde se calcula una recta que minimiza la distancia a todos los puntos. Se puede ver un ejemplo extraído de la wikipedia debajo:

Linear regression.svg
De Sewaqu – Trabajo propio, Dominio público, Enlace

Nosotros vamos a usarlo para calcular de forma automática la relación entre dos variables, siempre y cuando esta sea lineal. Al final del proceso obtenemos la ecuación de una recta en la forma:

y = mx + b

Para ello se parte de una muestra de valores (x, y). Estos valores no deben de coincidir exactamente con la recta (serian los puntos azules de la imagen).

Las formulas para calcular lo parámetros:

m = σ²(x,y) / σ²(x)

b = µ(y) – m * µ(x)

Siendo σ²(x,y) la covarianza, σ²(x) la varianza y µ(x) la media

El mayor problema que hay en el caso de un arduino es que no hay memoria para guardar todas las muestras así que hemos de encontrar una forma de ir calculando estos valores estadísticos sin guardar todo el histórico de datos, de forma incremental. La solución la encontré aquí.  Así no hace falta guardar todos os valores, esto ademas permite que el algoritmo este siempre aprendiendo, aunque lo veremos más adelante.

También podemos calcular la correlación entre variables. Contra más cercano a a 1 o -1 mejor ya que indica una alta correlación entre ambas variables, sin embargo si es cercano a 0 indica una nula correlación.

r = σ²(x,y) / (σ(x) * σ(y))

Siendo r la correlación y σ(x) la desviación estándar, igual a √σ²(x).

Al final los cálculos en C para el arduino de m y b quedan en:


meanX = meanX + ((x-meanX)/n);
meanX2 = meanX2 + (((x*x)-meanX2)/n);
varX = meanX2 - (meanX*meanX);

meanY = meanY + ((y-meanY)/n);
meanY2 = meanY2 + (((y*y)-meanY2)/n);
varY = meanY2 - (meanY*meanY);

meanXY = meanXY + (((x*y)-meanXY)/n);

covarXY = meanXY - (meanX*meanY);

m = covarXY / varX;
b = meanY-(m*meanX);

Y para la correlación:

double stdX = sqrt(varX);
double stdY = sqrt(varY);
double stdXstdY = stdX*stdY;
double correlation;

if(stdXstdY == 0){
  correlation = 1;
} else {
  correlation = covarXY / stdXstdY;
}

 

Limites

En la vida real lo más probable es que no nos interese aplicar la regresión lineal a todos los posibles valores de la función solo a los que están contenidos entre  dos punto para ello se fijan los limites en los que la linea esta definida en el constructor.

LinearRegression lr = LinearRegression(0,100);

Fijar el valor de N

Una de las ventajas de este algoritmo es que es capaz de ir recalculando su valor de manera dinámica según se añaden más datos. El problema es que según crece n los nuevos datos cambian la media cada vez menos. Si por ejemplo tratamos con un valor que cambia con el tiempo y queremos que la recta se vaya adaptando debemos fijar el valor de n de tal forma que lo permita. Lo complicado esta en acertar con ese valor, si es muy bajo sera muy sensible al ruido y si es muy alto necesitara mucho tiempo para adaptarse a los nuevo valores.

En este caso se puede hacer con la función fixN

lr.fixN(100);

Regresión lineal segmentada

El principal problema de la regresión lineal es que es lineal. ¿Y si necesitamos que se adapte a una distribución que no sea una linea?. Se puede conseguir algo más de flexibilidad definiendo varias lineas de regresión. Podemos dividir una distribución de puntos en varios tramos y en cada tramo calcular su linea de regresión, así en lugar de una solo linea tenemos un conjunto de ellas, para ello podemos usar lo limites que se le pasa en el constructor


LinearRegression lr = LinearRegression(0,20);

LinearRegression lr = LinearRegression(0,40);

LinearRegression lr = LinearRegression(0,60);

LinearRegression lr = LinearRegression(0,80);

LinearRegression lr = LinearRegression(0,100);

Ejemplo


#include 

LinearRegression lr = LinearRegression(0,100);

void setup() {
  lr.learn(1,3);
  lr.learn(2,4);
  lr.learn(3,5);
  lr.learn(4,6);
  lr.learn(5,7);
  lr.learn(6,8);

  Serial.begin(9600);

}

void loop() {
  Serial.print("Result: ");
  Serial.println(lr.calculate(6));

  Serial.print("Correlation: ");
  Serial.println(lr.correlation());

  Serial.print("Values: ");

  lr.getValues(values);
  Serial.print("Y = ");
  Serial.print(values[0]);
  Serial.print("*X + ");
  Serial.println(values[1]);

  delay(2000);
}

La librería esta disponible en github

Función Fitness

La función fitness suele ser una de las partes que menos  trata se habla de metaheurística. Sin embargo es de las partes más importantes, si no directamente la más. Una mala heurística puede darte una mala aproximación. Pero una mala función fitness puede darte una solución completamente acertada para un problema que no es el que tú quieres resolver.

Es mportante tener en cuenta que las metaheurísticas no resuelven el problema que tu quieres, sino el que la función fitness describe. Suena como algo obvio pero causa más quebraderos de cabeza de lo que parece. Para empezar hay veces en las que no es sencillo valorar las soluciones. Por ejemplo con problemas de combinatoria, sobre todo si hay restricciones entre los elementos, puede ser complicado decir si una solución parcial es mejor que otra y más difícil aún estimar cuánto mejor. Valorar incorrectamente estas soluciones puede causar que el algoritmo «se desvíe de su camino» o incluso que haya soluciones incorrectas con valores mejores que las correcta.

Otro problema surge cuando hay que valorar soluciones que no son válidas, por ejemplo soluciones que matemáticamente tienen sentido pero son irrealizables en la práctica. En principio lo lógico puede parecer considerarlas inválidas y no continuar por ese camino, sin embargo puede ser necesario para llegar a explorar otra zona donde si son válidas.

Rendimiento

También influye en el rendimiento del algoritmo ya que el cálculo del fitness suele ser la parte más costosa de cada iteración. Cualquier optimización de la misma repercute beneficiosamente en el tiempo que cuesta realizar cada iteración.

Precisamente por eso cabe plantearse el empezar con una versión simplificada sin las restricciones más costosas o con menos resolución y según avance el algoritmo pasar a otra más precisa y completa. Como siempre estas optimizaciones no deben afectar al «relieve» del espacio de búsqueda. En las metaheurísticas con una fase de búsqueda global y otra local también puede ser interesante usar funciones menos precisas en la búsqueda global para ahorrar tiempo.

Minimizar, maximizar, optimizar

Algunos algoritmos funcionan buscando el máximo, otros el mínimo. El resultado de la función de fitness debe de adaptarse a ello. En el caso de que tengamos una función de fitness pensada para un tipo y queramos transformarla en el otro, la forma más simple es calcular el valor máximo que puede tomar la función fitness en el espacio de búsqueda  (si no es posible conocerlo exactamente habrá que estimarlo) y restarle el valor de la función fitness en ese punto. Es decir a partir de una función de fitness F la nueva función fitness será:

f'(x) = fmax – f(x)

En resumen el resultado de la función fitness aporta la información a la metaheurística para funcionar. Si la función fitness no «dibuja un mapa» adecuado para la búsqueda da igual que metaheurística se use, no va a funcionar correctamente.

Generando números pseudoaleatorios y realmente aleatorios en Arduino

Números pseudoaletorios, función random()

Primero vamos a ver como generar números pseudoaleatorios usando la función random() de Arduino. Su uso es muy sencillo primero, normalmente en la función setup, se fija la semilla del generador usando la función randomSeed() y un valor que se le pasa como parámetro y luego se invoca a la función random() usadon una de sus dos versiones:

random(max)
random(min, max)

La primera calcula un valor entre 0 y max, la segunda entre min y max.

La semilla fijada en radomSeed() se usa para generar una secuencia de números pseudoaleatorios. A diferencia de los números aleatorios, que son distintos cada vez, los pseudoaletaorios son siempre los mismos. Cada semilla genera una secuencia única de números aleatorios que es siempre la misma. Por lo que si queremos que cada vez que reiniciemos la placa la secuencia de números sea diferente, tenemos que establecer la semilla con un valor que cambie cada vez. Hay varias opciones:

  • Tener un valor almacenado en la memoria EEPROM e incrementarlo en cada vez que se inicie el programa y usarlo como semilla.
  • Usar la función micros() que devuelve el número de microsegundos desde que el software se inicio.
  • El más habitual es usar el valor de de un puerto analógico donde no haya nada conectado.

El problema de usar estos tres métodos es que el primero es predecible y los otros dos no son realmente buenas fuentes de aleatoriedad. Sin embargo para la mayoría de los casos (que no se requieran números realmente aleatorios por seguridad) pueden ser suficientes.

Un ejemplo de uso:

long randNumber;

void setup() {
  Serial.begin(9600);  
  randomSeed(analogRead(0));
}

void loop() {
  //devuelve un número entre 0 y 300  
  randNumber = random(300);
  Serial.println(randNumber);

  //devuelve un número entre 10 y 200
  randNumber = random(10, 20);
  Serial.println(randNumber);

  delay(2000);
}

Generar números realmente aleatorios con un trozo de cable y analogRead

Si buscas una manera de generar números realmente aleatorios con Arduino se suele aconsejar recurrir a leer el valor de un puerto analógico que no este conectado a nada. El problema es que realmente los valores obtenidos no son aleatorios. Suelen oscilar en torno a un valor sin alejarse demasiado de él. Es decir si el valor leído es el 150 los más probable es que el siguiente número sea cercano, es más probable que sea el 151 que el 3. Cómo generador de números aleatorios no solo no es ninguna maravilla, es que es en muchos casos peor que el generador de números pseudoaleatorios de random()

Hay montajes electrónicos que producen valores aleatorios a partir del ruido que sufren sus componentes, pero suelen ser complicados. (Además ya no sería con un Arduino y tengo que justificar que el articulo este en la sección de «Arduino»)

Volviendo a nuestra idea de leer valores del puerto analógico vemos que el problema es que los números que devuelven oscilan entorno a un valor, esto se debe a que lo que leemos es el ruido en el puerto analógico, el ruido actúa como función aleatoria, pero este ruido tienen una característica especial, que explicada breve y mal es: «A más fuerte sea el ruido menos probable es que ocurra». Por lo tanto variaciones grandes del valor del puerto analógico son poco probables. Sin embargo hay una parte muy pequeña de este valor que si que se ve sometida a variaciones, la parte más pequeña del valor del puerto y por tanto la que más fácilmente varia, el bit de menor peso. Vamos a tomar solo ese bit y con ocho de ellos componer un byte. Ese byte debería ser aleatorio.

Para obtener el bit de menor peso podemos usar el siguiente código:

analogRead(analogInput)%2

Veamos el ejemplo para obtener un byte leyendo el puerto 8 veces:

byte randomAnalog(int analogInput){
  byte rnd = 0;
  for(int i = 0; i <; 8; i++){
    int aux = analogRead(analogInput)%2 << i; 
    rnd += aux;
    delay(10);
  }
  return rnd;
}

El delay(10) lo añadí por que sin ninguna espera analogRead me devolvía el mismo valor varias veces.

¿Pero donde esta el cable? Os preguntareis. Para aumentar el ruido, nada mejor que conectar un cable suelto en el  puerto que se va a leer, contra más largo y retorcido esté mejor.

Combinar varias fuentes

Si te fías poco de este sistema puedes usar dos fuentes, o más, de aleatoriedad obteniendo bytes de dos puertos analógicos distintos y luego combinándolos con un xor.

byte r0 = randomAnalog(A0);
byte r1 = randomAnalog(A1);

byte r = r1 ^ r0;

Puede encontrar el código en el repositorio de github de ArduTips.

Un problema que pueden tener estos sistemas es que generalmente cuando hablamos de números aleatorios nos referimos a que producen produce el bit 0 y el bit 1 con un 50% de probabilidades (lo que se denomina un sistema justo), pero en este caso no podemos estar seguros de que sea así, sin embargo hay una manera de convertir cualquier sistema aleatorio a justo se puede leer aquí.

Puedes ver la explicación en vídeo de como generar números pseudoaleatorios en mi canal de youtube:

Has click para ver el vídeo en Youtube

También esta disponible el vídeo de como generar números aleatorios:

Has click para ver el vídeo en Youtube

Cifrado seguro en Arduino

Parece imposible cifrar de forma segura en un arduino con una potencia de cálculo equiparable a la de un despertador. Pero eso es porque siempre que se habla de cifrado se acaba hablando de complicados algoritmos matemáticos, sin embargo se puede lograr un cifrado perfectamente seguro usando operaciones matemáticas más simples. Os presento la forma de cifrado más simple.

Cifrar:

Ci = Mi xor Ki

Descifrar:

Mi = Ci xor Ki

Una simple operación xor de un byte del mensaje M con un byte de la contraseña de cifrado K. Os estaréis preguntando que si es tan seguro por qué no lo usamos en lugar de complicados algoritmos. Bueno tiene una pega, la contraseña ha de ser completamente aleatoria (o en su defecto lo más aleatoria posible) y ambos han de tener la misma longitud. Este sistema se conoce como libreta de un solo uso. Su nombre no es caprichoso, usar la misma contraseña de cifrado más de una vez para cifrar otro mensaje compromete la seguridad del sistema.


//Cifrar
C[i] = M[i] ^ K[i+j]; // j es el punto del cuaderno usado hasta la fecha.

//Descifrar
M[i] = C[i] ^ K[i+j]; // j es el punto del cuaderno usado hasta la fecha.

El problema de generar la larguísima "libreta" para cifrar lo dejo en vuestras manos. Podéis usar un generador en cualquier lenguaje, comprar números aleatorios, escribir en papelitos un montón de números tirarlos a aire y apuntarlos según se recogen...hay infinitas posibilidades y contra menos predecible sea el sistema usado, mejor. De hecho esa es su principal vulnerabilidad que la secuencia usada sea predecible.

Con esa larga secuencia de bytes usados para cifrar ya conseguida. El siguiente paso es cifrar lo que se quiera enviar. Para ello se toma un byte de datos y un byte de la "libreta", se realiza un xor entre ambos y listo. Es sencillo y el coste computacional es mínimo.  Los byte de la libreta siempre se cogen de forma secuencial sin nunca repetirlos pase lo que pase.

Por supuesto todos los dispositivos que participan en la conversación tienen que tener una copia de la contraseña. Que se les ha tenido que "entregar" de forma segura (conectadolos con un cable o con una tarjeta SD) eso significa que el acceso físico a uno de estos dispositivos compromete la seguridad del cifrado (como con casi todos los sistemas). También es necesario incluir en el mensaje un numero de secuencia que indique a partir de que punto de la "libreta" usar para descifrar.

Para intentar agotar la "libreta" lo más tarde posible hay que procurar no cifrar datos innecesarios. Por otro lado, en algunos casos es necesario cifrar algún tipo de contador para votar ataques de repetición. Es posible que en algunos casos necesitemos "libretas" grandes por lo que habrá que ampliar la capacidad de almacenamiento del dispositivo por ejemplo montando un lector de tarjetas microSD con eso podemos tener espacio para una "libreta" que nos dure siglos y sale más barato que recurrir a otro tipo de soluciones.

En caso de terminar con la "libreta" hay que evitar reutilizarla. Podemos hacer un truco para tratar de alargar su utilidad. Aunque este truco no nos asegura que el cifrado vuelva a ser completamente seguro. El truco consiste en aplicar dos tipos de operaciones a la clave:

  • Intercambiar posiciones de los caracteres
  • A cada carácter aplicarle rotaciones de bits, negaciones o xor. Mejor si se combinan varias de  ellas.

Es buena idea no realizar exactamente las mismas operaciones en cada carácter si no variarlas siguiendo un patrón lo mas grande posible carácter. Estás operaciones han de conocerse por todos los dispositivos que participan en la comunicación ya que si no obtendrán "libretas" distintas.

Con eso la libreta obtenida no es segura ni mucho menos, y lo correcto seria cambiarla, pero es mejor opción que reutilizarla directamente. Como ventaja está de nuestra parte que este tipo de dispositivos suelen transferir pocos datos así que hasta que el atacante consiga una cantidad suficiente de datos como para descifrar nuestros mensajaes puede tardar mucho tiempo. Del orden de semanas, meses o años.

Diccionarios vs algoritmos generadores

El mundo está lleno de grandes enfrentamientos. Espacios vs tabuladores, Android vs iOs, …. Hoy toca diccionarios vs algoritmos generadores. El motivo del enfrentamiento es que una palabra se puede tener diversas formas, por ejemplo los verbos tienen prácticamente una forma distinta dependiendo de la persona, el tiempo o el modo. Un nombre tiene masculino y femenino y sus respectivos plurales. ¿Como recopilamos todas esas variaciones? Hay dos opciones principales: diccionarios y algoritmos generadores.

Diccionarios:

Es el más simple de entender. Almacenamos un listado con cada palabra y sus posibles variaciones.

Ventajas:

  • Es fácil de entender y de modificar.
  • No tiene problemas con las excepciones.

Inconvenientes:

  • Ocupa mucho espacio.
  • No sabe qué hacer con las palabras nuevas que no están en el diccionario.
  • Es costoso y difícil recopilar todos los casos.

Algoritmos generadores:

Se basan en usar un algoritmo que a partir de una forma de la palabra genera todas las demás.

Ventajas:

  • Ocupa poco espacio.
  • Pueden trabajar con palabras nuevas sin problemas.

Inconvenientes:

  • No pueden trabajar con excepciones.
  • Son difíciles de modificar.
  • A veces tienes que aplicar varios algoritmos para ir de una forma a otra ya que no hay uno directo.

Algoritmos generadores con diccionarios de excepciones:

Siempre hay una tercera opción que es mezclar las otras dos. Se usan algoritmos generadores para generar la nueva forma de la palabra, y solo se almacenan en el diccionario las excepciones a estos algoritmos. Ocupa menos espacio y es capaz de tener en cuenta las excepciones.

Por ejemplo, podríamos tener un algoritmo generador realmente simple que tuviera esta regla:

«Si la palabra femenina acaba en ‘a’ el masculino remplaza la ‘a’ por ‘o'»

Funciona bien la mayoría de los casos, pero sería necesario tener un diccionario que indique que el femenino de ‘vaca’ es ‘toro’ y no ‘vaco’.

Pero no todo es alegría y regocijo. Aún con este sistema es difícil ser exhaustivo y tener en cuenta todos los posibles casos. Además de que el lenguaje es algo vivo que siempre está creciendo y cambiando por lo que hay que realizar un esfuerzo por mantenerlo actualizado.

Encontrando la sílaba tónica

La sílaba tónica es aquella que se pronuncia con más énfasis en la frase. Encontrarla es útil para saber el significado de las palabras ya que muchas pueden cambiar con la pronunciación. Por ejemplo: médico, medico y medicó.

El algoritmo para encontrarla en español es muy simple. Vamos a suponer que ya tenemos la palabra dividida en sílabas. Si es monosílaba, no  y hay mucho donde elegir, está claro que esa sílaba es la tónica. Si tiene más sílabas hay que buscar cual tiene la tilde. Si no la tiene ninguna solo puede ser llana o aguda. Si termina en «n»,»s» o vocal y no tiene tilde es llana. Si termina en cualquier otra letra es aguda.

Y ya está, simple y rápido.

Este algoritmo está incluido en la librería jsESsyllable .


var syllable = new jsESsyllable();

var word = "...";
var syllables = syllable.divide(word);
var strong = syllable.stress(syllables);

Puedes probarlo online.