Inclusion de sous séquences à l'intérieur de séquence (Bin)

Version imprimable

06/05/2005, 12h10
netcomput

Inclusion de sous séquences à l'intérieur de séquence (Bin)

Bonjour,

Je recherche un algo qui me permette de déterminer l'inclusion d'une séquence binaire dans une autre et optionnellement combien de fois.

Par exemple, soit la séquence Db : 1101100, et C la séquence de recherche : 110.

Je voudrais savoir si C est inclu dans DB.

J'ai déjà exploré les algo de détection de sous séquence à l'intérieur de séquence comme Knuth-Morris-Pratt ou les algo de calcul de distance entre termes. Mais tout ceci est trop lourd à mettre en place (dans mon cas). Je me suis donc tourner vers des solutions de relation entre les nombres comme PGCD ou relation BEZOUT. Ces solutions me satisfont en terme de complexité, mais n'offrent pas de solution probante (dans le cas où C est un nombre premier).

Afin de clarifier un peu, je vais ajouter d'autres exemples:
Soit DB 1101100 et C 110; C est inclus dans DB 2 fois
Soit DB 1101100 et C 1101; C est inclus dans DB 1 fois
Soit DB 1101100 et C 11000; C est inclus dans DB 0 fois

bien évidement, une solution serait de faire une comparaison binaire (ET) avec un décallage tant que C < DB. Mais j'aimerais trouver une solution un peu plus élégante.

Voilà j'espère avoir été suffisament clair dans mes explications, je vous souhaite une excellente journée.

Stéphane
06/05/2005, 13h52
Mac LAK

Sans vouloir être vexant, étant donné qu'à un moment où à un autre, tu vas devoir faire des AND binaires et des décalages, pourquoi rajouter une couche de traitement ?

A ma connaissance, aucun langage ne permet de manipuler/chercher des bits au sein d'un mot, en plus, pas même l'assembleur...

En considérant ta séquence comme un flux de bits (lus par mots d'une taille adéquate), il faut et il suffit de créer un masque binaire correspondant à ta sous-séquence, la "mapper" sur l'unité de lecture (le mot) et faire avancer le flux de bits en vérifiant à chaque étape la présence (ou l'absence) de la sous-séquence. C'est le plus rapide, mais ça limite la taille de sous-séquence à une entité manipulable directement (32 bits max en général).

Une autre solution, tout aussi fiable, est d'effectuer une simili-analyse lexicale en lisant la séquence bit à bit, en utilisant par exemple un arbre binaire pour "reconnaître" la sous-séquence. C'est moins rapide, mais ça permet d'outrepasser les limites mots/octets.

A mon avis, le problème va plus être dans l'implémentation, certains langages étant fort peu adaptés à ce genre de manipulations binaires.
07/05/2005, 00h07
netcomput

Dans la vision que j'ai, le parcours itératif me semble un peu "long" pour le traitement que je veux en faire. De plus, je pense qu'il serait possible de trouver une relation mathématique entre les termes étant données qu'ils possèdent une racine commune. Je pense que le traitement pourrait plus rapide.

Enfin c'est l'idée que j'ai sur la question.

Et ce n'est pas vexant, tant que la remarque est objective et constructive.

Merci pour cette participation.

Stéphane
07/05/2005, 01h56
Mac LAK

Citation:

Envoyé par netcomput

Dans la vision que j'ai, le parcours itératif me semble un peu "long" pour le traitement que je veux en faire.

As-tu essayé ? J'ai souvent remarqué que les algos les plus simples sur le papier ne sont pas forcément les plus rapides à l'exécution, et réciproquement...
Mais admettons : quelle est la longueur totale de la séquence (en bits), la longueur moyenne/maximale de la sous-séquence, et le nombre de sous-séquences différentes à rechercher ?
Parceque si ces nombres ne s'écrivent pas avec au moins 6 chiffres, ça ne sera pas franchement long à condition d'implémenter ton algo de manière un minimum optimisée...

Citation:

Envoyé par netcomput

De plus, je pense qu'il serait possible de trouver une relation mathématique entre les termes étant données qu'ils possèdent une racine commune. Je pense que le traitement pourrait plus rapide.

Que veux-tu dire par "racine commune" ? Un certain nombre de bits communs côté "gauche" du flux de bits ?
La seule chose que tu peux en déduire, c'est que tes nombres sont dans un certain intervalle, et/ou que tu peux "sauter" un certain nombre de bits lors des recherches, mais c'est tout... Et encore, ça n'est pas non plus tout à fait vrai (il faut que la taille de la séquence et de la sous-séquence soient compatibles avec des manipulations unitaires du processeur).

Citation:

Envoyé par netcomput

Enfin c'est l'idée que j'ai sur la question.
Et ce n'est pas vexant, tant que la remarque est objective et constructive.

Libre à toi. Mais comme je te l'ai dit, de toutes façons, ça finira obligatoirement avec des masques et des décalages binaires, même "planqués", alors... Il faudrait que les propriétés mathématiques soient réellement remarquables pour "accélérer" le traitement, et que le nombre de bits "sautés" par calcul mathématique soit suffisant pour compenser la perte de temps CPU occasionnée par ces calculs...

Tu peux en dire plus sur les données sources (cf. questions ci-dessus), et éventuellement dire quel est le but final recherché ? Il y a peut-être une meilleure manière d'y arriver (plus rapidement, j'entends) en regardant le problème sous un autre angle...