Algoritmo de votación mayoritaria de Boyer-Moore

El algoritmo de votación mayoritaria de Boyer-Moore es un algoritmo para encontrar la mayoría de una secuencia de elementos utilizando tiempo lineal y un número constante de palabras de memoria. Recibe su 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 procesamiento en flujo .

En su forma más simple, el algoritmo encuentra un elemento mayoritario, si lo hay: es decir, un elemento que aparece repetidamente en más de la mitad de los elementos de la entrada. Se puede usar una versión del algoritmo que realiza una segunda pasada por los datos para verificar que el elemento encontrado en la primera pasada sea realmente mayoritario. ^{[ 1 ]}

Si no se realiza una segunda pasada y no hay mayoría, el algoritmo no detectará que no existe una mayoría estricta. En caso de que no exista una mayoría estricta, el elemento devuelto puede ser arbitrario; no se garantiza que sea el elemento que aparece con mayor frecuencia (la moda de la secuencia). Para secuencias cuyo número de repeticiones puede ser pequeño, no es posible que un algoritmo de procesamiento en flujo encuentre el elemento más frecuente en un espacio menor que lineal. ^{[ 2 ]}

El algoritmo mantiene en sus variables locales un elemento de la secuencia y un 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, si son iguales, incrementa el contador o lo decrementa. Al final de este proceso, si la secuencia tiene una mayoría, será el elemento almacenado por el algoritmo. Esto se puede expresar en pseudocódigo como los siguientes pasos:

Inicializa un elemento m. Inicializa un contador c ← 0 para cada elemento x de la secuencia de entrada: si c = 0 , haz m ← x c ← 1 sino si m = x , haz c ← c + 1 sino haz c ← c - 1 regresa m

Incluso cuando la secuencia de entrada no tiene una mayoría, el algoritmo reportará 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 cuántas veces aparece el elemento reportado y determinar si realmente es una mayoría. Esta segunda pasada es necesaria, ya que un algoritmo de espacio sublineal no puede determinar si existe un elemento mayoritario en una sola pasada por la entrada. ^{[ 3 ]}

La cantidad de memoria que necesita el algoritmo es el espacio para un elemento y un contador. En el modelo de acceso aleatorio de computación que se usa 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 mantener un registro 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 para la secuencia de entrada en sí.

De forma similar, en una máquina de acceso aleatorio, el algoritmo requiere un tiempo O ( n ) (tiempo lineal) para una secuencia de entrada de n elementos, ya que realiza solo un número constante de operaciones por elemento de entrada. El algoritmo también puede implementarse en una máquina de Turing en un tiempo lineal con respecto a la longitud de la entrada ( n veces el número de bits por elemento de entrada). ^{[ 4 ]}

Tras procesar n elementos de entrada, la secuencia de entrada se puede particionar en ( n − c ) / 2 pares de elementos desiguales, y quedan c copias de m . Esta es una demostración por inducción; es trivialmente cierta cuando n = c = 0 , y se mantiene cada vez que se añade un elemento x :

• Si x = m , agréguelo al conjunto de c copias de m (e incremente c ).
• Si x ≠ m y c > 0 , entonces elimina una de las c copias de m del conjunto restante y emparéjala con el valor final (y decrementa c ).
• Si c = 0 , entonces establece m ← x y agrega x al conjunto (previamente vacío) de copias de m (y establece c en  1).

En todos los casos, se mantiene el invariante del bucle . ^{[ 1 ]}

Después de que se haya procesado toda la secuencia, se deduce que ningún elemento x ≠ m puede tener mayoría, porque x puede ser igual a lo sumo a un elemento de cada par desigual y a ninguna de las c copias restantes de m . Por lo tanto, si hay un elemento mayoritario, solo puede ser m . ^{[ 1 ]}

• Problema de distinción de elementos , el problema de comprobar si una colección de elementos tiene algún elemento repetido.
• Función de mayoría , la mayoría de una colección de valores booleanos.
• Problema de la mayoría (autómata celular) , el problema de encontrar un elemento mayoritario en el modelo computacional del autómata celular.
• El algoritmo de Misra-Gries para los candidatos más influyentes y el resumen de Misra-Gries son una generalización natural del algoritmo de votación mayoritaria de Boyer-Moore, que almacena más de un elemento y más de un recuento.