Category Archives: Programación

Escritos sobre código, algoritmos y lenguajes de programación

Un rápido y compacto corrector ortográfico en Scala

Construir un corrector ortográfico no es realmente una tarea muy difícil. Muchos inmediatamente mencionarán la distancia de Levenshtein para saber la distancia de edición entre 2 palabras.

Tomando el ejemplo de Wikipedia:

La distancia de Levenshtein entre “casa” y “calle” es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

  1. casa → cala (sustitución de ‘s’ por ‘l’)
  2. cala → calla (inserción de ‘l’ entre ‘l’ y ‘a’)
  3. calla → calle (sustitución de ‘a’ por ‘e’)

Entonces, buscar los posibles candidatos de una palabra mal escrita se convierte en buscar las palabras que tengan la menor distancia de edición con ella. Es simple, pero en el peor de los casos tendríamos que buscar entre todo el conjunto de palabras que tengamos (como un diccionario), lo cual hace que la búsqueda sea O(n).

Para alivianar el problema, existen los BK-Tree, que básicamente son árboles cuyos nodos son palabras y las aristas tienen el valor de la distancia de edición entre esos nodos. Acá hay una explicación (en inglés) que cubre lo necesario para entenderlos: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

El caso es que usar un BK-Tree para esta tarea acelera mucho la búsqueda de candidatos, puesto que no es necesario cubrir todos los nodos si la distancia máxima que se busca es relativamente pequeña (digamos, 1 o 2).

Buscando implementaciones en Scala, me doy cuenta de que en Scalaz existe la clase BKTree (aunque está deprecated en la versión 7). Viendo el código, y teniendo una lista de 90,000 palabras en inglés, me di a la tarea de implementar un muy sencillo corrector ortográfico en ese lenguaje. La distancia máxima entre palabras la puse en 1. El resultado:

package org.mmg.tests

import scala.io.Source._
import scalaz._
import Scalaz._

object SpellCorrector {

  def main(a: Array[String]) {
	  val words = fromFile("EnglishWords.txt").getLines.toList	  
	  val bt = words.foldLeft(BKTree[String]())((acc, w) => acc + w) 	  	  
	  val MAX_DIST = 1

	 while (true) {
    	print("Input the word you want to check (Ctrl-C to end): ")
    	Option(Console.readLine) filterNot {_.isEmpty} foreach {s => 
        	bt.valuesApproximate(s, MAX_DIST) foreach println
    	}
     }
  }

}

Y probando:

Input the word you want to check (Ctrl-C to end): tail
ail
til
bail
fail
Gail
hail
jail
kail
mail
nail
pail
rail
sail
tail
vail
wail
tall
tael
tain
toil
trail

Los resultados se obtienen relativamente rápido. El ejemplo anterior toma sólo algunas décimas de segundo (casi 90,000 palabras). Por supuesto que esto no quiere decir que sea óptimo, pero si no se busca un desempeño en áreas críticas, funciona.

Obviamente esto es muy simple, pero puede mejorar si por ejemplo le asignamos menos peso a operaciones de la distancia de Levenshtein entre letras que frecuentemente se escriben mal, como por ejemplo, entre la “o” y la “p”, que están juntas en un teclado QWERTY. Eso haría que la distancia fuera menor entre ciertas palabras y reduciría el número de candidatos que se muestran.

Por supuesto, si tenemos un modelo probabilístico podemos usar el teorema de Bayes para buscar mejores candidatos, y aunque no es en sí tan complicado, sí me tomaría más tiempo escribirlo aquí.

Como sea, esta implementación es rápida, y puede sacar de algún apuro.

Funciones como ciudadanos de primera clase y expresiones lambda

En la entrada anterior, varias personas me hicieron el apunte de que debería haber puesto la última parte (donde explico para qué puede ser útil ese conocimiento) en el principio. Otros comentaron que aunque es posible entender el escrito, sí es necesario conocer ciertos conceptos, como mapeo, para “agarrar el hilo”.

Agradezco mucho sus comentarios 🙂

Aunque no pretendo hacer (de momento) una guía exhaustiva sobre programación funcional, sí me gustaría plasmar algunos conceptos básicos que puedan servir para despertar el interés de investigar más.

Cabe mencionar que programar en forma funcional no necesariamente es mejor que la programación orientada a objetos. Cada paradigma tiene pros y contras, pero conocer lo que cada uno ofrece nos permite tomar mejores decisiones a la hora de crear código o de seleccionar un lenguaje para ciertas tareas.

Vayamos al grano:

Continue reading Funciones como ciudadanos de primera clase y expresiones lambda

Monads – Yo también tenía que escribir al respecto

Seguí la tradición: cuentan las leyendas que cuando una persona comienza a ver la luz al usar Monads, invariablemente escribe un tutorial. Pero en mi caso, no es un tutorial, sino más bien una breve explicación de lo que son, junto con algunos ejemplos. Esto es con el fin de que yo mismo compruebe si entiendo el concepto general, y al mismo tiempo de que salgan gurús en programación funcional y me corrijan y me digan en qué estoy mal.

Ésta no es una guía exhaustiva, y omitiré muchos conceptos, pero pondré referencias por aquello de que haya interesados en el tema.

Como nota, sé que en español los términos son Funtor mónadas, pero nada más no me entran en la cabeza, por lo que los usaré en inglés. Además, aunque no está dirigido a un lenguaje en particular, la mayoría de los ejemplos mostrados están en Scala.

Continue reading Monads – Yo también tenía que escribir al respecto

8-puzzle: Implementación sencilla de A*

Hace poco estuve leyendo unas notas de un curso en línea sobre planeación en IA. En una de ellas me encontré con un algoritmo que tenía rato que no veía ni utilizaba, y me dio curiosidad por implementarlo en Scala; me refiero al algoritmo A*.

En vez de explicar qué hace específicamente el algoritmo, un googlazo o una búsqueda en Wikipedia proveen información más detallada al respecto. El problema a resolver era el famoso 8-puzzle, aquel cuadro con números del 1 al 8 en el que hay que ponerlos en orden:

El algoritmo A* aplicado a este problema lo pueden encontrar fácilmente con una búsqueda en internet, pero como yo quería practicar Scala (lenguaje que uso en mis proyectos) me puse a ver qué tal me quedaba. Solamente tuve un problema en el algoritmo: tuve que usar un mutable hashset (horror, lo sé), porque al usar uno inmutable el tiempo de ejecución se hacía muy largo. Si hay alguien por ahí que quiera optimizar el código, adelante. También implementé la solución de forma imperativa nada más para comparar.

Aquí el código. Recuerden que esto no es la mejor implementación, y que por ende, puede mejorar. Los heurísticos implementados son Manhattan Distance (distancia de un estado x a uno meta) Misplaced tiles (contar el número de cuadros que no están en su lugar. El segundo también lleva a la solución, pero tarda más en encontrarla. La función principal (solve) está optimizada como tail recursive para evitar un posible stack overflow. Además, van a ver muchos val quizá innecesarios que puse para darle legibilidad al depurarlo en el caso de que fuera necesario.

Sugerencias y comentarios son bienvenidos:

Continue reading 8-puzzle: Implementación sencilla de A*

Notas rápidas al trabajar con Access

Ignoremos el hecho de que Access es MALO, pero MALO con ganas. No tengo idea de por qué no hicieron las cosas en Oracle, pero también pasaremos eso por alto.

Una pequeña lista de problemas que me he encontrado al trabajar con esta aberración. Nota: estoy trabajando con Access 2010.

  • Las consultas que usan LIKE necesitan * en vez de %. Ejemplo:
    (Mal) Select nombre from agenda where name like ‘%Medina%’
    (Bien) Select nombre from agenda where name like ‘*Medina*’
  • Lo anterior es FALSO si la consulta se envía desde fuera (en mi caso, C#).
    A fuerzas necesita el %
  • No se puede hacer un join de tablas con campos de tipo “Memo” (no me pregunten por qué tengo que hacer joins con ese tipo de información :S).
    El tipo de datos “Memo” no guarda los datos en la tabla, sino en otro lugar y la tabla contiene solamente un apuntador a esos datos. Como SQL no sabe qué onda con apuntadores, te dice que no es posible hacer el join.
  • Al parecer, al crear una consulta directamente en SQL es necesario guardarla primero antes de ejecutarla si se quiere que Access respete la indentación que le dimos. No he comprobado esto al 100%, pero sí golpeé el monitor cuando abrí una mega consulta que hice y Access me mostró todo por ningún lado, mientras que otras sí las dejaba como las había formateado.
  • No se puede poner comentarios con “–” en el SQL que maneja Access. Horrible, si me permiten el comentario.
  • Access no aguanta hacer subqueries muy pesadas. Una consulta estilo:
    Select id from agenda 
    where nombre in (
        -- Una súper consulta incluyendo más subqueries, union, left outer join, etc.
    )

    hace que Access te diga “esa operación no se puede realizar en subqueries.

    La misma consulta en MySQL y PostgreSql corre sin problemas, por lo que el SQL está correcto.

Sé que soy un completo Noob en esto de Access, por lo que se aceptan sugerencias y correcciones.

Programando “de forma normal”

La semana pasada, y de hecho también este lunes, estuvo simplemente fatal. En el trabajo aplicaron la súper estrategia de meter a alguien en un proyecto del que no tiene idea de cómo está compuesto, y le echan trabajo que, como siempre, era para ayer, sin contar que todo está hecho en un lenguaje que ese alguien nunca ha usado y un juguete que simula ser una base de datos (léase “Access”). ¿Necesito decir que ese alguien era yo?

He trabajado en desarrollo de sistemas antes y sé lo que son los tiempos que se manejan en el proceso: nunca son reales y uno tiene que andar a la carrera para poder sacar “los pequeños cambios” que curiosamente salen después de que los requerimientos fueron tomados, aceptados y congelados. Pero quizá lo que más me sorprende es la reafirmación de que en muchos lugares el software que se usa para producción dista mucho de tener una calidad siquiera aceptable, y Japón no es la excepción. Cierto. He visto código que sí está bien hecho, con buen formato y con su respectiva documentación, pero son pocos los casos.

Lo que tocó hacer estaba en C# y la base de datos en Access… simplemente increíble. El código estaba bien estructurado, pero había funciones que realizaban más de una tarea y que eran enormes; comentarios totalmente inexistentes que hacían mucho más difícil de entender lo que el programador pensó al momento de codificar. Lo grave del asunto es que, después de tanto tiempo y de haber trabajado en 3 países, ya considero esto como normal puesto que entiendo que muchas veces se anda a las carreras con tal de cumplir con los tiempos establecidos aunque tu vida social desaparezca por ello.

Justo el buen panda me envió este artículo en el que se habla de lo que aquí comento, especialmente aplicado a programas que manejan acciones de empresas y de cómo pueden hacer perder millones por un simple error. Además de los tiempos, muchas empresas no toman en consideración las pruebas ya que representan un costo extra, y es casi verdad universal que quienes manejan las empresas piensan que con ver correr el prototipo de un sistema es suficiente para decidir si funciona o no.

Aclaro aquí algo: yo también he estado en la situación de que hay que acabar a como dé lugar sin importar cómo quede el código, y estoy seguro que mi forma de estructurar programas puede mejorar. En resumen: no me creo ni soy el mejor desarrollador del mundo. No obstante, estoy completamente seguro de que muchos me darían la razón si vieran el código del que estoy hablando.

De código de investigación ni hablamos. Me da pavor ver lo que hice durante mi estancia en la universidad…

Como quieran y gusten, terminé lo que tenía que hacer en el tiempo que me establecieron, pero para lograrlo me tuve que quedar hasta muy tarde en el trabajo (el lunes salí a las 11:30 pm y apenas alcancé tren a la casa). Sin embargo, hoy ha comenzado a otra parte del proyecto, y para los tiempos que manejan no me va a quedar de otra que echarme un clavado al código ya hecho, entender lo que hace (y viendo como hay valores que pasan por referencia, como las propiedades de los objetos están definidas como públicas… y mejor no le sigo) y reusar lo que sea posible. El problema a resolver es interesante, y de hecho me gustaría pensarlo en términos de probabilidad y hasta algoritmos como el Hill Climbing, pero todo indica que no tengo el tiempo que necesito para realizar el análisis que eso implica.

Con todo, es totalmente un placer decirles que la diferencia entre mi trabajo anterior y éste es como del cielo a la tierra. Compadezco a mis ex compañeros por tener que trabajar en una situación tan estresante.

Aquí seguimos.

 

Encuentra la diferencia – versión Kanji – en Scala

Y ya con este código dejo el tema por la paz. Lo pongo para que quede en el registro:

object Uniques {
  def main(a: Array[String]) {
    if (a.length != 1) {
      println("Need an argument to analyze")
      sys.exit(1)
    }
    else {
      findUniques(a(0)) match {
        case l if (l.isEmpty) => println("All characters are the same")
        case l => l foreach println
      }
    }
  }

  def findUniques(seq: String) =  seq filter {c => seq.count(_ == c) == 1} map {c => "Unique instance found: " + c + " in position " + (seq.indexOf(c) + 1)}
}

Y probando el caso en cuestión:

mmedina@yggdrasil-m:~/Programming/Scala/Tests$ scala Uniques "麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈 麈麈麈麈麈麈麈麈麈"
Unique instance found: 塵 in position 66

Hacerlo para que funcione con otros tipos de datos sin cambiar nada de código no es muy complicado.

Encuentra la diferencia – versión Kanji – en Haskell

Lo prometido es deuda. Siguiendo con el escrito anterior, aquí está el código que resuelve el problema, pero ahora en Haskell:

import qualified Data.ByteString as B
import qualified Data.ByteString.UTF8 as U
import System.Environment(getArgs)
import Data.List
import Data.Maybe

main = do
    putStrLn "Write the sequence you want to analyze:"
    B.getLine >>=  processArguments

processArguments :: B.ByteString ->  IO ()
processArguments xs = findUniques $ U.toString xs

findUniques = printUniques . findUniques'

findUniques' :: (Eq a, Show a) => [a] ->  [(a,Int)]
findUniques' xs = let uniques = filter (\i ->  countInstances i xs == 1) $ nub xs
                  in [(x,y) | x <- uniques, y <- mapMaybe (\i ->  i `elemIndex` xs) [x]]

printUniques :: (Eq a, Show a) =>  [(a,Int)] ->  IO ()
printUniques [] = putStrLn "All instances are the same"
printUniques us = mapM_ putStrLn $ map (\c →  ((("Unique instance: " ++ ) $ show $ fst c) ++ ) $ ((" in position " ++ ) $ show $ (+1) $ snd c)) us

countInstances :: (Eq a, Show a) =>  a ->  [a] ->  Int
countInstances _ [] = 0
countInstances c (x:xs)
    | c == x = 1 + countInstances c xs
    | otherwise = countInstances c xs

 

Es un hecho que puedo usar un where en la definición de printUniques, pero bueno, el caso es que funciona:

mmedina@yggdrasil-m:~/Programming/Haskell/FindDifference$ ./fdc
Write the sequence you want to analyze:
麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈
Unique instance: '\22645' in position 66

Todo muy bonito, sí. Pero entonces: ¿para qué tanto código en Haskell? Explico:

Continue reading Encuentra la diferencia – versión Kanji – en Haskell

Encuentra la diferencia – versión Kanji

Hace unos días, me llegó un retweet con lo siguiente:

【間違い探し☆超超超超上級編】 麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈塵麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈麈 解けたらRT!

El punto es encontrar el kanji que es diferente, y al hacerlo, enviar el mensaje en un RT. Según el principio del mensaje, este problema es de nivel súper-súper-súper-súper avanzando.

“Buena forma de pasar el tiempo”, pensé, pero no para resolverlo “a mano”, sino creando un programa que lo hiciera por mí.

Viendo mis opciones, decidí programar el algoritmo en Python, tanto como práctica como para seguir dándome de topes por lo de las string unicode vs byte strings (quienes saben python entienden a lo que me refiero).

En sí, el algoritmo es sencillo, así que no tomó mucho tiempo:

# -*- coding: utf-8 -*-

import sys

def searchDifferentKanji(strseq):
    utf8Str = unicode(strseq,"utf-8")
    difstr = list(set(utf8Str))

    for c in difstr:
        if utf8Str.count(c) == 1:
            return c.encode("utf-8"), utf8Str.index(c) + 1

    return '',-1

if __name__ == "__main__":
    if len(sys.argv) != 2:
        print "Error: Need a string to check"
        exit(1)
    else:
        difchar, pos = searchDifferentKanji(sys.argv[1])
        if pos != -1:
            print "Different char: " + unicode(difchar,"utf-8") + " in position " + str(pos)
        else:
            print "All characters are the same"

Lo que hago es simple: creo un set a partir de la cadena, haciendo con esto que todos los elementos repetidos se esfumen, y lo convierto a lista, la cual contiene exactamente un carácter por cada carácter diferente en la cadena original. Después recorro esa lista buscando en la cadena si el elemento actual aparece una sola vez; de ser así, es el carácter que estoy buscando, por lo que lo regreso, junto con la posición en la que está.

Existen problemas similares que contienen más de una diferencia, es decir: entre un mar de repeticiones del mismo carácter se encuentran varios diferentes. Para resolverlos, el algoritmo arriba expuesto puede ser sencillamente modificado para que no rompa el ciclo con el primer carácter diferente que encuentre, y agregue la tupla de (carácter,posición) a una lista, que sería el valor que la función “searchDifferentKanji” regresaría.

Como nota adicional, el kanji de ese problema es , que se lee 「しゅ」(shu), y conlleva el significado de “ciervo grande”. El kanji diferente es , con varias lecturas, entre ellas las más comúnes 「ちり」 (chiri), que significa “polvo”, “basura” y 「ごみ」(gomi), que también significa “basura”.

Sí: me queda de tarea hacerlo en Haskell.