Casuale a lunghezza variabile codificato numeri con distribuzione uniforme

Question

Supponiamo che io ho dati presentati con la codifica a lunghezza variabile quando posso recuperare i dati parsing alcune b-albero virtuale e fermandosi quando raggiungo la voce (simile alla codifica di Huffman). C'è sconosciuta numero di elementi (nel migliore dei casi è noto solo il limite superiore). Esiste un algoritmo per generare numeri uniformemente distribuiti? Il problema è che un algoritmo moneta basata darà risultato non uniforme in questo caso, ad esempio se v'è un numero codificato come 101 e c'è un numero codificato 10.010.101, quest'ultima appare molto raramente confronto alla precedente.

UPDATE: In altre parole, ho un insieme di massimo N elementi (ma forse meno) quando ogni elemento può essere affrontato con numero arbitrario di bit (e con accordo con la teoria informativo, quindi se uno è codificato 101 allora nessun altro elemento può essere codificato con lo stesso prefisso). Quindi è più come B-Tree quando vado a destra oa sinistra a seconda di un po 'e ad un certo momento ho arrivare alla voce di dati. Voglio ottenere una sequenza di numeri casuali affrontato con questa tecnica, ma la distribuzione di essi deve essere uniforme (l'esempio perché la scelta in modo casuale sinistra-destra non funziona è al di sopra, i numeri 101 e 10.010.101)

Grazie

Max

Answer 1

mi viene in mente tre metodi di base, uno dei quali coinvolge reguessing frequente e uno dei quali coinvolge mantenere le informazioni supplementari. Credo che facendo una o l'altra di queste cose è inevitabile. Ho intenzione di iniziare con le informazioni di uno in più:

In ogni nodo, memorizzare un count numero che rappresenta il numero di discendenti che ha. Per ogni nodo, è necessario avere un numero compreso tra 1 e count per quel nodo di dirvi se andare a destra oa sinistra confrontandolo con conteggio del figlio sinistro. Ecco l'algoritmo:

n := random integer between 1 and root.count
node := route
while node.count != 1
     if n <= node.left.count
          node = node.left
     else
          node = node.right
          n = n - node.left.count

Quindi, in sostanza, stiamo imponendo un ordinamento da sinistra a destra in tutti i nodi e selezionando l'ennesimo da sinistra. Questo è abbastanza veloce, solo avendo un O (profondità di albero), che è probabilmente il meglio che possiamo fare a meno di fare qualcosa di simile anche la costruzione di un vettore che contiene tutte le etichette dei nodi. Questo aggiunge anche un overhead di O (profondità di albero) per eventuali modifiche all'albero dal conteggi devono essere corretti. Se si sta andando nella direzione opposta e non cambiare mai l'albero a tutti, ma sta per essere selezionando i nodi casuali molto, solo il bit i denti e mettere tutte le etichette dei nodi in un vettore. In questo modo è possibile selezionare uno casuale nel tempo O (1) dopo la O (N) tempo di set-up iniziale.

Se, tuttavia, non si desidera utilizzare tutto lo spazio di archiviazione, ecco un'alternativa con un sacco di reguessing. In primo luogo trovare un balzo (che io Etichetta B) per la profondità dell'albero (possiamo usare N-1, se necessario, ma, ovviamente, questo è un molto loose legato. Il più stretto il limite che può essere trovato, il più veloce l'algoritmo corre). Successivo stiamo andando a generare una possibile etichetta del nodo in modo casuale, ma anche. Ci sono 2 ^ (B + 1) -1 possibilità. Non è solo 2 ^ B perché, ad esempio, la stringa "0011" e "11" sono completamente diverse stringhe. Come risultato, è necessario contare tutte le possibili stringhe binarie di lunghezza tra 0 e B. Ovviamente, abbiamo 2 ^ i stringhe di lunghezza i. Così per stringhe di lunghezza I o meno, abbiamo la somma (i = 0 a B) {2 ^ i} = 2 ^ (B + 1) -1. Così, possiamo solo scegliere un numero compreso tra 0 e 2 ^ (B + 1) -2 e poi trovare l'etichetta nodo corrispondente. Naturalmente, la mappatura dai numeri alle etichette dei nodi non è banale, quindi mi fornisco qui.

convertire il numero che abbiamo scelto in una stringa di bit in via ordinaria. Poi, leggendo da sinistra, se la prima cifra è uno 0, allora l'etichetta nodo è la stringa rimanente verso destra (forse la stringa vuota, che è un'etichetta nodo valido anche se non sono suscettibili di essere in uso). Se la prima cifra è un 1, allora buttiamo via e ripetere questo processo. Pertanto, se B = 4, allora l'etichetta nodo "0001" verrebbe dal numero "00001". L'etichetta nodo "001" verrebbe dal numero "10001". L'etichetta nodo "01" verrebbe dal numero "11001". L'etichetta nodo "1" verrebbe dal numero "11101". E l'etichetta del nodo "" verrebbe dal numero "11110". non abbiamo incluso il numero 2 ^ (B + 1) -1 ( "11111" in questo caso) che non ha alcuna valida interpretazione del presente regime. Lascio come esercizio per il lettore a dimostrare a se stessi che ogni stringa dal lunghezza 0 a B può essere rappresentata nell'ambito di questo regime. Piuttosto che cercare di dimostrarlo, mi limiterò a asseriscono che funzionerà.

Così ora abbiamo un'etichetta del nodo. Il passo successivo è quello di verificare se tale etichetta esiste per attraversare l'albero. Se è così, abbiamo finito. Se non lo fa, quindi scegliere un nuovo numero e ricominciare da capo (che è la parte reguessing). E 'probabile che a reguess molto, dal momento che solo una piccola frazione di etichette dei nodi di legge sarà in uso, ma questo non inclinare l'equità, basta aumentare il tempo.

Ecco una versione pseudo-codice di questo processo in quattro funzioni:

function num_to_binary_list(n,digits) =
  if digits == 0 return ()
  if n mod 2 == 0 return 0 :: num_to_digits(n/2,digits-1)
  else return 1 :: num_to_digits((n-1)/2,digits-1)

function binary_list_to_node_label_list(l) =
  if l.head() == 0 return l.tail()
  else return binary_list_to_node_label_list(l.tail())

function check_node_label_list_against_tree(str,node) =
  if node == null return false,null
  if str.isEmpty() 
    if node.isLeaf() return true,node
    else return false,null
  if str.head() == 0 return check_node_label_list_against_tree(str.tail(),node.left)
  else check_node_label_list_against_tree(str.tail,node.right)

function generate_random_node tree b =
  found := false
  while (not found)
    x := random(0,2**(b+1)-2) // We're assuming that this random selects inclusively
    node_label := binary_list_to_node_label(num_to_binary_list(x,b+1))
    found,node := check_node_label_list_against_tree(node_label,tree)
  return node

L'analisi tempistica per questo, naturalmente, è abbastanza orrendo. Fondamentalmente, il ciclo while verrà eseguito in media (2 ^ (B + 1) -1) / N volte. Così, nel peggiore dei casi, si tratta di O ((2 ^ N) / N) che è terribile. Nel migliore dei casi, B sarebbe sul oder di log (N), quindi sarebbe approssimativamente O (1), ma che richiede che l'albero equamente bilanciato cui può non essere. Eppure, se si vuole veramente senza spazio in più, questo metodo fa.

Io in realtà non credo che si può fare meglio di questo ultimo metodo senza memorizzare alcune informazioni. Sembra interessante per essere in grado di attraversare l'albero, prendere decisioni casuali, come si va, ma senza memorizzare informazioni aggiuntive sulla struttura, sei solo, non sarà in grado di farlo. Ogni volta che si effettua una decisione di ramificazione, si potrebbe avere solo un nodo sul lato sinistro e un milione di nodi sul lato destro o potrebbe avere un milione di nodi sul lato sinistro e solo sul lato destro. Perché quelli sono possibili e non sai che è il caso, non c'è alcun modo per prendere una decisione, anche casuale tra le due parti. Ovviamente 50-50 non funziona e qualsiasi altra scelta sta per essere altrettanto problematico.

Quindi, se non si desidera più spazio, il secondo metodo funzionerà, ma essere lento. Se non ti dispiace l'aggiunta di un po 'di spazio in più, il primo metodo funziona ed essere veloce. E, come ho detto prima, se non avete intenzione di essere cambiando l'albero e ti verrà la selezione di un sacco di nodi casuali, quindi stringere i denti e basta attraversare l'albero e bastone tutti i nodi foglia in una matrice di auto-coltivazione o vettoriale e quindi scegliere tra quello.