Facundo Batista: Búsqueda por prefijos tolerante a errores


Hace un tiempo les hablé de un árbol que hice para sacar prefijos de palabras.

En el laburo estoy estudiando la forma de hacer un autocompletador. Entonces, luego de leer cosas por ahí, decidí probar ese árbol que ya tenía hecho.

Nunca le había tirado tantos datos, pero la verdad es que salió andando de perlas.

Por otro lado, tenía un detalle que necesitaba solucionar: yo quería que la búsqueda de palabras soportara errores en la escritura. O sea, que si uno buscara "maise", encontrara "maizena".

Encontré un paper bastante loco, Efficient Error-tolerant Query Autocompletion, pero que mostraba la forma de soportar errores al buscar palabras completas, no prefijos. Igual, apliqué ideas de ahí, y en un par de días de laburo conseguí lo que quería. Pero, al cargar el millón y medio de registros que tengo que cargar, ¡explotaba por memoria!

Luego de algunas optimizaciones obvias, se me ocurrió lo de deduplicar los subtrees internos. ¿Qué es deduplicar? Deduplicar es la acción por la cual si tengo un objeto A, y luego tengo otro B, que resulta ser igual a A, puedo usar el A directamente en ambos casos, descartando B (libera memoria), y listo.

Deduplicar diccionarios no es un asunto trivial. Tiré el asunto en la lista de PyAr, y en pocas horas logré que todo funcione correctamente. Ahora no sólo no explota, sino que ocupa bastante poca memoria!

    Memory usage after loading the tree: rss: +586 MB  vms: +586 MB
    Time to load the tree: 327190.99 msec
    <WordTree at 3068071276 [tau=1]: 1478347 words 30015540 (2201293) nodes (unique)>

Millón y medio de palabras, 30 millones de nodos (de los cuales 2.2 millones son únicos), ocupando 590 MB de memoria. Nada mal, ¿no? Que tarde 5.5 minutos en armar toda la estructura es un problema, la semana que viene voy a mirar eso bien.

Todo el código, acá.

Marcos Dione: processing-huge-DEM-datasets

As I mentioned in one of my lasts posts about it, I started using SRTM 1 arc data for rendering my maps. So far, with the 3 arc dataset, I was able to generate a huge image by stitching the tiles with gdal_merge.py, then generating the 3 final images (height, slope and hill shade) plus one intermediary for the slope, all with gdaldem. Now this is no longer possible, as the new dataset is almost 10x the old one, so instead of going that way, I decided to try another one.

With gdalbuildvrt it is possible to generate an XML file that 'virtually' stitches images. This means that any attempt to access data through this file will actually make the library (libgdal) to find the proper tile(s) and access them directly.

So now the problem becomes processing each tile individually and then virtual stitching them. The first part is easy, as I just need to do the same I was doing to the huge stitched image before. I also took the opportunity to use tiled files, which instead of storing the image one scan line at a time (being 1 arc second resolution, each scan line has 3601 pixels; the extra one is for overlapping with the neighbors), it stores the file in 256x256 sub-tiles, possibly (that is, no tested) making rendering faster by clustering related data closer. The second step, with gdalbuildvrt, should also be easy.

The first block on the way is the fact that SRTM tiles above 50°N are only 1801 pixels wide, most posibly because it makes no sense anyways. This meant that I had to preprocess the original tiles so libgdal didn't have to do the interpolation at render time (in fact, it already has to do it once while rendering, using the lanczos scaling algorithm). This was done with gdalwarp.

The second one came from slope and hill shading tiles. As the algortihm goes, it generates some 'fade out' values in the edges, and when libgdal was stitching them, I could see it as a line in the seam. This was fixed by passing -compute_edges to gdaldem.

Finally, for some reason gdalbuildvrt was generating some very strange .vrt files. The format of these files is more or less the following:

  • For each band in the source tiles it creates a band in the result.
    • For each source tile, it describes:
      • The source file
      • The source band
      • The size and tiling of the source (3601², 256²)
      • The rectangle we want from the source (0², 3601²)
      • The rectangle in the result (x, y, 3601²)

The problem I saw was some weird declararions of the rectangles in the result, where the coordinates or the sizes didn't match what I expected. I will try to figure this out with the GDAL poeple in the following weeks, but first I want to make sure that the source tiles are easily downloadable (so far I have only found download options through USGS' EarthExplorer, which requires you to be logged in in order to download tiles, which means that it is not very scriptable, so not very reproducible).

So for the moment I'm using my own .vrt file generator, completely not generic enough for release, but soon. I also took the opportunity to make the rectangles in the result non-overlapping, being just 3600² in size. I know that the generated file works because I'm also generating smaller samples of the resulting layers (again, height, slope and hill shading) for rendering smaller zoom levels.

The only remaining question about huge DEM datasets is contour generation. So far I had just generated contour lines for each tile and lived with the fact that they too look ugly at the seams.


gdal gis srtm

Mariano Guerra: Making a GIF out of a folder of PNGs (plus resizing)

I need to update the gif from the Event Fabric landing page and I forgot how I did it last time.

So this time I will write it here as a reminder.

First take the screenshots, I do it the good ol' way by using the browser fullscreen and hitting the screeshot key at almost regular intervals.

That leaves me with a set of screenshots I want to resize, so I run:

mogrify -path small -resize 800x450 *.png

Note

This requires imagemagick to be installed

This will resize all the *.png files in the current folder to 800x450 and write the results into a folder called small.

Now we go to the small folder and generate the gif:

cd small
convert -delay 100 -loop 0 *.png animation.gif

This will greate a gif that transitions every second from the png images and save it in the animation.gif file.

Mariano Draghi (cHagHi): Rearrancando...

Restart, human!

Restart, human! por Anders Sandberg

Nueva casa, nueva tecnología, nuevo formato. Todo es nuevo. Menos el contenido, que está abandonado hace casi un año. Y que ya venía semi abandonado antes de eso.

Ya ni los ¿clásicos? posts sobre los viajes estoy haciendo. Hay por lo menos dos que no están acá. Y es una pena. Esto nunca fue muy popular, ni tuvo muchos lectores, pero siempre fue un buen ejercicio esto de escribir, y más de una vez fue interesante en lo personal volver para atrás y releer algunas cosas. Y eso que he escrito cada pelotudez... :p Pero nada, las pelotudeces también son interesantes. Es interesante ver como uno cambia, o como el mundo cambia, y contrastar lo que pensaba, sentía o vivía mi "yo" de hace X tiempo con mi "yo" actual.

Y cada tanto, cada muy tanto, hasta llegué a escribir algo que le sirvió a alguien. Y eso también está bueno.

¿Y por qué dejé de hacerlo? No se muy bien, pero en general siento que la culpa es de Facebook y Twitter. Es mucho más fácil escribir una gilada de 140 caracteres en Twitter o un par de párrafos en Facebook que ponerlo en un blog.


Para motivarme un poco, porque uno ante todo es nerd (?), decidí demoler el blog anterior y armarlo otra vez. Estoy usando Nikola, mascota de Roberto Alsina, que resulta que además de recomendar muy buenos libros, desarrolla muy buenos generadores de sitios estáticos ;-) (¡gracias Roberto!)

La principal ventaja para mi de haber migrado a Nikola es que ahora el contenido del blog está en archivos de texto, en un formato que es legible por un humano incluso sin la magia que lo transforma en páginas web.

La segunda ventaja es que está desarrollado en Python, que es un lenguaje de programación que me gusta hasta el infinito y más allá más que PHP (que es lo que usa WordPress), y que me resulta mucho más fácil de entender cuando necesito tocar algo, o agregar funcionalidad, o hacer modificaciones.

La tercer ventaja es que Nikola es minimalista. No tiene las decenas de características que tiene WordPress, ni sus miles y miles de plugins. Tiene lo que necesito. Es más simple. Y cuando uno no necesita la complejidad extra, "simple es mejor que complejo" [*].

Migrar de WordPress a Nikola es algo que es más o menos automático en un 75%, pero si sos obse como yo y realmente querés emprolijar las cosas, requiere luego una serie de ajustes que dependen de cuan horrible sea el formato heredado de WordPress. Para algunos de esos ajustes fui haciendo reemplazos semi-automáticos con distintas herramientas, para otros tuve que ir a mano (y para esos casos, que no fueron taaaaantos, agradecí no haber estado escribiendo con más frecuencia :p). En todo este proceso me vino de 10 la experiencia previa de Humitos.

Todavía tengo cosas que ajustar, como los tags y categorías, o hacer que el sitio tenga un look un poco menos genérico. Y otro gran tema es encontrar un mecanismo cómodo para poder publicar desde el celu/tablet, o una compu desde la que no tenga acceso al servidor. Esto es medio una desventaja común a todos los generadores de sitios estáticos. Hay varias opciones, pero todas requieren algún trabajillo extra, todas tienen algún pero, y va a requerir un poco más de tiempo evaluar que es lo que más me conviene.

Pero la base está...


Para terminar el revoleo, el blog no está más alojado en un hosting compartido. Me llevé todo a un VPS. Y eso también es toda una novedad, y en parte un desafío, porque tengo que administrar absolutamente todo yo. Es un arma de doble filo: puedo hacer lo que quiera en el servidor, y por lo tanto también puedo romper todo. Y tengo que tener un ojo puesto en todo lo que sea configuración, actualizaciones, seguridad, etc.

Al pasar a un VPS hay una cosa que estaba seguro que no quería administrar: las cuentas de correo de mi dominio. Administrar un servidor de correo propio es, para mi, "ligas mayores" (para hacerlo razonablemente bien), así que tuve que encontrar una solución, preferentemente gratuita. En una época la respuesta obvia a esto era Google Apps, pero no es más gratis. Por recomendación de Roberto (que además de recomendar buenos libros, y de desarrollar buenos generadores de sitios estáticos, hace buenas recomendaciones de servicios en la nube), el correo de mi dominio quedó en Zoho, que ofrece un plan gratuito que me alcanza y sobra.

Y acá estamos. Todo nuevito. Ahora solo falta escribir...


[*] El Zen de Python

Mariano Draghi (cHagHi): Rearrancando...

Restart, human!

Restart, human! por Anders Sandberg

Nueva casa, nueva tecnología, nuevo formato. Todo es nuevo. Menos el contenido, que está abandonado hace casi un año. Y que ya venía semi abandonado antes de eso.

Ya ni los ¿clásicos? posts sobre los viajes estoy haciendo. Hay por lo menos dos que no están acá. Y es una pena. Esto nunca fue muy popular, ni tuvo muchos lectores, pero siempre fue un buen ejercicio esto de escribir, y más de una vez fue interesante en lo personal volver para atrás y releer algunas cosas. Y eso que he escrito cada pelotudez... :p Pero nada, las pelotudeces también son interesantes. Es interesante ver como uno cambia, o como el mundo cambia, y contrastar lo que pensaba, sentía o vivía mi "yo" de hace X tiempo con mi "yo" actual.

Y cada tanto, cada muy tanto, hasta llegué a escribir algo que le sirvió a alguien. Y eso también está bueno.

¿Y por qué dejé de hacerlo? No se muy bien, pero en general siento que la culpa es de Facebook y Twitter. Es mucho más fácil escribir una gilada de 140 caracteres en Twitter o un par de párrafos en Facebook que ponerlo en un blog.


Para motivarme un poco, porque uno ante todo es nerd (?), decidí demoler el blog anterior y armarlo otra vez. Estoy usando Nikola, mascota de Roberto Alsina, que resulta que además de recomendar muy buenos libros, desarrolla muy buenos generadores de sitios estáticos ;-) (¡gracias Roberto!)

La principal ventaja para mi de haber migrado a Nikola es que ahora el contenido del blog está en archivos de texto, en un formato que es legible por un humano incluso sin la magia que lo transforma en páginas web.

La segunda ventaja es que está desarrollado en Python, que es un lenguaje de programación que me gusta hasta el infinito y más allá más que PHP (que es lo que usa WordPress), y que me resulta mucho más fácil de entender cuando necesito tocar algo, o agregar funcionalidad, o hacer modificaciones.

La tercer ventaja es que Nikola es minimalista. No tiene las decenas de características que tiene WordPress, ni sus miles y miles de plugins. Tiene lo que necesito. Es más simple. Y cuando uno no necesita la complejidad extra, "simple es mejor que complejo" [*].

Migrar de WordPress a Nikola es algo que es más o menos automático en un 75%, pero si sos obse como yo y realmente querés emprolijar las cosas, requiere luego una serie de ajustes que dependen de cuan horrible sea el formato heredado de WordPress. Para algunos de esos ajustes fui haciendo reemplazos semi-automáticos con distintas herramientas, para otros tuve que ir a mano (y para esos casos, que no fueron taaaaantos, agradecí no haber estado escribiendo con más frecuencia :p). En todo este proceso me vino de 10 la experiencia previa de Humitos.

Todavía tengo cosas que ajustar, como los tags y categorías, o hacer que el sitio tenga un look un poco menos genérico. Y otro gran tema es encontrar un mecanismo cómodo para poder publicar desde el celu/tablet, o una compu desde la que no tenga acceso al servidor. Esto es medio una desventaja común a todos los generadores de sitios estáticos. Hay varias opciones, pero todas requieren algún trabajillo extra, todas tienen algún pero, y va a requerir un poco más de tiempo evaluar que es lo que más me conviene.

Pero la base está...


Para terminar el revoleo, el blog no está más alojado en un hosting compartido. Me llevé todo a un VPS. Y eso también es toda una novedad, y en parte un desafío, porque tengo que administrar absolutamente todo yo. Es un arma de doble filo: puedo hacer lo que quiera en el servidor, y por lo tanto también puedo romper todo. Y tengo que tener un ojo puesto en todo lo que sea configuración, actualizaciones, seguridad, etc.

Al pasar a un VPS hay una cosa que estaba seguro que no quería administrar: las cuentas de correo de mi dominio. Administrar un servidor de correo propio es, para mi, "ligas mayores" (para hacerlo razonablemente bien), así que tuve que encontrar una solución, preferentemente gratuita. En una época la respuesta obvia a esto era Google Apps, pero no es más gratis. Por recomendación de Roberto (que además de recomendar buenos libros, y de desarrollar buenos generadores de sitios estáticos, hace buenas recomendaciones de servicios en la nube), el correo de mi dominio quedó en Zoho, que ofrece un plan gratuito que me alcanza y sobra.

Y acá estamos. Todo nuevito. Ahora solo falta escribir...


[*] El Zen de Python

Roberto Alsina: Some New Stuff in Nikola

I did so­me qui­ck wo­rk on Niko­la (a sta­tic web­si­te/­blog ge­ne­ra­to­r) la­te­l­y, after a long ti­me, and he­re's what it wa­s:

Multilingual Sitemaps

So, site­maps are us­ed by Google to in­dex your si­te. It turns out that they can des­cri­be when the­re are se­ts of pa­ges ­that are trans­la­tions of ea­ch othe­r. So the next re­lea­se wi­ll do that (Is­sue #1610)

Matplotlib Plots

Ma­tplo­tlib co­mes wi­th a sphi­nx ex­ten­sion to do plo­ts So I went and im­ple­men­ted it, this was Is­sue #1242 and it's a plu­gin ca­lled py­plo­ts, whi­ch wi­ll be soon at http://­plu­gin­s.­ge­tniko­la.­co­m#­p­y­plo­ts

I hated the ori­gi­nal co­de. It felt con­vo­lute­d, and just weird (i­t's pro­ba­bly just me) so I wro­te it from scra­tch and it has so­me mi­nor di­ffe­ren­ce­s, but it's fair­ly com­pa­ti­ble.

Classy Images

The do­cu­tils ima­ge di­rec­ti­ve, for whate­ver rea­so­n, does­n't su­pport a cla­ss op­tio­n, so you need to do things like this:

.. class:: foo

.. image:: blah.png

Whi­ch is ... not pre­tty. So I did a ha­cky plu­gin that mo­nke­y­pa­tches the ima­ge di­rec­ti­ve to add that op­tio­n. ­The plu­gin is at http://­plu­gin­s.­ge­tniko­la.­co­m/#­cla­ss­y-i­ma­ges and this fixes Is­sue 1538

Mediawiki Markup

dj­b­cla­rk po­inted out that the­re is a li­bra­ry to par­se Me­diaWiki from py­thon ca­lle­d sm­c.­mw so I im­ple­men­ted a plu­gin to use it, so now you can use Me­diaWiki ­ma­rku­p. The plu­gin is at http://­plu­gin­s.­ge­tniko­la.­co­m/#­me­diawiki

Removed Default Swatch from Bootswatch

This was Is­sue #1656 and now you ha­ve to spe­ci­fy ­the swa­tch. This is a usa­bi­li­ty fix, be­cau­se de­faul­ts ma­tter.

Played with KaTeX

Niko­la su­ppor­ts ma­th using Ma­th­Ja­x. Ma­th­Jax has so­me in­te­res­ting qua­li­tie­s:

  • It's 160MB of co­de or so
  • It's not prac­ti­cal to use wi­thout a CDN
  • It's not prac­ti­cal to use we­ba­sset bund­les wi­th it

Then, klin­gtnet men­tio­ned so­me­thing ca­lled Ka­TeX I had ne­ver heard abou­t. I did a qui­ck ha­cky con­ver­sion to see how it wo­rks. ­Not do­ne ye­t, to­ta­lly ex­pe­ri­men­ta­l, but it may be po­s­si­ble to bund­le it, and ma­y­be even ha­ve it tur­ned on by de­faul­t, re­mo­ving the need for the ma­th­jax la­bel whi­ch is aw­ful usa­bi­li­ty-wi­se.

So­me of the­se things are mer­ge­d, so­me are sti­ll PR­s, so­me are in co­re, so­me are plu­gin­s. They we­re all pre­tty fun ­to do :-)

Manuel Kaufmann (Humitos): ¡Nos compramos un robot!

Ya lo dije, el PyDay Asunción fue éxito y hoy sigue dando sus frutos.

El Sábado pasado participamos (en realidad solo asistimos, porque no ayudamos en mucho -nada, diría yo) al "HACKÁra Asuka Guaraní" para hacer la traducción de Sugar al Guaraní. Esta idea se propuso en el PyDay de Asunción, y semanas más tarde se llevó adelante: ¡Felicitaciones a todos por eso!

Ahí, en el PyDay Asunción yo le compré un robot "RoDi" a Gary Servin (disertante en el PyDay) con la idea de armar algún curso introductorio a la programación para chicos utilizando Python. Sin embargo, no tenía ni idea de RoDi y no había tenido tiempo de probarlo hasta hoy que me puse a jugar un poco.

El robot sale USD 40 (lo cuál es muy barato). Entonces, estaría bueno ver de comprar 2 o 3 más para tener un promedio de 10 alumnos y que trabajen en equipos de 2 o 3. ¿Cómo lo ven?

rodi.thumbnail.jpg

El robot RoDi

La dinámica es sencilla. Te conectás por WiFi a RoDi y le hacés GETs HTTP a diferentes URLs para que haga diferentes cosas (este firmware lo realizó Martín Abente -otro crack y disertante del PyDay).

Todo bien con RoDi, con Gary y Martín, pero a mí me gusta Python y es lo que quiero enseñar :) . Así que me hice una API super sencilla utilizando requests para empezar a gestionar la idea loca de hacer un curso de Python + Robótica para chicos y ver cómo me va. En principio sería un juego, una aventura más que nada. Tengo algunas ideas en la cabeza, pero hay que meterle fichas y hacerla más tangible...

>>> import rodi
>>> robot = rodi.RoDi()
>>> robot.blink(1000)
>>> robot.move_forward()
>>> robot.move_left()
>>> robot.move_backward()
>>> # easy, ha?
...

Y aquí un video de prueba:

Manuel Kaufmann (Humitos): POIs en La Palma de Cervelló

¡Qué lindo que es despertarse y recibir un mail tan alentador!

Hoy me escribió Konfrare Albert, desde una asociación muy pequeña de una población muy pequeña cercana a Barcelona (como lo describe él mismo) llamada Konfraria de la Vila del Pingüí:

Te escribo para informarte de que hemos conseguido que el
Ayuntamiento de nuestro pueblo se comprometa a utilizar
OpenStreetMap en su web, y empecé a intentar generarles un mapa
que aproveche el potencial de OpenStreetMap.

Me topé con tu página y me pareció genial, así que viendo que el
código tiene una licencia GPL me decidí a empezar a adaptarla a
nuestras necesidades. Todavía no he colgado el código en GitHub
pero sí, la idea es hacerlo.

Decime si esto no es un win-win. Yo hice el sitio web porque tenía una necesidad personal y la cubrí con esta página. Luego, lo publiqué y unos meses más tarde me escriben para decirme que se consiguió que el Ayuntamiento use OpenStreetMap en su web y que encima van a usar un software que escribí yo.

Aquí pueden visitar la adaptación que está haciendo Konfrare:

their-pois.thumbnail.jpg

Sitio web en Catalán que están usando en La Palma de Cervelló

my-pois.thumbnail.jpg

Sitio web original

¡Grosos estos pibes!

Nota

¡Además, aparezco en los agradecimientos en catalán! :)

Gran part del codi ha estat aprofitat de la pàgina creada per
Humitos (lloc web), i de la que en podeu trobar el codi a
GitHub sota una llicència GPL.