Campionamento di una distribuzione uniforme di stringhe di dimensioni fisse contenenti substrazioni proibite

Question

Dato un elenco di parole "proibite" (substrings), un alfabeto e una lunghezza della stringa di output desiderata, come posso campionarmi in modo efficiente stringhe di output non contenenti una parola proibita?

Per corde di output brevi con poche parole proibite, userei un semplice campionamento di rifiuto. Scegli una stringa (uniforme) con l'alfabeto e la lunghezza specificati, restituisci quella stringa se non contiene alcun elemento dell'elenco proibito, riprova altrimenti.

Se uso quell'algoritmo per le lunghezze di uscita più volte più grande della tipica parola proibita, la probabilità di rifiuto sarà più elevata. (La maggior parte delle parole sono lunghe 2 o 3 caratteri.)

Supponiamo che la lunghezza di uscita richiesta sia troppo lunga per elencare e memorizzare ogni possibile valore. La mia dimensione dell'alfabeto sarebbe da 16 a 36 caratteri, ma le soluzioni a grandi alfabeti sarebbero interessanti a cui pensare. (Nel qual caso chiamerei queste cose frasi casuali, n-grammi proibiti e parole del dizionario.)

La mia lista di parole proibite avrà cento a mille stringhe. Vorrei evitare soluzioni che richiedono una precomputazione costosa o molta memoria.

---

La mia prima idea è stata quella di provare a costruire una stringa casuale in modo incrementale, in contrasto con l'approccio tutto o niente del campionamento di rifiuto semplice. Dubito che il mio algoritmo produca ogni possibile produzione con uguale probabilità.

Segue l'idea dell'algoritmo:

1. Inizializza un buffer char abbastanza a lungo da adattarsi outlen personaggi.
2. Scegli una lettera casuale dell'alfabeto e aggiungila al buffer.
3. Se il buffer termina con una parola proibita di lunghezza k, Quindi rimuovere l'ultimo k Lettere dal buffer Char e vai a 2.
4. Altrimenti, vai a 2 se il buffer ha meno di outlen personaggi.
5. Restituisci il contenuto del buffer se è pieno.

Il passaggio 3 serve a riavvolgere l'algoritmo, restituendo il buffer Char in uno stato legale precedente.

Capisco che la cancellazione dell'intero buffer nel passaggio 3 produrrebbe sicuramente un output uniforme proprio come il semplice metodo di campionamento del rifiuto. Tuttavia, il numero medio di rifiuti prima che venga generato il primo output valido sarà lo stesso.

Mi sono bloccato cercando di determinare se il mio algoritmo proposto è uniforme. Non ho avuto fortuna a trovare algoritmi alternativi. Non ho ancora esaminato come le prestazioni di questo algoritmo sarebbero paragonate al campionamento del rifiuto di base.