Décider si une chaîne de caractères génériques correspond complètement à une autre chaîne de caractères génériques dans un ensemble

Voici un problème qui me dérange depuis un moment. Disons qu'une chaîne est une séquence de 1 et de 0 et qu'une chaîne générique est une séquence de 1, 0 et? S. Toutes les chaînes et les chaînes génériques ont la même longueur. Ce sont des caractères génériques UNIX standard; 10 ?? 1 correspond à 10011, 10111, etc. - a? correspond à un 1 ou un 0 dans cette position. Si et sont des chaînes génériques, alors nous écrivons si chaque chaîne mise en correspondance par est également mise en correspondance par .w v ≤ w v $v$$w$$v \leq w$$v$$w$

Les problèmes : étant donné un ensemble de chaînes génériques et une requête (également une chaîne générique), existe-t-il un tel que ? Et sinon, pouvons-nous ajouter à efficacement?v w ∈ S v ≤ w v $S$$v$$w \in S$$v \leq w$$v$$S$

Voici la solution évidente (où est la taille des chaînes, est la taille du mot de la RAM (généralement 32 ou 64)): parcourez chaque élément de la liste et testez la condition (qui peut être effectuée en 2 ou 3 opérations en utilisant le bit-twiddling). Testez également si est valable pour tout élément pendant que nous numérisons. Si échoue à notre test, ajoutez à l'ensemble et supprimez les nous avons marqués.kmv≥wwvv$O(\frac{k}{m}n)$$k$$m$$v \geq w$$w$$v$$v$$w$

Mais ce n'est pas assez rapide. Ce serait vraiment cool s'il y avait une solution , ou, dans un monde parfait, une complexité similaire à un arbre radix ( ). Il est également correct que les requêtes soient approximativement correctes : autrement dit, si , alors retournez oui ou non; mais si la condition ne tient pas définitivement, retournez non.O ( k ) v ≤ $O(\log n)$$O(k)$$v \leq w$

Bien que cela n'aide pas le pire des cas, vous pouvez supposer que tous les éléments de sont délimités par une chaîne générique; c'est-à-dire qu'il existe des tels que pour tout , .v w ∈ S v ≥ $S$$v$$w \in S$$v \geq w$

Des idées que j'ai essayées

• Les chaînes génériques forment un joint-semi-réseau. Nous pourrions avoir un arbre n-aire qui contient des chaînes génériques; les feuilles seraient des cordes génériques et les branches représenteraient la jonction de tous les enfants. Si la requête et la jointure sont incomparables, nous n'avons pas à perdre de temps à essayer de comparer avec tous les enfants de cette branche. De plus, si nous effectuons une mise à jour et que la mise à jour s'avère supérieure à une jointure, nous pouvons simplement supprimer la branche entière. Malheureusement, il s'agit toujours de dans le pire des cas, et nous ne trouvons pas toujours les «meilleures» jointures à effectuer lors de l'analyse de l'arborescence pour ajouter des éléments.$O(n)$
• On pourrait former une structure arborescente radix de . Nous savons que est limité par une chaîne générique; supposons que c'est? 0? 0. Ensuite, toutes les branches du trie doivent uniquement se trouver sur les 1er et 3e bits des chaînes. Si le bit courant sur lequel nous branchons la requête est un 1, nous devons vérifier le? et les 1 branches; si c'est 0, on vérifie le? et les 0 branches; si c'est le cas, nous ne vérifions que le? branche. Parce que nous devons potentiellement prendre plusieurs branches, cela ne semble pas très bien (il est difficile de mettre à jour le trie pour la même raison). Étant donné que l'appariement est une opération très très rapide, cela fait mal par rapport à la stratégie naïve de faire beaucoup de traversées dans un arbre (suivre un groupe de pointeurs est beaucoup plus cher que de faire des OU et des ET).$S$$S$

Travaux connexes

• Dans la communauté des réseaux, ce problème se manifeste sous le nom de "classification des paquets", voici un bon aperçu des algorithmes et des structures de données connus . Malheureusement, l'hypothèse est presque toujours faite que les chaînes génériques ne correspondent qu'aux préfixes, et la requête est un tuple de ces chaînes. Bien sûr, nous pouvons toujours convertir une chaîne générique générale pour répondre à ces critères: 1? 00? 1 ?? est (1,?, 0, 0,?, 1,?,?). Ce ne serait cependant pas efficace. L'autre hypothèse émise est que ces tuples sont associés à une "couleur", et l'interrogation doit renvoyer la couleur (pas seulement celle qui correspond). Cela rend le problème beaucoup plus difficile, car nous devons ordonner les tuples (ou bien il est ambigu lequel de (0,?) Et (?, 1) correspond à (0, 1)).

• Dans la communauté des algorithmes, j'ai trouvé beaucoup de résultats liés à la recherche de sous-chaînes qui correspondent à "ne se soucient pas". C'est un problème beaucoup plus difficile, et je ne peux vraiment pas utiliser l'une des techniques.

En conclusion

Merci pour toute aide!

Que diriez-vous d'utiliser un automate à états finis? Le langage est fini et donc régulier. Même après les transformations ci-dessous, ce sera toujours régulier. Donc, après les étapes habituelles pour convertir l'expression régulière en un automate à états finis déterministe, vous aurez un identificateur pour ce que vous voulez qui fonctionne en temps . Espérons que cette idée sera toujours réalisable s'il y a des bugs dans ce qui est proposé ci-dessous.O ( k $S$$O(k)$

Le problème est de savoir comment traiter avec l’opérateur générique:?. Un caractère générique dans une chaîne générique correspond à un 0 ou 1 dans une chaîne de test. Mais puisque nous essayons de reconnaître les chaînes génériques, un caractère générique dans une chaîne générique correspond à 0, 1 ou? dans une autre chaîne générique. Cet ensemble est toujours régulier, donc nous transformons chaque occurrence de? à l'expression régulière (0 | 1 |?) où la barre verticale est l'opérateur d'alternance habituel. Donc, si votre ensemble est {10 ?? 1, 0? 1? 0}, l'expression régulière résultante sera (10 (0 | 1 |?) (0 | 1 |?) 1 | 0 (0 | 1 | ?) 1 (0 | 1 |?) 0)$S$

En ce qui concerne l'ajout de chaînes à la machine, il existe des travaux récents sur la modification incrémentielle d'un automate à états finis. Voir cet article de Daciuk et al: "Incremental Construction of Minimal Acyclic Finite-State Automata".

est-ce que cela aide?