Hilfe bei Algorithmus

[BeRsErKeR]

Hallo Leute,

hier tummeln sich einige helle Köpfe. Ich brauche einen gewissen Lösungsalgorithmus für ein spezielles Problem und komm gerade einfach nicht drauf. Vielleicht kann mir da ja jemand weiter helfen.


Grundlage:

Es existieren 4 Variablen. Nennen wir sie mal a, b, c und d, die einen bestimmten Wertebereich haben und somit durch eine bestimmte Anzahl von Bits dargestellt werden. Der Wertebereich und die Bitlänge sind für a und c fest, bei b hängt beides vom Wert in a ab und bei d hängt beides vom Wert in c ab, allerdings nicht in dem Sinne, dass der Wert direkt den Wertebereich oder direkt die Bitlänge angibt, sondern wie folgt:

Die Variable a wird immer mit 2 Bits ausgedrückt. Der Wertebereich geht von 3 bis 6. Diese Zahl entspricht der Bitanzahl von b.
Die Variable c wird immer mit 3 Bits ausgedrückt. Der Wertebereich geht von 3 bis 10. Diese Zahl entspricht der Bitanzahl von d.

Die Wertebereiche von b sind:
- bei 3 Bits: 3 ~ 10
- bei 4 Bits: 11 ~ 26
- bei 5 Bits: 27 ~ 58
- bei 6 Bits: 59 ~ 122

Die Wertebereiche von d sind:
- bei 3 Bits: 0 ~ 7
- bei 4 Bits: 8 ~ 23
- bei 5 Bits: 24 ~ 55
- bei 6 Bits: 56 ~ 119
- bei 7 Bits: 120 ~ 247
- bei 8 Bits: 248 ~ 503
- bei 9 Bits: 504 ~ 1015
- bei 10 Bits: 1016 ~ 2039


Weiterhin gibt es 2 Input-Werte (vorzeichenlos und ganzzahlig), x und y. Dabei gilt immer y > x oder hier explizit y >= (x + 1).

x liegt innerhalb des maximalen Gesamt-Wertebereichs von b, sprich innerhalb von 3 bis 112. Je nach Wert von x wird für b der passende Wertebereich rausgesucht und davon abhängig die Bitanzahl für b und somit auch der Wert von a bestimmt.

Bei y ist dies ähnlich. Da y aber immer größer als x sein muss, wird zunächst (x + 1) von y abgezogen. Das Ergebnis nennen wir mal yy.

yy liegt nun innerhalb des maximalen Gesamt-Wertebereichs von d, sprich innerhalb von 0 bis 2029. Je nach Wert von yy wird für d der passende Wertebereich rausgesucht und davon abhängig die Bitanzahl für d und somit auch der Wert von c bestimmt.

Daraus ergibt sich eine Gesamtbitanzahl.


Ziel:

Das Ziel des Algorithmus, der nur x als Eingabe erhält und die Grundlagen kennt (ok, nur ich kenne sie :) ), ist es nun abhängig von x ein maximales y zu bestimmen, sodass gilt:

NötigeGesamtbitanzahl <= x * 4



Ich steh grad echt auf dem Schlauch. Schon allein die nötige Bitanzahl für b, abhängig von x zu berechnen, will mir nicht glücken. Habt ihr da Ideen?

[BeRsErKeR]

Mal ein einfaches Beispiel für x = 3:

1. Die maximal erlaubte Gesamtbitanzahl ist x * 4, also 12.

2. d ist 3 Bits groß, da 3 (Wert von x) im ersten Wertebereich liegt. Somit ist der Wert von a automatisch auch 3. Die Bitanzahl von a und b zusammen ist daher 5 (2 für a und 3 für b).

3. Es verbleiben also noch maximal 7 Bits für c und d. Da c immer 3 Bits benötigt, bleiben für d maximal 4 Bits übrig.

4. Mit 4 Bits hat d den Wertebereich 8 ~ 23.

5. Daraus folgt, dass der Maximalwert für yy gleich 23 ist und somit für y 27 (23 + x + 1) ist.


Mein erstes Problem ist bereits der erste Teil von Punkt 2. Die Wertebereiche entsprechen ja leider nicht direkt den Wertebereichen von bestimmten Bitanzahlen, da sie aufsummiert sind (für 3, wie in diesem Beispiel kann man einfach log2 nutzen, aber wie gehts weiter?). Mit ner Schleife würde es eventuell auch gehen, aber ich bin mir sicher, dass man das auch einfacher lösen kann. Der Algo ist recht zeitkritisch und sollte nicht zu lange dauern. Eine Sprungtabelle würde ich auch gern vermeiden wenn's geht oder meint ihr das wäre sinnvoll? Für d wäre die dann aber schon recht groß. Mehrere Bedingungen vielleicht? Ist irgendwie alles so unelegant. :(

Punkt 5 wäre dann so ähnlich, nur umgedreht. Da muss ich dann den Wertebereich bzw. die obere Grenze des Wertebereichs rauskriegen.

Ich sollte vielleicht noch dazu sagen (weil das oben falsch rüber kam), dass der Algo das Wissen über die Grundlagen nicht wirklich hat (sondern eher ich :D ). Es gibt also bislang nicht eine Liste mit Wertebereichen oder ähnliches im Code. Das soll durch diesen Algo irgendwie berechnet werden. Die Bitanzahl für a und c und deren Wertebereich würde ich natürlich noch fest vorgeben und auch, dass der 1. Wertebereich von b bei 3 beginnt und der von d bei 0 geb ich fest vor. Den Rest sollte der Algo im Idealfall ohne Zusatzwissen hinbekommen.

[BeRsErKeR]

Ich habe mal versucht Punkt 5 etwas mathematischer zu betrachten. Prinzipiell ist der obere Grenzwert des Wertebereichs ja nix anders als:
Sum(2^(n-3)) - 1, wobei mit Sum, die Summe von 3 bis n gemeint ist, mit 3 <= n <= 10. Lässt sich sowas irgendwie ohne Iteration/Rekursion berechnen? Vielleicht ein wenig Bitgeschubse?

Ok erste Lösung gefunden (Punkt 5):

yy = (1 << (n + 1)) - 9;

Hier ist n die Bitanzahl. Ich wusste doch, dass das einfacher geht. :)


Leider ist das ganze nicht so einfach für Punkt 2 umkehrbar. :(

Für diesen Fall liegen die Werte aber innerhalb von:

min = (1 << n) - 5;
max = (1 << (n + 1)) - 6;

Die Bitanzahl liegt demnach also innerhalb von:

n_min = (int)log2(x + 6) - 1
n_max = (int)log2(x + 5)

Ok mein Fehler. Die Bitanzahl ist immer n = (int)log2(x + 5). log2 lässt sich zum Glück sehr schnell berechnen, wenn als Bedingung die gaußsche Klammer gegeben ist (abrunden). Die Stelle des höchstwertigen 1-Bit sollte reichen. Läuft also auf eine Mini-Schleife (max 4 Iterationen) raus. Mal gucken, vielleicht bekomm ich das für diesen eingeschränkten Fall auch einfacher hin.

Hm naja die temporäre (eventuell auch permanente) Lösung ist erstmal diese für Punkt 2:

Code: Alles auswählen

int bits = 0;
x += 5; x >>= 3;
while (x >>= 1) ++bits;

[BeRsErKeR]

Sorry dass ich das Forum hier als Notizblock missbraucht habe. Ich wusste nicht, dass ich selbst drauf komme. Weiß nicht ob man das hier löschen sollte oder aufheben. Eventuell braucht es noch wer oder was Ähnliches?

Wen es interessiert um was es geht: Diese 4 Werte (a - d) nutze ich um die Match-Längen und Match-Offsets für eine wörterbuchbasierte Komprimierung zu kodieren. Da z.B. lange Matches größer kodiert werden können als kurze (um prozentual mehr Platz zu sparen), werden kurze Längen auch mit weniger Bits kodiert als lange. Wenn ein Match der Länge 100 (Bytes) nun 8 Bits für die Längenkodierung schluckt ist das nicht so schlimm, als wenn das ein Match mit der Länge 3 (Bytes) tut. Naja das ganze kann man vielleicht noch optimieren.

Da ein Offset niemals kleiner als die Länge sein kann, wird bei der Kodierung der Wert der Länge vom Offset-Wert abgezogen. Daher speichere ich die Längen vor den Offsets. Es wird auch noch 1 abgezogen (aus anderen Gründen, die nun zu weit führen würden).

Auf jeden Fall fiel mir auf, dass ein sehr kurzes Match zwar nicht viel Platz für die Längenkodierung frisst, ein großes Offset aber relativ viel Kodierungsplatz braucht (das Offset ist aber relativ unabhängig von der Match-Länge). Hätte man also ein Match mit der Länge 3 und ein großes Offset (z.B. 2000), dann spart man im Endeffekt maximal 3 Bytes (die Match-Länge), benötigt aber schon 18 Bits für die Längen- und Offset-Kodierung. Dazu kommt noch das Match-Literal. Im worst case vergrößert man also sogar die Anzahl der Bits. Hinzu kommt, dass die 3 Literale, die man als Match erfasst noch huffman-kodiert werden würden (das Match-Literal aber auch). Es bringt also bei großen Offsets nichts, kurze Matches zu speichern. In diesem Fall wäre es sinnvoller die Literale direkt zu belassen.

Als Faustregel habe ich mir überlegt, dass ein Match nur dann erfasst wird, wenn die Anzahl an Bits für die Kodierung maximal halb so groß ist, wie die Anzahl der unkodierten Bits. Um das zu entscheiden brauche ich den Algo.

[BeRsErKeR]

In C# gegossen sieht das nun so aus:

Code: Alles auswählen

public static int GetMaxMatchOffset(int length)
{
      int bits = (length << 2) - 6;
      length += 5; length >>= 3;
      while ((length >>= 1) != 0) --bits;
      return (1 << (bits + 1)) - 9;
}
public static bool CaptureMatch(int offset, int length)
{
      return offset <= GetMaxMatchOffset(length) + length + 1;
}

C++ ist identisch, aber da braucht man das != 0 nicht in der Schleifenbedingung. ;)

Anmerkung: Dass die Länge im Bereich 3 - 122 ist, wird vorher schon sichergestellt.

[TGGC]

Schreib die Zahlen einfach als int Arrays von a[], b[] usw. in eine Bineaerdatei und komprimiere das ganze mit einem dem bekannten Packalgorithmen...

[BeRsErKeR]

Entweder ich versteh dich nicht oder du verstehst mich nicht. Also es geht hier nicht drum, a oder b zu komprimieren. Das sind Werte, die bei einer Komprimierung verwendet werden. Ich weiß nicht wozu ich da Arrays von a oder b komprimiert speichern sollte. Oder beziehst du dich hier auf das Problem, dass diese Daten sonst zu viele Bits für kurze Matches mit hohen Offsets brauchen? Falls ja bin ich mir gerade nicht sicher, ob dann komprimierte int-Arrays wirklich kleiner werden und ich bräuchte dann auch wieder eine Referenzierung, wo ich dort die passenden Werte zu einem Match finde (ich dekomprimiere nicht zwangsläufig von Anfang an, es ist möglich später einzusteigen).

Mir ist allerdings bewusst, dass ich den obigen Algorithmus auch schneller über eine Sprungliste mit 120 Einträgen realisieren könnte (zu jedem x erhält man das passende y). Aber ob das so viel bringt?