Quelle est la meilleure façon de rechercher des données binaires pour des chaînes de bits de longueur variable?

Question

Quelqu'un peut-il me dire quel est le meilleur moyen de décoder des données binaires avec des chaînes de bits de longueur variable en java?

Par exemple:

  

Les données binaires sont 10101000 11100010 01100001 01010111 01110001 01010110

     

Je pourrais avoir besoin de trouver le premier match de l'un des numéros suivants: 01, 100, 110, 1110, 1010 ...

     

Dans ce cas, la correspondance serait 1010. Je dois ensuite faire de même pour le reste des données binaires. Les chaînes de bits peuvent comporter jusqu'à 16 bits et dépasser les limites des octets.

En gros, j'essaie de décoder les jpeg en utilisant les chaînes de bits que j'ai créées à partir des tables de Huffman dans les en-têtes. Je peux le faire, mais c’est très désordonné, je commence par tout transformer, y compris les données binaires, en Stringbuffers et je sais que ce n’est pas la bonne façon.

Avant de tout charger dans des tampons de chaîne, j’avais essayé d’utiliser uniquement des nombres en binaire, mais bien entendu, je ne peux pas ignorer les 0 premiers dans un code comme 00011. Je suis sûr qu’il doit exister une méthode intelligente en utilisant des opérateurs tiens à faire cela, mais je regarde les pages expliquant les masques de bits, les décalages vers la gauche, etc. et je n’ai toujours pas la moindre idée!

Merci beaucoup pour toute aide!

EDIT:

Merci pour toutes les suggestions. J'ai opté pour l'approche de l'arbre binaire, car cela semble être la méthode standard avec Huffman. Cela a du sens, car les codes de Huffman sont créés à l’aide d’arbres. J'examinerai également la possibilité de stocker les données binaires nécessaires à la recherche dans un grand entier. Je ne sais pas comment marquer plusieurs réponses comme correctes, mais merci quand même.

Answer 1

Puisque vous décodez des données codées Huffman, vous devez créer un arbre binaire dans lequel les feuilles contiennent la chaîne de bits décodée sous forme de données et les bits de chaque code Huffman constituent le chemin d'accès aux données correspondantes. Les bits du code de Huffman sont accessibles avec des opérations de décalage de bits et de masque de bits. Lorsque vous atteignez une feuille, vous sortez les données sur cette feuille et revenez à la racine de l'arbre. C'est très rapide et efficace.

Answer 2

Vous pouvez utiliser une machine à états consommant des zéros et des uns. La machine à états aurait des états finaux pour tous les motifs que vous souhaitez détecter. Chaque fois qu'il entre dans l'un des états finaux, il vous envoie un message avec le motif correspondant et revient à l'état initial.

Enfin, vous n’auriez qu’une seule machine à états sous la forme d’un DAG contenant tous vos modèles.

Pour l'implémenter, utilisez le modèle d'état ( http://en.wikipedia.org/wiki/State_pattern ) ou toute autre implémentation d'une machine à états.

Answer 3

Vous pouvez essayer de le ranger dans un BigInteger , puis en utilisant les méthodes de décalage et de test. Puis utilisez loop pour marcher et accepter chaque sous-motif.

Si le code de Huffman est dans une arborescence, 1 == noeud de droite, 0 == noeud de gauche.

for( int i =numbitsTotal; i > 0; --i )
{
   int bit = bigInt.testBit( i );
   if( bit == 1 )
   {
       // take right node -- if null accept code, apply from top
   }
   else
   {
      // take left node -- if null accept code, apply from top
   }
}

Answer 4

Je suggérerais un trie . Il est explicitement conçu pour la recherche par préfixe. Dans votre cas, ce serait un trie binaire.

Answer 5

Vous pouvez utiliser un java.util.BitSet pour stocker vos données binaires, puis vous pouvez implémenter des fonctions de recherche pour trouver la position d'un BitSet plus petit dans le grand ...