Алгоритм большинства голосов Бойера — Мура

Алгоритм большинства голосов Бойера — Мура — это алгоритм для нахождения преобладающего элемента последовательности. Преобладающим элементом последовательности длины n называется такой элемент этой последовательности, который встречается в ней более чем n/2 раз. Сложность данного алгоритма O(n), а требуемая дополнительная память — O(1).

Состояние алгоритма после каждого входящего символа. Входные символы представлены вдоль нижней части фигуры. Сохраненные элементы и их счет показаны на графике.

Алгоритм назван в честь Р. Бойера[англ.] и Джей Мура[англ.], опубликовавших его в 1981 году.[1]

Описание

править

Алгоритм требует введения двух дополнительных переменных: первая будет содержать элемент последовательности, который является наиболее подходящим на роль преобладающего элемента из уже рассмотренных, а вторая является счётчиком и изначально равна нулю. Алгоритм состоит из единственного прохода по рассматриваемой последовательности. На каждом шаге выполняются следующие действия: если текущее значение переменной-счётчика равно нулю, то данный элемент последовательности записывается в первую переменную, а счётчик становится равен 1. Если же значение счётчика отлично от нуля, то текущий элемент последовательности сравнивается со значением, записанным в первую переменную. Если они совпадают, то счётчик увеличивается на 1, иначе — уменьшается на 1.

Псевдокод алгоритма:

  • алг (a1, a2,... an):
    • counter ← 0
    • для всех i от 1 до n:
      • если counter = 0, то:
        • majority_element ← ai
        • counter ← 1
      • иначе если ai = majority_element:
        • counter ← counter+1
      • иначе:
        • counter ← counter-1
    • вывод majority_element

После рассмотрения всех элементов в первой переменной будет содержаться преобладающий элемент последовательности, если таковой существует. Однако если такового элемента в последовательности нет, то первая переменная всё равно будет содержать некоторый элемент последовательности . Поэтому, если уверенности в существовании преобладающего элемента нет, то следует выполнить дополнительный проход по массиву, дабы убедиться, что найденный элемент в массиве встречается более чем n/2 раз. Если в результате второго прохода окажется, что элемент встречается не более n/2 раз, то последовательность преобладающего элемента не содержит.[2]

Примечания

править
  1. Boyer, R. S.; Moore, J S. (1991), "MJRTY - A Fast Majority Vote Algorithm", in Boyer, R. S. (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, Dordrecht, The Netherlands: Kluwer Academic Publishers, pp. 105—117, doi:10.1007/978-94-011-3488-0_5{{citation}}: Википедия:Обслуживание CS1 (url-status) (ссылка) Originally published as a technical report in 1981.
  2. Cormode, Graham; Hadjieleftheriou, Marios (October 2009), "Finding the frequent items in streams of data", Communications of the ACM, 52 (10): 97, doi:10.1145/1562764.1562789, no algorithm can correctly distinguish the cases when an item is just above or just below the threshold in a single pass without using a large amount of space.