En el campo de los algoritmos de transmisión , los resúmenes de Misra-Gries se utilizan para resolver el problema de los elementos frecuentes en el modelo de transmisión de datos . Es decir, dado un flujo largo de entrada que solo se puede examinar una vez (y en algún orden arbitrario), el algoritmo de Misra-Gries se puede usar para calcular qué valor (si lo hay) constituye la mayor parte del flujo, o de manera más general , el conjunto de elementos que constituyen una fracción fija del flujo.
El resumen de Misra – Gries
Como para todos los algoritmos en el modelo de flujo de datos, la entrada es una secuencia finita de números enteros de un dominio finito. El algoritmo genera una matriz asociativa que tiene valores de la secuencia como claves y estimaciones de su frecuencia como los valores correspondientes. Toma un parámetro k que determina el tamaño de la matriz, lo que afecta tanto la calidad de las estimaciones como la cantidad de memoria utilizada.
algoritmo Misra-gries: [1] de entrada: A positivo número entero k A finito secuencia s tomando valores en el rango de 1,2, ..., m de salida: Una matriz asociativa A con las estimaciones de frecuencia para cada elemento de s A : = nueva matriz asociativa (vacía) mientras s no está vacío: tome un valor i de s si i está en las claves ( A ): A [ i ]: = A [i] + 1 en caso contrario si | claves ( A ) | < k - 1: A [ i ]: = 1 else : para cada K en las teclas ( A ): A [ K ]: = A [ K ] - 1 si A [ K ] = 0: quitar K de las teclas ( A ) regresar A
Propiedades
El algoritmo Misra-Gries utiliza el espacio O ( k (log ( m ) + log ( n ))) , donde m es el número de valores distintos en la secuencia yn es la longitud de la secuencia.
Se garantiza que todos los elementos que aparecen al menos n / k veces aparecerán en la matriz de salida. [1] Por lo tanto, en una segunda pasada sobre los datos, se pueden calcular las frecuencias exactas de los k −1 elementos para resolver el problema de los elementos frecuentes, o en el caso de k = 2, el problema de la mayoría. Esta segunda pasada ocupa un espacio O ( k log ( m )). [ cita requerida ]
La salida resúmenes (arrays) por el algoritmo son fusionables , en el sentido de que la combinación de los resúmenes de las dos corrientes de s y r mediante la adición de sus arrays keywise y luego decrementar cada contador en la matriz resultante hasta que sólo k claves de permanecer resultados en un resumen de la misma (o mejor) calidad en comparación con ejecutar el algoritmo Misra-Gries sobre la concatenación de s con r .
Ejemplo
Sea k = 2 y el flujo de datos sea 1,4,5,4,4,5,4,4 (n = 8, m = 5). Tenga en cuenta que 4 aparece 5 veces en el flujo de datos, lo que es más de n / k = 4 veces y, por lo tanto, debería aparecer como la salida del algoritmo.
Dado que k = 2 y | keys (A) | = k − 1 = 1, el algoritmo solo puede tener una clave con su valor correspondiente. El algoritmo se ejecutará de la siguiente manera (- significa que no hay ninguna clave presente):
Valor de la corriente | Clave | Valor |
---|---|---|
1 | 1 | 1 |
4 | - | 0 |
5 | 5 | 1 |
4 | - | 0 |
4 | 4 | 1 |
5 | - | 0 |
4 | 4 | 1 |
4 | 4 | 2 |
Salida: 4
Referencias
- ↑ a b Cormode, 2014 .
- Misra, J .; Gries, David (1982). "Encontrar elementos repetidos". Ciencia de la Programación de Computadores . 2 (2): 143-152. doi : 10.1016 / 0167-6423 (82) 90012-0 . hdl : 1813/6345 .
- Cormode, Graham (2014). "Resúmenes de Misra-Gries". En Kao, Ming-Yang (ed.). Enciclopedia de algoritmos . Springer EE. UU. págs. 1-5. doi : 10.1007 / 978-3-642-27848-8_572-1 . ISBN 9783642278488.