Contar objetos distintos parece una tarea sencilla, casi trivial. Pero para las computadoras, ha sido durante décadas un desafío técnico que consume recursos y exige soluciones complejas. Ahora, un trío de científicos ha revelado un algoritmo tan elegante como efectivo, capaz de revolucionar esta tarea fundamental con un enfoque increíblemente simple.

El eterno problema de contar cosas únicas

En teoría, contar cuántos elementos distintos hay en una lista no suena a gran hazaña. Para un humano, identificar cuántas palabras únicas hay en un párrafo o cuántos tipos de fruta hay en una cesta es cuestión de segundos. Pero para las computadoras, esta tarea —conocida como el problema de los elementos distintos— ha representado un obstáculo técnico durante años, especialmente en contextos donde la memoria y la velocidad son limitadas.

Las aplicaciones de este problema son vastas: desde detectar patrones de fraude financiero y analizar tráfico web en tiempo real, hasta procesar texto masivo, secuencias genéticas o datos de sensores en ciudades inteligentes. Tradicionalmente, este problema se ha resuelto mediante algoritmos “basados en hash”, que requieren funciones matemáticas sofisticadas y son sensibles a la calidad de dichas funciones. En otras palabras: funcionan, pero no son óptimos.

Eso cambió con la llegada del algoritmo CVM, bautizado así por sus creadores: Vinodchandran Variyam (Universidad de Nebraska-Lincoln), Sourav Chakraborty (Instituto Indio de Estadística) y Kuldeep Meel (Universidad de Toronto). Este método elimina las funciones hash y basa todo en una técnica de muestreo probabilístico tan clara que podría enseñarse a estudiantes de primer semestre.

En lugar de intentar rastrear cada elemento distinto, el algoritmo simula el conteo mediante rondas sucesivas de filtrado aleatorio. El truco está en usar lanzamientos virtuales de monedas para decidir si conservar un elemento en la memoria, que se reduce con cada ronda hasta que se llega a una lista final. Luego, con solo multiplicar el número de elementos por una potencia de 2 (según el número de rondas), se obtiene una estimación sorprendentemente precisa del total de elementos distintos.

Un algoritmo potente, eficiente y apto para principiantes

Lo que hace excepcional al algoritmo CVM no es solo su precisión, sino su eficiencia en términos de uso de memoria. En un ejemplo explicado por los propios investigadores, se intentó contar las palabras únicas de Hamlet con una memoria capaz de almacenar solo 100 palabras. Tras varias rondas de este filtrado aleatorio, el algoritmo estimó un total de 3,904 palabras distintas, muy cerca del número real: 3,967.

Con una capacidad ligeramente mayor —1,000 palabras— el margen de error se reduce a casi cero. Y como explicó Variyam: si tuvieras suficiente memoria para guardar todas las palabras desde el principio, la precisión sería del 100%. Pero el verdadero valor del CVM surge en escenarios donde eso no es posible. En la era del big data, donde se procesan millones de datos por segundo, un algoritmo que requiera menos memoria y recursos puede marcar una diferencia monumental.

Además, su implementación es directa. “El nuevo algoritmo es sorprendentemente simple y fácil de implementar”, señaló Andrew McGregor, profesor de la Universidad de Massachusetts, Amherst. 

Varios investigadores ya lo han incorporado en sus programas de estudio. Donald Knuth, considerado el padre del análisis de algoritmos, se sumó al coro de elogios: escribió en mayo de 2023 un artículo donde confesó que no podía dejar de compartirlo con sus colegas. 

“Estoy bastante seguro de que algo así se convertirá en un tema estándar en los libros de texto”, afirmó.

El algoritmo aún no ha sido formalmente revisado por pares, pero la comunidad científica lo ha validado oficiosamente a través de su uso, discusión y experimentación. En ese sentido, ya ha superado la prueba más importante: su aplicabilidad práctica.

¿Cómo algo tan simple tardó tanto en descubrirse?

En retrospectiva, lo más desconcertante sobre el CVM es cómo nadie había pensado en él antes. No se basa en una herramienta matemática esotérica ni en un descubrimiento tecnológico reciente que cambie para siempre la forma de contar. De hecho, emplea principios elementales de la teoría de la probabilidad que han estado al alcance de los investigadores durante décadas.

“Es sorprendente que este sencillo algoritmo no se hubiera descubierto antes”, dijo Variyam. Pero no es la primera vez que la ciencia pasa por alto lo evidente. A veces, lo más obvio está justo frente a nosotros, oculto por el deseo de encontrar soluciones complejas a problemas aparentemente complejos.

Este nuevo algoritmo para contar no solo simplifica un problema esencial de la informática: lo redefine. Y en un mundo donde la eficiencia en el manejo de datos es clave para el progreso tecnológico, eso lo convierte en un hito silencioso pero trascendental.

Referencia:

• arXiv/Distinct Elements in Streams: An Algorithm for the (Text) Book. Link