El algoritmo de voto mayoritario de Boyer-Moore es un algoritmo para encontrar la mayoría de una secuencia de elementos usando tiempo lineal y espacio constante. Lleva el nombre de Robert S. Boyer y J Strother Moore , quienes lo publicaron en 1981, [1] y es un ejemplo prototípico de un algoritmo de transmisión .
En su forma más simple, el algoritmo encuentra un elemento mayoritario, si lo hay: es decir, un elemento que ocurre repetidamente para más de la mitad de los elementos de la entrada. Se puede usar una versión del algoritmo que hace una segunda pasada a través de los datos para verificar que el elemento encontrado en la primera pasada sea realmente mayoritario.
Si no se realiza una segunda pasada y no hay mayoría, el algoritmo no detectará que no existe mayoría. En el caso de que no exista una mayoría estricta, el elemento devuelto puede ser arbitrario; no se garantiza que sea el elemento que ocurre con mayor frecuencia (el modo de la secuencia). No es posible que un algoritmo de transmisión encuentre el elemento más frecuente en un espacio menos que lineal, para secuencias cuyo número de repeticiones puede ser pequeño. [2]
Descripción
El algoritmo mantiene en sus variables locales un elemento de secuencia y un contador, siendo el contador inicialmente cero. Luego procesa los elementos de la secuencia, uno a la vez. Al procesar un elemento x , si el contador es cero, el algoritmo almacena x como su elemento de secuencia recordado y establece el contador en uno. De lo contrario, compara x con el elemento almacenado y aumenta el contador (si son iguales) o disminuye el contador (en caso contrario). Al final de este proceso, si la secuencia tiene mayoría, será el elemento almacenado por el algoritmo. Esto se puede expresar en pseudocódigo mediante los siguientes pasos:
- Inicializar un elemento my un contador i con i = 0
- Para cada elemento x de la secuencia de entrada:
- Si i = 0 , entonces asigne m = x e i = 1
- de lo contrario, si m = x , entonces asigne i = i + 1
- si no, asigne i = i - 1
- Regresar m
Incluso cuando la secuencia de entrada no tiene mayoría, el algoritmo informará uno de los elementos de la secuencia como resultado. Sin embargo, es posible realizar una segunda pasada sobre la misma secuencia de entrada para contar el número de veces que ocurre el elemento informado y determinar si realmente es una mayoría. Este segundo paso es necesario, ya que no es posible que un algoritmo de espacio sublineal determine si existe un elemento mayoritario en un solo paso a través de la entrada. [3]
Análisis
La cantidad de memoria que necesita el algoritmo es el espacio para un elemento y un contador. En el modelo informático de acceso aleatorio que se utiliza habitualmente para el análisis de algoritmos , cada uno de estos valores se puede almacenar en una palabra de máquina y el espacio total necesario es O (1) . Si se necesita un índice de matriz para realizar un seguimiento de la posición del algoritmo en la secuencia de entrada, no cambia el límite de espacio constante general. La complejidad de bits del algoritmo (el espacio que necesitaría, por ejemplo, en una máquina de Turing ) es mayor, la suma de los logaritmos binarios de la longitud de entrada y el tamaño del universo del que se extraen los elementos. [2] Tanto el modelo de acceso aleatorio como los análisis de complejidad de bits solo cuentan el almacenamiento de trabajo del algoritmo, y no el almacenamiento de la secuencia de entrada en sí.
De manera similar, en una máquina de acceso aleatorio, el algoritmo toma tiempo O ( n ) (tiempo lineal) en una secuencia de entrada de n elementos, porque realiza solo un número constante de operaciones por elemento de entrada. El algoritmo también se puede implementar en una máquina de Turing en el tiempo lineal en la longitud de entrada ( n veces el número de bits por elemento de entrada).
Exactitud
Si hay un elemento mayoritario, el algoritmo siempre lo encontrará. Porque, suponiendo que el elemento mayoritario es m , sea c un número definido en cualquier paso del algoritmo para ser el contador, si el elemento almacenado es m , o la negación del contador en caso contrario. Luego, en cada paso en el que el algoritmo encuentra un valor igual am , el valor de c aumentará en uno, y en cada paso en el que encuentre un valor diferente, el valor de c puede aumentar o disminuir en uno. Si m es realmente la mayoría, habrá más aumentos que disminuciones, y c será positivo al final del algoritmo. Pero esto puede ser cierto solo cuando el elemento final almacenado es m , el elemento mayoritario.
Ver también
- Problema de distinción de elementos , el problema de probar si una colección de elementos tiene elementos repetidos
- Función de mayoría , la mayoría de una colección de valores booleanos
- Problema mayoritario (autómata celular) , el problema de encontrar un elemento mayoritario en el modelo computacional del autómata celular
Referencias
- ^ Boyer, RS ; Moore, J S. (1991), "MJRTY - A Fast Majority Vote Algorithm", en Boyer, RS (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe , Automated Reasoning Series, Dordrecht, Países Bajos: Kluwer Academic Publishers , págs. 105-117, doi : 10.1007 / 978-94-011-3488-0_5. Publicado originalmente como informe técnico en 1981.
- ^ a b Trevisan, Luca ; Williams, Ryan (26 de enero de 2012), "Notas sobre algoritmos de transmisión" (PDF) , CS154: Automata and Complexity , Universidad de Stanford.
- ^ Cormode, Graham; Hadjieleftheriou, Marios (octubre de 2009), "Encontrar elementos frecuentes en flujos de datos", Comunicaciones del ACM , 52 (10): 97, doi : 10.1145 / 1562764.1562789 ,
ningún algoritmo puede distinguir correctamente los casos en los que un elemento está justo encima o justo por debajo del umbral en una sola pasada sin utilizar una gran cantidad de espacio
.