Binaire de longueur de course de l'encodage
J'ai un formulaire web pour le contenu de qui je voudrais générer une représentation courte en Base64. La forme, entre autres choses, contient une liste de 264 valeurs binaires, la plus grande partie de ce qui va être de 0 à tout moment unique. (Ils représentent des régions sur une carte géographique). Même en Base64, ce 264-nombre de bits génère un long, intimidant chaîne. Je veux mettre en œuvre run-length encoding, aussi efficacement que possible. Pouvez-vous m'aider? J'ai googlé binaire RLE, mais n'ai rien trouvé d'utilisation.
Ce que j'ai essayé jusqu'ici - l'exécution de RLE sur la chaîne binaire décimal à l'aide de comptages et les "A" comme séparateur dénotant un changement entre 0 et 1, puis en convertissant le résultat à partir de la base de 11 à base 64. Par exemple:
00000000001111111000000010000000000000000000000001111111110001111010101000000000000000000000000000000000000111111111110111000000000000111111100000001000000000000000000000000111111111000111101010100000000000000000000000000000000000011111111111011100
devient
10A5A5AA22A7A1A2AAAAAAA34A9AA1A10A5A5AA22A7A1A2AAAAAAA34A9AA1A
qui devient à son tour
CNnbr/FxkgbbOw0LNAKgk65P8SdvaTG+t74o
ou, dans la base de 62,
6imo7zq1pqr2mqglTHzXwJRAksm7fvHZHWQK
C'est mieux, mais je ne peux pas aider mais le doute si je fais quelque chose de mal, utilise le chiffre "Un" comme séparateur est la meilleure façon de le faire?
Et une autre mise à jour:
Grâce à @comingstorm, j'ai raccourci le comprimé de chaîne un peu plus.
ILHHASCAASBYwwccDASYgAEgWDI=
Comme je l'ai mentionné dans les commentaires, véritable cas d'utilisation entraînera généralement dans une même chaîne plus courte.
OriginalL'auteur avramov | 2011-09-29
Vous devez vous connecter pour publier un commentaire.
Puisque vous êtes le codage des bits, vous voudrez probablement utiliser un peu à base de RPM au lieu d'un octet. Dans ce contexte, vous devriez envisager de Elias gamma de codage (ou une variante de celui-ci) pour encoder efficacement vos tirages.
Une première approximation raisonnable pour votre format de codage pourrait être:
Puisque vous savez combien de bits sont compressés chaîne, vous n'avez pas besoin d'un code d'arrêt; vous pouvez simplement ajouter n'importe quel nécessaires binaire rembourrage arbitraire bits.
Remarque qu'il est toujours possible pour le long terme "compression" pour développer votre chaîne de bits; si vous êtes inquiète, vous pouvez ajouter une autre initiale de bits pour indiquer si vos données sont au format (compressé ou non, la limitation de votre compression des frais généraux à 1 bit.
OriginalL'auteur comingstorm
264 bits, qui sont à seulement 33 octets, et qui sont en base64 seulement 44 octets. Je pense que cette (très petite) quantité d'informations est à peine compressable. La représentation éparse nulvinge se réfère seulement les magasins de l'est non nul, les éléments et leurs valeurs (comme vous venez de l'0/1), c'est à dire dans votre cas il suffit de l'indice de la non zéro bits. Mais comme vous l'avez 264 possible bits - vous besoin de 9 bits pour l'index, ce qui signifie, dans le cas où vous avez plus de 29 de zéro, des entrées, vous devez déjà plus que l'original.
Peut-être que votre question est mal formulé, mais je ne vois pas comment 264 bits peut conduire à un environnement intimidant chaîne base64 (Comment pouvez-vous générer cela - peut-être que vous traduire pas les 264 bits, mais 264 ASCIIs caractères (avec la valeur
0et1) - qui pourrait expliquer votre longue chaîne de résultat?).vous avez raison, j'ai calculé avec la taille de mot. Mais l'état général est encore pour 44 octets: trop petit pour le compresser.
Eh bien, j'ai réussi à raser un peu de lettres, voir ci-dessus. Le nombre binaire ci-dessus est en fait assez peu de morceau de données d'entrée. Il serait plus courte en plus des cas réalistes. Je ne suis pas sûr au sujet de l'aide de la "Une".
OriginalL'auteur flolo
Une alternative que je pense que c'est plus ce que vous voulez est une matrice creuse:
http://en.wikipedia.org/wiki/Sparse_matrix
OriginalL'auteur nulvinge