Haciendo uso de la aleatoriedad, un equipo ha creado un algoritmo simple para estimar una gran cantidad de objetos distintos en un flujo de datos.

Un artículo de Steve Nadis. Historia original reimpresa con permiso de Quanta Magazine, una publicación editorialmente independiente respaldada por la Fundación Simons.

Imagina que te envían a una selva tropical virgen para realizar un censo de la vida silvestre. Cada vez que ves un animal, tomas una foto. Tu cámara digital llevará un registro de la cantidad total de tomas, pero a ti solo te interesa la cantidad de animales únicos, todos los que aún no has contado. ¿Cuál es la mejor manera de obtener ese número? «La solución obvia requiere recordar todos los animales que has visto hasta ahora y comparar cada animal nuevo con la lista», explica Lance Fortnow, científico informático del Instituto de Tecnología de Illinois. Pero hay formas más inteligentes de proceder, añade, porque si tienes miles de entradas, el enfoque obvio no es nada fácil.

Se pone peor. ¿Qué pasa si eres Facebook y quieres contar la cantidad de usuarios distintos que inician sesión cada día, incluso si algunos de ellos inician sesión desde múltiples dispositivos y en múltiples ocasiones? Ahora estamos comparando cada nuevo inicio de sesión con una lista que podría ascender a miles de millones.

En un artículo reciente, los científicos informáticos han descrito una nueva forma de aproximar el número de entradas distintas en una lista larga, un método que requiere recordar solo una pequeña cantidad de entradas. El algoritmo funcionará para cualquier lista en la que los elementos se añadan de uno en uno: piensa en las palabras de un discurso, los productos en una cinta transportadora o los automóviles en una carretera.

El algoritmo CVM, llamado así por sus creadores (Sourav Chakraborty del Instituto Indio de Estadística, Vinodchandran Variyam de la Universidad de Nebraska en Lincoln, y Kuldeep Meel de la Universidad de Toronto) es un paso significativo hacia la solución del llamado problema de los elementos distintos, con el que los científicos informáticos llevan batallando más de 40 años. Pide una manera de monitorear eficientemente un flujo de elementos (cuyo número total puede exceder la memoria disponible) y luego estimar el número de elementos únicos.

«El nuevo algoritmo es sorprendentemente simple y fácil de implementar», comenta Andrew McGregor de la Universidad de Massachusetts, Amherst. «No me sorprendería que esta se convirtiera en la forma predeterminada de abordar en la práctica el problema [de los elementos distintos]».

Para ilustrar tanto el problema como cómo lo resuelve el algoritmo CVM, imagina que estás escuchando el audiolibro de Hamlet. Hay 30.557 palabras en la obra. ¿Cuantas son distintas? Para averiguarlo, puedes escuchar la obra (haciendo uso frecuente del botón de pausa), escribir cada palabra alfabéticamente en un cuaderno y saltarte las palabras que ya están en tu lista. Cuando llegues al final, simplemente contarás la cantidad de palabras de la lista. Este enfoque funciona, pero requiere una cantidad de memoria aproximadamente igual a la cantidad de palabras únicas.

En situaciones típicas de transmisión de datos podría haber millones de elementos de los que realizar un seguimiento. «Quizás no quieras almacenarlo todo», dice Variyam. Y ahí es donde el algoritmo CVM puede ofrecer una forma más sencilla. El truco, afirmó, consiste en confiar en la aleatorización.

Volvamos a Hamlet, pero esta vez tu memoria de trabajo, que consiste en una pizarra, tiene espacio para sólo 100 palabras. Una vez que comienza la obra, escribes las primeras 100 palabras que escuchas, omitiendo nuevamente las repeticiones. Cuando el espacio esté lleno, presiona pausa y lanza una moneda por cada palabra. Sale cara y la palabra permanece en la lista; cruz, y la borras. Después de esta ronda preliminar, te quedarán unas 50 palabras distintas.

Ahora avanza con lo que el equipo llama Ronda 1. Sigue leyendo Hamlet y agrega nuevas palabras a medida que avanzas. Si encuentras una palabra que ya está en tu lista, lanza una moneda nuevamente. Si es cruz, borra la palabra; cara y la palabra permanece en la lista. Continúa de esta manera hasta tener 100 palabras en la pizarra. Luego, elimina aleatoriamente aproximadamente la mitad nuevamente, según el resultado de 100 lanzamientos de moneda. Esto concluye la Ronda 1.

Luego, pasa a la Ronda 2. Continúa como en la Ronda 1, solo que ahora haremos que sea más difícil mantener una palabra. Cuando encuentres una palabra repetida, lanza la moneda nuevamente. Cruz, y la borras, como antes. Pero si sale cara, lanzarás la moneda por segunda vez. Solo mantén la palabra si obtienes una segunda cara. Una vez que llenas el tablero, la ronda termina con otra purga de aproximadamente la mitad de las palabras, basada en 100 lanzamientos de moneda.

En la tercera ronda, necesitarás tres caras seguidas para mantener una palabra. En la cuarta ronda necesitarás cuatro cabezas seguidas. Y así sucesivamente.

Finalmente, en la késima ronda, llegarás al final de Hamlet. El objetivo del ejercicio ha sido garantizar que cada palabra, en virtud de las selecciones aleatorias que has realizado, tenga la misma probabilidad de estar ahí: 1/2^k. Si, por ejemplo, tienes 61 palabras en tu lista al final de Hamlet y el proceso necesitó seis rondas, puedes dividir 61 por la probabilidad, 1/2⁶, para estimar el número de palabras distintas, lo que da un resultado de 3904 en este caso. (Es fácil ver cómo funciona este procedimiento: supongamos que comienzas con 100 monedas y lanzas cada una individualmente, conservando solo las que salen cara. Terminarás con cerca de 50 monedas, y si alguien divide ese número por la probabilidad , ½, puede adivinar que originalmente había alrededor de 100 monedas).

Variyam y sus colegas demostraron matemáticamente que la precisión de esta técnica aumenta con el tamaño de la memoria. Hamlet tiene exactamente 3.967 palabras únicas. (Las contaron). En experimentos que utilizaron una memoria de 100 palabras, la estimación promedio después de cinco ejecuciones fue de 3955 palabras. Con una memoria de 1.000 palabras, la media mejoró hasta 3.964. «Por supuesto», explica Variyam, «si la [memoria] es tan grande que caben todas las palabras, entonces podemos obtener una precisión del 100%».

«Este es un gran ejemplo de cómo, incluso para problemas muy básicos y bien estudiados, a veces hay soluciones muy simples pero no obvias esperando ser descubiertas», afirma William Kuszmaul de la Universidad de Harvard.

El artículo original, Computer Scientists Invent an Efficient New Way to Count, se publicó el 16 de mayo de 2024 en Quanta Magazine.

Traducido por César Tomé López