Contraseñas y entropía

Contraseñas y entropía

Hoy un amigo nos ha enviado un mensaje al grupo de la Promoción para ver que opinábamos al respecto de la siguiente imagen

IMG-20200902-WA0018.jpg

y yo que la he visto, instantáneamente me he acordado del cálculo necesario para rellenar esta tabla.

Lo primero de todo se debe calcular la entropía. La entropía de una contraseña es calculo matemático que representa un indicador de como se encuentra esta contraseña sobre una población, si incluimos en nuestra contraseña mayúsculas, minúsculas, números y símbolos, la entropía de nuestra contraseña será mayor puesto que la población de carcateres usados es mucho mayor, en este caso, unos 94 (26 minúsculas, 26 mayúsculas, 10 números y 32 símbolos). La fórmula es la siguiente:

entropia.png

o lo que es lo mismo, es el logaritmo en base de 2 de la cantidad de elementos de la población por la longitud de la cadena. Si efectuamos el cálculo inverso, 2 elevado a la entropía debe ser igual a la población elevada al número de caracteres de  nuestra contraseña, que esto serían el número máximo de operaciones necesarias para intentar reventar nuestra password por fuerza bruta.

Si nuestra contraseña usa solo las minúsculas, su “pool” sería de 26 y por tanto la contraseña tendría una entropía baja y fácil de descubrir.

Si hay alguien que quiera comprobar la fuerza de su contraseña online puede hacerlo desde Kaspersky
Bien, pero lo que a mi me importa es como sabemos, con código. En la clase le he incluido una penalización si nuestra contraseña se encuentra entre las más conocidas.

En C#

    /*
************************************************************************************************************************************************
    * © JOAQUIN MARTINEZ RUS 2020
    * Archivo:         PasswordEntropy.cs
    * Descripción:     Clase que calcula la entropia y el tiempo en descifrar por fuerza bruta de de una contraseña
    * Historial:
    *                  1. Joaquin Martínez Rus - 02 sep 2020. Creación
    *
    * Comentarios:
    *
    *
    ****************************************************************/
    public class PasswordEntropy
    {
        public PasswordEntropy(string password)
        {
            Password = password;

        }

        public string Password { get; set; }
        public double Entropy => GetEntropy();
        public string EntropyToString => GetTimeByEntropy(Entropy);

        private double GetEntropy()
        {
            //Pools
            double pool = 0;

            // Numbers
            pool += Password.Any(k => char.IsDigit(k)) ? 10 : 0;
            // Lower 26
            pool += Password.Any(k => char.IsLower(k)) ? 26 : 0;
            // Upper 26
            pool += Password.Any(k => char.IsUpper(k)) ? 26 : 0;
            // Simbols 30
            pool += Password.Any(k => (char.IsSymbol(k) || char.IsPunctuation(k))) ? 32 : 0;

            if (pool == 0) return pool;
            // entropy = Lenght * log pool / log2
            var p = Math.Log(pool, 2);
            var entropy = Password.Length * Math.Log(pool, 2);

            // el uso de una contraseña famosa, indica una falta de seguridad absoluta
            // por lo que no se incluye como deducción de entropía, sino que se incluye en el
            // mismo cálculo de la entropía
            if (IsFamous(Password))
            {
                entropy = (int)Entropies.NoSecurity - 1; // Inexistencia de seguridad
            }
            return entropy;
        }

        private const double OPERATIONPERSECOND = 4*10E12;

        private bool IsFamous(string password)
        {
            var list = new List()
            {
                "1234",
                "2000",
                "12345",
                "111111",
                "123123",
                "123456",
                "654321",
                "696969",
                "1234567",
                "12345678",
                "abc123",
                "alejandra",
                "america",
                "baseball",
                "bonita",
                "daniel",
                "dragon",
                "estrella",
                "football",
                "harley",
                "iloveyou",
                "jennifer",
                "jesus",
                "jordan",
                "letmein",
                "mariposa",
                "master",
                "michael",
                "monkey",
                "mustang",
                "password",
                "pussy",
                "qwerty",
                "roberto",
                "sebastian",
                "shadow",
                "superman",
                "Tequiero"
            };
            return list.Contains(password);
        }

        public enum Entropies
        {
            Blank = 0,
            NoSecurity =10,
            TooWeak=20,
            VeryWeak=28,
            Weak=35,
            Medium=55,
            Strong=75,
            Stronger=127,
            OverTheTopStrong = 190
        }

        private string GetTimeByEntropy(double entropy)
        {
            if (entropy == 0) return string.Empty;
            string output = "";

            double value = Math.Pow(2, entropy) / OPERATIONPERSECOND;
            double ms = 0;
            double seconds = value;
            double minutes = seconds / 60;
            double hours = minutes / 60;
            double days = hours / 24;
            double months = days / 30;
            double years = months / 12;
            double centuries = years / 100;
            double millennium = centuries / 10;

            seconds = value;
            if (value == 0) return "";

            if (seconds  0 && seconds  59 && minutes  59 && hours  24 && days  30 && months  11 && years  99 && centuries  1000000)
            {
                output = "Tu contraseña puede ser descifrada en más de un millón de años!";
            }
            else
            {
                millennium = Math.Round(millennium, 1);
                output = $"Tu contraseña puede ser descifrada en {millennium}, {(millennium == 1 ? "milenio" : "milenios")}";
            }

            return output;
        }
    }

static void Main(string[] args)
        {
            var password = "x#Pr0m0cio_N";

            for (int i = 1; i <= password.Length; i++)
            {
                var pwd = new PasswordEntropy(password.Substring(0,i));
                Console.WriteLine($"Password: {pwd.Password}\n{pwd.EntropyToString}");
                Console.WriteLine("Press any key");
            }

            Console.ReadKey();
        }

el resultado iterando por la contraseña que he creado


Password: x
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#P
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0m
Tu contraseña puede ser descifrada en 17, milisegundos
Press any key
Password: x#Pr0m0
Tu contraseña puede ser descifrada en 2, segundos
Press any key
Password: x#Pr0m0c
Tu contraseña puede ser descifrada en 3, minutos
Press any key
Password: x#Pr0m0ci
Tu contraseña puede ser descifrada en 4, horas
Press any key
Password: x#Pr0m0cio
Tu contraseña puede ser descifrada en 15,6, dias
Press any key
Password: x#Pr0m0cio_
Tu contraseña puede ser descifrada en 4,1, años
Press any key
Password: x#Pr0m0cio_N
Tu contraseña puede ser descifrada en 3,8, siglos
Press any key

y en Kotlin

class PasswordEntropy(val password: String) {

    init {

    }

    fun entropy(): Double {

        //Pools
        var pool = 0.0

        // Numbers
        pool += if (password.any { c -> c.isDigit() }) 10.0 else 0.0
        // Lower 26
        pool += if (password.any { c -> c.isLowerCase() }) 26.0 else 0.0
        // Upper 26
        pool += if (password.any { c -> c.isUpperCase() }) 26.0 else 0.0
        val (noSymbols, symbols) = password.partition { it.isLetter() || it.isDigit() }
        // Simbols 32
        pool += if (symbols.count()>0) 32.0 else 0.0
        if (pool == 0.0) return pool
        // entropy = Lenght * log pool / log2

        var entropy = password.length * log2(pool)

        // el uso de una contraseña famosa, indica una falta de seguridad absoluta
        // por lo que no se incluye como deducción de entropía, sino que se incluye en el
        // mismo cálculo de la entropía
        if (isFamous()) {
            entropy = 9.0 // Inexistencia de seguridad
        }
        return entropy
    }

    private fun isFamous(): Boolean{
        return listOf(
            "1234",
            "2000",
            "12345",
            "111111",
            "123123",
            "123456",
            "654321",
            "696969",
            "1234567",
            "12345678",
            "abc123",
            "alejandra",
            "america",
            "baseball",
            "bonita",
            "daniel",
            "dragon",
            "estrella",
            "football",
            "harley",
            "iloveyou",
            "jennifer",
            "jesus",
            "jordan",
            "letmein",
            "mariposa",
            "master",
            "michael",
            "monkey",
            "mustang",
            "password",
            "pussy",
            "qwerty",
            "roberto",
            "sebastian",
            "shadow",
            "superman",
            "Tequiero").contains(password)

    }
    private val OPERATION_PER_SECOND: Double = 4*10E12

    fun entropyToString(): String {
        val entropy = entropy()
        if (entropy == 0.0) return ""

        val value = 2.0.pow(entropy) / OPERATION_PER_SECOND
        var ms = 0
        var seconds = value
        val minutes = seconds / 60.0
        val hours = minutes / 60.0
        val days = hours / 24.0
        val months = days / 30.0
        val years = months / 12.0
        val centuries = years / 100.0
        val millennium = centuries / 10.0

        seconds = value
        if (value == 0.0) return ""

        return when {
            seconds  {
                ms = seconds.toInt() * 1000
                "Tu contraseña puede ser descifrada en $ms, ${if (ms == 1) "milisegundo" else "milisegundos"}"
            }
            seconds > 0 && seconds  "Tu contraseña puede ser descifrada en ${seconds.toInt()}, ${if (seconds.toInt() == 1) "segundo" else "segundos"}"
            seconds > 59 && minutes  "Tu contraseña puede ser descifrada en ${minutes.toInt()}, ${if (minutes.toInt() == 1) "minuto" else "minutos"}"
            minutes > 59 && hours  "Tu contraseña puede ser descifrada en ${hours.toInt()}, ${if (hours.toInt() == 1) "hora" else "horas"}"
            hours > 24 && days  "Tu contraseña puede ser descifrada en ${days.toInt()}, ${if (days.toInt() == 1) "dia" else "dias"}"
            days > 30 && months  "Tu contraseña puede ser descifrada en ${months.toInt()}, ${if (months.toInt() == 1) "mes" else "meses"}"
            months > 11 && years  "Tu contraseña puede ser descifrada en ${years.toInt()}, ${if (years.toInt() == 1) "año" else "años"}"
            years > 99 && centuries  "Tu contraseña puede ser descifrada en ${"%.1f".format(centuries)}, ${if (centuries == 1.0) "siglo" else "siglos"}"
            millennium > 1000000 -> "Tu contraseña puede ser descifrada en más de un millón de años!"
            else -> "Tu contraseña puede ser descifrada en ${millennium.toInt()}, ${if (millennium.toInt() == 1) "milenio" else "milenios"}"
        }
    }

}

fun main(){
    val password = "x#Pr0m0cio_N";

    for (i in (1..password.length)) {
        val pwd = PasswordEntropy(password.substring(0,i))
        println("Password: ${pwd.password}\n${pwd.entropyToString()}\n")

    }
}

el resultado para Kotlin


Password: x
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#P
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0
Tu contraseña puede ser descifrada en 0, milisegundos
Press any key
Password: x#Pr0m
Tu contraseña puede ser descifrada en 17, milisegundos
Press any key
Password: x#Pr0m0
Tu contraseña puede ser descifrada en 2, segundos
Press any key
Password: x#Pr0m0c
Tu contraseña puede ser descifrada en 3, minutos
Press any key
Password: x#Pr0m0ci
Tu contraseña puede ser descifrada en 4, horas
Press any key
Password: x#Pr0m0cio
Tu contraseña puede ser descifrada en 15,6, dias
Press any key
Password: x#Pr0m0cio_
Tu contraseña puede ser descifrada en 4,1, años
Press any key
Password: x#Pr0m0cio_N
Tu contraseña puede ser descifrada en 3,8, siglos
Press any key

Saludos a la X Promoción del IPE 2!!!

Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional

Interface. Genetic Algorithm II

Interface. Genetic Algorithm II
En este post veremos como un algoritmo genético es capaz de ordenar un tablero de ajedrez. Es como si un niño de 2 años pusiera las piezas aleatoriamente en el tablero y el algoritmo se encargara de poner cada una en su sitio.

Crearemos una clase ChessPiece para cada figura de ajedrez y una clase ChessBoard que implementará la interfaz IMutable. Esto quiere decir que nuestro cromosoma es una lista de piezas de ajedrez y que el Fitness es del tipo doble.
Acto seguido, creamos el geneset o conjunto de genes que formarán el cromosoma donde incluiremos también la casilla vacía. Luego le daremos un valor a cada pieza y otro valor a cada casilla, cada vez que se acierte, el fitness se verá incrementado hasta el 100%.

class ChessBoard : IMutable {
    override val geneset = mutableListOf(
            ChessPiece("T",ChessPieceColor.BLACK,11),
            ChessPiece("C",ChessPieceColor.BLACK,13),
            ChessPiece("A",ChessPieceColor.BLACK,15),
            ChessPiece("D",ChessPieceColor.BLACK,16),
            ChessPiece("R",ChessPieceColor.BLACK,18),
            ChessPiece("A",ChessPieceColor.BLACK,15),
            ChessPiece("C",ChessPieceColor.BLACK,13),
            ChessPiece("T",ChessPieceColor.BLACK,11),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("P",ChessPieceColor.BLACK,4),
            ChessPiece("T",ChessPieceColor.WHITE,10),
            ChessPiece("C",ChessPieceColor.WHITE,12),
            ChessPiece("A",ChessPieceColor.WHITE,14),
            ChessPiece("D",ChessPieceColor.WHITE,17),
            ChessPiece("R",ChessPieceColor.WHITE,19),
            ChessPiece("A",ChessPieceColor.WHITE,14),
            ChessPiece("C",ChessPieceColor.WHITE,12),
            ChessPiece("T",ChessPieceColor.WHITE,10),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5),
            ChessPiece("P",ChessPieceColor.WHITE,5))

    init {

        geneset.addAll((1..32).map { ChessPiece("_",ChessPieceColor.EMPTY,0) })
    }

    override val target: Double = 64.0
    override var bestParent = createParent(0)
    override var bestFitness: Double = 0.0
    private val values = mutableListOf(11,13,15,16,18,15,13,11,4,4,4,4,4,4,4,4,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,0,0,0,0,0,0,5,5,5,5,5,5,5,5,10,12,14,17,19,14,12,10)

    override fun isSuccess(): Boolean = bestFitness == 1.0

    var result=""
    override fun start() {
        bestFitness = getFitness(bestParent)
        var childFitness: Double
        var child: MutableList
        //Display(bestParent, bestFitness)
        var attemps=0

        do {
            do {
                child = mutate(bestParent)
                childFitness = getFitness(child)

            } while (bestFitness > childFitness)

            bestFitness = childFitness
            bestParent = child
            result +=toShortString() + "\n\n\n"
            attemps ++
            println(toShortString() + "\n")
        } while (!isSuccess())
        println("Nº de intentos: $attemps")
    }

    override fun createParent(param: Any): MutableList {
        // llena el tablero con las 32 fichas piezas + 32 vacias
        return geneset.shuffled().toMutableList()
    }

    override fun getFitness(obj: MutableList): Double = obj.mapIndexed { index, chessPiece -> if (values[index] == chessPiece.value) 1.0 else 0.0  }.sum() / target

    override fun mutate(parent: MutableList): MutableList {
        val parentFitness: Double = getFitness(parent)
        var childFitness = 0.0
        var child = mutableListOf()

        do {
            child.clear()
            child.addAll(parent)

            val startIndex = Random.nextInt(bestParent.size)
            val endIndex = Random.nextInt(bestParent.size)
            val start = parent[startIndex]
            val end = parent[endIndex]
            child[startIndex] = end
            child[endIndex] = start
            childFitness = getFitness(child)

        }while (childFitness chessPiece.toString() + if ((index+1) % 8 ==0) "\n" else "\t" }
            .joinToString("")}\nFitness: $bestFitness"

    fun toShortString(): String ="${bestParent
                    .mapIndexed { index, chessPiece -> (if (chessPiece.value==0) " " else if (chessPiece.value == values[index]) (if (chessPiece.color==ChessPieceColor.WHITE) "○" else "●") else "#")+if ((index+1) % 8 == 0) "\n" else "" }
                    .joinToString("")
        }\nFitness: ${"%.3f".format(bestFitness)}"
    fun  foo(collection: MutableList){

    }
}

fun main(){
    val chessBoard = ChessBoard()
    chessBoard.start()
    println(chessBoard.bestParent)
}

Y este es el resultado del progreso de los cromosomas para 36 intentos
cromosomas.png

TN	CN	AN	DN	RN	AN	CN	TN
PN	PN	PN	PN	PN	PN	PN	PN
__	__	__	__	__	__	__	__
__	__	__	__	__	__	__	__
__	__	__	__	__	__	__	__
__	__	__	__	__	__	__	__
PB	PB	PB	PB	PB	PB	PB	PB
TB	CB	AB	DB	RB	AB	CB	TB

Fitness: 1.0

Y ahora implementaremos la interfaz con mi mejor amigo, C#

 public class ChessPiece
    {
        public ChessPiece(string name, Colors color, int value)
        {
            Name = name;
            ChessPieceColor = color;
            Value = value;
        }

        public string Name { get; set; }
        public int Value { get; set; }
        public Colors ChessPieceColor { get; set; }

        public enum Colors
        {
            Black,
            White,
            Empty
        }

        public string ColorToString => ValueToString(ChessPieceColor);

        public new string ToString => $"{Name}{ColorToString}";

        private string ValueToString(Colors color)
        {
            switch (color)
            {
                case Colors.Black:
                    return "N";
                case Colors.White:
                    return "B";
                case Colors.Empty:
                    return "_";
                default:
                    return "";
            }
        }

    }

    public class ChessBoard : IMutable
    {
        public ChessBoard()
        {
            Geneset = new List()
            {
                    new ChessPiece("T", ChessPiece.Colors.Black, 11),
                    new ChessPiece("C", ChessPiece.Colors.Black, 13),
                    new ChessPiece("A", ChessPiece.Colors.Black, 15),
                    new ChessPiece("D", ChessPiece.Colors.Black, 16),
                    new ChessPiece("R", ChessPiece.Colors.Black, 18),
                    new ChessPiece("A", ChessPiece.Colors.Black, 15),
                    new ChessPiece("C", ChessPiece.Colors.Black, 13),
                    new ChessPiece("T", ChessPiece.Colors.Black, 11),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("P", ChessPiece.Colors.Black, 4),
                    new ChessPiece("T", ChessPiece.Colors.White, 10),
                    new ChessPiece("C", ChessPiece.Colors.White, 12),
                    new ChessPiece("A", ChessPiece.Colors.White, 14),
                    new ChessPiece("D", ChessPiece.Colors.White, 17),
                    new ChessPiece("R", ChessPiece.Colors.White, 19),
                    new ChessPiece("A", ChessPiece.Colors.White, 14),
                    new ChessPiece("C", ChessPiece.Colors.White, 12),
                    new ChessPiece("T", ChessPiece.Colors.White, 10),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5),
                    new ChessPiece("P", ChessPiece.Colors.White, 5)
            };

            Geneset.AddRange(Enumerable.Range(0, 32).ToList().Select(k => new ChessPiece("_", ChessPiece.Colors.Empty, 0)));           

        }

        public List Geneset { get; set; }
        public double Target { get; set; } = 64;
        public List BestParent { get; set; }
        public double BestFitness { get; set; }

        private Random rnd = new Random();
        private IList Values = new List() { 11, 13, 15, 16, 18, 15, 13, 11, 4, 4, 4, 4, 4, 4, 4, 4, 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, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 10, 12, 14, 17, 19, 14, 12, 10 };
        private string result = "";

        public List CreateParent(object param) => Suffled(Geneset);

        public double GetFitness(List obj) => obj
            .Select((item, index) => new { Item = item, Index = index })
            .Select(k => k.Item.Value == Values[k.Index] ? 1.0 : 0.0)
            .Sum()/Target;

        public bool IsSuccess() => BestFitness == 1.0;

        public List Mutate(List parent)
        {

            var parentFitness = GetFitness(parent);
            var childFitness = 0.0;
            var child = new List();

            do
            {
                child.Clear();
                child.AddRange(parent);

                var startIndex = rnd.Next(BestParent.Count());
                var endIndex = rnd.Next(BestParent.Count());
                var start = parent[startIndex];
                var end = parent[endIndex];

                child.RemoveAt(startIndex);
                child.Insert(startIndex, end);
                child.RemoveAt(endIndex);
                child.Insert(endIndex, start);

                childFitness = GetFitness(child);
                //print(child);
            } while (childFitness k.Value)));
        }

        public void Start()

        {
            BestParent = CreateParent(null);
            BestFitness = GetFitness(BestParent);
            var childFitness = 0.0;
            var child = new List();

            var attemps = 0;
            do
            {
                do
                {
                    child = Mutate(BestParent);
                    childFitness = GetFitness(child);
                } while (BestFitness > childFitness);

                BestFitness = childFitness;
                BestParent = child;
                result += ToShortString + "\n\n\n";
                Console.WriteLine(result);
                attemps++;
            } while (!IsSuccess());

            Console.WriteLine(ToShortString + "\n");
            Console.WriteLine($"Nº intentos: {attemps}");
        }

        private List Suffled(List source) => source
            .Select(x => new { value = x, order = rnd.Next() })
            .OrderBy(x => x.order).Select(x => x.value).ToList();

        public new string ToString => $"{string.Join("",BestParent.Select((item, index) => new { Item = item, Index = index }).Select(k => k.Item.ToString + (((k.Index + 1) % 8 == 0) ? '\n' : ' '))) }";
        public string ToShortString => $"{string.Join("",BestParent.Select((item, index) => new { Item = item, Index = index }).Select(k => (k.Item.Value == 0 ? " " : (k.Item.Value == Values[k.Index]) ? (k.Item.ChessPieceColor == ChessPiece.Colors.White ? "O" : "■") : "#") + (((k.Index + 1) % 8 == 0) ? '\n' : ' '))) }";

    }
 class Program
    {
        static void Main(string[] args)
        {
            var chessboard = new ChessBoard();
            chessboard.Start();
            Console.WriteLine(chessboard.ToString);
            Console.WriteLine("Press any key...");
            Console.ReadKey();
        }
    }

Si quieres leer mi anterior post sobre la interface de algoritmos genéticos, aquí lo tienes.

Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

Interface. Genetic Algorithm I

Interface. Genetic Algorithm I

¿Cómo conseguir un objetivo por los mismos medios por los que una especie sobrevive? La respuesta es, mutando y cruzándo sus individuos para obtener ese objetivo.

Los algoritmos genéticos desde el punto de vista del desarrollo de software, tienen casi todos un patrón único y si tienen un patrón único atienden a una estructura común, por tanto es como cualquier interface, atienden siempre a la misma composición, de modo que ¿Por qué no generamos una interface que implemente este comportamiento? ¿Por qué crear una interface? Generamos una interface porque esperamos que cualquier clase que implemente esta interface haga lo mismo y la interface es el elemento adecuado. (¿he entrado en bucle? uhmmm). Para saber más acerca de interfaces, aquí tiene un artículo de Wakicode.

Bien, la verdad que he buscado y “requetebuscado” (que dicen en mi tierra) y no he visto nada parecido acerca de una interface de algoritmo genéticos.

Un algoritmo genético tiene los siguientes elementos:

  • Un conjunto de genes en los que se basan cada uno de objetos generados
  • Un patrón inicial o digamos un Adán o una Eva
  • Un candidato a ser el mejor de la especie
  • Un indicador métrico de aptitud del mejor de la especie

y efectua las siguientes tareas:

  • Inicia el algoritmo
  • Crea el patrón inicial
  • Obtiene la métrica de cualquier objeto de la especie. Función de Aptitud
  • Ejecuta un cruce entre individuos de la especie. Cruce
  • Ejecuta una mutación sobre un objeto. Mutación
  • Comprueba si se ha cumplido con el objetivo. Criterio de parada
  • Si no se ha conseguido el objetivo, volvemos a realizar la tarea
  • Obtención de la solucióndiagrama algoritmo genetico.png

Además un algoritmo genético no tiene porque realizar un cruce porque a lo mejor nuestro problema lo podemos solucionar mutando solamente sus genes sin realizar cruce. Cada algoritmo hay que estudiarlo

Dicho esto nos ponemos manos a la obra y vamos a desarrollar una interfaz que tenga estos elementos y que nos permita realizar estas acciones con diferentes tipos. En principio voy a crear una interface del tipo Mutable y luego heredaré de esta para crear una nueva Crossover  con funciones de cruce.

En Kotlin

/**
 * @author Joaquin Martinez Rus ©
 * @since 15AGO20
 * version 1.1
 */
interface IMutable
{
    val geneset: T
    val target: F
    var bestParent: T
    var bestFitness: F

    /**
     * Return true when target is reached
     * @return Boolean
     */
    fun isSuccess(): Boolean

    /**
     * Start algorithm
     * @sample
     * CreateParent
     * Mutate
     * GetFitness
     * Compare
     * IsSuccess
     */
    fun start()

    /**
     * Return a new parent object
     * @param Parameter of generation
     * @return Type T
     */
    fun createParent(param: Any): T

    /**
     * Get object fitness
     * @return F value
     */
    fun getFitness(obj: T): F

    /**
     * Return a mutation of a parent object
     * @param Parent element
     * @return type T mutated
     */
    fun mutate (parent: T): T
}

/**
 * @author Joaquin Martinez Rus ©
 * @since 15AGO20
 * version 1.1
 */
interface ICrossOver : IMutable
{
    /**
     * Return a crossover of two objects of same type
     * @param Parent element
     * @return type T crossed over
     */
    fun crossOver(father: T, mother: T): T
}

y en C#

/* ************************************************************************************************************************************************
    * © JOAQUIN MARTINEZ RUS 2020
    * Archivo:         Imutable.cs
    * Descripción:     Interface que implementa un algoritmo genético de mutación
    * Historial:
    *                  1. Joaquin Martínez Rus - 15 ago 2020. Creación
    *
    * Comentarios:
    *
    *
    **************************************************************************************************************************************************/
    public interface IMutable where F : IComparable
    {
        public T Geneset { get; set; }
        public F Target { get; set; }
        public T BestParent { get; set; }
        public F BestFitness { get; set; }

        ///
        /// Return true when target is reached
        /// 

        /// Boolean
        bool IsSuccess();

        ///
        ///  Start algorithm
        ///  Example
        ///  CreateParent
        ///  Mutate
        ///  Getfitness
        ///  Compare
        ///  IsSuccess
        /// 

        void Start();

        ///
        /// Return a new parent object
        /// 

        /// Parameter of generation
        /// Type T
        T CreateParent(object param);

        ///
        /// Get object fitness
        /// 

        /// Object from which the fitness is obtained
        /// F Value
        F GetFitness(T obj);

        ///
        /// Return a mutation of a parent object
        /// 

        /// Parent element
        /// T mutated
        T Mutate(T parent);

    }

    /* ************************************************************************************************************************************************
    * © JOAQUIN MARTINEZ RUS 2020
    * Archivo:         ICrossOver.cs
    * Descripción:     Interface que implementa un algoritmo genético de mutación y cruce
    * Historial:
    *                  1. Joaquin Martínez Rus - 15 ago 2020. Creación
    *
    * Comentarios:
    *
    *
    **************************************************************************************************************************************************/
    public interface ICrossOver : IMutable where F: IComparable
    {
        ///
        /// Return a crossover of two objects of same type
        /// 

        /// Fateher
        /// Mother
        /// type T crossed over
        T CrossOver(T father, T mother);

    }

Analicemos la interface.Lo primero. La interface es una interface genérica con dos tipos, T es el tipo del objeto del algoritmo y F es el tipo de la propiedad Fitness que obligatoriamente debe ser comparable. Este será el cromosoma.
Cuatro propiedades, un geneset o conjunto de genes, el objetivo que pretenderá alcanzar el algoritmo (target), un objeto genérico como mejor individuo de su especie (bestParent) y un indicador de aptitud del mejor de los individuos (bestFitness).
Luego tenemos 5 métodos, método start para iniciar el algoritmo, un método createParent que creará el primero de la especie al cual le he incluido un parámetro por si quisiéramos determinar alguna particularidad sobre él, un método mutate que mutará un objeto en otro, un método getFitness que obtiene la aptitud y por último otro método booleano que determina si el algoritmo ha cumplido su objetivo (isSuccess).La interface ICrossOver hereda de esta añadiéndole un método más llamado crossOver con dos parámetros o padre y madre del objeto resultante.Si ahora creamos una clase que implemente esta interface, nos aseguramos que como mínimo tendremos que desarrollar los elementos de la interface, más fácil imposible. ¿Dónde tenemos que estrujarnos el cerebro? en diseñar el tipo de cromosoma, el objetivo como debe alcanzarse o en como debe mutar. No es poco, pero si tienes poca experiencia con algoritmos genéticos, esta es tu interface.

En la práctica, vamos a generar un algoritmo sencillo que adivine una frase. Esto tan fácil como crear una clase que implemente IMutable y en nuestro IDE nos aparecerá en rojo indicándonos que algo mal. La mayoría de los IDE,s tiene un asistente, una bombilla, una herramienta, un algo que al pulsar sobre él nos indica que algo está pasando y este dirá “implement as constructor parameters”, seleccionamos las propiedades y et voilá, propiedades en la clase, pulsamos de nuevo y nos dirá implement members.

genetics01.jpg.png

Al pulsar, seleccionamos todos lo métodos y clase lista. Ahora el código

genetics02.png
Y aquí la clase con su código, esta solo mutará por tanto implementa IMutable, donde el algoritmo intentará adivinar unos preciosos versos de Mario Benedetti “Corazón coraza” con 334 caracteres.
El algoritmo creará una cadena aleatoria inicialmente e irá mutando hasta llegar al objetivo deseado.

class GuessString (override val target: Double, override val geneset: String) : IMutable{
    val guess = "Porque te tengo y no porque te pienso\n" +
            "porque la noche está de ojos abiertos\n" +
            "porque la noche pasa y digo amor\n" +
            "porque has venido a recoger tu imagen\n" +
            "y eres mejor que todas tus imágenes\n" +
            "porque eres linda desde el pie hasta el alma\n" +
            "porque eres buena desde el alma a mí\n" +
            "porque te escondes dulce en el orgullo\n" +
            "pequeña y dulce\n" +
            "corazón coraza"
    override var bestParent: String = createParent(guess.length)
    override var bestFitness: Double = getFitness(bestParent)
    private var attempts = 0

    init {
        start()
    }

    override fun start()
    {
        var childFitness: Double
        var child: String

        do {
            do {
                child = mutate(bestParent)
                childFitness = getFitness(child)
            } while (bestFitness >= childFitness)

            bestFitness = childFitness
            bestParent = child
            attempts ++
        } while (!isSuccess())
        println("Intentos: $attempts")
    }

    override fun isSuccess(): Boolean {
        val value = (bestFitness.toString().toDouble() / guess.length)
        return value >= target
    }

    override fun createParent(param: Any) : String {
        val genes = StringBuilder()
        val length = geneset.length
        (0 until param.toString().toInt()).forEach {
            genes.append(geneset[Random.nextInt(length)])
        }

        return genes.toString()
    }

    override fun getFitness(obj: String): Double = guess.mapIndexed { i, c -> if (c==obj[i]) 1.0 else 0.0}.sum()

    override fun mutate(parent: String): String {
        var index = 0
        val parentFitness: Double = getFitness(parent)
        var childFitness = 0.0

        var newGene: Char
        var alternate: Char
        var definitive: Char
        var indexGeneset: Int
        var child: String

        var length =  geneset.length

        do {
            index = Random.nextInt(parent.length)
            indexGeneset = Random.nextInt( length)

            newGene = geneset[indexGeneset]

            indexGeneset = Random.nextInt( length)
            alternate = geneset[indexGeneset]
            //definitivo
            definitive = if (newGene == parent[index]) alternate else newGene

            child = parent.replaceRange(index,index+1, definitive.toString())

            childFitness = getFitness(child)

        } while (parentFitness >= childFitness)

        return child
    }
}

fun main() {
val guess =GuessString(
        1.0,
        " áéíóúabcdefghijklmnñopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ,\n")
println(guess.bestParent)
}

Y el resultado

Intentos: 328
Porque te tengo y no porque te pienso
porque la noche está de ojos abiertos
porque la noche pasa y digo amor
porque has venido a recoger tu imagen
y eres mejor que todas tus imágenes
porque eres linda desde el pie hasta el alma
porque eres buena desde el alma a mí
porque te escondes dulce en el orgullo
pequeña y dulce
corazón coraza

Pues aquí tenéis mi interface para algoritmos genéticos.
En el próximo post, veremos un algoritmo genético que posicionará las piezas de ajedrez en su sitio.
Pd: En realidad, la clase de adivinar no es gran cosa, porque se podría haber conseguido por iteración, pero entonces no habriáis aprendido el algortimo genético. Entonces, espero que os haya servido. 😉
Podía haber elegido a Antonio Machado a Calderón de la Barca o a cualquier otro poeta o poema, pero, este me parece especialmente bello. Leedlo completo, es corto, tres estrofas.
Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.

Descomposición factorial con hilos II

Descomposición factorial con hilos II
Y ahora vamos a emular un lugar donde se descomponen los números y cada vez que se encuentra uno, se obtiene y se muestra su descomposición.

Para realizar esto, usaremos los monitores de Java, los métodos wait() y notify(). Estos métodos tienen que ir siempre incluidos sobre métodos marcados como syncronized o usar el método syncronized(metodo sincronizado). wait() y notify() (hay alguno más) heredan del Object, por lo que todos los objetos que hereden de esta clase, lo tienen disponible.

¿Que hace wait()? suspende indefinidamente el hilo hasta que se reanude con notify().

Así que crearé una clase que solicitará la descomposición del número, el cual es enviado al supuesto servidor compartido de descomposiciones factoriales, este se encarga de descomponerlo (tarea dura) y una vez que termine, habrá un receptor de datos esperando a su finalización para mostrar su descomposición.

DESC

La clase SolicitudDescomposicionVisualizadorDescomposicion heredan de Thread, los iniciamos desde la clase principal y a trabajar por parte del servidor. He aquí el código:

public static void main(String[] args) {
        // TODO code application logic here
        
        ServidorDescomposicion r=new ServidorDescomposicion();
        for (int i = 0; i < 10; i++) {
            SolicitudDescomposicion productor=new SolicitudDescomposicion(i, r);
            VisualizadorDescomposicion consumidor=new VisualizadorDescomposicion(i, r);
            
            productor.start();
            consumidor.start();
        }
        
    }
public class SolicitudDescomposicion extends Thread {
    
    ServidorDescomposicion r;
    
    public SolicitudDescomposicion(int n, ServidorDescomposicion _r){
        this.setName("Productor " + n);
        r=_r;
    }
    
    @Override
    public void run(){
        int n=Math.abs(new Random().nextInt());
        System.out.println("Enviando número descomposición desde el productor:\t" + n);
        r.descomponerNumero(n);
    }
}

public class VisualizadorDescomposicion extends Thread{
    
    ServidorDescomposicion r;
    
    public VisualizadorDescomposicion(int n, ServidorDescomposicion _r){
        this.setName("Consumidor " + n);
        r=_r;
    }
    
    @Override
    public void run(){        
        String desc="";
        try {
            desc = r.getDescomposicion();
        } catch (InterruptedException ex) {
            Logger.getLogger(VisualizadorDescomposicion.class.getName()).log(Level.SEVERE, null, ex);
        }
        System.out.println("Datos obtenidos desde el consumidor.Resultado:\t\t" + desc);        
    }
}
public class ServidorDescomposicion {

    ArrayList buffer;
    boolean existData;


    //&& estado.equals(estadoEnum.DESCOMPONIENDO
    //&& estado.equals(estadoEnum.LIBRE)
    public ServidorDescomposicion() {
        buffer = new ArrayList();
    }

    public synchronized void descomponerNumero(int numero) {
        descomponer(numero);
    }

    void retardo(int ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException ex) {
            Logger.getLogger(ServidorDescomposicion.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public synchronized String getDescomposicion() throws InterruptedException {
        
        while(!existData){
            try {
                wait();
            } catch (InterruptedException ex) {
                Logger.getLogger(ServidorDescomposicion.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        
        String descomposicion = "";
        descomposicion = buffer.remove(0);
        if (buffer.size()==0) {
            existData=false;
        }
        notify();
        
        return descomposicion;
    }

    void descomponer(int numero) {
        // Cálculos y resultados
        int iniNum = numero;
        int numeroAux = numero;
        int n = 0;
        int nn = 0;

        String text = "";
        String puntos = ".";

        for (long i = 2; i < numero; i++) { 
            while (numeroAux % i == 0) {
                numeroAux /= i;
                text += i + ".";
                if (numeroAux == 1) {
                    numero = numeroAux;
                }
            }
        }
        if (text.isEmpty()) {
            System.out.printf("El número %s es primo!\n", iniNum);
            text = String.valueOf(iniNum);
        }
        buffer.add(String.format("%s=%s", iniNum, text));
        existData=true;

    }

}

y el resultado para 10 números enteros


Enviando número descomposición desde el productor:	1007666687
Enviando número descomposición desde el productor:	233955388
Enviando número descomposición desde el productor:	403028651
Enviando número descomposición desde el productor:	1405658987
Enviando número descomposición desde el productor:	809322159
Enviando número descomposición desde el productor:	263332588
Enviando número descomposición desde el productor:	1552584352
Enviando número descomposición desde el productor:	1342709543
Datos obtenidos desde el consumidor.Resultado:		1007666687=17.31.43.53.839.
Datos obtenidos desde el consumidor.Resultado:		1342709543=7.191815649.
Datos obtenidos desde el consumidor.Resultado:		1552584352=2.2.2.2.2.11.89.49559.
Datos obtenidos desde el consumidor.Resultado:		263332588=2.2.487.135181.
Datos obtenidos desde el consumidor.Resultado:		809322159=3.113.733.3257.
Datos obtenidos desde el consumidor.Resultado:		403028651=67.6015353.
Datos obtenidos desde el consumidor.Resultado:		233955388=2.2.31.443.4259.
Datos obtenidos desde el consumidor.Resultado:		1405658987=127.199.55619.

Saludos

Descomposición factorial con hilos I

Descomposición factorial con hilos I

Un ejemplo de aprovechamiento de recursos sobre procesos penosos en los que ponemos el pc a prueba, puede ser la descomposición de números grandes en factores primos. En este ejemplo sobre la plataforma Java, se descomponen números del tipo Long con un método estándar (no muy eficiente) con una clase que implementa la Interfaz Runnable. A la clase le pasamos un número como parámetro y otro de identificador.Si creamos varios hilos, cada uno descomponiendo un número grande, aprovechará los distintos núcleos para el cálculo. Este es el resultado para números enteros pequeños mostrando el número de hilos vivos.

INICIO Hilo nº0-> Descomposición de 1763458
INICIO Hilo nº2-> Descomposición de 882375341
INICIO Hilo nº3-> Descomposición de 396209470
INICIO Hilo nº1-> Descomposición de 1633289887
Hilo nº 0-> Descomponiendo 1763458. Nº iteraciones: 1
Hilo nº 2-> Descomponiendo 882375341. Nº iteraciones: 96
Hilo nº 3-> Descomponiendo 396209470. Nº iteraciones: 1
Hilo nº 3-> Descomponiendo 198104735. Nº iteraciones: 4
Hilo nº 3-> Descomponiendo 39620947. Nº iteraciones: 18
Hilo nº 3-> Descomponiendo 2085313. Nº iteraciones: 210
Hilo nº 1-> Descomponiendo 1633289887. Nº iteraciones: 66
Hilo nº 1-> Descomponiendo 24377461. Nº iteraciones: 100
Hilo nº 3-> Descomponiendo 9883. Nº iteraciones: 9882
FIN Hilo nº 3-> 396209470 = 2*5*19*211*9883*. Nº iteraciones: 9882
Quedan 3 hilos vivos
Hilo nº 2-> Descomponiendo 9096653. Nº iteraciones: 1810
Hilo nº 2-> Descomponiendo 5023. Nº iteraciones: 5022
FIN Hilo nº 2-> 882375341 = 97*1811*5023*. Nº iteraciones: 5022
Quedan 2 hilos vivos
Hilo nº 1-> Descomponiendo 241361. Nº iteraciones: 241360
FIN Hilo nº 1-> 1633289887 = 67*101*241361*. Nº iteraciones: 241360
Quedan 1 hilos vivos
Hilo nº 0-> Descomponiendo 881729. Nº iteraciones: 881728
FIN Hilo nº 0-> 1763458 = 2*881729*. Nº iteraciones: 881728
Quedan 0 hilos vivos

Y el código de las clases…

Clase Main

package Descompositor;

import java.util.Random;

// <editor-fold defaultstate="collapsed" desc="Cabecera de clase">
/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2017
 *  @version:   1.0
 *  File:       Main.java
 *  Created:    29/11/2017
 *  Project:    PSP. Ejemplo de descomposición multihilo.
 *  Comments:
 *******************************************************/
// </editor-fold>
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        for (int i = 0; i < 5; i++) {
            Descomposicion d=new Descomposicion(Math.abs(new Random().nextLong()),i);
            Thread hilo=new Thread(d);
            hilo.start();
        }
    }
}

y la clase encargada de la descomposición

package Descompositor;
import java.util.Date;
// <editor-fold defaultstate="collapsed" desc="Cabecera de clase">
/******************************************************
 *  @author:    Joaquín Martínez Rus (c) 2017
 *  @version:   1.0
 *  File:       Descomposicion.java
 *  Created:    29/11/2017
 *  Project:    PSP. Ejemplo de descomposición multihilo.
 *  Comments:
 *******************************************************/
// </editor-fold>
public class Descomposicion implements Runnable{

    public Descomposicion(long n, int j){
        this.name=j;
        this.number=n;
        Descomposicion.instanciasVivas++;
    }

    public static int instanciasVivas;
    int name;
    long number;

    @Override
    public void run() {
        descomponer(number, name);
    }

    void descomponer(long numero, int j){
        // Cálculos y resultados

        long iniNum=numero;
        long numeroAux = numero;
        long n=0;
        int nn=0;

        System.out.printf("INICIO Hilo nº%s-> Descomposición de %s\n" , j, numeroAux);
        String text="";
        String puntos=".";

        for (long i = 2; i 1000000000) {
                nn++;
                String cadena="Hilo Nº %s-> Seguimos calculando para %s...\n";
                if (nn>2) {
                    if (text.isEmpty()) {
                        cadena = "Hilo Nº %s-> parece que el número %s es primo...\n";
                    }
                    else{
                        cadena ="Hilo Nº %s-> No es primo y seguimos calculando para %s...\n";
                        nn=0;
                    }
                }
                System.out.printf(cadena, j, numeroAux);
                n=0;

            }
            // DESCOMPOSICIÓN
            while (numeroAux % i == 0) {
                System.out.printf("Hilo nº %s-> Descomponiendo %s. Nº iteraciones: %s\n",j, numeroAux, n);
                numeroAux /= i;
                text += i + "*";
                if (numeroAux == 1) {
                    numero=numeroAux;
                }
            }
        }
        if (text.isEmpty()){
            System.out.printf("El número %s es primo!\n",iniNum);
            text = String.valueOf(iniNum);
        }
        System.out.printf("FIN Hilo nº %s-> %s = %s. Nº iteraciones: %s\n",j, iniNum, text, n);

        Descomposicion.instanciasVivas--;
        System.out.printf("Quedan %s hilos vivos\n",Descomposicion.instanciasVivas);

    }
}

Os adjunto el proyecto de NetBeans.

Saludos

 

Distancia de Levenshtein

Distancia de Levenshtein

La distancia de Levenshtein es el número mínimo que necesitamos para convertir una palabra en otra, un ejemplo pelo y perro tienen una distancia de 2 porque tendríamos que sustituir la l por una r y añadir una r, dos movimientos, distancia 2. Otro ejemplo, murcielago y muerdago que tienen una distancia de 5, ya que a murciélago le tenemos que quitar c,i,e,l y a muerdago le quitamos la d, por tanto necesitamos 5 movimientos para convertir una palabra en otra. Resumiendo, cuanto más pequeña sea la distancia, más parecidas son las dos palabras.

¿Esto para que sirve?, pues muy fácil, para obtener palabras similares en los buscadores o mostrar palabras alternativas por ejemplo. Vamos a ver el algoritmo y como funciona.

Este algoritmo es una matriz de n filas por m columnas donde n y m son el número de caracteres + 1 de cada palabra. El primer paso que se realiza es rellenar la primera fila y la primera columna con números secuenciales de 0 hasta n+1 y desde 0 hasta m+1 , quedando del siguiente modo para el caso del ejemplo inicial la matriz de 11×9:

levensthein0Una vez tenemos la matriz inicial, empezaremos a realizar comparaciones por filas de cada caracter con el caracter de cada columna. En cada operación, obtenemos primero el peso y tres valores de los cuales deduciremos el menor de ellos como valor final y con un ejemplo lo veremos mejor.

Comenzamos comparando los caracteres, la letra “m” de murcielago (en la columna), lo comparamos con la “m” de muerdago (filas), si es el mismo caracter se le asigna un peso de 0 y si es diferente, le asignamos 1, en este caso como son iguales, le asignamos un 0. A continuación obtenemos los tres valores, el primero con la casilla superior sumándole al valor de esta un 1, en este caso 1+1=2, el siguiente con la casilla que está situada a su izquierda haciéndolo de igual modo, 1+1=2 y por último a la casilla superior izquierda, la que está situada en la diagonal a la que le sumaremos el valor del peso, 0+0=0; de estos tres valores, cogeremos el menor que en este caso es el 0. levensthein1

Vamos a por el siguiente, peso igual a 0, porque u es igual a u, por la izquierda, 0+1=1, la diagonal 1+0=1 y la superior 1+2=2, el mínimo de los tres es 1

levensthein2

continuando con las comparaciones y obtención del mínimo, quedaría nuestra matriz completa del siguiente modo:

levensthein3

El último valor, es la distancia de Levenshtein, en este caso es 5, si quisieramos ver la proporción de acierto, deberíamos obtener la la diferencia con la unidad de la relación entre la distancia y el número de caracteres del mayor en este caso, 1 – (5/10)=0,5 o 50%. La distancia de “murcielago” y “cerro muriano” es de 10, por tanto 1-(10/13)=0.2308 o del 23,08%.

El algoritmo implementado con lenguajes de programación no tiene ningún misterio para el que esté acostumbrado a las matrices, además en Wikipedia, podéis encontrar su implementación en diferentes lenguajes, por ejemplo en php ya tiene una función como tal.

vladimir-levenshtein¿Que utilidades podemos darle? por ejemplo palabras sugerentes en base a un diccionario o aproximaciones, corrección de ortografía, etc. y además, existen variantes del algoritmo como la de Damerau-Levenshtein, otros más complejos, algoritmos fonéticos.

Este algoritmo se lo debemos a Vladimir Levenshtein, un matemático ruso que lo desarrolló en 1965.

He hecho en C# una app de consola como muestra para obtener la matriz y en base a un diccionario, nos muestre sugerencia de palabra.  levensthein4

levensthein5