Kompakte Codierung der Ganzzahl in Bitstring

8

Ich möchte positive ganze Zahlen kompakt xin Bits codieren , so dass ein zustandsloser Decoder, der den Maximalwert mvon jedem kennt, wieder in die ursprünglichen ganzen Zahlen decodieren kann x. Es soll möglich sein, die Verkettung von Codierungen eindeutig zu decodieren, wie dies bei der Huffman-Codierung der Fall ist.
[Die obige Einleitung motiviert den Rest, ist aber nicht Teil der formalen Definition]

Notation: Für jede nicht negative ganze Zahl isei n(i)die Anzahl der Bits, die zur Darstellung iin Binärzahlen erforderlich sind . das ist die kleinste nicht negative ganze Zahl, kso dassi>>k == 0

  i :   0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  ..
n(i):   0   1   2   2   3   3   3   3   4   4   4   4   4   4   4   4   5   5   5   ..

Ich möchte eine Funktion, F(x,m)die für 0<xund x<=mmit der Ausgabe einer Zeichenfolge von ' 0' oder ' 1' definiert ist und folgende Eigenschaften aufweist:

  1. F(x,m)hat eine Länge von weniger als 2*n(x)oder 2*n(m)-1, je nachdem, welcher Wert kleiner ist.
  2. Wenn x<ydann:
    • F(x,m)ist nicht länger als F(y,m);
    • F(x,m)und F(y,m)unterscheiden sich an einer Position über die Länge von F(x,m);
    • Es gibt ein 0In F(x,m)an der ersten solchen Position.
  3. Wenn für bestimmte mEigenschaften 1 und 2 höchstens nicht F(x,m)für alle positiven Eigenschaften eindeutig definiert sind , lehnen wir jede Codierung ab, die eine längere als eine ansonsten akzeptable Codierung ergibt , für die kleinste, für die die Länge nicht übereinstimmt.xmF(x,m)x

Hinweis: Bei der oben implizit 0<x, 0<y, 0<m, x<=m, und y<=m, so dass F(x,m)und F(y,m)definiert.

Es ist das kürzeste Programm darum gebeten , dass, da jeder xund die mErfüllung die oben genannten Einschränkungen und bis zu 9 Dezimalstellen, gibt eine in F(x,m)Übereinstimmung mit den oben genannten Regeln. Das folgende C-Framework (oder sein Äquivalent in anderen Sprachen) wird nicht gezählt:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define C(c) putchar((c)?'1':'0') // output '0' or '1'
#define S(s) fputs((s),stdout)    // output a string
typedef unsigned long t;          // at least 32 bits
void F(t x,t m);                  // prototype for F
int main(int argc,char *argv[]){
 if(argc==3)F((t)atol(argv[1]),(t)atol(argv[2]));
 return 0;}
void F(t x,t m) {   // counting starts on next line
}                   // counting ends before this line

Kommentar: Eigenschaft 1 begrenzt die codierte Länge aggressiv. Eigenschaft 2 formalisiert, dass eine eindeutige Decodierung möglich ist, und kanonisiert die Codierung; Ich behaupte (ohne Beweis), dass dies ausreicht, um die Ausgabe von Fwann m+1eine Zweierpotenz eindeutig zu definieren, und dass Eigenschaft 3 ausreicht, um Ffür andere eindeutig zu definieren m.

Hier ist eine Teiltabelle (handgemacht; die erste veröffentlichte Version war voller Fehler, sorry):

  x     :   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
F(x,1)  : empty
F(x,2)  :   0       1
F(x,3)  :   0       10      11
F(x,4)  :   0       10      110     111
F(x,5)  :   0       10      110     1110    1111
F(x,6)  :   0       100     101     110     1110    1111
F(x,7)  :   0       100     101     1100    1101    1110    1111
F(x,8)  :   0       100     101     110     11100   11101   11110   11111

F(x,15) :   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111
code-golf fgrieu
quelle
"Kompakte Codierung?" Wie ist dies kompakter als die kanonische Basis-2-Darstellung der ganzen Zahl? :)
Martin Ender
@ m.buettner: Das Problem mit der kanonischen Darstellung in Basis 2 ist, dass 3, dann 7, 7, dann 3, 1, dann 15 und eine Reihe anderer Dinge, die alle als codieren 11111, die Dekodierung unmöglich machen. Mit der vorgeschlagenen Codierung kann die Verkettung mehrerer Ausgänge eindeutig decodiert werden (auch wenn sich das Maximum mdynamisch ändert). Ich habe versucht, das zu klären.
Fgrieu
1
Ich bin mit Ihrem Tisch nicht einverstanden. Für F (x, 5) haben Sie 0,100,101,110,111. Die Codierung 0,10,110,1110,1111 erfüllt jedoch (1) und (2), und da 10 kürzer als 100 ist, wird Ihre Codierung für F (x, 5) abgelehnt.
Nneonneo
1
Oh, aber für F (x, 8) ist dein Tisch immer noch falsch. 0,100,101,110,11100,11101,11110,11111 ist besser für F (4,8) (110 vs 1100).
Nneonneo
1
Nee. Das ist illegal, weil F (7,8) weniger als 6 Stellen haben muss.
Nneonneo

Antworten:

1

Python 3, 163 Bytes

n=int.bit_length
R=range
def F(x,m,c=0):
 for i in R(x):L=2*n(m)-2;D=1<<L;r=n(D-c-sum(D>>min(2*n(x+1)-1,L)for x in R(i+1,m)))-1;v=c;c+=1<<r
 return bin(v)[2:L+2-r]

Ignoriere den c=0Parameter, das ist ein Golftrick.

Dies wählt gierig die kürzestmögliche Darstellung für jede Zahl, unter der Bedingung, dass die verbleibenden Zahlen noch darstellbar sind. Daher erfüllt es konstruktionsbedingt genau die gewünschten Eigenschaften. Es ist tatsächlich nicht so schwer, diesen Code zu ändern, um einen anderen Satz von Codierungsregeln zu unterstützen.

Hier sind zum Beispiel die Ausgaben bis zu m=15:

m\x |   1       2       3       4       5       6       7       8       9       10      11      12      13      14      15
----+----------------------------------------------------------------------------------------------------------------------------
1   |   
2   |   0       1
3   |   0       10      11
4   |   0       10      110     111
5   |   0       10      110     1110    1111
6   |   0       100     101     110     1110    1111
7   |   0       100     101     1100    1101    1110    1111
8   |   0       100     101     110     11100   11101   11110   11111
9   |   0       100     101     110     11100   11101   11110   111110  111111
10  |   0       100     101     1100    1101    11100   11101   11110   111110  111111
11  |   0       100     101     1100    1101    11100   11101   111100  111101  111110  111111
12  |   0       100     101     1100    11010   11011   11100   11101   111100  111101  111110  111111
13  |   0       100     101     1100    11010   11011   11100   111010  111011  111100  111101  111110  111111
14  |   0       100     101     11000   11001   11010   11011   11100   111010  111011  111100  111101  111110  111111
15  |   0       100     101     11000   11001   11010   11011   111000  111001  111010  111011  111100  111101  111110  111111
nneonneo
quelle
2

Python, 171

def F(x,m):
 a=0;b=[9]
 while len(b)<m:
    if 4**len(bin(len(b)))*2>64*a<4**len(bin(m)):
     if(a&a+1)**a:b+=[a];a+=1
     else:a*=2
    else:a=b.pop()*2
 return bin((b+[a])[x])[2:]

Beachten Sie, dass Zeilen, die mit 4 Leerzeichen zu beginnen scheinen, tatsächlich mit einer Registerkarte beginnen.

Testen mit dem Bitpwner-Testskript:

         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)   0       
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      110      11100    11101    11110    11111   
F(x,9)   0        100      101      110      11100    11101    11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      1100     11010    11011    11100    11101    111100   111101   111110   111111  
F(x,13)  0        100      101      1100     11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111

Erläuterung:

Dies alles basiert auf der Beobachtung, dass wir zwischen zwei aufeinanderfolgenden Elementen des Codes, F (x, m) und F (x + 1, m), immer eins zur Binärzahl addieren und dann einige Male mit zwei multiplizieren. Wenn diese Schritte ausgeführt werden, handelt es sich um einen gültigen Code. Der Rest testet einfach, um sicherzustellen, dass es kurz genug ist.

Golf: 175 -> 171: geändert 2 ** (2 * ... auf 4 **)

isaacg
quelle
Nit: F (1,1) sollte die leere Zeichenfolge sein.
Nneonneo
1

Python - 370

Erstellt einen Huffman-Baum, gleicht ihn gemäß den Regeln aus und geht dann durch den Baum, um die endgültigen Werte zu erhalten. 

def w(n,m,c,p=""):
    try:[w(n[y],m,c,p+`y`)for y in 1,0]
    except:c[n[0]]=p
d=lambda x:len(x)>1and 1+d(x[1])
v=lambda x,y:v(x[1],y-1)if y else x
def F(x,m):
    r=[m];i=j=0
    for y in range(1,m):r=[[m-y],r]
    while d(r)>len(bin(m))*2-6-(m==8):g=v(r,i);g[1],g[1][0]=g[1][1],[g[1][0],g[1][1][0]];i,j=[[i+1+(d(g)%2<1&(1<i<5)&(m%7<1)),j],[j+1]*2][d(g)<5]
    c={};w(r,m,c);return c[x]

Eine prägnantere Lösung, die auf dem entstehenden Muster basiert, finden Sie in der Antwort von isaacg.
Es ist ein gutes Beispiel dafür, wie ein völlig anderer Ansatz das Problem lösen kann.

Prüfung:

chars = 8
maxM = 15
print " "*chars,
for m in range(1,maxM+1):
    p = `m`
    print p+" "*(chars-len(p)),
print
for m in range(1,maxM+1):
    p = "F(x,"+`m`+")"
    print p+" "*(chars-len(p)),
    for x in range(1,maxM+1):
        try:
            q = `F(x,m)`[1:-1]
            print q+" "*(chars-len(q)),
        except:
            print
            break

Ergebnisse:

         1        2        3        4        5        6        7        8        9        10       11       12       13       14       15      
F(x,1)           
F(x,2)   0        1       
F(x,3)   0        10       11      
F(x,4)   0        10       110      111     
F(x,5)   0        10       110      1110     1111    
F(x,6)   0        100      101      110      1110     1111    
F(x,7)   0        100      101      1100     1101     1110     1111    
F(x,8)   0        100      101      1100     1101     1110     11110    11111   
F(x,9)   0        100      101      1100     1101     1110     11110    111110   111111  
F(x,10)  0        100      101      1100     1101     11100    11101    11110    111110   111111  
F(x,11)  0        100      101      1100     1101     11100    11101    111100   111101   111110   111111  
F(x,12)  0        100      101      11000    11001    11010    11011    11100    11101    11110    111110   111111  
F(x,13)  0        100      101      11000    11001    11010    11011    11100    11101    111100   111101   111110   111111  
F(x,14)  0        100      101      11000    11001    11010    11011    11100    111010   111011   111100   111101   111110   111111  
F(x,15)  0        100      101      11000    11001    11010    11011    111000   111001   111010   111011   111100   111101   111110   111111
Vektorisiert
quelle
Wie von nneonneo gezeigt, ist F(7,8)of 111110falsch, denn das hat die Länge 6 und "weniger als 2*n(x)" impliziert weniger als 6.
fgrieu