Алгоритм більшості голосів Боєра — Мура

Алгоритм більшості голосів Боєра — Мура — це алгоритм для знаходження більшості для послідовності елементів з використанням лінійного часу та постійної кількості слів пам'яті. Алгоритм названий на честь Роберта Боєра та Джея Мура, які опублікували його в 1981 році, і є прототипним прикладом потокового алгоритму.

Стан алгоритму Боєра — Мура після обробки кожного вхідного символу. Вхідні дані показані в нижній частині малюнка, а збережений елемент і значення лічильника елемента у відповідному стані зображені як символ та висота.

У своїй найпростішій формі алгоритм знаходить основний елемент, якщо він є: тобто елемент, який повторюється для більш ніж половини елементів вхідних даних. Для перевірки того, що елемент, знайдений під час першого проходу, дійсно є основним, можна виконати другий прохід по даним при якому підраховується скільки разів зустрічається цей елемент, після чого перевіряється, що елемент є основним.

Якщо не виконувати другий прохід і при цьому немає більшості, то алгоритм не виявить, що більшість відсутня. У випадку, якщо не існує строгої більшості, повернутий елемент може бути довільним; не гарантовано, що це елемент, який зустрічається найчастіше (мода послідовності). Потоковий алгоритм не може знайти найпоширеніший елемент без використання менш ніж лінійного простору у випадку послідовностей, кількість повторень в яких може бути невеликою.

Опис алгоритму

Алгоритм підтримує у своїх локальних змінних елемент послідовності та лічильник, причому лічильник спочатку дорівнює нулю. Потім він один за одним обробляє елементи послідовності. Під час обробки елемента x, якщо лічильник дорівнює нулю, алгоритм зберігає x як запам'ятований елемент послідовності та встановлює лічильник на одиницю. В іншому випадку він порівнює x із збереженим елементом і або збільшує лічильник (якщо вони однакові), або зменшує лічильник (в іншому випадку). Наприкінці цього процесу, якщо послідовність має більшість, це буде елемент, отриманий алгоритмом. Підсумуємо опис алгоритму в псевдокоді:

• Ініціалізувати елемент m та лічильник i з i = 0
• Для кожного елемента x вхідної послідовності:
  • Якщо i = 0, тоді присвоїти m = x і i = 1
  • інакше, якщо m = x, тоді присвоїти i = i + 1
  • інакше присвоїти i = i − 1
• Повернути m

Навіть якщо вхідна послідовність не має більшості, алгоритм повідомить один з елементів послідовності як результат роботи. Однак, можна виконати другий прохід над тією ж вхідною послідовністю, щоб підрахувати, скільки разів зустрічається отриманий раніше елемент і визначити, чи є він насправді більшістю. Цей другий прохід необхідний, оскільки алгоритм, який використовує сублінійний простір не може визначити, чи існує основний елемент за один прохід по входовим даним.

Реалізація на мові Python

Знайдемо елемент, який може бути основним і перевіримо його на більшість.

from typing import List, Union

def majorityElement(nums: List[int]) -> Union[int, None]:
    candidate, counter = None, 0
    for element in nums:
        if element == candidate:
            counter += 1
        elif counter == 0:
            candidate, counter = element, 1
        else:
            counter -= 1
    # Перевіряємо на більшість
    if nums.count(candidate) >= len(nums) // 2 + 1:
        majority_element = candidate
    else:
        majority_element = None
    return majority_element

Аналіз алгоритму

Об'єм пам'яті, який потрібен алгоритму, — це простір для одного елемента та одного лічильника. У моделі обчислень з довільним доступом, яка зазвичай використовується для аналізу алгоритмів, кожне з цих значень може зберігатися в машинному слові, а загальний необхідний простір дорівнює O(1). Якщо для відстеження позиції алгоритму у вхідній послідовності потрібен індекс масиву, то він не змінює загальну оцінку простору. Бітова складність алгоритму (простір, який йому знадобиться, наприклад, на машині Тьюрінга) є вищою, ніж сума двійкових логарифмів довжини вхідних даних і розміру універсуму, з якого беруться елементи. Як модель довільного доступу, так і аналіз бітової складності враховують лише робочу пам'ять алгоритму, а не пам'ять для самої вхідної послідовності.

Аналогічно, на машині з довільним доступом алгоритм займає час O(n) (лінійний час) для вхідної послідовності з n елементів, оскільки він виконує лише постійну кількість операцій на кожен вхідний елемент. Алгоритм також може бути реалізований на машині Тюрінга в часі, лінійному відносно довжини входу (n помножене на число бітів виділених на вхідний елемент).

Коректність алгоритму

Припустимо, що ми маємо послідовність розміром N, яка має мажоритарний елемент m. Шляхом заперечення можна показати, що алгоритм не може вивести немажоритарний елемент.

Алгоритм вибирає перший елемент у послідовності як мажоритарний кандидат c та ініціалізує counter для цього кандидата зі значенням 1. Якщо кандидат не є мажоритарним елементом, тоді лічильник повинен досягати нуля, оскільки в послідовності є більше елементів, які не дорівнюють кандидату. Коли лічильник досягає нуля після K < N ітерацій, ми обробили рівно K / 2 елементів із значенням кандидата (K має бути парним). Незалежно від того, дорівнює кандидат мажоритарному елементу m чи ні, у нас залишається підпослідовність довжиною N — K, де m все ще є мажоритарним елементом.

Див. також

• Задача відмінності елементів, задача на перевірку того, що колекція має будь-які повторювані елементи
• Мажоритарна функція, більшість із колекції булевих значень
• Задача більшості, задача знаходження мажоритарного елемента в обчислювальній моделі клітинного автомата
• Алгоритм Місри — Ґріса про важких нападників та резюме Місри — Ґріса, природне узагальнення алгоритму Боєра — Мура щодо зберігання кількох елементів.