Algoritme Fractional Cascading

En ciències de la computació , l'algoritme Fractional Cascading és una tècnica per a accelerar una seqüència de busques binàries per al mateix valor en una seqüència d'estructures de senyes relacionades. La primera busca binaria en la seqüència pren una cantitat logarítmica de temps, com és estàndar per a les busques binàries, pero les busques successives en la seqüència són més ràpides. La versió original de Fractional Cascading, presentada en dos artículs per Chazelle i Guibas en 1986 ( Chazelle i Guibas 1986a ; Chazelle i Guibas 1986b ), va combinar l'idea de la cascada, sorgida de les estructures de senyes per a busques de ranc de Lueker (1978) i Willard (1978), en l'idea de mostreig fraccionat, que es va originar en Chazelle (1983). Més tarde autors varen introduir formes més complexes de Fractional Cascading que permeten que l'estructura de senyes es mantinga, com els canvis en les senyes per una seqüència d'events d'inserció i eliminació discrets.

Eixemple

Com un simple eixemple de Fractional Cascading, considere el següent problema. Se nos ha donat com a entrada un conjunt de k llestes ordenades L_i de número real, de manera que la llongitut total Σ|L_i| de les llistes és n, i devem processar-les per a que pugam realisar busques binàries per a un valor q en cada una de les k llestes. Per eixemple, en k = 4 i n = 17,

L₁ = 2.4, 6.4, 6.5, 8.0, 9.3

L₂ = 2.3, 2.5, 2.6

L₃ = 1.3, 4.4, 6.2, 6.6

L₄ = 1.1, 3.5, 4.6, 7.9, 8.1

La solució més simple a este problema de busca és només almagasenant cada llista per separat. Si ho fem aixina, la necessitat d'espai és O(n), pero el temps per a realisar una consulta és O(k log(n/k)), ya que devem realisar una busca binaria separada en cada una de les k llestes. El pijor dels casos per a la consulta d'esta estructura es produïx quan cada una de les k llestes té igual tamany n/k, per lo que cada una de les k busques binàries pren un temps d'O(log(n/k)).

Una segona solució permet consultes ràpides a costa de més espai: és possible combinar les k llestes en una gran llista única L, i associar a cada element x en L una llista dels resultats de la busca de x en cada una de les llistes més chicotetes L_i. Si es descriu un element d'esta llista combinada com a x[a,b,c,d] a on x is el valor numèric i a, b, c, i d són les posicions (el primer número té posició 0) del pròxim element major o iqual que x en cada una de les llistes d'entrada(o la llongitut de la llista si eixe element no existix), llavors tindríem que:

L = 1.1[0,0,0,0], 1.3[0,0,0,1], 2.3[0,0,1,1], 2.4[0,1,1,1], 2.5[1,1,1,1], 2.6[1,2,1,1],

3.5[1,3,1,1], 4.4[1,3,1,2], 4.6[1,3,2,2], 6.2[1,3,2,3], 6.4[1,3,3,3], 6.5[2,3,3,3],

6.6[3,3,3,3], 7.9[3,3,4,3], 8.0[3,3,4,4], 8.1[4,3,4,4], 9.3[4,3,4,5]

Esta solució combinada permet a una consulta en temps O(log n + k): basta buscar q en L i despuix buscar sobre la llista corresponent l'element x resultant. Per eixemple, si q = 5.0, la busca de q en L torna l'element 6.2[1,3,2,3], de la qual tornem els valors L₁[1] = 6.4, L₂[3] (un valor major que la llongitut de la llista indica que q no apareix en L₂), L₃[2] = 6.2, i L₄[3] = 7.9. No obstant, esta solució paga un alt preu per la complexitat espacial: s'utilisa l'espai d'O(kn) perque cada u dels n elements en L deu almagasenar una llista de k resultats.

Fractional Cascading permet que este mateix problema de busca siga resolt en cotes d'espai i temps: temps de consulta O(log n + k), i espai O(n).

La solució en Fractional Cascading és almagasenar una nova seqüència de llestes M_i. La llista final d'esta seqüència, M_k, és igual a L_k; cada llista anterior M_i es forma per la fusió de L_i en els elements de les posicions impars de M_i + 1 (cada dos elements). En cada element x en esta llista fusionada, almagasenem dos números: la posició resultant de la busca de x en L_i i la posició resultant de la busca de x en M_i + 1. Per a les senyes anteriors, açò nos donaria les següents llestes:

M₁ = 2.4[0, 1], 2.5[1, 1], 3.5[1, 3], 6.4[1, 5], 6.5[2, 5], 7.9[3, 5], 8[3, 6], 9.3[4, 6]

M₂ = 2.3[0, 1], 2.5[1, 1], 2.6[2, 1], 3.5[3, 1], 6.2[3, 3], 7.9[3, 5]

M₃ = 1.3[0, 1], 3.5[1, 1], 4.4[1, 2], 6.2[2, 3], 6.6[3, 3], 7.9[4, 3]

M₄ = 1.1[0, 0], 3.5[1, 0], 4.6[2, 0], 7.9[3, 0], 8.1[4, 0]

Supongam que volem realisar una consulta en esta estructura, per a q = 5. En primer lloc, fem una busca binaria estàndar per a q en M₁, trobant el valor 6.4[1,5]. El "1" en 6.4[1,5], nos diu que la busca q en L₁ deu tornar L₁[1] = 6.4. El "5" en 6.4[1,5] nos diu que l'ubicació aproximada de q en M₂ és la 5. Per a ser més precís, la busca binaria de q en M₂ torna ya siga el valor 7.9[3, 5] en la posició 5, o el valor 6.2[3, 3] una posició anterior. Comparant q en 6.2, i veent que és menor, determinem que li resultat correcte de la busca en M₂ és 6.2[3, 3]. El primer "3" en 6.2[3, 3] que la busca de q en L₂ deu tornar L₂[3], indicant que q no apareix en L₂. El segon "3" en 6.2[3, 3] nos diu que la posició aproximada de q en M₃ és la 3. Més precisament, la busca binaria de q en M₃ torna el valor 6.2[2, 3] en la posició 3, o el valor 4.4[1, 2] una posició anterior. Comparant q en 4.4 nos diu que el resultat correcte de la busca en M₃ és 6.2[2,3]. El "2" en 6.2[2,3] nos diu que la busca de q en L₃ deu tornar L₃[2] = 6.2, i el "3" en 6.2[2,3] el resultat de buscar q en M₄ és M₄[3] = 7.9[3,0] o M₄[2] = 4.6[2,0]; comparant q en 4.6 nos donem conte que el resultat correcte és 7.9[3,0] i que el resultat de buscar q en L₄ és L₄[3] = 7.9. Per lo tant, hem trobat q en cada una de les nostres quatre llistes, fent només una busca binaria en la llista M₁ seguit de només una comparació en cada una de les llistes successives.

De manera més general, per a qualsevol estructura de senyes d'este tipo, es realisa una consulta per mig d'una busca binaria per a q en M₁, i la determinació del valor resultant de la posició de q en L₁. Després, per a cada i > 1, s'utilisa la posició coneguda de q en M_i per a trobar la seua posició en M_i + 1. El valor associat en la posició de q en M_i apunta a la posició en M_i + 1 que és el mateix resultat de la busca de q en M_i + 1 o només una posició anterior, de modo que del passe i al i + 1 solament es requerix d'una comparació. Per lo tant, el temps total per a una consulta és O(log n + k).

En el nostre eixemple, les llistes fraccionades en cascada tenen un total de 25 elements, menys de dos voltes la de l'entrada original. En general, el tamany de M_i en esta estructura de senyes és com a molt

$|L_i|+\frac{1}{2}|L_{i+1}|+\frac{1}{4}|L_{i+2}|+\cdots +\frac{1}{2^j}|L_{i+j}|+\cdots ,$

com pot ser fàcilment demostrat per inducció. Per lo tant, el tamany total de l'estructura de senyes és com a molt

$\sum |M_i|=\sum |L_i|(1+\frac{1}{2}+\frac{1}{4}+\cdots )\le 2n=O(n),$

Problema general

En general, Fractional Cascading comença en un grafo de catàlec, un grafo dirigit en el que cada vèrtiç té una llista ordenada. Una consulta en esta estructura de senyes consistix en un camí en el grafo i un valor q; l'estructura de senyes deu determinar la posició de q en cada una de les llistes ordenades associades en els vèrtiços de la trayectòria. En el simple eixemple anterior, el grafo de catàlec és en sí mateixa un camí, en només quatre nodos. És possible que els vèrtiços posteriors en la ruta siguen determinats dinàmicament com a part d'una consulta, en resposta als resultats trobats per les busques en les parts anteriors del camí.

Per a controlar les consultes d'este tipo, per a un grafo en el que cada vèrtiç té com a molt d arestes entrantes i com a molt d arestes eixints per a alguna constant d, les llistes associades en cada vèrtiç són aumentats per una fracció dels elements de cada veí eixint del vèrtiç; la fracció deu elegir-se per a que siga menor que 1 /d, de modo que la cantitat total pel qual totes les llistes s'aumenten seguix sent llineal en el tamany de l'entrada. Cada element de cada llista aumentada almagasena la posició d'eixe element en la llista no aumentada almagasenada en el mateix vèrtiç, i en cada una de les llistes de veïns eixints. En el senzill eixemple de dalt, d = 1, i aumentem cada llista en la fracció 1/2 dels elements veïns.

Una consulta en esta estructura de senyes consistix en una busca binaria estàndar en la llista aumentada associada en el primer vèrtiç de la ruta de consulta, junt en busques simples en cada vèrtiç successiu de la trayectòria. Si s'utilisa una fracció 1 /r d'elements per a aumentar les llistes de cada element veí, a continuació, cada resultat de la consulta successiva es pot trobar dins de com a molt r passos de la posició almagasenada en el resultat de la consulta des del vèrtiç trayectòria anterior, i per lo tant pot ser trobat en un temps constant sense tindre que realisar una busca binaria completa.

Referències

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .