Je dois extraire uniformément des DFA (automates finis déterministes) à partir d'un ensemble de DFA que j'appelle S. Il semble un problème simple, mais je n'ai pas le jeu S. S contient toutes les DFA de dimension n , donc je sais que la dimension de S, je peux construire S, mais je ne peux pas parce que est très grande. Je sais aussi la dimension des ensembles Sm où, par exemple S3 est un sous-ensemble de S et S3 contient toutes les DFA avec 3 états, Sm contient toutes les DFA avec les États m où m < n.Échantillonnage sans remplacement à partir d'un ensemble inconnu
Je n'ai pas l'ensemble S et donc je dois simuler un échantillonnage uniforme. De plus, je dois faire l'échantillonnage sans le remplacer. Je crée un ensemble D = {1,2,3 ........ n} et pour chaque valeur que j'appelle i, en D J'associe la valeur | Si |/| S | où | | indique le nombre d'éléments dans l'ensemble qui est l'argument. A savoir, j'ai créé une distribution. Maintenant, je peux extraire une valeur de D en fonction de cette distribution. De cette façon, j'ai trouvé l'ensemble à partir duquel extraire un seul DFA. Par exemple si à partir de D je extrait 4 alors je dois extraire uniformément un DFA de S4.
Mais ma question est, comment puis-je un DFA de sample Si (S4 dans l'exemple ci-dessus) sans remplacement? A savoir si j'ai déjà extrait précédemment un DFA spécifique, dans l'échantillonnage suivant, je dois éviter ce DFA spécifique. Remarquez qu'un DFA est une matrice, une table (un tableau bidimensionnel). Remarquez aussi que extraire un DFA spécifique signifie uniformément extraire pour chaque cellule du tableau ci-dessus une valeur dans {1, ....., k} où k est le nombre des éléments de l'alphabet (il faut aussi extraire pour chaque état si accepte ou rejette).
(je dois mettre en œuvre 11 C++, mais cela est assez hors de propos)
Cette procédure ne semble pas efficace. Pour chaque DFA échantillonné, je dois comparer avec tout le hachage de DFA précédemment extrait. En outre, je ne connais pas MurmurHash3 128 bits, n'assure-t-il aucune collision? (à savoir 2 dfa avec le même hachage) – Umbert
Les valeurs de hachage peuvent être triées, donc la recherche si un hachage est déjà apparu ne prend que des comparaisons log2 (n). La probabilité d'une collision est extrêmement faible (recherche 'hash collision probability). Vous pouvez utiliser la fonction de hachage 256 bits. Mais ce serait probablement une surpuissance –
Oui, avec 80000 valeur (mon cas) et 128 bits de probabilité de collision est d'environ 9,4 * 10^-30. Goog idée de tri également. Je dois comprendre que l'utilisation de MurmurHash3 seul – Umbert