Algoritmus většinového hlasování Boyer – Moore - Boyer–Moore majority vote algorithm

Stav algoritmu Boyer – Moore po každém vstupním symbolu. Vstupy jsou zobrazeny ve spodní části obrázku a uložený prvek a počítadlo jsou zobrazeny jako symboly a jejich výšky podél černé křivky.

The Algoritmus většinového hlasování Boyer – Moore je algoritmus pro nalezení většina posloupnosti prvků pomocí lineární čas a konstantní prostor. Je pojmenován po Robert S. Boyer a J Strother Moore, který jej publikoval v roce 1981,^[1] a je prototypickým příkladem a streamovací algoritmus.

Ve své nejjednodušší formě vyhledá algoritmus většinový prvek, pokud existuje: tj. Prvek, který se opakovaně vyskytuje u více než poloviny prvků vstupu. Verze algoritmu, která provede druhý průchod datem, může slouží k ověření, že prvek nalezený v prvním průchodu je skutečně většinou.

Pokud se druhý průchod neprovede a není žádná většina, algoritmus nezjistí, že žádná většina neexistuje. V případě, že neexistuje žádná přísná většina, může být vrácený prvek libovolný; není zaručeno, že bude prvkem, který se vyskytuje nejčastěji ( režimu Není možné, aby streamovací algoritmus našel nejčastější prvek v méně než lineárním prostoru pro sekvence, jejichž počet opakování může být malý.^[2]

Popis

Algoritmus udržuje ve svém lokální proměnné prvek sekvence a počitadlo, přičemž počitadlo je zpočátku nulové. Potom zpracovává prvky sekvence po jednom. Při zpracování prvku $X$ , pokud je čítač nula, algoritmus ukládá $X$ jako jeho zapamatovaný sekvenční prvek a nastaví počítadlo na jeden. Jinak to porovná $X$ na uložený prvek a buď zvýší počitadlo (pokud jsou stejné), nebo sníží počitadlo (jinak). Na konci tohoto procesu, pokud má sekvence většinu, bude to prvek uložený v algoritmu. vyjádřen v pseudo kód jako následující kroky:

Inicializovat prvek $m$ a počítadlo $i$ s $i = 0$
Pro každý prvek X vstupní sekvence:
- Li $i = 0$ , poté přiřadit $m = X$ a $i = 1$
- jinak pokud $m = X$ , poté přiřadit $i = i + 1$
- jinak přiřadit $i = i - 1$
Vrátit se $m$

I když vstupní sekvence nemá většinu, algoritmus nahlásí jako výsledek jeden ze sekvenčních prvků. Je však možné provést druhý průchod přes stejnou vstupní sekvenci, aby se spočítal počet výskytů hlášeného prvku a Určete, zda je to vlastně většina. Tento druhý průchod je nutný, protože není možné, aby algoritmus sublearního prostoru určil, zda v jednom průchodu vstupem existuje většinový prvek.^[3]

Analýza

Množství paměti, které algoritmus potřebuje, je prostor pro jeden prvek a jeden čítač. V náhodný přístup model výpočtu obvykle používaný pro analýza algoritmů, každou z těchto hodnot lze uložit do a strojové slovo a celkový potřebný prostor je $Ó (1)$ . Pokud je index pole potřebný ke sledování polohy algoritmu ve vstupní sekvenci, nezmění to celkovou vázanou konstantní mezeru. trochu složitost (prostor, který by potřeboval například na a Turingův stroj ) je vyšší, součet binární logaritmy vstupní délky a velikosti vesmíru, ze kterého jsou prvky čerpány.^[2] Jak model náhodného přístupu, tak analýza bitové složitosti počítají pouze pracovní úložiště algoritmu, a nikoli úložiště samotné vstupní sekvence.

Podobně na stroji s náhodným přístupem algoritmus nějakou dobu trvá $Ó (n)$ (lineární čas) na vstupní posloupnosti $n$ položky, protože provádí pouze konstantní počet operací na vstupní položku. Algoritmus lze také implementovat na Turingově stroji v čase lineárně ve vstupní délce ( $n$ násobek počtu bitů na vstupní položku).

Správnost

Pokud existuje většinový prvek, algoritmus jej vždy najde. Předpokládejme, že většinový prvek je $m$ , nechť $C$ být číslo definované v kterémkoli kroku algoritmu jako čítač, pokud je uloženým prvkem $m$ , nebo negace pultu jinak. Pak v každém kroku, ve kterém algoritmus narazí na hodnotu rovnou $m$ , hodnota $C$ se zvýší o jednu a v každém kroku, ve kterém narazí na jinou hodnotu, bude hodnota $C$ se může zvýšit nebo snížit o jednu. Li $m$ ve skutečnosti je většina, bude více přírůstků než úbytků a $C$ bude pozitivní na konci algoritmu. To však může být pravda, pouze pokud je konečný uložený prvek $m$ , většinový prvek.

Viz také

Problém odlišnosti prvku, problém testování, zda kolekce prvků má nějaké opakované prvky
Funkce většiny, většina sbírky Booleovské hodnoty
Většinový problém (mobilní automat), problém najít většinový prvek v EU buněčný automat výpočetní model

Reference

^ Boyer, R. S.; Moore, J S. (1991), „MJRTY - algoritmus rychlého většinového hlasování“, Boyer, R. S. (ed.), Automated Reasoning: Eseje na počest Woodyho Bledsoe, Automated Reasoning Series, Dordrecht, Nizozemsko: Kluwer Academic Publishers, str. 105–117, doi:10.1007/978-94-011-3488-0_5. Původně publikováno jako technická zpráva v roce 1981.
^ ^A ^b Trevisan, Luca; Williams, Ryan (26. ledna 2012), „Poznámky k streamovacím algoritmům“ (PDF), CS154: Automaty a složitost, Stanfordská Univerzita.
^ Cormode, Graham; Hadjieleftheriou, Marios (říjen 2009), „Hledání častých položek v datových tocích“, Komunikace ACM, 52 (10): 97, doi:10.1145/1562764.1562789, žádný algoritmus nedokáže správně rozlišit případy, kdy je položka těsně nad nebo těsně pod prahovou hodnotou v jediném průchodu bez použití velkého prostoru.

[bm-1] Boyer, R. S.; Moore, J S. (1991), „MJRTY - algoritmus rychlého většinového hlasování“, Boyer, R. S. (ed.), Automated Reasoning: Eseje na počest Woodyho Bledsoe, Automated Reasoning Series, Dordrecht, Nizozemsko: Kluwer Academic Publishers, str. 105–117, doi:10.1007/978-94-011-3488-0_5. Původně publikováno jako technická zpráva v roce 1981.

[cs154-2] A ^b Trevisan, Luca; Williams, Ryan (26. ledna 2012), „Poznámky k streamovacím algoritmům“ (PDF), CS154: Automaty a složitost, Stanfordská Univerzita.

[3] Cormode, Graham; Hadjieleftheriou, Marios (říjen 2009), „Hledání častých položek v datových tocích“, Komunikace ACM, 52 (10): 97, doi:10.1145/1562764.1562789, žádný algoritmus nedokáže správně rozlišit případy, kdy je položka těsně nad nebo těsně pod prahovou hodnotou v jediném průchodu bez použití velkého prostoru.

[1]

[2]

[3]