Archive for June 2009

## Text Partitioning

On optimally partitioning a text to improve its compression
Written by Paolo Ferragina, Igor Nitto and Rossano Venturini

I found this article really interesting and nicely presented. The problem they focus on is:

Problem: Given a compressor $C$ and a text $T$ of length $n$, drawn from an alphabet $\Sigma$ of size $\sigma$. Find the optimal partition of $T=T_1T_2\ldots T_k$ such that $|C(T_1)C(T_2)\ldots C(T_k)|$ is minimized.

This means that we want to cut the text in $k$ pieces, with $k$ unknown, such that applying the compressor $C$ over each piece achieves the best compression possible over the text. This is ignoring possible permutations of the text, such as the Burrows-Wheeler Transform (BWT).

A simple solution is to transform this problem into a shortest path problem, every position in the text is a node in the graph, and every node $i$ is connected with nodes $i+1,i+2,\ldots, n$. The cost of going from node $i$ to node j < i[/latex] is $|C(T_{i,j})|$. It is easy to see that the best partition obtains a total size equal to the minimum path from $1$ to $n$. Here I include a figure of the graph (using IPE :-)). [caption id="attachment_49" align="aligncenter" width="449" caption="Example shortest path for text partitioning"][/caption] The main problem is that just building this graph takes [latex]O(n^3) time. Assume that $C$ takes linear time to compress a sequence, then building the graph takes:

$\sum_{i=1}^{n-1} \sum_{j=i+1}^n j-i =\sum_{i=1}^{n-1}\sum_{j=1}^{n-i} j = \sum_{i=1}^{n-1}\sum_{j=1}^{n-1} j$ $= \sum_{i=1}^{n-1} O(n^2) = O(n^3)$

In the paper they present an algorithm to approximate the problem, they require $O(n\log_{\epsilon+1}n)$ time and achieve an $(1+\epsilon)-$approximation. The main idea behind the approach is to approximate the graph in such a way that, by storing less edges, they can still approximate the cost of the minimum path. They show how to run the algorithm without building the approximated version of the graph, to keep the space consumption low. They also show how to estimate the size of the compression for 0-order and k-order compressors during the process.

## Drawings for Latex

Maybe many of you know many programs for drawing in Linux that allow you to embed the image in a $\LaTeX$ document and at the same time use the math typesettings of $\LaTeX$. I used to draw in Dia (dia-gnome in Ubuntu), then I devolved to xfig. Ok, lets stop here, I say devolved because I like better dia, not because I want to start a religious fight :-).

A couple of months ago Alejandro showed me a program called IPE (also in Ubuntu repositories). This program is amazing, it is easy to use (and that coming from a really bad user) and it supports $\LaTeX$ in a very friendly way, just type latex into the text fields and then with Ctrl+l you make the transition between the code and the actual drawing, you can see the way the picture looks right away and what you see is exactly what you get.

The only problem so far, I still don’t know how to change a text after typing it, but there is a solution for this (besides the brute-force approach of making the whole image from scratch). When you save the image as .ipe file, the file contains an XML that represents the image and has the source of each text, you can modify it there and then load the image into IPE again.

I’m editing the post to add the link to IPE, as Victor suggested:

http://tclab.kaist.ac.kr/ipe/

## Cooler address and Latex support

I just moved the blog with it’s old content to continue here, I got a much cooler url! Anyway, the main reason for moving the blog wasn’t the url, it was the $LaTeX$ support :-), now I can type geekier things like $\sum_{i=0}^n 2^i = 2^{n+1}-1$. And what has this to do with Categories Math and Computer Science? I just used them so they have at least one post :p.

## Wireless Card Linux/Windows

I moved to my new place last month and the second thing I got was the Internet connection (first was the bed). My new apartment is small but has a *really* bad distribution of all the plugs in the walls. Since I didn’t have any good way to connect with a wire my computer to the router, I bought a wireless card. The card is a TRENDnet TEW-421PC/423PI, which is really cheap and it’s supposed to work fine. My apartment is so small that it shouldn’t give any problems, yet it did. The connection did drop randomly from time to time, as always, the drops did occur on the worst moment possible. It did happen in Linux (Ubuntu 9.04 32 bits) and Windows XP, but my notebook was working fine (so I assumed it was the card and not the router). When I was about to take the card back to the place I bought it, I found a page that explained that you could update your driver for the card using windows update. That did work perfectly, and then the problem for Linux was remaining. What I did was to install ndiswrapper with the drivers that came with the card and then copy the file rtl8185.sys from the folder system32 (in Windows) to /etc/ndiswrapper/net8185/. Now my Linux works with the new driver too, until now everything seems to work fine.

## And I’m back…

Yes, after almost one year I’m starting to write again, or maybe starting to write, didn’t write much last time :p. A big difference now is that I’m writing in English. Why? Well, it has a very simple explanation. I’m living in Canada now and most of the people I’ve met last time don’t speak Spanish. The second reason, and the most important one, most people I know will understand the posts in English, maybe using Google translator, but if they want to read it they will. The same doesn’t happen that much in the other direction, so here I go. By the way, this helps me to improve or practice mi writing =).

A couple of weeks ago I discovered Google Reader. By this time I think I’m almost selling my soul to Google: Gmail, Google Calendar, this blog, and now, Google Reader. Still it’s a really great application, it saves me from checking lots of pages that I visit almost every week and sometimes don’t find anything new or too many new things that I don’t know where to start. Now I just visit Google Reader every day and that’s it.

Ok, what’s this post about? I’m not writing the post to promote Google Reader itself, but to list the subscriptions I find more interesting :-). Here’s the list:

– http://blog.computationalcomplexity.org/feeds/posts/default
– http://mysliceofpizza.blogspot.com/feeds/posts/default
– http://terrytao.wordpress.com/feed/

And you can also add my blog :P http://fclaude.recoded.cl

## Y se terminó

Bueno, no completamente, pero ya el viernes pasado entregué el borrador de mi tesis. Ahora estoy de “vacaciones” por un rato. Eso se suponía hasta hoy, me llegó una buena noticia, pero que me obliga a trabajar. De todas formas, este post es para contar el alivio que significó el por fin entregar mi borrador.

Después de tanto tiempo trabajando en la tesis y además de haber sufrido todos los errores que cometí, y conté en el post anterior, ya por fin se terminó (al menos hasta que lleguen las correcciones). Ahora queda esperar la fecha de la defensa y esperar que todo salga bien :).

Ya desde el jueves retomaré mi descanso al menos por algunos días, después a seguir trabajando, pero mucho más relajado =).

## El stress de escribir una tesis…

Hace un par de días estaba hablando con un amigo sobre como darse cuenta cuando uno está estresado. La verdad es que a veces no es tan fácil notarlo. En general los motivos son diversos, no todos nos preocupamos por las mismas cosas y no a todos nos afectan de la misma manera. En mi caso lo que me tenía MUY preocupado era mi tesis. Mi tesis ha sido un trabajo entretenido y muy gratificante, lamentablemente ya estoy contra el reloj y tengo solo un par de meses para defenderla y estar listo. Lo curioso es que mi tesis ha salido bastante bien, no debiese estar tan preocupado ni tan atrasado, ¿en qué momento pasó esto? ¿qué hice mal en el camino?

Creo que es importante plantearse esas cosas cada vez que uno está terminando algo, siempre es bueno mejorar las experiencias venideras. En lo que sigue contaré los errores que a mi gusto cometí, de seguro hay muchos más.

Vamos desde el principio. Aunque el comienzo de mi tesis no fue tan bueno como uno podría esperar, no puedo quejarme. Acostumbrarse a un tema nuevo cuesta trabajo y mucho. Pero después ya es un trabajo, uno debe seguir avanzando y ya está. Pero ahora cuando ya estoy en la escritura me doy cuenta de que me faltaron algunas cosas en el proceso. Uno se obseciona con obtener resultados buenos y trabaja enfocado en ese objetivo, demasiado rápido a veces y no te detienes a ver bien las cosas. Cuando llega el final te das cuenta de que hay muchas cosas que deberías haber revisado mejor y pierdes demasiado tiempo haciéndolo. Pero eso no es lo peor, lo peor es que uno suele escribir sólo las cosas buenas mientras está haciendo la tesis. Te preocupas de los resultados publicables y vas dejando los otros de lado. Pero al final los necesitas también. No puedes escribir la tesis sin esos intentos fallidos que le dan la continuidad y que además agregan el valor de cerrar posibles caminos a explorar para futuros trabajos.

Durante la escritura lo que más me ha costado es recordar exactamente qué es lo que hice en las partes no novedosas (sin mencionar el inglés y los problemas de redacción), las que no te parecieron interesantes pero que hoy las necesito. Además me ha perjudicado el no haber sido ordenado para tabular y guardar los resultados, muchas cosas las he tenido que medir de nuevo por no recordar las condiciones en las que medí la primera vez.

Creo que esos fueron los errores principales, es importante considerarlos para mi próxima tesis. Uno no tiene el tiempo para escribir todo a medida que lo hace, sobre todo porque también está la presión por publicar artículos que son más urgentes y tienen plazos más estrechos. Lo que sí es posible, es mantener un resumen de lo que vas haciendo y además mantener los datos relevantes ordenados. No vale la pena repetir el trabajo de medición después por haber sido descuidado al principio.

Hay otro punto que es más complicado pero que no se puede clasificar como un error directamente y es la libertad que uno tiene mientras hace su tesis. Cuesta mantener un ritmo de trabajo sin horarios establecidos y sin una presión constante, al menos a mi me costó mucho al principio. Uno siempre cree que después se puede poner al día y a la larga acumula suficiente para que ese proceso no sea del todo placentero. De hecho, suele significar un par de noches en vela :P.

## LoudWords Alpha

Así empezó nuestra conversación en msn con mi amigo Mauricio Farah:

Mauricio says:
yo estoy orgulloso, instalar un msi hecho por mis amiguis
Francisco http://www.loudwords.cl el mejor servicio del mundo!!! says:
jajajajaja siiiii
Francisco http://www.loudwords.cl el mejor servicio del mundo!!! says:
yo tb, y les quedó bonito
Mauricio says:
si, esta bueno

¿Por qué pasó esto? Bueno, ambos conocemos al equipo de Loudwords (http://www.loudwords.cl/) pero además tenemos algo en común, la frase de nuestro msn dice lo mismo: http://www.loudwords.cl/, promueve lo bueno. Esa es la idea de LoudWords, las empresas pueden hacer publicidad a través de msn y mejor aún, a los usuarios se les paga por adoptar a las marcas como auspiciadores. Además se puede promover causas.

La idea es MUY buena, además el instalador es fácil de usar y no afecta en nada el funcionamiento de messenger. Realmente vale la pena probarlo! Se puede descargar en la página de LoudWords (sección de Usuarios). Por ahora el servicio está en la versión alpha y aún no hay auspiciadores.