Dotaz na režim rozsahu - Range mode query

v datové struktury, problém s režimem rozsahu žádá o vybudování datové struktury na některých vstupních datech, aby efektivně odpovídal na dotazy žádající o režimu jakékoli po sobě jdoucí podmnožiny vstupu.

Problémové prohlášení

Vzhledem k řadě ${ displaystyle A [1: n] = [a_ {1}, a_ {2}, ..., a_ {n}]}$ , chceme odpovědět na dotazy formuláře ${ displaystyle mode (A, i: j)}$ , kde ${ Displaystyle 1 leq já leq j leq n}$ . Způsob ${ displaystyle mode (S)}$ libovolného pole ${ displaystyle S = [s_ {1}, s_ {2}, ..., s_ {k}]}$ je prvek ${ displaystyle s_ {i}}$ taková, že frekvence ${ displaystyle s_ {i}}$ je větší nebo roven frekvenci ${ displaystyle s_ {j} ; celkem j v {1, ..., k }}$ . Například pokud ${ displaystyle S = [1,2,4,2,3,4,2]}$ , pak ${ displaystyle mode (S) = 2}$ protože se vyskytuje třikrát, zatímco všechny ostatní hodnoty se vyskytují méněkrát. V tomto problému se dotazy ptají na režim dílčích polí formuláře ${ displaystyle A [i: j] = [a_ {i}, a_ {i + 1}, ..., a_ {j}]}$ .

Věta 1

Nechat ${ displaystyle A}$ a ${ displaystyle B}$ být kdokoli multisety. Li ${ displaystyle c}$ je režim ${ displaystyle A cup B}$ a ${ displaystyle c notin A}$ , pak ${ displaystyle c}$ je režim ${ displaystyle B}$ .

Důkaz

Nechat ${ displaystyle c notin A}$ být módem ${ displaystyle C = A pohár B}$ a ${ displaystyle f_ {c}}$ být jeho frekvence v ${ displaystyle C}$ . Předpokládejme to ${ displaystyle c}$ není režim ${ displaystyle B}$ . Existuje tedy prvek ${ displaystyle b}$ s frekvencí ${ displaystyle f_ {b}}$ to je režim ${ displaystyle B}$ . Od té doby ${ displaystyle b}$ je režim ${ displaystyle B}$ a to ${ displaystyle c notin A}$ , pak ${ displaystyle f_ {b}> f_ {c}}$ . Tím pádem, ${ displaystyle b}$ by měl být režim ${ displaystyle C}$ což je rozpor.

Výsledek

Prostor	Čas dotazu	Omezení	Zdroj
${ displaystyle O (n)}$	${ displaystyle O ({ sqrt {n}})}$		^[1]
${ displaystyle O (n)}$	${ displaystyle O ({ sqrt {n / w}})}$	${ displaystyle w}$ je velikost slova	^[1]
${ displaystyle O (n ^ {2} log log n / log n)}$	${ displaystyle O (1)}$		^[2]
${ displaystyle O (n ^ {2-2 epsilon})}$	${ displaystyle O (n ^ { epsilon} log n)}$	${ displaystyle 0 leq epsilon leq 1/2}$	^[2]

Dolní mez

Libovolná datová struktura pomocí ${ displaystyle S}$ buňky ${ displaystyle w}$ bity každý potřebuje ${ displaystyle Omega left ({ frac { log n} { log (Sw / n)}} right)}$ čas odpovědět na dotaz v režimu rozsahu.^[3]

To kontrastuje s jinými problémy s dotazem na rozsah, jako je například dotaz na minimální rozsah, který má řešení nabízející čas dotazu na konstantní čas a lineární prostor. To je způsobeno tvrdostí problému režimu, protože i když režim známe ${ displaystyle A [i: j]}$ a režim ${ displaystyle A [j + 1: k]}$ , neexistuje jednoduchý způsob výpočtu režimu ${ displaystyle A [i: k]}$ . Libovolný prvek ${ displaystyle A [i: j]}$ nebo ${ displaystyle A [j + 1: k]}$ může být režim. Například pokud ${ displaystyle mode (A [i: j]) = a}$ a jeho frekvence je ${ displaystyle f_ {a}}$ , a ${ displaystyle mode (A [j + 1: k]) = b}$ a jeho frekvence je také ${ displaystyle f_ {a}}$ , mohl by tam být prvek ${ displaystyle c}$ s frekvencí ${ displaystyle f_ {a} -1}$ v ${ displaystyle A [i: j]}$ a frekvence ${ displaystyle f_ {a} -1}$ v ${ displaystyle A [j + 1: k]}$ . ${ displaystyle a not = c not = b}$ , ale jeho frekvence v ${ displaystyle A [i: k]}$ je větší než frekvence ${ displaystyle a}$ a ${ displaystyle b}$ , který dělá ${ displaystyle c}$ lepší kandidát na ${ displaystyle režim (A [i: k])}$ než ${ displaystyle a}$ nebo ${ displaystyle b}$ .

Struktura dat v lineárním prostoru s časem druhé odmocniny

Tato metoda od Chan et al.^[1] používá ${ displaystyle O (n + s ^ {2})}$ prostor a ${ displaystyle O (n / s)}$ čas dotazu. Nastavením ${ displaystyle s = { sqrt {n}}}$ , dostaneme ${ displaystyle O (n)}$ a ${ displaystyle O ({ sqrt {n}})}$ hranice prostoru a času dotazu.

Předběžné zpracování

Nechat ${ displaystyle A [1: n]}$ být pole a ${ displaystyle D [1: Delta]}$ být pole, které obsahuje odlišné hodnoty A, kde ${ displaystyle Delta}$ je počet odlišných prvků. Definujeme ${ displaystyle B [1: n]}$ být pole takové, že pro každého ${ displaystyle i}$ , ${ displaystyle B [i]}$ obsahuje hodnost (pozici) ${ displaystyle A [i]}$ v ${ displaystyle D}$ . Pole ${ displaystyle B, D}$ lze vytvořit lineárním skenováním ${ displaystyle A}$ .

Pole ${ displaystyle Q_ {1}, Q_ {2}, ..., Q _ { Delta}}$ jsou také vytvořeny tak, aby pro každého ${ displaystyle a in {1, ..., Delta }}$ , ${ displaystyle Q_ {a} = {b ; | ; B [b] = a }}$ . Poté vytvoříme pole ${ displaystyle B '[1: n]}$ , tak, že pro všechny ${ displaystyle b in {1, ..., n }}$ , ${ displaystyle B '[b]}$ obsahuje hodnost ${ displaystyle b}$ v ${ displaystyle Q_ {B [b]}}$ . Opět lineární sken ${ displaystyle B}$ stačí k vytvoření polí ${ displaystyle Q_ {1}, Q_ {2}, ..., Q _ { Delta}}$ a ${ displaystyle B '}$ .

Nyní je možné odpovědět na dotazy ve formuláři „je frekvence ${ displaystyle B [i]}$ v ${ displaystyle B [i: j]}$ alespoň ${ displaystyle q}$ "v konstantním čase kontrolou, zda ${ displaystyle Q_ {B [i]} [B '[i] + q-1] leq j}$ .

Pole je rozděleno na B ${ displaystyle s}$ bloky ${ displaystyle b_ {1}, b_ {2}, ..., b_ {s}}$ , každý o velikosti ${ displaystyle t = lceil n / s rceil}$ . Tedy blok ${ displaystyle b_ {i}}$ překlenuje ${ displaystyle B [i cdot t + 1: (i + 1) t]}$ . Režim a frekvence každého bloku nebo sady po sobě jdoucích bloků budou předem vypočítány ve dvou tabulkách ${ displaystyle S}$ a ${ displaystyle S '}$ . ${ displaystyle S [b_ {i}, b_ {j}]}$ je režim ${ displaystyle b_ {i} pohár b_ {i + 1} pohár ... pohár b_ {j}}$ nebo ekvivalentně režim ${ displaystyle B [b_ {i} t + 1: (b_ {j} +1) t]}$ , a ${ displaystyle S '}$ ukládá odpovídající frekvenci. Tyto dvě tabulky lze uložit do ${ displaystyle O (s ^ {2})}$ prostoru a lze je vyplnit ${ displaystyle O (s cdot n)}$ skenováním ${ displaystyle B}$ ${ displaystyle s}$ krát, výpočet řady ${ displaystyle S, S '}$ pokaždé s následujícím algoritmem:

algoritmus computeS_Sprime je    vstup: Pole B = [0: n - 1], pole D = [0: Delta - 1], celé číslo s    výstup: Tabulky S a Sprime    nechat S ← Tabulka (0: n - 1, 0: n - 1) let Sprime ← Tabulka (0: n - 1, 0: n - 1) let první Výskyt ← Pole (0: Delta - 1) pro všechny i v {0, ..., Delta - 1} dělat        firstOccurence [i] ← -1 konec pro    pro i ← 0: s - 1 dělat            nechat j ← i × t nechat C ← 0 let fc ← 0 let noBlock ← nechám block_start ← j nech block_end ← min {(i + 1) × t - 1, n - 1} zatímco j dělat                -li firstOccurence [B [j]] = -1 pak                firstOccurence [B [j]] ← j skončit, pokud		            -li atLeastQInstances (firstOccurence [B [j]], block_end, fc + 1) pak                c ← B [j] fc ← fc + 1 skončit, pokud		            -li j = block_end pak                S [i * s + noBlock] ← c Sprime [i × s + noBlock] ← fc noBlock ← noBlock + 1 block_end ← min {block_end + t, n - 1} skončit, pokud        skončit chvíli        pro všechny j v {0, ..., Delta - 1} dělat            firstOccurence [j] ← -1 konec pro    konec pro

Dotaz

Definujeme algoritmus dotazu přes pole ${ displaystyle B}$ . To lze přeložit jako odpověď ${ displaystyle A}$ , protože pro všechny ${ displaystyle a, i, j}$ , ${ displaystyle B [a]}$ je režim pro ${ displaystyle B [i: j]}$ kdyby a jen kdyby ${ displaystyle A [a]}$ je režim pro ${ displaystyle A [i: j]}$ . Můžeme převést odpověď na ${ displaystyle B}$ na odpověď pro ${ displaystyle A}$ v konstantním čase při pohledu dovnitř ${ displaystyle A}$ nebo ${ displaystyle B}$ na odpovídajícím indexu.

Byl zadán dotaz ${ displaystyle mode (B, i, j)}$ , je dotaz rozdělen do tří částí: prefix, span a přípona. Nechat ${ Displaystyle b_ {i} = lceil (i-1) / t rceil}$ a ${ displaystyle b_ {j} = lfloor j / t rfloor -1}$ . Ty označují indexy prvního a posledního bloku, které jsou zcela obsaženy v ${ displaystyle B}$ . Rozsah těchto bloků se nazývá rozpětí. Předpona je pak ${ displaystyle B [i: min {b_ {i} t, j }]}$ (sada indexů před rozpětím) a přípona je ${ displaystyle B [max {(b_ {j} +1) t + 1, i }: j]}$ (sada indexů po rozpětí). Předpona, přípona nebo rozpětí mohou být prázdné, druhé je if ${ displaystyle b_ {j}$ .

Pro rozpětí režim ${ displaystyle c}$ je již uložen v ${ displaystyle S [b_ {i}, b_ {j}]}$ . Nechat ${ displaystyle f_ {c}}$ být frekvence režimu, ve kterém je uložen ${ displaystyle S '[b_ {i}, b_ {j}]}$ . Pokud je rozpětí prázdné, nechte ${ displaystyle f_ {c} = 0}$ . Připomeňme, že podle věty 1 je režim ${ displaystyle B [i: j]}$ je buď prvek předpony, rozpětí nebo přípony. Přes každý prvek v předponě a v příponě se provádí lineární sken, aby se zkontrolovalo, zda je jeho frekvence větší než aktuální kandidát ${ displaystyle c}$ , v jakém případě ${ displaystyle c}$ a ${ displaystyle f_ {c}}$ jsou aktualizovány na novou hodnotu. Na konci skenování ${ displaystyle c}$ obsahuje režim ${ displaystyle B [i: j]}$ a ${ displaystyle f_ {c}}$ jeho frekvence.

Postup skenování

Postup je podobný pro předponu i příponu, takže stačí spustit tento postup pro obě:

Nechat ${ displaystyle x}$ být index aktuálního prvku. Existují tři případy:

Li ${ displaystyle Q_ {B [x]} [B '[x] -1] geq i}$ , pak byl přítomen v ${ displaystyle B [i: x-1]}$ a jeho frekvence již byla spočítána. Přechod na další prvek.
Jinak zkontrolujte, zda je frekvence ${ displaystyle B [x]}$ ${ displaystyle B [x]}$ v ${ displaystyle B [i: j]}$ ${ displaystyle B [i: j]}$ je alespoň ${ displaystyle f_ {c}}$ $f_ {c}$ (To lze provést v konstantním čase, protože je to ekvivalent kontroly ${ displaystyle B [x: j]}$ ${ displaystyle B [x: j]}$ ).
1. Pokud tomu tak není, přejděte na další prvek.
2. Pokud ano, pak vypočítat skutečnou frekvenci ${ displaystyle f_ {x}}$ z ${ displaystyle B [x]}$ v ${ displaystyle B [i: j]}$ lineárním skenováním (počínaje indexem ${ displaystyle B '[x] + f_ {c} -1}$ ) nebo binární vyhledávání v ${ displaystyle Q_ {B [x]}}$ . Soubor ${ displaystyle c: = B [x]}$ a ${ displaystyle f_ {c}: = f_ {x}}$ .

Toto lineární skenování (kromě frekvenčních výpočtů) je omezeno velikostí bloku ${ displaystyle t}$ , protože předpona ani přípona nesmí být větší než ${ displaystyle t}$ . Další analýza lineárních skenů provedených pro frekvenční výpočty ukazuje, že je také omezena velikostí bloku.^[1] Čas dotazu tedy je ${ displaystyle O (t) = O (n / s)}$ .

Subkvadratická datová struktura prostoru s konstantním časem dotazu

Tuto metodu ^[2] používá ${ displaystyle O left ({ frac {n ^ {2} log { log {n}}} { log {n}}} right)}$ prostor pro dotaz v konstantním čase. Můžeme pozorovat, že pokud je požadována konstantní doba dotazu, je to lepší řešení než řešení navržené Chanem a kol.,^[1] protože druhý dává prostor ${ displaystyle O (n ^ {2})}$ pro konstantní čas dotazu, pokud ${ displaystyle s = n}$ .

Předběžné zpracování

Nechat ${ displaystyle A [1: n]}$ být pole. Předzpracování se provádí ve třech krocích:

Rozdělte pole ${ displaystyle A}$ v ${ displaystyle s}$ bloky ${ displaystyle b_ {1}, b_ {2}, ..., b_ {s}}$ , kde je velikost každého bloku ${ displaystyle t = lceil n / s rceil}$ . Postavte stůl ${ displaystyle S}$ velikosti ${ displaystyle s times s}$ kde ${ displaystyle S [i, j]}$ je režim ${ displaystyle b_ {i} pohár b_ {i + 1} pohár ... pohár b_ {j}}$ . Celkový prostor pro tento krok je ${ displaystyle O (s ^ {2})}$
Pro jakýkoli dotaz ${ displaystyle mode (A, i, j)}$ , nechť ${ displaystyle b_ {i '}}$ být blok, který obsahuje ${ displaystyle i}$ a ${ displaystyle b_ {j '}}$ být blok, který obsahuje ${ displaystyle j}$ . Nechť rozpětí je sada bloků zcela obsažených v ${ displaystyle A [i: j]}$ . Způsob ${ displaystyle c}$ bloku lze načíst z ${ displaystyle S}$ . Podle věty 1 může být režim buď prvkem předpony (indexy ${ displaystyle A [i: j]}$ před začátkem rozpětí), prvek přípony (indexy ${ displaystyle A [i: j]}$ po skončení rozpětí), nebo ${ displaystyle c}$ . Velikost předpony plus velikost přípony je ohraničena ${ displaystyle 2t}$ , tedy poloha režimu je uložena jako celé číslo v rozsahu od ${ displaystyle 0}$ na ${ displaystyle 2t}$ , kde ${ displaystyle [0: 2t-1]}$ označuje pozici v předponě / příponě a ${ displaystyle 2t}$ označuje, že režim je režimem rozsahu. Existují ${ displaystyle { binom {t} {2}}}$ možné dotazy týkající se bloků ${ displaystyle b_ {i '}}$ a ${ displaystyle b_ {j '}}$ , takže tyto hodnoty jsou uloženy v tabulce velikostí ${ displaystyle t ^ {2}}$ . Kromě toho existují ${ displaystyle (2t + 1) ^ {t ^ {2}}}$ takové tabulky, takže celkový prostor potřebný pro tento krok je ${ displaystyle O (t ^ {2} (2t + 1) ^ {t ^ {2}})}$ . Pro přístup k těmto tabulkám je kromě režimu v tabulce přidán ukazatel ${ displaystyle S}$ pro každou dvojici bloků.
Zpracování dotazů ${ displaystyle mode (A, i, j)}$ kde ${ displaystyle i}$ a ${ displaystyle j}$ jsou ve stejném bloku, všechna taková řešení jsou předpočítána. Existují ${ displaystyle O (st ^ {2})}$ z nich jsou uloženy v trojrozměrné tabulce ${ displaystyle T}$ této velikosti.

Celkový prostor využívaný touto datovou strukturou je ${ displaystyle O (s ^ {2} + t ^ {2} (2t + 1) ^ {t ^ {2}} + st ^ {2})}$ , což se snižuje na ${ displaystyle O left ({ frac {n ^ {2} log { log {n}}} { log {n}}} right)}$ pokud vezmeme ${ displaystyle t = { sqrt { log {n} / log { log {n}}}}}$ .

Dotaz

Byl zadán dotaz ${ displaystyle mode (A, i, j)}$ , zkontrolujte, zda je zcela obsažen uvnitř bloku, v takovém případě je odpověď uložena v tabulce ${ displaystyle T}$ . Pokud dotaz zahrnuje přesně jeden nebo více bloků, odpověď je uvedena v tabulce ${ displaystyle S}$ . Jinak použijte ukazatel uložený v tabulce ${ displaystyle S}$ v poloze ${ displaystyle S [b_ {i '}, b_ {j'}]}$ , kde ${ displaystyle b_ {i '}, b_ {j'}}$ jsou indexy bloků, které obsahují ${ displaystyle i}$ a ${ displaystyle j}$ , najít stůl ${ displaystyle U_ {b_ {i '}, b_ {j'}}}$ který obsahuje polohy režimu pro tyto bloky a pomocí této polohy vyhledejte režim v ${ displaystyle A}$ . To lze provést v konstantním čase.

Reference

^ ^A ^b ^C ^d ^E Chan, Timothy M .; Durocher, Stephane; Larsen, Kasper Green; Morrison, Jason; Wilkinson, Bryan T. (2013). „Datové struktury v lineárním prostoru pro dotaz v režimu rozsahu v polích“ (PDF). Teorie výpočetních systémů. Springer: 1–23.
^ ^A ^b ^C Krizanc, Danny; Morin, Pat; Smid, Michiel H. M. (2003). "Režim rozsahu a střední rozsah dotazů na seznamy a stromy" (PDF). ISAAC: 517–526.
^ Greve, M; Jørgensen, A .; Larsen, K .; Truelsen, J. (2010). Msgstr "Dolní hranice a aproximace sondy buňky pro režim dosahu". Automaty, jazyky a programování: 605–616.

[chan2013-1] A ^b ^C ^d ^E Chan, Timothy M .; Durocher, Stephane; Larsen, Kasper Green; Morrison, Jason; Wilkinson, Bryan T. (2013). „Datové struktury v lineárním prostoru pro dotaz v režimu rozsahu v polích“ (PDF). Teorie výpočetních systémů. Springer: 1–23.

[morin-2] A ^b ^C Krizanc, Danny; Morin, Pat; Smid, Michiel H. M. (2003). "Režim rozsahu a střední rozsah dotazů na seznamy a stromy" (PDF). ISAAC: 517–526.

[jorgensen-3] Greve, M; Jørgensen, A .; Larsen, K .; Truelsen, J. (2010). Msgstr "Dolní hranice a aproximace sondy buňky pro režim dosahu". Automaty, jazyky a programování: 605–616.

[1]

[2]

[3]