Échantillonnage d'une distribution uniforme des chaînes de taille fixe ne contenant aucune sous-lamelle interdite

Question

Compte tenu d'une liste de mots «interdits» (sous-chaînes), d'un alphabet et d'une longueur de chaîne de sortie souhaitée, comment pourrais-je efficacement échantillonner des chaînes de sortie ne contenant aucun mot interdit?

Pour les chaînes de sortie courtes avec peu de mots interdits, j'utiliserais un échantillonnage de rejet simple. Choisissez une chaîne (uniformément) avec l'alphabet et la longueur spécifiés, renvoyez cette chaîne s'il ne contient aucun élément de la liste interdite, réessayez autrement.

Si j'utilise cet algorithme pour les longueurs de sortie plusieurs fois plus grands que le mot interdit typique, la probabilité de rejet sera plus élevée. (La plupart des mots mesurent 2 ou 3 caractères.)

Supposons que la longueur de sortie demandée soit trop longue pour énumérer et stocker chaque valeur possible. Ma taille d'alphabet serait de 16 à 36 caractères, mais les solutions aux grands alphabets seraient intéressantes à penser. (Dans ce cas, j'appellerais ces choses phrases aléatoires, n-grammes interdits et mots du dictionnaire.)

Ma liste de mots interdite aura cent à mille cordes. Je voudrais éviter les solutions nécessitant une précomputation coûteuse ou beaucoup de mémoire.

---

Ma première idée a été d'essayer de construire une chaîne aléatoire progressivement, contrairement à l'approche tout ou rien d'échantillonnage de rejet simple. Je doute que mon algorithme produit chaque sortie possible avec une probabilité égale.

L'idée de l'algorithme suit:

1. Initialiser un tampon de charbon assez longtemps pour s'adapter outlen personnages.
2. Choisissez une lettre aléatoire de l'alphabet et ajoutez-la au tampon.
3. Si le tampon se termine par un mot de longueur interdit k, puis retirez le dernier k Lettres du tampon char et passer à 2.
4. Sinon, passez à 2 si le tampon a moins de outlen personnages.
5. Renvoyez le contenu du tampon s'il est plein.

L'étape 3 sert à rembobiner l'algorithme, renvoyant le tampon char à un état juridique précédent.

Je comprends que nettoyer l'ensemble du tampon à l'étape 3 produirait certainement une sortie uniforme comme la méthode d'échantillonnage de rejet simple. Cependant, le nombre moyen de refus avant la première sortie valide sera le même.

Je suis resté coincé en essayant de déterminer si mon algorithme proposé est uniforme. Je n'ai pas eu de chance de trouver des algorithmes alternatifs non plus. Je n'ai pas encore examiné comment les performances de cet algorithme se compareraient à l'échantillonnage de rejet de base.