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

Boyer–Moore majority vote algorithm
Состояние алгоритма Бойера – Мура после каждого входного символа. Входы показаны в нижней части рисунка, а сохраненный элемент и счетчик показаны в виде символов, а их высота - вдоль черной кривой.

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

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

Если второй проход не выполняется и нет большинства, алгоритм не обнаружит отсутствия большинства. В случае отсутствия строгого большинства возвращаемый элемент может быть произвольным; не гарантируется, что это элемент, который встречается чаще всего ( Режим Потоковый алгоритм не может найти наиболее часто встречающийся элемент в менее чем линейном пространстве для последовательностей, количество повторений которых может быть небольшим.[2]

Описание

Алгоритм сохраняет в своем локальные переменные элемент последовательности и счетчик, причем счетчик изначально равен нулю. Затем он обрабатывает элементы последовательности, по одному за раз. Икс, если счетчик равен нулю, алгоритм сохраняет Икс как запомненный элемент последовательности и устанавливает счетчик на единицу. В противном случае он сравнивает Икс к сохраненному элементу и либо увеличивает счетчик (если они равны), либо уменьшает счетчик (в противном случае). В конце этого процесса, если последовательность имеет большинство, это будет элемент, сохраненный алгоритмом. Это может быть выражено в псевдокод как следующие шаги:

  • Инициализировать элемент м и счетчик я с я = 0
  • Для каждого элемента Икс входной последовательности:
    • Если я = 0, затем назначьте м = Икс и я = 1
    • иначе если м = Икс, затем назначьте я = я + 1
    • иначе назначить я = я − 1
  • Возвращаться м

Даже если входная последовательность не имеет большинства, алгоритм сообщит об одном из элементов последовательности в качестве своего результата. Однако можно выполнить второй проход над той же входной последовательностью, чтобы подсчитать, сколько раз встречается указанный элемент и Этот второй проход необходим, поскольку алгоритм сублинейного пространства не может определить, существует ли элемент большинства за один проход через вход.[3]

Анализ

Объем памяти, необходимый алгоритму, равен пространству для одного элемента и одного счетчика. в произвольный доступ модель вычислений, обычно используемая для анализ алгоритмов, каждое из этих значений можно сохранить в машинное слово а общее необходимое пространство О(1). Если индекс массива необходим для отслеживания положения алгоритма во входной последовательности, он не меняет общую границу постоянного пространства. битовая сложность (пространство, которое потребуется, например, на Машина Тьюринга) больше, сумма двоичные логарифмы входной длины и размера вселенной, из которой нарисованы элементы.[2] И модель произвольного доступа, и анализ битовой сложности учитывают только рабочую память алгоритма, но не память самой входной последовательности.

Точно так же на машине с произвольным доступом алгоритм требует времени О(п) (линейное время) на входной последовательности п items, потому что он выполняет только постоянное количество операций для каждого элемента ввода. Алгоритм также может быть реализован на машине Тьюринга во времени, линейном по входной длине (п умноженное на количество бит на элемент ввода).

Правильность

Если есть элемент большинства, алгоритм всегда его найдет. Ибо, если предположить, что мажоритарный элемент м, позволять c быть числом, определенным на любом шаге алгоритма как счетчик, если сохраненный элемент м, или отрицание счетчика в противном случае. Затем на каждом шаге, на котором алгоритм встречает значение, равное м, значение c увеличится на единицу, и на каждом шаге, на котором он встречает другое значение, значение c может увеличиваться или уменьшаться на единицу. Если м действительно большинство, будет больше увеличения, чем уменьшения, и c будет положительным в конце алгоритма. Но это может быть правдой только тогда, когда последний сохраненный элемент м, мажоритарный элемент.

Смотрите также

Рекомендации

  1. ^ Бойер, Р.С.; Мур, Дж. С. (1991), «MJRTY - алгоритм быстрого голосования большинством», в Бойе, Р. С. (ред.), Автоматизированное рассуждение: очерки в честь Вуди Бледсо, Automated Reasoning Series, Дордрехт, Нидерланды: Kluwer Academic Publishers, стр. 105–117, Дои:10.1007/978-94-011-3488-0_5. Первоначально опубликовано как технический отчет в 1981 году.
  2. ^ а б Тревизан, Лука; Уильямс, Райан (26 января 2012 г.), «Примечания к алгоритмам потоковой передачи» (PDF), CS154: Автоматы и сложность, Стэндфордский Университет.
  3. ^ Кормод, Грэм; Хаджилефтериу, Мариос (октябрь 2009 г.), «Обнаружение часто встречающихся элементов в потоках данных», Коммуникации ACM, 52 (10): 97, Дои:10.1145/1562764.1562789, ни один алгоритм не может правильно различить случаи, когда элемент находится чуть выше или чуть ниже порога за один проход без использования большого количества места.