Successioni crescenti compresse, con accesso diretto e salti
Sebastiano Vigna
Da dove partiamo
Un indice inverso associa a ogni termine la lista dei documenti che lo contengono, in ordine crescente
I documenti sono numerati da a : la lista è una successione
Nell'esempio di oggi «gatto» compare in documenti su
Per ogni documento si memorizzano anche quante volte compare il termine, e in quali posizioni: ci torneremo alla fine
Il problema: memorizzare una successione crescente in poco spazio, e leggerla in fretta
gatto
cane
topo
Da dove partiamo
Un indice inverso associa a ogni termine la lista dei documenti che lo contengono, in ordine crescente
I documenti sono numerati da a : la lista è una successione
Nell'esempio di oggi «gatto» compare in documenti su
Per ogni documento si memorizzano anche quante volte compare il termine, e in quali posizioni: ci torneremo alla fine
Il problema: memorizzare una successione crescente in poco spazio, e leggerla in fretta
gatto
cane
topo
Da dove partiamo
Un indice inverso associa a ogni termine la lista dei documenti che lo contengono, in ordine crescente
I documenti sono numerati da a : la lista è una successione
Nell'esempio di oggi «gatto» compare in documenti su
Per ogni documento si memorizzano anche quante volte compare il termine, e in quali posizioni: ci torneremo alla fine
Il problema: memorizzare una successione crescente in poco spazio, e leggerla in fretta
gatto
cane
topo
Da dove partiamo
Un indice inverso associa a ogni termine la lista dei documenti che lo contengono, in ordine crescente
I documenti sono numerati da a : la lista è una successione
Nell'esempio di oggi «gatto» compare in documenti su
Per ogni documento si memorizzano anche quante volte compare il termine, e in quali posizioni: ci torneremo alla fine
Il problema: memorizzare una successione crescente in poco spazio, e leggerla in fretta
gatto
cane
topo
Da dove partiamo
Un indice inverso associa a ogni termine la lista dei documenti che lo contengono, in ordine crescente
I documenti sono numerati da a : la lista è una successione
Nell'esempio di oggi «gatto» compare in documenti su
Per ogni documento si memorizzano anche quante volte compare il termine, e in quali posizioni: ci torneremo alla fine
Il problema: memorizzare una successione crescente in poco spazio, e leggerla in fretta
gatto
cane
topo
Tre modi di leggere una lista
Lettura in successione (next): un elemento dopo l'altro, dal primo all'ultimo
Accesso diretto (get): dato , restituisce
Salto (skipTo): dato , restituisce il più piccolo elemento , cioè il minimo dei maggioranti di
Se nessun elemento è , il risultato è
Esempi: skipTo, skipTo
next, next, next…
Tre modi di leggere una lista
Lettura in successione (next): un elemento dopo l'altro, dal primo all'ultimo
Accesso diretto (get): dato , restituisce
Salto (skipTo): dato , restituisce il più piccolo elemento , cioè il minimo dei maggioranti di
Se nessun elemento è , il risultato è
Esempi: skipTo, skipTo
get
Tre modi di leggere una lista
Lettura in successione (next): un elemento dopo l'altro, dal primo all'ultimo
Accesso diretto (get): dato , restituisce
Salto (skipTo): dato , restituisce il più piccolo elemento , cioè il minimo dei maggioranti di
Se nessun elemento è , il risultato è
Esempi: skipTo, skipTo
skipTo
Tre modi di leggere una lista
Lettura in successione (next): un elemento dopo l'altro, dal primo all'ultimo
Accesso diretto (get): dato , restituisce
Salto (skipTo): dato , restituisce il più piccolo elemento , cioè il minimo dei maggioranti di
Se nessun elemento è , il risultato è
Esempi: skipTo, skipTo
skipTo
Tre modi di leggere una lista
Lettura in successione (next): un elemento dopo l'altro, dal primo all'ultimo
Accesso diretto (get): dato , restituisce
Salto (skipTo): dato , restituisce il più piccolo elemento , cioè il minimo dei maggioranti di
Se nessun elemento è , il risultato è
Esempi: skipTo, skipTo
skipTo
Una soluzione banale
Un array di interi: si scrive in bit, tutti con la stessa lunghezza
get è immediato: i bit di partono dalla posizione
skipTo: ricerca dicotomica, accessi sparsi in memoria
Spazio: bit, nell'esempio
Ma la successione è crescente: è un'informazione che non stiamo usando
Le successioni crescenti di elementi minori di sono : per sceglierne una servono bit, con (nell'esempio il valore esatto è circa 66; l'approssimazione dà 71)
Una soluzione banale
Un array di interi: si scrive in bit, tutti con la stessa lunghezza
get è immediato: i bit di partono dalla posizione
skipTo: ricerca dicotomica, accessi sparsi in memoria
Spazio: bit, nell'esempio
Ma la successione è crescente: è un'informazione che non stiamo usando
Le successioni crescenti di elementi minori di sono : per sceglierne una servono bit, con (nell'esempio il valore esatto è circa 66; l'approssimazione dà 71)
Una soluzione banale
Un array di interi: si scrive in bit, tutti con la stessa lunghezza
get è immediato: i bit di partono dalla posizione
skipTo: ricerca dicotomica, accessi sparsi in memoria
Spazio: bit, nell'esempio
Ma la successione è crescente: è un'informazione che non stiamo usando
Le successioni crescenti di elementi minori di sono : per sceglierne una servono bit, con (nell'esempio il valore esatto è circa 66; l'approssimazione dà 71)
Una soluzione banale
Un array di interi: si scrive in bit, tutti con la stessa lunghezza
get è immediato: i bit di partono dalla posizione
skipTo: ricerca dicotomica, accessi sparsi in memoria
Spazio: bit, nell'esempio
Ma la successione è crescente: è un'informazione che non stiamo usando
Le successioni crescenti di elementi minori di sono : per sceglierne una servono bit, con (nell'esempio il valore esatto è circa 66; l'approssimazione dà 71)
Una soluzione banale
Un array di interi: si scrive in bit, tutti con la stessa lunghezza
get è immediato: i bit di partono dalla posizione
skipTo: ricerca dicotomica, accessi sparsi in memoria
Spazio: bit, nell'esempio
Ma la successione è crescente: è un'informazione che non stiamo usando
Le successioni crescenti di elementi minori di sono : per sceglierne una servono bit, con (nell'esempio il valore esatto è circa 66; l'approssimazione dà 71)
Una soluzione banale
Un array di interi: si scrive in bit, tutti con la stessa lunghezza
get è immediato: i bit di partono dalla posizione
skipTo: ricerca dicotomica, accessi sparsi in memoria
Spazio: bit, nell'esempio
Ma la successione è crescente: è un'informazione che non stiamo usando
Le successioni crescenti di elementi minori di sono : per sceglierne una servono bit, con (nell'esempio il valore esatto è circa 66; l'approssimazione dà 71)
La soluzione classica: gli scarti
Invece degli elementi, gli scarti (gap): ( può essere ), , , …
Nelle liste lunghe gli scarti sono piccoli
Con un codice a lunghezza variabile i numeri piccoli occupano pochi bit: per esempio , che scrive con bit
La lettura in successione è facile: si decodifica uno scarto e lo si somma all'elemento precedente
Ma get e skipTo richiedono di decodificare tutto quello che viene prima
lista
scarti
La soluzione classica: gli scarti
Invece degli elementi, gli scarti (gap): ( può essere ), , , …
Nelle liste lunghe gli scarti sono piccoli
Con un codice a lunghezza variabile i numeri piccoli occupano pochi bit: per esempio , che scrive con bit
La lettura in successione è facile: si decodifica uno scarto e lo si somma all'elemento precedente
Ma get e skipTo richiedono di decodificare tutto quello che viene prima
lista
scarti
La soluzione classica: gli scarti
Invece degli elementi, gli scarti (gap): ( può essere ), , , …
Nelle liste lunghe gli scarti sono piccoli
Con un codice a lunghezza variabile i numeri piccoli occupano pochi bit: per esempio , che scrive con bit
La lettura in successione è facile: si decodifica uno scarto e lo si somma all'elemento precedente
Ma get e skipTo richiedono di decodificare tutto quello che viene prima
lista
scarti
28 bit per i primi 8 elementi
La soluzione classica: gli scarti
Invece degli elementi, gli scarti (gap): ( può essere ), , , …
Nelle liste lunghe gli scarti sono piccoli
Con un codice a lunghezza variabile i numeri piccoli occupano pochi bit: per esempio , che scrive con bit
La lettura in successione è facile: si decodifica uno scarto e lo si somma all'elemento precedente
Ma get e skipTo richiedono di decodificare tutto quello che viene prima
lista
scarti
28 bit per i primi 8 elementi
La soluzione classica: gli scarti
Invece degli elementi, gli scarti (gap): ( può essere ), , , …
Nelle liste lunghe gli scarti sono piccoli
Con un codice a lunghezza variabile i numeri piccoli occupano pochi bit: per esempio , che scrive con bit
La lettura in successione è facile: si decodifica uno scarto e lo si somma all'elemento precedente
Ma get e skipTo richiedono di decodificare tutto quello che viene prima
lista
scarti
28 bit per i primi 8 elementi
get? Bisogna decodificare tutto quello che c'è prima
Tabelle di salto
Rimedio: una tabella di salto (skip table), con un campione ogni elementi
Il campione è l'elemento e la posizione del codice successivo; è il quanto (quantum)
get: si parte dall'ultimo campione prima di e si decodifica da lì
skipTo: si cerca l'ultimo campione minore di e si decodifica da lì
Funziona, ma è una struttura in più, con parametri da scegliere
Domanda: non è che possiamo fare del tutto a meno degli scarti?
codici degli scarti: 72 bit
Tabelle di salto
Rimedio: una tabella di salto (skip table), con un campione ogni elementi
Il campione è l'elemento e la posizione del codice successivo; è il quanto (quantum)
get: si parte dall'ultimo campione prima di e si decodifica da lì
skipTo: si cerca l'ultimo campione minore di e si decodifica da lì
Funziona, ma è una struttura in più, con parametri da scegliere
Domanda: non è che possiamo fare del tutto a meno degli scarti?
codici degli scarti: 72 bit
, bit 5
, bit 17
, bit 37
, bit 47
Tabelle di salto
Rimedio: una tabella di salto (skip table), con un campione ogni elementi
Il campione è l'elemento e la posizione del codice successivo; è il quanto (quantum)
get: si parte dall'ultimo campione prima di e si decodifica da lì
skipTo: si cerca l'ultimo campione minore di e si decodifica da lì
Funziona, ma è una struttura in più, con parametri da scegliere
Domanda: non è che possiamo fare del tutto a meno degli scarti?
codici degli scarti: 72 bit
, bit 5
, bit 17
, bit 37
, bit 47
get: salto a e decodifico 2 scarti
Tabelle di salto
Rimedio: una tabella di salto (skip table), con un campione ogni elementi
Il campione è l'elemento e la posizione del codice successivo; è il quanto (quantum)
get: si parte dall'ultimo campione prima di e si decodifica da lì
skipTo: si cerca l'ultimo campione minore di e si decodifica da lì
Funziona, ma è una struttura in più, con parametri da scegliere
Domanda: non è che possiamo fare del tutto a meno degli scarti?
codici degli scarti: 72 bit
, bit 5
, bit 17
, bit 37
, bit 47
get: salto a e decodifico 2 scarti
skipTo: ultimo campione è , poi decodifico
Tabelle di salto
Rimedio: una tabella di salto (skip table), con un campione ogni elementi
Il campione è l'elemento e la posizione del codice successivo; è il quanto (quantum)
get: si parte dall'ultimo campione prima di e si decodifica da lì
skipTo: si cerca l'ultimo campione minore di e si decodifica da lì
Funziona, ma è una struttura in più, con parametri da scegliere
Domanda: non è che possiamo fare del tutto a meno degli scarti?
codici degli scarti: 72 bit
, bit 5
, bit 17
, bit 37
, bit 47
get: salto a e decodifico 2 scarti
skipTo: ultimo campione è , poi decodifico
Tabelle di salto
Rimedio: una tabella di salto (skip table), con un campione ogni elementi
Il campione è l'elemento e la posizione del codice successivo; è il quanto (quantum)
get: si parte dall'ultimo campione prima di e si decodifica da lì
skipTo: si cerca l'ultimo campione minore di e si decodifica da lì
Funziona, ma è una struttura in più, con parametri da scegliere
Domanda: non è che possiamo fare del tutto a meno degli scarti?
codici degli scarti: 72 bit
, bit 5
, bit 17
, bit 37
, bit 47
get: salto a e decodifico 2 scarti
skipTo: ultimo campione è , poi decodifico
Bit alti e bit bassi
Peter Elias (1975, sì, quell'Elias) e, indipendentemente, Robert Fano: una successione crescente si può memorizzare senza scrivere gli scarti fra gli elementi con un codice a lunghezza variabile
Sia : ogni si spezza nei suoi bit bassi e nei bit alti
Idea: i bit bassi cambiano in modo imprevedibile da un elemento all'altro: si scrivono così come sono, uno dopo l'altro, bit in tutto
I bit alti invece crescono lentamente: valgono meno di , e si comprimono bene
Nell'esempio: , ,
Bit alti e bit bassi
Peter Elias (1975, sì, quell'Elias) e, indipendentemente, Robert Fano: una successione crescente si può memorizzare senza scrivere gli scarti fra gli elementi con un codice a lunghezza variabile
Sia : ogni si spezza nei suoi bit bassi e nei bit alti
Idea: i bit bassi cambiano in modo imprevedibile da un elemento all'altro: si scrivono così come sono, uno dopo l'altro, bit in tutto
I bit alti invece crescono lentamente: valgono meno di , e si comprimono bene
Nell'esempio: , ,
binario
Bit alti e bit bassi
Peter Elias (1975, sì, quell'Elias) e, indipendentemente, Robert Fano: una successione crescente si può memorizzare senza scrivere gli scarti fra gli elementi con un codice a lunghezza variabile
Sia : ogni si spezza nei suoi bit bassi e nei bit alti
Idea: i bit bassi cambiano in modo imprevedibile da un elemento all'altro: si scrivono così come sono, uno dopo l'altro, bit in tutto
I bit alti invece crescono lentamente: valgono meno di , e si comprimono bene
Nell'esempio: , ,
binario
bassi
Bit alti e bit bassi
Peter Elias (1975, sì, quell'Elias) e, indipendentemente, Robert Fano: una successione crescente si può memorizzare senza scrivere gli scarti fra gli elementi con un codice a lunghezza variabile
Sia : ogni si spezza nei suoi bit bassi e nei bit alti
Idea: i bit bassi cambiano in modo imprevedibile da un elemento all'altro: si scrivono così come sono, uno dopo l'altro, bit in tutto
I bit alti invece crescono lentamente: valgono meno di , e si comprimono bene
Nell'esempio: , ,
binario
bassi
Bit alti e bit bassi
Peter Elias (1975, sì, quell'Elias) e, indipendentemente, Robert Fano: una successione crescente si può memorizzare senza scrivere gli scarti fra gli elementi con un codice a lunghezza variabile
Sia : ogni si spezza nei suoi bit bassi e nei bit alti
Idea: i bit bassi cambiano in modo imprevedibile da un elemento all'altro: si scrivono così come sono, uno dopo l'altro, bit in tutto
I bit alti invece crescono lentamente: valgono meno di , e si comprimono bene
Nell'esempio: , ,
binario
bassi
I bit alti: scarti in unario
I bit alti sono una successione non decrescente di numeri piccoli
Ne scriviamo gli scarti (con ) in unario: diventa zeri seguiti da un uno
Gli scarti sommano a : in media valgono meno di 2, e per numeri così piccoli l'unario è il codice giusto
Nell'esempio: 16 uni e 15 zeri, 31 bit
I bit alti: scarti in unario
I bit alti sono una successione non decrescente di numeri piccoli
Ne scriviamo gli scarti (con ) in unario: diventa zeri seguiti da un uno
Gli scarti sommano a : in media valgono meno di 2, e per numeri così piccoli l'unario è il codice giusto
Nell'esempio: 16 uni e 15 zeri, 31 bit
scarti
I bit alti: scarti in unario
I bit alti sono una successione non decrescente di numeri piccoli
Ne scriviamo gli scarti (con ) in unario: diventa zeri seguiti da un uno
Gli scarti sommano a : in media valgono meno di 2, e per numeri così piccoli l'unario è il codice giusto
Nell'esempio: 16 uni e 15 zeri, 31 bit
scarti
unario
I bit alti: scarti in unario
I bit alti sono una successione non decrescente di numeri piccoli
Ne scriviamo gli scarti (con ) in unario: diventa zeri seguiti da un uno
Gli scarti sommano a : in media valgono meno di 2, e per numeri così piccoli l'unario è il codice giusto
Nell'esempio: 16 uni e 15 zeri, 31 bit
scarti
unario
alti
Dove sta l'elemento
L'uno di ha a sinistra uni, uno per ogni elemento precedente, e zeri, la somma degli scarti fino a quello di compreso
Quindi la sua posizione è
E viceversa: se l'uno di indice sta in posizione , i bit alti sono
In generale, il numero di zeri a sinistra di un uno è il valore dei bit alti del suo elemento
alti
a sinistra: uni (elementi ) e zeri (i bit alti di )
Dove sta l'elemento
L'uno di ha a sinistra uni, uno per ogni elemento precedente, e zeri, la somma degli scarti fino a quello di compreso
Quindi la sua posizione è
E viceversa: se l'uno di indice sta in posizione , i bit alti sono
In generale, il numero di zeri a sinistra di un uno è il valore dei bit alti del suo elemento
alti
a sinistra: uni (elementi ) e zeri (i bit alti di )
posizione dell'uno di :
Dove sta l'elemento
L'uno di ha a sinistra uni, uno per ogni elemento precedente, e zeri, la somma degli scarti fino a quello di compreso
Quindi la sua posizione è
E viceversa: se l'uno di indice sta in posizione , i bit alti sono
In generale, il numero di zeri a sinistra di un uno è il valore dei bit alti del suo elemento
alti
a sinistra: uni (elementi ) e zeri (i bit alti di )
posizione dell'uno di :
Dove sta l'elemento
L'uno di ha a sinistra uni, uno per ogni elemento precedente, e zeri, la somma degli scarti fino a quello di compreso
Quindi la sua posizione è
E viceversa: se l'uno di indice sta in posizione , i bit alti sono
In generale, il numero di zeri a sinistra di un uno è il valore dei bit alti del suo elemento
alti
a sinistra: uni (elementi ) e zeri (i bit alti di )
posizione dell'uno di :
L'esempio completo
Vettore dei bit alti: i 31 bit appena costruiti
Bit bassi: bit; quelli di partono dalla posizione
Totale: 79 bit, meno di 5 bit per elemento invece di 7
Ricostruire : il suo uno è in posizione 15, quindi i bit alti sono ; i bassi sono :
alti
L'esempio completo
Vettore dei bit alti: i 31 bit appena costruiti
Bit bassi: bit; quelli di partono dalla posizione
Totale: 79 bit, meno di 5 bit per elemento invece di 7
Ricostruire : il suo uno è in posizione 15, quindi i bit alti sono ; i bassi sono :
alti
bassi
L'esempio completo
Vettore dei bit alti: i 31 bit appena costruiti
Bit bassi: bit; quelli di partono dalla posizione
Totale: 79 bit, meno di 5 bit per elemento invece di 7
Ricostruire : il suo uno è in posizione 15, quindi i bit alti sono ; i bassi sono :
alti
bassi
L'esempio completo
Vettore dei bit alti: i 31 bit appena costruiti
Bit bassi: bit; quelli di partono dalla posizione
Totale: 79 bit, meno di 5 bit per elemento invece di 7
Ricostruire : il suo uno è in posizione 15, quindi i bit alti sono ; i bassi sono :
alti
bassi
Quanto spazio
Bit bassi:
Vettore dei bit alti: ogni codice unario finisce con un uno, quindi ci sono uni
Ogni zero aumenta di 1 i bit alti: gli zeri sono
Con il nostro vale , cioè : al più zeri
In tutto al più bit, cioè per elemento (se è una potenza di 2, gli zeri sono al più e il conto torna)
Il minimo è : al più bit per elemento in più, asintoticamente irrilevante: Elias–Fano è succinta (succinct)
Quanto spazio
Bit bassi:
Vettore dei bit alti: ogni codice unario finisce con un uno, quindi ci sono uni
Ogni zero aumenta di 1 i bit alti: gli zeri sono
Con il nostro vale , cioè : al più zeri
In tutto al più bit, cioè per elemento (se è una potenza di 2, gli zeri sono al più e il conto torna)
Il minimo è : al più bit per elemento in più, asintoticamente irrilevante: Elias–Fano è succinta (succinct)
Quanto spazio
Bit bassi:
Vettore dei bit alti: ogni codice unario finisce con un uno, quindi ci sono uni
Ogni zero aumenta di 1 i bit alti: gli zeri sono
Con il nostro vale , cioè : al più zeri
In tutto al più bit, cioè per elemento (se è una potenza di 2, gli zeri sono al più e il conto torna)
Il minimo è : al più bit per elemento in più, asintoticamente irrilevante: Elias–Fano è succinta (succinct)
Quanto spazio
Bit bassi:
Vettore dei bit alti: ogni codice unario finisce con un uno, quindi ci sono uni
Ogni zero aumenta di 1 i bit alti: gli zeri sono
Con il nostro vale , cioè : al più zeri
In tutto al più bit, cioè per elemento (se è una potenza di 2, gli zeri sono al più e il conto torna)
Il minimo è : al più bit per elemento in più, asintoticamente irrilevante: Elias–Fano è succinta (succinct)
Quanto spazio
Bit bassi:
Vettore dei bit alti: ogni codice unario finisce con un uno, quindi ci sono uni
Ogni zero aumenta di 1 i bit alti: gli zeri sono
Con il nostro vale , cioè : al più zeri
In tutto al più bit, cioè per elemento (se è una potenza di 2, gli zeri sono al più e il conto torna)
Il minimo è : al più bit per elemento in più, asintoticamente irrilevante: Elias–Fano è succinta (succinct)
Quanto spazio
Bit bassi:
Vettore dei bit alti: ogni codice unario finisce con un uno, quindi ci sono uni
Ogni zero aumenta di 1 i bit alti: gli zeri sono
Con il nostro vale , cioè : al più zeri
In tutto al più bit, cioè per elemento (se è una potenza di 2, gli zeri sono al più e il conto torna)
Il minimo è : al più bit per elemento in più, asintoticamente irrilevante: Elias–Fano è succinta (succinct)
Demo: costruire Elias–Fano
Interactive Demo
Ogni elemento si spezza: i bit bassi vanno in fondo all'array dei bassi, lo scarto dei bit alti si aggiunge in unario al vettore dei bit alti.
Non dipende dalla distribuzione
Il limite allo spazio dipende solo da e : non ci sono liste «sfortunate»
Con i codici per scarti, invece, lo spazio dipende dai valori degli scarti
Nell'esempio gli scarti con costano 72 bit, Elias–Fano 79: gli scarti piccoli premiano
Ma con (scarti tutti 8) costa 112 bit, ed Elias–Fano sempre 79
Sulle liste vere di un indice Elias–Fano comprime meglio dei codici per scarti usati di solito
binario
scarti +
Elias–Fano
minimo
Non dipende dalla distribuzione
Il limite allo spazio dipende solo da e : non ci sono liste «sfortunate»
Con i codici per scarti, invece, lo spazio dipende dai valori degli scarti
Nell'esempio gli scarti con costano 72 bit, Elias–Fano 79: gli scarti piccoli premiano
Ma con (scarti tutti 8) costa 112 bit, ed Elias–Fano sempre 79
Sulle liste vere di un indice Elias–Fano comprime meglio dei codici per scarti usati di solito
binario
scarti +
Elias–Fano
minimo
Non dipende dalla distribuzione
Il limite allo spazio dipende solo da e : non ci sono liste «sfortunate»
Con i codici per scarti, invece, lo spazio dipende dai valori degli scarti
Nell'esempio gli scarti con costano 72 bit, Elias–Fano 79: gli scarti piccoli premiano
Ma con (scarti tutti 8) costa 112 bit, ed Elias–Fano sempre 79
Sulle liste vere di un indice Elias–Fano comprime meglio dei codici per scarti usati di solito
binario
scarti +
Elias–Fano
minimo
Non dipende dalla distribuzione
Il limite allo spazio dipende solo da e : non ci sono liste «sfortunate»
Con i codici per scarti, invece, lo spazio dipende dai valori degli scarti
Nell'esempio gli scarti con costano 72 bit, Elias–Fano 79: gli scarti piccoli premiano
Ma con (scarti tutti 8) costa 112 bit, ed Elias–Fano sempre 79
Sulle liste vere di un indice Elias–Fano comprime meglio dei codici per scarti usati di solito
binario
scarti +
scarti tutti 8,
Elias–Fano
minimo
Non dipende dalla distribuzione
Il limite allo spazio dipende solo da e : non ci sono liste «sfortunate»
Con i codici per scarti, invece, lo spazio dipende dai valori degli scarti
Nell'esempio gli scarti con costano 72 bit, Elias–Fano 79: gli scarti piccoli premiano
Ma con (scarti tutti 8) costa 112 bit, ed Elias–Fano sempre 79
Sulle liste vere di un indice Elias–Fano comprime meglio dei codici per scarti usati di solito
binario
scarti +
scarti tutti 8,
Elias–Fano
minimo
Una struttura bilanciata
Nel vettore dei bit alti ci sono uni e al più zeri: almeno un bit su tre è un uno
Scegliendo , o comunque con vicino a , gli zeri sono circa : almeno circa metà dei bit
Muovendosi nel vettore dei bit alti si incontrano spesso sia elementi (uni) sia incrementi dei bit alti (zeri)
Questo equilibrio renderà veloci tutte e tre le operazioni
I bit bassi invece non si scorrono mai: quelli di si leggono direttamente, partono dalla posizione
Con le ripetizioni (successioni non decrescenti) funziona tutto allo stesso modo: scarti nulli, cioè uni consecutivi
Una struttura bilanciata
Nel vettore dei bit alti ci sono uni e al più zeri: almeno un bit su tre è un uno
Scegliendo , o comunque con vicino a , gli zeri sono circa : almeno circa metà dei bit
Muovendosi nel vettore dei bit alti si incontrano spesso sia elementi (uni) sia incrementi dei bit alti (zeri)
Questo equilibrio renderà veloci tutte e tre le operazioni
I bit bassi invece non si scorrono mai: quelli di si leggono direttamente, partono dalla posizione
Con le ripetizioni (successioni non decrescenti) funziona tutto allo stesso modo: scarti nulli, cioè uni consecutivi
Una struttura bilanciata
Nel vettore dei bit alti ci sono uni e al più zeri: almeno un bit su tre è un uno
Scegliendo , o comunque con vicino a , gli zeri sono circa : almeno circa metà dei bit
Muovendosi nel vettore dei bit alti si incontrano spesso sia elementi (uni) sia incrementi dei bit alti (zeri)
Questo equilibrio renderà veloci tutte e tre le operazioni
I bit bassi invece non si scorrono mai: quelli di si leggono direttamente, partono dalla posizione
Con le ripetizioni (successioni non decrescenti) funziona tutto allo stesso modo: scarti nulli, cioè uni consecutivi
Una struttura bilanciata
Nel vettore dei bit alti ci sono uni e al più zeri: almeno un bit su tre è un uno
Scegliendo , o comunque con vicino a , gli zeri sono circa : almeno circa metà dei bit
Muovendosi nel vettore dei bit alti si incontrano spesso sia elementi (uni) sia incrementi dei bit alti (zeri)
Questo equilibrio renderà veloci tutte e tre le operazioni
I bit bassi invece non si scorrono mai: quelli di si leggono direttamente, partono dalla posizione
Con le ripetizioni (successioni non decrescenti) funziona tutto allo stesso modo: scarti nulli, cioè uni consecutivi
Una struttura bilanciata
Nel vettore dei bit alti ci sono uni e al più zeri: almeno un bit su tre è un uno
Scegliendo , o comunque con vicino a , gli zeri sono circa : almeno circa metà dei bit
Muovendosi nel vettore dei bit alti si incontrano spesso sia elementi (uni) sia incrementi dei bit alti (zeri)
Questo equilibrio renderà veloci tutte e tre le operazioni
I bit bassi invece non si scorrono mai: quelli di si leggono direttamente, partono dalla posizione
Con le ripetizioni (successioni non decrescenti) funziona tutto allo stesso modo: scarti nulli, cioè uni consecutivi
Una struttura bilanciata
Nel vettore dei bit alti ci sono uni e al più zeri: almeno un bit su tre è un uno
Scegliendo , o comunque con vicino a , gli zeri sono circa : almeno circa metà dei bit
Muovendosi nel vettore dei bit alti si incontrano spesso sia elementi (uni) sia incrementi dei bit alti (zeri)
Questo equilibrio renderà veloci tutte e tre le operazioni
I bit bassi invece non si scorrono mai: quelli di si leggono direttamente, partono dalla posizione
Con le ripetizioni (successioni non decrescenti) funziona tutto allo stesso modo: scarti nulli, cioè uni consecutivi
Tre numeri:
Scorrendo il vettore dei bit alti teniamo tre numeri: la posizione , gli uni superati , gli zeri superati
Ogni bit fa crescere di uno, e oppure : quindi vale sempre
è l'indice del prossimo elemento, i bit alti raggiunti: sull'uno di , e
Basta conoscerne due: il terzo viene dall'equazione
get conosce e cerca : i bit alti sono . skipTo conosce e cerca : l'indice è
alti
superati: uni, zeri
Tre numeri:
Scorrendo il vettore dei bit alti teniamo tre numeri: la posizione , gli uni superati , gli zeri superati
Ogni bit fa crescere di uno, e oppure : quindi vale sempre
è l'indice del prossimo elemento, i bit alti raggiunti: sull'uno di , e
Basta conoscerne due: il terzo viene dall'equazione
get conosce e cerca : i bit alti sono . skipTo conosce e cerca : l'indice è
alti
superati: uni, zeri
:
Tre numeri:
Scorrendo il vettore dei bit alti teniamo tre numeri: la posizione , gli uni superati , gli zeri superati
Ogni bit fa crescere di uno, e oppure : quindi vale sempre
è l'indice del prossimo elemento, i bit alti raggiunti: sull'uno di , e
Basta conoscerne due: il terzo viene dall'equazione
get conosce e cerca : i bit alti sono . skipTo conosce e cerca : l'indice è
alti
superati: uni, zeri
:
il prossimo uno è di , con bit alti :
Tre numeri:
Scorrendo il vettore dei bit alti teniamo tre numeri: la posizione , gli uni superati , gli zeri superati
Ogni bit fa crescere di uno, e oppure : quindi vale sempre
è l'indice del prossimo elemento, i bit alti raggiunti: sull'uno di , e
Basta conoscerne due: il terzo viene dall'equazione
get conosce e cerca : i bit alti sono . skipTo conosce e cerca : l'indice è
alti
superati: uni, zeri
:
il prossimo uno è di , con bit alti :
Tre numeri:
Scorrendo il vettore dei bit alti teniamo tre numeri: la posizione , gli uni superati , gli zeri superati
Ogni bit fa crescere di uno, e oppure : quindi vale sempre
è l'indice del prossimo elemento, i bit alti raggiunti: sull'uno di , e
Basta conoscerne due: il terzo viene dall'equazione
get conosce e cerca : i bit alti sono . skipTo conosce e cerca : l'indice è
alti
superati: uni, zeri
:
il prossimo uno è di , con bit alti :
Lettura in successione
Teniamo l'indice dell'elemento corrente e la posizione del suo uno nel vettore dei bit alti
Elemento successivo: si cerca il prossimo uno dopo ; gli zeri che si incontrano sono lo scarto dei bit alti
Bit alti: ; bit bassi: quelli in posizione ; bassi
Il vettore dei bit alti ha al più bit (tre per elemento), letti sempre in avanti
alti
Lettura in successione
Teniamo l'indice dell'elemento corrente e la posizione del suo uno nel vettore dei bit alti
Elemento successivo: si cerca il prossimo uno dopo ; gli zeri che si incontrano sono lo scarto dei bit alti
Bit alti: ; bit bassi: quelli in posizione ; bassi
Il vettore dei bit alti ha al più bit (tre per elemento), letti sempre in avanti
alti
valori: 3, 5, 11, 12
Lettura in successione
Teniamo l'indice dell'elemento corrente e la posizione del suo uno nel vettore dei bit alti
Elemento successivo: si cerca il prossimo uno dopo ; gli zeri che si incontrano sono lo scarto dei bit alti
Bit alti: ; bit bassi: quelli in posizione ; bassi
Il vettore dei bit alti ha al più bit (tre per elemento), letti sempre in avanti
alti
valori: 3, 5, 11, 12, 14, 26, 29, 30, 52
Lettura in successione
Teniamo l'indice dell'elemento corrente e la posizione del suo uno nel vettore dei bit alti
Elemento successivo: si cerca il prossimo uno dopo ; gli zeri che si incontrano sono lo scarto dei bit alti
Bit alti: ; bit bassi: quelli in posizione ; bassi
Il vettore dei bit alti ha al più bit (tre per elemento), letti sempre in avanti
Il vettore dei bit alti sta in parole da 64 bit; teniamo la parola corrente
Se si passa alla parola successiva
Il prossimo uno è l'uno meno significativo di : lo trova un'istruzione che conta gli zeri finali (TZCNT)
Poi cancella quell'uno: sottrarre 1 cambia solo gli zeri finali e l'uno meno significativo
In tutto una manciata di istruzioni per elemento (Philip Pronin @ Facebook)
bit 15 … bit 0 (il bit 0 è il primo della successione)
(parola di 16 bit, per brevità)
Una parola alla volta
Il vettore dei bit alti sta in parole da 64 bit; teniamo la parola corrente
Se si passa alla parola successiva
Il prossimo uno è l'uno meno significativo di : lo trova un'istruzione che conta gli zeri finali (TZCNT)
Poi cancella quell'uno: sottrarre 1 cambia solo gli zeri finali e l'uno meno significativo
In tutto una manciata di istruzioni per elemento (Philip Pronin @ Facebook)
bit 15 … bit 0 (il bit 0 è il primo della successione)
(parola di 16 bit, per brevità)
Una parola alla volta
Il vettore dei bit alti sta in parole da 64 bit; teniamo la parola corrente
Se si passa alla parola successiva
Il prossimo uno è l'uno meno significativo di : lo trova un'istruzione che conta gli zeri finali (TZCNT)
Poi cancella quell'uno: sottrarre 1 cambia solo gli zeri finali e l'uno meno significativo
In tutto una manciata di istruzioni per elemento (Philip Pronin @ Facebook)
zeri finali: 3 → il prossimo uno è il bit 3 della parola
bit 15 … bit 0 (il bit 0 è il primo della successione)
(parola di 16 bit, per brevità)
Una parola alla volta
Il vettore dei bit alti sta in parole da 64 bit; teniamo la parola corrente
Se si passa alla parola successiva
Il prossimo uno è l'uno meno significativo di : lo trova un'istruzione che conta gli zeri finali (TZCNT)
Poi cancella quell'uno: sottrarre 1 cambia solo gli zeri finali e l'uno meno significativo
In tutto una manciata di istruzioni per elemento (Philip Pronin @ Facebook)
zeri finali: 3 → il prossimo uno è il bit 3 della parola
l'uno appena letto è sparito
bit 15 … bit 0 (il bit 0 è il primo della successione)
(parola di 16 bit, per brevità)
Una parola alla volta
Il vettore dei bit alti sta in parole da 64 bit; teniamo la parola corrente
Se si passa alla parola successiva
Il prossimo uno è l'uno meno significativo di : lo trova un'istruzione che conta gli zeri finali (TZCNT)
Poi cancella quell'uno: sottrarre 1 cambia solo gli zeri finali e l'uno meno significativo
In tutto una manciata di istruzioni per elemento (Philip Pronin @ Facebook)
zeri finali: 3 → il prossimo uno è il bit 3 della parola
l'uno appena letto è sparito
bit 15 … bit 0 (il bit 0 è il primo della successione)
(parola di 16 bit, per brevità)
Accesso diretto: get
I bit bassi di si leggono subito: partono dalla posizione
Per i bit alti serve la posizione dell'uno di indice : allora bassi
Esempio get: l'uno di indice 9 è in posizione 15; alti , bassi ,
Per trovare l'uno di indice si contano gli uni parola per parola: un POPCNT consuma 64 bit, cioè 20–30 elementi, in un'istruzione: pochi picosecondi per elemento
Arrivati alla parola giusta, l'uno cercato si trova con poche istruzioni
alti
bassi
bit –
Accesso diretto: get
I bit bassi di si leggono subito: partono dalla posizione
Per i bit alti serve la posizione dell'uno di indice : allora bassi
Esempio get: l'uno di indice 9 è in posizione 15; alti , bassi ,
Per trovare l'uno di indice si contano gli uni parola per parola: un POPCNT consuma 64 bit, cioè 20–30 elementi, in un'istruzione: pochi picosecondi per elemento
Arrivati alla parola giusta, l'uno cercato si trova con poche istruzioni
alti
bassi
bit –
Accesso diretto: get
I bit bassi di si leggono subito: partono dalla posizione
Per i bit alti serve la posizione dell'uno di indice : allora bassi
Esempio get: l'uno di indice 9 è in posizione 15; alti , bassi ,
Per trovare l'uno di indice si contano gli uni parola per parola: un POPCNT consuma 64 bit, cioè 20–30 elementi, in un'istruzione: pochi picosecondi per elemento
Arrivati alla parola giusta, l'uno cercato si trova con poche istruzioni
alti
bassi
bit –
, alti
Accesso diretto: get
I bit bassi di si leggono subito: partono dalla posizione
Per i bit alti serve la posizione dell'uno di indice : allora bassi
Esempio get: l'uno di indice 9 è in posizione 15; alti , bassi ,
Per trovare l'uno di indice si contano gli uni parola per parola: un POPCNT consuma 64 bit, cioè 20–30 elementi, in un'istruzione: pochi picosecondi per elemento
Arrivati alla parola giusta, l'uno cercato si trova con poche istruzioni
alti
bassi
bit –
, alti
Accesso diretto: get
I bit bassi di si leggono subito: partono dalla posizione
Per i bit alti serve la posizione dell'uno di indice : allora bassi
Esempio get: l'uno di indice 9 è in posizione 15; alti , bassi ,
Per trovare l'uno di indice si contano gli uni parola per parola: un POPCNT consuma 64 bit, cioè 20–30 elementi, in un'istruzione: pochi picosecondi per elemento
Arrivati alla parola giusta, l'uno cercato si trova con poche istruzioni
alti
bassi
bit –
, alti
Puntatori in avanti per get
Contare gli uni dall'inizio costa in proporzione a : troppo
Fissiamo il quanto (in pratica 256) e memorizziamo, per ogni , la posizione dell'uno di indice : sono i puntatori in avanti (forward pointers)
get: si parte dalla posizione dell'uno di indice e si superano meno di uni
Gli uni sono almeno un terzo dei bit: in media si leggono meno di bit, poche parole
Il puntatore memorizza solo , ma è noto: da abbiamo anche , e si riparte come se avessimo letto fin lì
alti
Puntatori in avanti per get
Contare gli uni dall'inizio costa in proporzione a : troppo
Fissiamo il quanto (in pratica 256) e memorizziamo, per ogni , la posizione dell'uno di indice : sono i puntatori in avanti (forward pointers)
get: si parte dalla posizione dell'uno di indice e si superano meno di uni
Gli uni sono almeno un terzo dei bit: in media si leggono meno di bit, poche parole
Il puntatore memorizza solo , ma è noto: da abbiamo anche , e si riparte come se avessimo letto fin lì
alti
Puntatori in avanti per get
Contare gli uni dall'inizio costa in proporzione a : troppo
Fissiamo il quanto (in pratica 256) e memorizziamo, per ogni , la posizione dell'uno di indice : sono i puntatori in avanti (forward pointers)
get: si parte dalla posizione dell'uno di indice e si superano meno di uni
Gli uni sono almeno un terzo dei bit: in media si leggono meno di bit, poche parole
Il puntatore memorizza solo , ma è noto: da abbiamo anche , e si riparte come se avessimo letto fin lì
alti
get: puntatore : , , ; poi un solo uno da superare
Puntatori in avanti per get
Contare gli uni dall'inizio costa in proporzione a : troppo
Fissiamo il quanto (in pratica 256) e memorizziamo, per ogni , la posizione dell'uno di indice : sono i puntatori in avanti (forward pointers)
get: si parte dalla posizione dell'uno di indice e si superano meno di uni
Gli uni sono almeno un terzo dei bit: in media si leggono meno di bit, poche parole
Il puntatore memorizza solo , ma è noto: da abbiamo anche , e si riparte come se avessimo letto fin lì
alti
get: puntatore : , , ; poi un solo uno da superare
Puntatori in avanti per get
Contare gli uni dall'inizio costa in proporzione a : troppo
Fissiamo il quanto (in pratica 256) e memorizziamo, per ogni , la posizione dell'uno di indice : sono i puntatori in avanti (forward pointers)
get: si parte dalla posizione dell'uno di indice e si superano meno di uni
Gli uni sono almeno un terzo dei bit: in media si leggono meno di bit, poche parole
Il puntatore memorizza solo , ma è noto: da abbiamo anche , e si riparte come se avessimo letto fin lì
alti
get: puntatore : , , ; poi un solo uno da superare
Salto: skipTo
Gli elementi con bit alti minori di sono tutti : si possono saltare
Gli zeri a sinistra dell'uno di sono : basta superare zeri
Arrivati in posizione abbiamo superato uni: il prossimo elemento ha quell'indice, e bit alti
Da lì si legge in successione: gli elementi con gli stessi bit alti di vanno confrontati con ; il primo con bit alti maggiori è comunque
alti
, : gli elementi con bit alti sono
Salto: skipTo
Gli elementi con bit alti minori di sono tutti : si possono saltare
Gli zeri a sinistra dell'uno di sono : basta superare zeri
Arrivati in posizione abbiamo superato uni: il prossimo elemento ha quell'indice, e bit alti
Da lì si legge in successione: gli elementi con gli stessi bit alti di vanno confrontati con ; il primo con bit alti maggiori è comunque
alti
, : gli elementi con bit alti sono
Salto: skipTo
Gli elementi con bit alti minori di sono tutti : si possono saltare
Gli zeri a sinistra dell'uno di sono : basta superare zeri
Arrivati in posizione abbiamo superato uni: il prossimo elemento ha quell'indice, e bit alti
Da lì si legge in successione: gli elementi con gli stessi bit alti di vanno confrontati con ; il primo con bit alti maggiori è comunque
alti
, : gli elementi con bit alti sono
dopo zeri:
Salto: skipTo
Gli elementi con bit alti minori di sono tutti : si possono saltare
Gli zeri a sinistra dell'uno di sono : basta superare zeri
Arrivati in posizione abbiamo superato uni: il prossimo elemento ha quell'indice, e bit alti
Da lì si legge in successione: gli elementi con gli stessi bit alti di vanno confrontati con ; il primo con bit alti maggiori è comunque
alti
, : gli elementi con bit alti sono
dopo zeri:
skipTo(58)
: superiamo 7 zeri, e arriviamo in posizione
Uni superati: , quindi il prossimo elemento è
: alti , bassi , : si va avanti
: è il risultato
alti
bassi
skipTo(58)
: superiamo 7 zeri, e arriviamo in posizione
Uni superati: , quindi il prossimo elemento è
: alti , bassi , : si va avanti
: è il risultato
alti
bassi
, indice
skipTo(58)
: superiamo 7 zeri, e arriviamo in posizione
Uni superati: , quindi il prossimo elemento è
: alti , bassi , : si va avanti
: è il risultato
alti
bassi
, indice
skipTo(58)
: superiamo 7 zeri, e arriviamo in posizione
Uni superati: , quindi il prossimo elemento è
: alti , bassi , : si va avanti
: è il risultato
alti
bassi
, indice
skipTo(42): un buco
: superiamo 5 zeri, e arriviamo in posizione
Uni superati: ; ma in posizione 13 c'è un altro zero: nessun elemento ha bit alti 5, cioè sta fra 40 e 47
Si prosegue: l'uno in posizione 14 è , con alti :
Quando i bit alti superano quelli di non serve nemmeno guardare i bassi: quell'elemento è il risultato
alti
bassi
skipTo(42): un buco
: superiamo 5 zeri, e arriviamo in posizione
Uni superati: ; ma in posizione 13 c'è un altro zero: nessun elemento ha bit alti 5, cioè sta fra 40 e 47
Si prosegue: l'uno in posizione 14 è , con alti :
Quando i bit alti superano quelli di non serve nemmeno guardare i bassi: quell'elemento è il risultato
alti
bassi
, indice
skipTo(42): un buco
: superiamo 5 zeri, e arriviamo in posizione
Uni superati: ; ma in posizione 13 c'è un altro zero: nessun elemento ha bit alti 5, cioè sta fra 40 e 47
Si prosegue: l'uno in posizione 14 è , con alti :
Quando i bit alti superano quelli di non serve nemmeno guardare i bassi: quell'elemento è il risultato
alti
bassi
, indice
skipTo(42): un buco
: superiamo 5 zeri, e arriviamo in posizione
Uni superati: ; ma in posizione 13 c'è un altro zero: nessun elemento ha bit alti 5, cioè sta fra 40 e 47
Si prosegue: l'uno in posizione 14 è , con alti :
Quando i bit alti superano quelli di non serve nemmeno guardare i bassi: quell'elemento è il risultato
alti
bassi
, indice
skipTo(124): oltre la fine
: superiamo 15 zeri, posizione , indice
Dopo non ci sono altri uni: nessun elemento è , il risultato è
In generale skipTo legge gli elementi con gli stessi bit alti di , e al più uno dopo; se gli zeri da superare non bastano, il risultato è subito
alti
bassi
skipTo(124): oltre la fine
: superiamo 15 zeri, posizione , indice
Dopo non ci sono altri uni: nessun elemento è , il risultato è
In generale skipTo legge gli elementi con gli stessi bit alti di , e al più uno dopo; se gli zeri da superare non bastano, il risultato è subito
alti
bassi
, indice
skipTo(124): oltre la fine
: superiamo 15 zeri, posizione , indice
Dopo non ci sono altri uni: nessun elemento è , il risultato è
In generale skipTo legge gli elementi con gli stessi bit alti di , e al più uno dopo; se gli zeri da superare non bastano, il risultato è subito
alti
bassi
, indice
nessun elemento :
skipTo(124): oltre la fine
: superiamo 15 zeri, posizione , indice
Dopo non ci sono altri uni: nessun elemento è , il risultato è
In generale skipTo legge gli elementi con gli stessi bit alti di , e al più uno dopo; se gli zeri da superare non bastano, il risultato è subito
alti
bassi
, indice
nessun elemento :
Puntatori in avanti per skipTo
Superare zeri contandoli dall'inizio è lento come contare gli uni dall'inizio per get
Memorizziamo anche, per ogni , la posizione subito dopo i primi zeri: da lì gli elementi hanno bit alti
skipTo: si parte dal puntatore , si superano meno di zeri e si confrontano gli elementi con gli stessi bit alti di
In media pochi bit: con vicino a , gli zeri sono almeno circa metà del vettore dei bit alti
Il puntatore memorizza solo , ma è noto: da abbiamo l'indice , quindi dove leggere i bit bassi
alti
Puntatori in avanti per skipTo
Superare zeri contandoli dall'inizio è lento come contare gli uni dall'inizio per get
Memorizziamo anche, per ogni , la posizione subito dopo i primi zeri: da lì gli elementi hanno bit alti
skipTo: si parte dal puntatore , si superano meno di zeri e si confrontano gli elementi con gli stessi bit alti di
In media pochi bit: con vicino a , gli zeri sono almeno circa metà del vettore dei bit alti
Il puntatore memorizza solo , ma è noto: da abbiamo l'indice , quindi dove leggere i bit bassi
alti
Puntatori in avanti per skipTo
Superare zeri contandoli dall'inizio è lento come contare gli uni dall'inizio per get
Memorizziamo anche, per ogni , la posizione subito dopo i primi zeri: da lì gli elementi hanno bit alti
skipTo: si parte dal puntatore , si superano meno di zeri e si confrontano gli elementi con gli stessi bit alti di
In media pochi bit: con vicino a , gli zeri sono almeno circa metà del vettore dei bit alti
Il puntatore memorizza solo , ma è noto: da abbiamo l'indice , quindi dove leggere i bit bassi
alti
skipTo: puntatore : , , ; poi altri zeri: ,
Puntatori in avanti per skipTo
Superare zeri contandoli dall'inizio è lento come contare gli uni dall'inizio per get
Memorizziamo anche, per ogni , la posizione subito dopo i primi zeri: da lì gli elementi hanno bit alti
skipTo: si parte dal puntatore , si superano meno di zeri e si confrontano gli elementi con gli stessi bit alti di
In media pochi bit: con vicino a , gli zeri sono almeno circa metà del vettore dei bit alti
Il puntatore memorizza solo , ma è noto: da abbiamo l'indice , quindi dove leggere i bit bassi
alti
skipTo: puntatore : , , ; poi altri zeri: ,
Puntatori in avanti per skipTo
Superare zeri contandoli dall'inizio è lento come contare gli uni dall'inizio per get
Memorizziamo anche, per ogni , la posizione subito dopo i primi zeri: da lì gli elementi hanno bit alti
skipTo: si parte dal puntatore , si superano meno di zeri e si confrontano gli elementi con gli stessi bit alti di
In media pochi bit: con vicino a , gli zeri sono almeno circa metà del vettore dei bit alti
Il puntatore memorizza solo , ma è noto: da abbiamo l'indice , quindi dove leggere i bit bassi
alti
skipTo: puntatore : , , ; poi altri zeri: ,
I costi
Lettura in successione: poche istruzioni per elemento, memoria letta in avanti
get e skipTo: tempo costante in media, grazie ai puntatori e all'equilibrio fra uni e zeri
Spesso i salti vanno in avanti: se è vicino si legge in successione dalla posizione corrente, se è lontano si usa il puntatore
Ogni operazione fa pochi accessi alla memoria (puntatore, bit alti, bit bassi), ciascuno a pochi bit contigui
Spazio dei puntatori: al più tre numeri ogni elementi; con , una frazione di bit per elemento
Niente di tutto questo dipende dalla distribuzione degli elementi
I costi
Lettura in successione: poche istruzioni per elemento, memoria letta in avanti
get e skipTo: tempo costante in media, grazie ai puntatori e all'equilibrio fra uni e zeri
Spesso i salti vanno in avanti: se è vicino si legge in successione dalla posizione corrente, se è lontano si usa il puntatore
Ogni operazione fa pochi accessi alla memoria (puntatore, bit alti, bit bassi), ciascuno a pochi bit contigui
Spazio dei puntatori: al più tre numeri ogni elementi; con , una frazione di bit per elemento
Niente di tutto questo dipende dalla distribuzione degli elementi
I costi
Lettura in successione: poche istruzioni per elemento, memoria letta in avanti
get e skipTo: tempo costante in media, grazie ai puntatori e all'equilibrio fra uni e zeri
Spesso i salti vanno in avanti: se è vicino si legge in successione dalla posizione corrente, se è lontano si usa il puntatore
Ogni operazione fa pochi accessi alla memoria (puntatore, bit alti, bit bassi), ciascuno a pochi bit contigui
Spazio dei puntatori: al più tre numeri ogni elementi; con , una frazione di bit per elemento
Niente di tutto questo dipende dalla distribuzione degli elementi
I costi
Lettura in successione: poche istruzioni per elemento, memoria letta in avanti
get e skipTo: tempo costante in media, grazie ai puntatori e all'equilibrio fra uni e zeri
Spesso i salti vanno in avanti: se è vicino si legge in successione dalla posizione corrente, se è lontano si usa il puntatore
Ogni operazione fa pochi accessi alla memoria (puntatore, bit alti, bit bassi), ciascuno a pochi bit contigui
Spazio dei puntatori: al più tre numeri ogni elementi; con , una frazione di bit per elemento
Niente di tutto questo dipende dalla distribuzione degli elementi
I costi
Lettura in successione: poche istruzioni per elemento, memoria letta in avanti
get e skipTo: tempo costante in media, grazie ai puntatori e all'equilibrio fra uni e zeri
Spesso i salti vanno in avanti: se è vicino si legge in successione dalla posizione corrente, se è lontano si usa il puntatore
Ogni operazione fa pochi accessi alla memoria (puntatore, bit alti, bit bassi), ciascuno a pochi bit contigui
Spazio dei puntatori: al più tre numeri ogni elementi; con , una frazione di bit per elemento
Niente di tutto questo dipende dalla distribuzione degli elementi
I costi
Lettura in successione: poche istruzioni per elemento, memoria letta in avanti
get e skipTo: tempo costante in media, grazie ai puntatori e all'equilibrio fra uni e zeri
Spesso i salti vanno in avanti: se è vicino si legge in successione dalla posizione corrente, se è lontano si usa il puntatore
Ogni operazione fa pochi accessi alla memoria (puntatore, bit alti, bit bassi), ciascuno a pochi bit contigui
Spazio dei puntatori: al più tre numeri ogni elementi; con , una frazione di bit per elemento
Niente di tutto questo dipende dalla distribuzione degli elementi
Demo: le tre operazioni
Interactive Demo
Lettura in successione, get(i) e skipTo(b) su Elias–Fano: si vedono i bit visitati, gli zeri superati e i bit bassi letti. I puntatori si possono attivare.
I conteggi
Per ogni documento della lista, quante volte compare il termine: , tutti
Non è una successione crescente: memorizziamo le somme prefisse
Allora (con ): due get, o due elementi letti in successione
Invece di trasformare una successione crescente in scarti, trasformiamo dei numeri piccoli in una successione crescente
documento
conteggio
I conteggi
Per ogni documento della lista, quante volte compare il termine: , tutti
Non è una successione crescente: memorizziamo le somme prefisse
Allora (con ): due get, o due elementi letti in successione
Invece di trasformare una successione crescente in scarti, trasformiamo dei numeri piccoli in una successione crescente
documento
conteggio
somma
I conteggi
Per ogni documento della lista, quante volte compare il termine: , tutti
Non è una successione crescente: memorizziamo le somme prefisse
Allora (con ): due get, o due elementi letti in successione
Invece di trasformare una successione crescente in scarti, trasformiamo dei numeri piccoli in una successione crescente
documento
conteggio
somma
I conteggi
Per ogni documento della lista, quante volte compare il termine: , tutti
Non è una successione crescente: memorizziamo le somme prefisse
Allora (con ): due get, o due elementi letti in successione
Invece di trasformare una successione crescente in scarti, trasformiamo dei numeri piccoli in una successione crescente
documento
conteggio
somma
Le posizioni, in fila
Per ogni documento servono anche le posizioni in cui compare il termine: le mettiamo in fila, un documento dopo l'altro
Il documento di indice occupa un blocco lungo
Quindi il suo blocco comincia dopo posizioni, e finisce prima di
Le somme prefisse dei conteggi sono i confini dei blocchi: per le posizioni del documento bastano e
documento 3
documento 5
documento 11
indice
Le posizioni, in fila
Per ogni documento servono anche le posizioni in cui compare il termine: le mettiamo in fila, un documento dopo l'altro
Il documento di indice occupa un blocco lungo
Quindi il suo blocco comincia dopo posizioni, e finisce prima di
Le somme prefisse dei conteggi sono i confini dei blocchi: per le posizioni del documento bastano e
documento 3,
documento 5,
documento 11,
indice
Le posizioni, in fila
Per ogni documento servono anche le posizioni in cui compare il termine: le mettiamo in fila, un documento dopo l'altro
Il documento di indice occupa un blocco lungo
Quindi il suo blocco comincia dopo posizioni, e finisce prima di
Le somme prefisse dei conteggi sono i confini dei blocchi: per le posizioni del documento bastano e
documento 3,
documento 5,
documento 11,
indice
Le posizioni, in fila
Per ogni documento servono anche le posizioni in cui compare il termine: le mettiamo in fila, un documento dopo l'altro
Il documento di indice occupa un blocco lungo
Quindi il suo blocco comincia dopo posizioni, e finisce prima di
Le somme prefisse dei conteggi sono i confini dei blocchi: per le posizioni del documento bastano e
documento 3,
documento 5,
documento 11,
indice
documento di indice : indici da a
Le posizioni con Elias–Fano
Dentro ogni blocco le posizioni crescono, ma da un blocco all'altro ricominciano
Prendiamo gli scarti, ricominciando a ogni documento, e ne memorizziamo le somme prefisse: una sola successione non decrescente, in Elias–Fano
Posizioni del documento di indice : get, poi lettura in successione fino all'indice
A ogni elemento si toglie quello che precede il blocco, di indice
posizioni nei documenti 3, 5, 11
Le posizioni con Elias–Fano
Dentro ogni blocco le posizioni crescono, ma da un blocco all'altro ricominciano
Prendiamo gli scarti, ricominciando a ogni documento, e ne memorizziamo le somme prefisse: una sola successione non decrescente, in Elias–Fano
Posizioni del documento di indice : get, poi lettura in successione fino all'indice
A ogni elemento si toglie quello che precede il blocco, di indice
posizioni nei documenti 3, 5, 11
scarti (ricominciando a ogni documento)
somme prefisse
Le posizioni con Elias–Fano
Dentro ogni blocco le posizioni crescono, ma da un blocco all'altro ricominciano
Prendiamo gli scarti, ricominciando a ogni documento, e ne memorizziamo le somme prefisse: una sola successione non decrescente, in Elias–Fano
Posizioni del documento di indice : get, poi lettura in successione fino all'indice
A ogni elemento si toglie quello che precede il blocco, di indice
posizioni nei documenti 3, 5, 11
scarti (ricominciando a ogni documento)
somme prefisse
documento di indice : get, poi gli elementi di indice e
Le posizioni con Elias–Fano
Dentro ogni blocco le posizioni crescono, ma da un blocco all'altro ricominciano
Prendiamo gli scarti, ricominciando a ogni documento, e ne memorizziamo le somme prefisse: una sola successione non decrescente, in Elias–Fano
Posizioni del documento di indice : get, poi lettura in successione fino all'indice
A ogni elemento si toglie quello che precede il blocco, di indice
posizioni nei documenti 3, 5, 11
scarti (ricominciando a ogni documento)
somme prefisse
documento di indice : get, poi gli elementi di indice e
meno (l'elemento di indice ):
In pratica
Un indice con Elias–Fano comprime le liste dei documenti meglio della maggior parte dei codici per scarti, ed è più veloce sia in successione sia nei salti
Il limite allo spazio dipende solo da e
Se la lista è densa, con oltre circa , conviene un vettore di bit (un uno per ogni elemento), con le sue strutture per get e skipTo
Variante: spezzare la lista in blocchi, ciascuno con i suoi e , adatta lo spazio alla distribuzione (Elias–Fano partizionato)
Lo stesso schema serve ovunque ci sia una successione crescente: indici, grafi compressi, funzioni di hash minimali perfette, strutture succinte
In pratica
Un indice con Elias–Fano comprime le liste dei documenti meglio della maggior parte dei codici per scarti, ed è più veloce sia in successione sia nei salti
Il limite allo spazio dipende solo da e
Se la lista è densa, con oltre circa , conviene un vettore di bit (un uno per ogni elemento), con le sue strutture per get e skipTo
Variante: spezzare la lista in blocchi, ciascuno con i suoi e , adatta lo spazio alla distribuzione (Elias–Fano partizionato)
Lo stesso schema serve ovunque ci sia una successione crescente: indici, grafi compressi, funzioni di hash minimali perfette, strutture succinte
In pratica
Un indice con Elias–Fano comprime le liste dei documenti meglio della maggior parte dei codici per scarti, ed è più veloce sia in successione sia nei salti
Il limite allo spazio dipende solo da e
Se la lista è densa, con oltre circa , conviene un vettore di bit (un uno per ogni elemento), con le sue strutture per get e skipTo
Variante: spezzare la lista in blocchi, ciascuno con i suoi e , adatta lo spazio alla distribuzione (Elias–Fano partizionato)
Lo stesso schema serve ovunque ci sia una successione crescente: indici, grafi compressi, funzioni di hash minimali perfette, strutture succinte
In pratica
Un indice con Elias–Fano comprime le liste dei documenti meglio della maggior parte dei codici per scarti, ed è più veloce sia in successione sia nei salti
Il limite allo spazio dipende solo da e
Se la lista è densa, con oltre circa , conviene un vettore di bit (un uno per ogni elemento), con le sue strutture per get e skipTo
Variante: spezzare la lista in blocchi, ciascuno con i suoi e , adatta lo spazio alla distribuzione (Elias–Fano partizionato)
Lo stesso schema serve ovunque ci sia una successione crescente: indici, grafi compressi, funzioni di hash minimali perfette, strutture succinte
In pratica
Un indice con Elias–Fano comprime le liste dei documenti meglio della maggior parte dei codici per scarti, ed è più veloce sia in successione sia nei salti
Il limite allo spazio dipende solo da e
Se la lista è densa, con oltre circa , conviene un vettore di bit (un uno per ogni elemento), con le sue strutture per get e skipTo
Variante: spezzare la lista in blocchi, ciascuno con i suoi e , adatta lo spazio alla distribuzione (Elias–Fano partizionato)
Lo stesso schema serve ovunque ci sia una successione crescente: indici, grafi compressi, funzioni di hash minimali perfette, strutture succinte
Riepilogo
Una successione crescente di elementi minori di : bit bassi scritti così come sono
Vettore dei bit alti: gli scarti fra i bit alti, in unario; l'uno di sta in posizione
Spazio: al più bit per elemento, vicino al minimo, qualunque sia la distribuzione
Lettura in successione: cercare il prossimo uno; get: l'uno di indice ; skipTo: superare zeri
Puntatori in avanti ogni uni e ogni zeri: danno , e da si ricava il numero mancante; get e skipTo in tempo costante in media
Negli indici: conteggi e posizioni con le somme prefisse
Riepilogo
Una successione crescente di elementi minori di : bit bassi scritti così come sono
Vettore dei bit alti: gli scarti fra i bit alti, in unario; l'uno di sta in posizione
Spazio: al più bit per elemento, vicino al minimo, qualunque sia la distribuzione
Lettura in successione: cercare il prossimo uno; get: l'uno di indice ; skipTo: superare zeri
Puntatori in avanti ogni uni e ogni zeri: danno , e da si ricava il numero mancante; get e skipTo in tempo costante in media
Negli indici: conteggi e posizioni con le somme prefisse
Riepilogo
Una successione crescente di elementi minori di : bit bassi scritti così come sono
Vettore dei bit alti: gli scarti fra i bit alti, in unario; l'uno di sta in posizione
Spazio: al più bit per elemento, vicino al minimo, qualunque sia la distribuzione
Lettura in successione: cercare il prossimo uno; get: l'uno di indice ; skipTo: superare zeri
Puntatori in avanti ogni uni e ogni zeri: danno , e da si ricava il numero mancante; get e skipTo in tempo costante in media
Negli indici: conteggi e posizioni con le somme prefisse
Riepilogo
Una successione crescente di elementi minori di : bit bassi scritti così come sono
Vettore dei bit alti: gli scarti fra i bit alti, in unario; l'uno di sta in posizione
Spazio: al più bit per elemento, vicino al minimo, qualunque sia la distribuzione
Lettura in successione: cercare il prossimo uno; get: l'uno di indice ; skipTo: superare zeri
Puntatori in avanti ogni uni e ogni zeri: danno , e da si ricava il numero mancante; get e skipTo in tempo costante in media
Negli indici: conteggi e posizioni con le somme prefisse
Riepilogo
Una successione crescente di elementi minori di : bit bassi scritti così come sono
Vettore dei bit alti: gli scarti fra i bit alti, in unario; l'uno di sta in posizione
Spazio: al più bit per elemento, vicino al minimo, qualunque sia la distribuzione
Lettura in successione: cercare il prossimo uno; get: l'uno di indice ; skipTo: superare zeri
Puntatori in avanti ogni uni e ogni zeri: danno , e da si ricava il numero mancante; get e skipTo in tempo costante in media
Negli indici: conteggi e posizioni con le somme prefisse
Riepilogo
Una successione crescente di elementi minori di : bit bassi scritti così come sono
Vettore dei bit alti: gli scarti fra i bit alti, in unario; l'uno di sta in posizione
Spazio: al più bit per elemento, vicino al minimo, qualunque sia la distribuzione
Lettura in successione: cercare il prossimo uno; get: l'uno di indice ; skipTo: superare zeri
Puntatori in avanti ogni uni e ogni zeri: danno , e da si ricava il numero mancante; get e skipTo in tempo costante in media
Negli indici: conteggi e posizioni con le somme prefisse