Misra y Gries definieron el problema de los pesos pesados (aunque no introdujeron el término pesos pesados [4] ) y describieron el primer algoritmo para ello en el artículo Finding repeated elements . [1] Su algoritmo extiende el algoritmo de búsqueda de mayoría de Boyer-Moore de manera significativa.
Una versión del problema de los pesos pesados es la siguiente: se da una bolsa b de n elementos y un entero k ≥ 2. Encuentre los valores que aparecen más de n ÷ k veces en b . El algoritmo de Misra-Gries resuelve el problema haciendo dos pasadas sobre los valores en b , mientras almacena como máximo k valores de b y su número de apariciones durante el transcurso del algoritmo.
Misra-Gries [1] es uno de los primeros algoritmos de transmisión y se describe a continuación en esos términos en la sección #Resúmenes.
Una bolsa es como un conjunto en el que el mismo valor puede aparecer varias veces. Supongamos que una bolsa está disponible como una matriz b[0:n – 1] de n elementos. En la descripción abstracta del algoritmo, tratamos a b y sus segmentos también como bolsas. De aquí en adelante, un peso pesado de la bolsa b es un valor que aparece más de n ÷ k veces en ella, para algún entero k , k≥2 .
Una bolsa k -reducida para la bolsa b se deriva de b repitiendo la siguiente operación hasta que ya no sea posible: eliminar k elementos distintos de b . Según su definición, una bolsa k -reducida contiene menos de k valores diferentes. El siguiente teorema es fácil de demostrar:
Teorema 1. Cada peso pesado de b es un elemento de una bolsa k -reducida para b .
El primer paso del cálculo de los elementos pesados construye una bolsa t reducida a k . El segundo paso declara que un elemento de t es un elemento pesado si aparece más de n ÷ k veces en b . Según el Teorema 1, este procedimiento determina todos y solo los elementos pesados. El segundo paso es fácil de programar, por lo que describimos solo el primer paso.
Para construir t , escanee los valores en b en un orden arbitrario. Para mayor especificidad, el siguiente algoritmo los escanea en el orden de índices crecientes. La invariante P del algoritmo es que t es una bolsa k -reducida para los valores escaneados y d es el número de valores distintos en t . Inicialmente, no se ha escaneado ningún valor, t es la bolsa vacía y d es cero.
Siempre que se escanea el elemento b[i] , para preservar el invariante: (1) si b[i] no está en t , agréguelo a t y aumente d en 1, (2) si b[i] está en t , agréguelo a t pero no modifique d , y (3) si d se vuelve igual a k , reduzca t eliminando k valores distintos de él y actualice d apropiadamente.
El algoritmo Misra–Gries es t, d := { }, 0 para i de 0 a n-1 hacer si b[i] t entonces t, d:= t ∪ {b[i]}, d+1 demás t, d:= t ∪ {b[i]}, d endif si d = k entonces Borrar k valores distintos de t; actualizar d endif endforUna posible implementación de t es como un conjunto de pares de la forma (v i , c i ) donde cada v i es un valor distinto en t y c i es el número de ocurrencias de v i en t . Entonces d es el tamaño de este conjunto. El paso "Eliminar k valores distintos de t " equivale a reducir cada c i en 1 y luego eliminar cualquier par ( v i , c i ) del conjunto si c i se convierte en 0.
Usando una implementación de árbol AVL de t , el algoritmo tiene un tiempo de ejecución de O(n log k) . Para evaluar el requerimiento de espacio, suponga que los elementos de b pueden tener m valores posibles, por lo que el almacenamiento de un valor v i necesita O(log m) bits. Dado que cada contador c i puede tener un valor tan alto como n , su almacenamiento necesita O(log n) bits. Por lo tanto, para O(k) pares valor-contador, el requerimiento de espacio es O(k (log n + log m)) .
En el campo de los algoritmos de streaming , la salida del algoritmo Misra-Gries en el primer paso puede denominarse resumen , y dichos resúmenes se utilizan para resolver el problema de los elementos frecuentes en el modelo de flujo de datos . Un algoritmo de streaming realiza un número pequeño y limitado de pasadas sobre una lista de elementos de datos llamada flujo . Procesa los elementos utilizando como máximo una cantidad logarítmica de espacio adicional en el tamaño de la lista para producir una respuesta.
El término resumen de Misra-Gries parece haber sido acuñado por Graham Cormode. [5] [6]
