Integer (1 Byte) Datentransformation DCT (FFT) gesucht

[Möbius]

Guten Tag Forenteilnehmer

Dies ist mein erster Beitrag in diesem Forum überhaupt und ich begrüsse Euch herzlich. Ehrlich gesagt mein erster Forenversuch überhaupt.https://www.delphipraxis.net/images/.../icon_cool.gif
Das Forum ist gut und hat mir schon viel geholfen. Hoffentlich kann ich anderen auch mal helfen.

Das Problem. Ich bin am Verzweifeln. Schon drei (unbrauchbare) Bücher gewälzt aber noch keine Lösung. Immer ist die Rede von Butterfly-Diagrammen (also Zerteilungen der Daten) und irgendwelchen "Lifting up Faktoren" etc.

Ich bräuchte für ein Projekt Delphi/Pascal Quellcode der mir für eine beliebige Datenmenge (kann auch auf Potenzen von 2, verfüllt mit restlichen Nullen sein) eine Integer Cosinus Transformation durchführt.
Auch eine Quelle mit lesbarem/übersetzbaren Pseudocode oder so wäre hilfreich.
Nach tagelanger Suche im Netz stosse ich immer nur auf reelwertige Funktionen (DCT) bzw. komplexwertige Funktionen (FFT) mit Floating Point Zahlen. Habe ich selber schon implementiert, runden nach der Operation führt aber bei der Rücktransformation zu Fehlern.

Dies wie schon im Titel vermerkt für Zeichengrössen eines Bytes, jedoch nicht für irgendwelche 8x8 oder 16x16 oder sonstige Matrizen sondern, mehr oder weniger, beliebige eingegebene Datengrössen.

Also der Wunsch ist eigentlich eine Datenmenge vom Zeitbereich in den Frequenzbereich zu transformieren. Dies auf Integer (Byte) Basis welche auch ohne Fehler Rücktransformierbar ist.

Eine passende Integer FFT ist auch okay, sofern im Übetragungskanal nur der reelwertige Anteil übergeben werden muss und die Rücktransformation auch mit einem (imaginären) Phasenanteil von Null klappt. Daher denke ich aber eine Cosinus Transformation eignet sich besser da kein komplewertiger Anteil.

Kennt jemand von Euch so eine Transformation und Rücktransformation oder hat sie schon selber implementiert?

Hoffe hab mich verständlich ausgedrückt
Bin für jede Hilfe dankbar

Reto

[TiGü]

Sowas?

https://github.com/jcodec/jcodec/blo...ct/IntDCT.java
https://javadoc.io/static/org.jcodec...ct/IntDCT.html

https://github.com/libjpeg-turbo/lib...ain/jfdctint.c
https://github.com/libjpeg-turbo/lib...ain/jidctint.c

[Möbius]

Hi TiGü

Ganz herzlichen Dank.
Nach sowas habe ich tagelang gesucht.
Reto

[TiGü]

Darf ich fragen, wie und womit du gesucht hast?

[Möbius]

Ja sicher gerne
Natürlich mit Google.
Dabei bin ich auf einige Bücher gestossen welche ich z.T. bestellt habe.
-> Besslich diskrete Orthogonaltransformationen.
-> K. R. Rao Fast Fourier Transform: Algorithms and Applications.

Das Problem bei den Büchern ist, dass sie sehr viel mathematischen Background enthalten aber wenn es um Integer Implementationen geht dann wird nur kurz von irgendeinem "Leverage Faktor" gesprochen. Zudem ist in den sog. "Butterfly" Diagrammen nicht ganz klar wie eine beliebige Datenmenge bearbeitet werden kann. Also auf eine Konstruktion eines Algorhitmuses in einer beliebigen Sprache gehen die Bücher nicht ein. Schon Pseudocode würde helfen.

Weitere Suche im Internet hat ein bisschen Code z.B. bei Rosetta Code zu Tage gefördert. Jedoch nur teilweise brauchbar. Auch in den Büchern steht, dass die DCT über den Umweg einer DFT gemacht werden kann. Aber eben auch wenn Integer ist diese komplexwertig und es ist mir nicht gelungen ohne den Imaginärteil eine Rücktransformation zu machen. Ist ja auch irgendwie klar. Der Realteil einer DFT stellt das Frequenzspektrum dar während der Imaginärteil die Phasenlagen des Signals darstellt.

Tja Deine Hilfestellung hat Hoffnungen geweckt, aber die Codes übersetzt in Delphi brauchen ca. 10 Minuten für 32 KiloByte :-(.
Es ist eben auch nur eine DCT und keine FCT.
Die Bücher sagen aber eine solche soll möglich sein.

Was ich wirklich brauche ist ein Algorithmus der mir ein Signal (Daten beliebiger Grösse N -> also wenn möglich ohne Nullen die auf 2^n verfüllen) vom Zeitbereich in den Frequenzbereich transformiert und wieder zurück. Dies aber nur reelwertig und auf Integer (Bytes) basierend.

Ach ja und mit den Codes aus dem Netz stimmt etwas nicht. Weil sie scheinen kein erwartetes Spektrum darzustellen.

Um was geht es überhaupt:
Ich arbeite an einem Daten-Kompressionsalgorithmus. Der ist schon sehr weit fortgeschritten und sieht derzeit mit den Daten aus dem ->Calgary Corpus bzw. dem ->Canterbury Corpus oder auch dem ->Large Corpus sehr gut aus.
Jedoch wie üblich mit relativ unstrukturierten Daten mit hoher Entropie (also auf Deutsch gesagt eine Sauordnung), da schneidet er permanent mit rund 100% (und nur sehr wenig mehr bei moderat grossen Files) ab! Wohlgemerkt gemessen an RAD-Daten (randomisierten Files).
Die Sachlage ist klar, wenn ich das nur um ein paar % runterdrücken kann, dann habe ich einen Kompressor der sich selber komprimieren kann! Die Konsequenzen bei einer iterativen Anwendung dürften klar sein.
Somit dürfte schon klar sein, dass mir eine FFT sehr wenig nützt. Ob nun integer oder nicht. Der Frequenzanteil (reel) (bei meiner eigenen Float64 basierten FFT) sieht wir erwartet gut aus bei solchen Daten. Ich bin ja von Haus aus Elektroniker und Toningenieur (ist schon eine Weile her ;-)). Aber eben solche RAD-Daten bezeichnet man im Audio-Jargon als statistisches weisses Rauschen. Und dieses Zeichnet sich aus durch sehr kleine Schwankungen der Amplituden (infinitesimal wohl gar keine) im Spektrum.

Und genau diese kleinen Schwankungen könnten dazu führen, dass mein Algorithmus die Daten besser verarbeiten kann.

Wie gesagt. Ist reine Theorie und Forschungsarbeit.

Ach ja, die DCT aus dem Netz von Deinem Tipp rechnet nicht nur ewig (eine FCT wäre natürlich besser), Sie zeigt auch ein Spektrum von sehr stark schwankenden Amplituden der Frequenanteile - Da kann etwas nicht stimmen. Die müssten eigentlich näher beisamen liegen.
Ganz klar ist, dass am Anfang des Spektrums sehr hohe Amplituden auftreten wenn ich die Daten als rein positive Werte (Bytes) einspeise. Dieser DC-Anteil schlägt hier natürlich zu Buche. Wenn ich die Daten als Int8 einspeise sieht das schon besser aus, die realtiv hohen Werte am Anfang der Sequenz dürften Verzerrungen sein, die sich ergeben weil ich kein kontinuierliches Signal einspeise. Damit liesse sich leben wenn die Rücktransformation diese Verzerrungen richtig heraus rechnet.

So suche ich also weiter...

Hoffe Dir aber den Werdegang meiner Idee und Suche etwas näher gebracht zu haben.

[TiGü]

Aber es ist doch auch möglich, dass du dich beim Übersetzen vertan hast?!

Welches Codebeispiel hast du denn nach Delphi übersetzt?
Das Java- oder das C-Beispiel?!

[Möbius]

Ja könnte natürlich auch sein.

Hier die Übersetzungen (non integer):

Delphi-Quellcode:

class procedure TCompressOSCT.DCT(const Input: TFloat64Array; out Output: TFloat64Array);  //1 double[] DCT (double[] g) { // forward DCT on signal g
var
  M, mCnt, uCnt: Int64;
  s, cm, sums, Phi: Float64;
begin
  M := Length(Input); //2 int M = g.length;
  s := sqrt(2.0 / M); //3 double s = Math.sqrt(2.0 / M); // common scale factor
  SetLength(Output, M); //4 double[] G = new double[M];
  for mCnt := 0 to High(Input) do //5 for (int m = 0; m < M; m++) {
  begin
    cm := 1; // 6 double cm = 1.0;
    if mCnt = 0 then // 7 if (m == 0)
    begin
      cm := 1 / sqrt(2); // 8 cm = 1.0 / Math.sqrt(2);
    end;
    sums := 0; // 9 double sum = 0;
    for uCnt := 0 to High(Input) do // 10 for (int u = 0; u < M; u++) {
    begin
      Phi := Pi * mCnt * (2 * uCnt + 1) / (2 * M); //11 double Phi = Math.PI * m * (2 * u + 1) / (2 * M);
      sums := sums + (Input[uCnt] * cm * cos(Phi)); // 12 sum += g[u] * cm * Math.cos(Phi); }
    end;
    Output[mCnt] := s * sums; // 14 G[m] = s * sum; }
  end;
end;

class procedure TCompressOSCT.InvDCT(const Input: TFloat64Array; out Output: TFloat64Array);  // 20 double[] iDCT (double[] G) { // inverse DCT on spectrum G
var
  M, mCnt, uCnt: Int64;
  s, cm, sums, Phi: Float64;
begin
  M := Length(Input); // 21 int M = G.length;
  s := sqrt(2.0 / M); // 22 double s = Math.sqrt(2.0 / M); //common scale factor
  SetLength(Output, M); // 23 double[] g = new double[M];
  for uCnt := 0 to High(Input) do // 24 for (int u = 0; u < M; u++) {
  begin
    sums := 0; // 25 double sum = 0;
    for mCnt := 0 to High(Input) do //26 for (int m = 0; m < M; m++) {
    begin
      cm := 1; // 27 double cm = 1.0;
      if mCnt = 0 then // 28 if (m == 0)
      begin
        cm := 1 / sqrt(2); // 29 cm = 1.0 / Math.sqrt(2);
      end;
      Phi := Pi * mCnt * (2 * uCnt + 1) / (2 * M); // 30 double Phi = Math.PI * m * (2 * u + 1) / (2 * M);
      sums := sums + (Input[mCnt] * cm * cos(Phi)); // 31 sum += G[m] * cm * Math.cos(Phi); 32 }
    end;
    Output[uCnt] := s * sums; // 33 g[u] = s * sum; 34 }
  end;
end;

[freimatz]

"0 to High(Input)" - müsste das nicht -1 sein? Passt vermutlich. "Low(Input) to High(Input)" wäre schöner.

[TiGü]

Warum zwei geschachtelte Schleifen?
In der Wikipediadefintion von DCT-I bis DCT-IV sehe ich immer nur ein Summenzeichen?

[Blup]

Ich habe mal versucht zu optimieren.
Unnötige doppelte Operationen mit Hilfe von Zwischenvariablen aus Schleifen ziehen.
Multiplikation durch Addition ersetzen, wenn das möglich ist.
Ob das eine merkliche Verbesserung der Laufzeit bringt, müsste man in der Praxis testen.

Delphi-Quellcode:

class procedure TCompressOSCT.DCT(const Input: TFloat64Array; out Output: TFloat64Array);
var
  M, mCnt, uCnt: Int64;
  s, sums, Phi, Pi2M, Pi2MmCnt: Float64;
begin
  M := Length(Input);
  SetLength(Output, M);
  if M > 0 then
  begin
    s := sqrt(2.0 / M);
    Pi2M := Pi / (2 * M);
    Pi2MmCnt := 0;
    for mCnt := 0 to M - 1 do
    begin
      sums := 0;
      Phi  := Pi2MmCnt;
      for uCnt := 0 to M - 1 do
      begin
        sums := sums + (Input[uCnt] * cos(Phi));
        Phi := Phi + Pi2MmCnt + Pi2MmCnt;
      end;
      Output[mCnt] := s * sums;
      Pi2MmCnt := Pi2MmCnt + Pi2M;
    end;
    Output[0] := Output[0] / sqrt(2);
  end;
end;

Warum wird eigentlich ausgerechnet nur Output[0] durch sqrt(2) dividiert?

[Michael II]

Zitat:

Zitat von Möbius (Beitrag 1496503)

Jedoch wie üblich mit relativ unstrukturierten Daten mit hoher Entropie (also auf Deutsch gesagt eine Sauordnung), da schneidet er permanent mit rund 100% (und nur sehr wenig mehr bei moderat grossen Files) ab! Wohlgemerkt gemessen an RAD-Daten (randomisierten Files).
Die Sachlage ist klar, wenn ich das nur um ein paar % runterdrücken kann, dann habe ich einen Kompressor der sich selber komprimieren kann!

Mir ist diese "Sachlage" alles andere als klar. Wenn du mal kurz Zeit hast, dann wäre es cool, wenn du ein paar Zeilen mehr dazu schreiben würdest.

Das liest sich für mich als würdest du völlig zufällige Bitfolgen komprimieren wollen. Und das klappt natürlich nicht. Wenn du die Menge D aller möglichen Wörter bis Länge n Bit deinem Kompressor füttern willst, dann hast du in D 2^n Wörter der Länge n, 2^n-1 der Länge n-1,... 2^1 Wörter der Länge 1.
Deine Kompression k muss zwei voneinander verschiedenen Wörtern w1 und w2 aus D voneinander verschiedene Werte k(w1) und k(w2) zuordnen (k injektiv); sonst könntest du nicht dekomprimieren. Wenn W die Menge aller Werte k(wi), für alle wi aus D ist, dann gilt also: W und D haben gleich viele Elemente.
Es gibt natürlich zig verschiedene solche Funktionen k; eine davon (die einfachste) ist k = id, also k(w) = w.
Oder anders geschrieben: Bei völlig zufälligen Zeichenfolgen rechnet dein Kompressor am besten gar nichts und gibt w als Wert aus.

Wahrscheinlich denkst du in eine andere Richtung (?)...

[Möbius]

@Freimatz
Nein das ist schon richtig so, Dynamische Arrays sind bei Delphi immer 0 basiert. D.h. Low(Array) und 0 sind äquivalent.

Vielen Dank für's optimieren, aber das Problem sind effekvtiv immer noch die 2 geschachtelten Schleifen. Ich rauch es aber sowieso Byte(Integer).

Eben wegen dieser "Sachlage". Ich arbeite schon einige Zeit an einem völlig neuartigen Kompressor und der hat mittlerweile echt gute Resultate. Bei Calgary und Canterbury Corpus kann er sicher vorne mitreden.
Aber es fehlt halt noch das i-Tüpfelchen.
Das Argument, dass man eine Nachricht N mit n Buchstaben nicht kürzer als N codieren kann, ohne dass man "Opfer" auf der anderen längeren Seite bringen muss, will mir nicht so recht in den Kopf.
Z.B. kann man ein Kartenspiel so lange perfekt mischen bis es sortiert ist. Dann braucht man bloss die Zahl der Mischvorgänge zu übermitteln um dies wieder rückgängig zu machen. Zauberkünstler nutzen diesen Trick übrigens für manche Kartenkunststücke. Man muss freilich die Kunst beherrschen ein Karttendeck wiederholt exakt in der mitte zu teilen und perfekt Karte links auf Karte rechts jeweils mischen können. Ein Deck mit 52 Karten ist verblüffender Weise nach 5 Durchgängen wieder sortiert.
Okay in der Praxis sind hier normalerweise viele Permutationen nötig.

Die Idee letztlich mit der FCT(Fast Cosinus Trandorm) jedenfalls könnte sich imho für völlig zufällige Daten eignen. Da rein zufällige Daten im Prinzip dem weissen Rauschen gleichkommen, müsste doch eigentlich eine Tranformation vom Zeitbereich in den Frequenzbereich ein Spektrum mit sehr kleinen Differenzen in den Amplituden der Spektralanteile liefern.
Das könnte schon ein interessanter input sein für irgended einen Codierer.

[Möbius]

Guten Tag zusammen

Also ich hab mal ein bisschen die Bücher gewälzt und so. Bin hier auf eine alternative orthogonale Transformation gestossen.
Die Walsh-Hadamard Transformation. Die funktioniert bestens mit Integer Werten.

Hier der Code falls das ma jemand brauchen könnte:

Delphi-Quellcode:

class procedure AClass.WalshHadamardTransform(var Data: TIDatas);
var
  i, j, n, m, x, y: UInt64;
  Output: TIDatas;
begin
  SetLength(Output, Length(Data));
  Output := Copy(Data, 0, Length(Data));
  n := Length(Data);
  m := 1;
  while 2 * m <= n do
  begin
    i := 0;
    while i < n do
    begin
      for j := i to i + m - 1 do
      begin
        x := Output[j];
        y := Output[j + m];
        Output[j] := y;
        Output[j + m] := x + y;
      end;
      i := i + 2 * m;
    end;
    m := m * 2;
  end;
  Data := Copy(Output, 0, Length(Output));
end;

class procedure AClass.InvWalshHadamardTransform(var Data: TIDatas);
var
  i, j, n, m, x, y: UInt64;
  Output: TIDatas;
begin
  SetLength(Output, Length(Data));
  Output := Copy(Data, 0, Length(Data));
  n := Length(Data);
  m := 1;
  while 2 * m <= n do
  begin
    i := 0;
    while i < n do
    begin
      for j := i to i + m - 1 do
      begin
        x := Output[j];
        y := Output[j + m];
        Output[j] := -x + y;
        Output[j + m] := x;
      end;
      i := i + 2 * m;
    end;
    m := m * 2;
  end;
  Data := Copy(Output, 0, Length(Output));
end;

[Sinspin]

Zitat:

Zitat von Möbius (Beitrag 1496703)

Hier der Code falls das ma jemand brauchen könnte:

Ausgezeichnet. Danke!

Ich habe mich vor einigen Jahren auch damit befasst und bin dann auf Gleitkomma ausgewichen mit anschließender Scalierung um wieder Integer zu bekommen.
Allerdings gab es immer eine unschöne (hörbare) Abweichung im wieder hergestellten Audiosignal. Mal sehen wie es mit der Methode funktioniert.

[Möbius]

Schön wenn es jemandem hilft.
Übrigens mein Code funktioniert auch in Place. D.h. die Copy kann man sich schenken. Hab's nur zum experimentieren drin gelassen.
Diese TIdatas ist übrigens ein Integer Array.
Wenn Du dies auf Audio anwendest dürften die Werte zwischendrin relativ hoch werden.
Ich hab das auch beobachtet.

[venice2]

Zitat:

Diese TIdatas ist übrigens ein Integer Array.

Schön zu hören.
Vielleicht solltest du diese Definition zu deinem Schnipsel hinzufügen ohne wären diese Sinnlos wenn man nicht weis wofür TIdatas steht.

[freimatz]

BTW: Welchen Sinn hat das Copy? Wird da nicht eh alles kopiert? Würde dann nicht Output := Data; reichen? Und wieso überhaupt Kopieren und nicht gleich auf Data arbeiten?

[Michael II]

Zitat:

Zitat von freimatz (Beitrag 1496730)

BTW: Welchen Sinn hat das Copy? Wird da nicht eh alles kopiert? Würde dann nicht Output := Data; reichen? Und wieso überhaupt Kopieren und nicht gleich auf Data arbeiten?

Siehe Info in #15 ;-)

[Möbius]

Ui ui das wollte ich nicht.
Ich habe wohl meinen Code für die WalshHadamard-Transformation zu frühr veröffentlicht.
Wie ich schon gesagt habe "soll das ganze Copy" gar nichts. war rein der Entwicklung/Beobachtung geschuldet.
Ich stelle Euch folgenden Code zur Verfügung:

Delphi-Quellcode:

type
  PDatas = ^TDatas;
  TDatas = array of UInt8;

oder auch

type
  PDatas = ^TDatas;
  TDatas = array of Int64;

oder etwas dazwischen...


class procedure TCompressOSCT.WalshHadamardTransform(var Data: TDatas);
var
  i, j, n, m, x, y: UInt64;
begin
  n := Length(Data);
  m := 1;
  while 2 * m <= n do
  begin
    i := 0;
    while i < n do
    begin
      for j := i to i + m - 1 do
      begin
        x := Data[j];
        y := Data[j + m];
        Data[j] := y;
        Data[j + m] := x + y;
      end;
      i := i + 2 * m;
    end;
    m := m * 2;
  end;
  Data := Copy(Data, 0, Length(Data));
end;

class procedure TCompressOSCT.InvWalshHadamardTransform(var Data: TDatas);
var
  i, j, n, m, x, y: UInt64;
begin
  n := Length(Data);
  m := 1;
  while 2 * m <= n do
  begin
    i := 0;
    while i < n do
    begin
      for j := i to i + m - 1 do
      begin
        x := Data[j];
        y := Data[j + m];
        Data[j] := -x + y;
        Data[j + m] := x;
      end;
      i := i + 2 * m;
    end;
    m := m * 2;
  end;
end;

Also dieser Code für die WalshHadamard-Transformation funktioniert.
Somit also InPlace jetzt und mit einer Erklärung für was TDatas steht.
Imho kommt Delphi nicht klar mit var Parametern die ein "Array of Integer" darstellen. Es muss ein Typ festgelegt werden.

Um aber die zunehmende Debatte mit mehr Beteiligung nicht über Code-Platitüden welche ich schon erklärt habe warum ich es so mache veröffentlicht habe am Leben zu erhalten:

Folgendes:
Ich habe vorsichtiger Weise TDatas mal als Int64 definiert.
Obschon ich nur Bytes einspeise.
Prompt waren die "Antworten" im Output relativ Hohe Koeffizienten (sehr weit über 255=Byte).

Das interessante ist aber wenn ich TDatas gnadenlos als UInt8 definiere und es laufen lasse, dann ist klar, dass die hohen Stellen gnadenlos verloren gehen wenn ich Sie wieder an UInt8 zuweise.
Der Witz ist aber, dass die Rücktransformation trotzdem zu 100% klappt!
Den "AudioFreaks" unter uns würde ich dies nicht Empfehlen - das Gejaule dürfte ohrenbetäubend sein :wink:
Für die reinen "Daten Freaks" aber ev. interessant...

[Michael II]

Zitat:

Zitat von Möbius (Beitrag 1496697)

Aber es fehlt halt noch das i-Tüpfelchen.
Das Argument, dass man eine Nachricht N mit n Buchstaben nicht kürzer als N codieren kann, ohne dass man "Opfer" auf der anderen längeren Seite bringen muss, will mir nicht so recht in den Kopf.
Z.B. kann man ein Kartenspiel so lange perfekt mischen bis es sortiert ist. Dann braucht man bloss die Zahl der Mischvorgänge zu übermitteln um dies wieder rückgängig zu machen. Zauberkünstler nutzen diesen Trick übrigens für manche Kartenkunststücke. Man muss freilich die Kunst beherrschen ein Karttendeck wiederholt exakt in der mitte zu teilen und perfekt Karte links auf Karte rechts jeweils mischen können. Ein Deck mit 52 Karten ist verblüffender Weise nach 5 Durchgängen wieder sortiert.
Okay in der Praxis sind hier normalerweise viele Permutationen nötig.

Hallo Möbius, erst einmal danke fürs Posten des Codes; dieser hilft sicher einigen weiter.

Zu Karten und Rauschen: Du wirfst Chaos (Rauschen) und Ordnung (Einmischen/Ausmischen) in den gleichen Topf.

Beim Kartenmischen - wie du es beschreibst - herrscht sehr grosse Ordnung - nur deshalb lässt sich mit ähnlich geordnetem "Zurückmischen" sehr rasch wieder die Ausgangsposition erreichen. Zum Thema Einmischen/Ausmischen findest du viele Infos im Web; u.a. hier.

Würdest du aus einem 52er Karten Set 52 Mal völlig zufällig genau eine Karte ziehen und auf einem neuen Stapel ablegen, dann hättest du diese Ordnung nicht.

Zum Rauschen und deiner Hoffnung dieses komprimieren zu können. Vergiss es ;-). Ich empfehle dir, dich in Informationstheorie einzulesen. Dann sollte dir sehr rasch klar werden, dass dies nicht klappen kann.

Und wo eine gewisse Ordnung herrscht: Vielleicht hilft diese Seite einen Schritt weiter? Danach solltest du fast ;-) überzeugt sein, dass Gewinn auf der einen Seite (häufige Worte => kurze Codes), Verlust auf der anderen Seite (seltene Wörter => lange Codes) bedeutet. (Beispiel zum Link: Vollständiger binärer der Tiefe 5. Du kannst 2^5=32 Wörter an die 32 Blätter des Baums hängen. Damit codierst du jedes der 32 Worte mit 5 Bits. - Wenn du häufiger vorkommende Wörter mit weniger Bits codieren willst, dann benötigst du einen binären Baum mit Blättern näher der Wurzel. Du musst aber immer noch alle 32 Wörter an die Blätter deines Baums hängen können. D.h. du wirst deinen binären Baum anderswo erweitern müssen - und hast damit Wörter, welche du mit mehr als 5 Bits codierst.)

Sobald du fertig bist mit deiner "Möbius Kompression" wirst du hier hoffentlich einen Link auf dein Paper und dein Produkt posten. Viel Glück!

[Möbius]

Hallo Michael

Erst mal Danke für die guten Tipps.
Mein Kompressor-Projekt ist sehr sehr weit fortgeschrtten und kommt auf dem Calgary Corpus, Canterbury Corpus und Large Corpus mittlerweile an die Besten PPM (Prediction by Partial Matching) Kompressoren ran. Zeitlich sowieso, Zahlenmässig nah dran.
Also Artikel zur Huffman Komprimierung nützen mir nicht viel - diese ist Standard in meinen Programmen und wird final wohl noch durch die etwas bessere IntegerArithmetische Codierung ersetzt. Da muss man heute schon mehr bringen um was Neues zu machen.

Beim Kartenmischen muss ich widersprechen (Spektrum der Wissenschaft hin oder her - ich bin Abonennt). Ich bin mir mathematisch zwar nicht ganz sicher, aber konsequentes mischen (ein und dann aus) führt wohl irgendwann zu allen möglichen Permutationen der Karten. Von Ordnung kann hier nicht die Rede sein. Was heisst schon "Ordnung". Es ist eine Konvention was ordentlich ist. Jede Permutation stellt eine Art von Ordnung dar.

Nein die wirkliche Perfidie an RAD-Daten (Random-Daten) ist wirklich, dass diese statistischem Rauschen gleich kommen. Es gibt keine Zeichenwiederholungen, oder Wortbildungen o.ä. der einen Angriffspunkt gibt.
Ich habe mir für meine Forschungsplatform extra einen speziellen Zufallsgenerator gebaut. Der generiert nicht nur Zufallszahlen sondern erlaubt es, über weitere Zufallsgeneratoren, dass manchmal auch Zeichenwiederholngen oder Wortwiederholungen auftreten. Erstaunlich. Schon geringste Abweichungen vom absoluten Zufall führen zu interessanten komprimierten Ergebnissen.

Ich weiss ich weiss. Es gibt irgend ein Theorem/Beweis (ich weiss nicht mehr von wem), dass sich eine Zahlenmenge N nicht durch eine kleinere Zahlenmenge n vollständig abbilden lässt.
Der Beweis ist mir aber zu einfach. Schliesslich ist ja klar das Ordinalzahlen dazu dienen Kardinalzahlen abzuzählen. Also man braucht 1000 Ordinalzahlen um 1000 Karinalzahlen zu komprimieren.
Das ist aber imho falsch. Durch weglassen der führenden Nullen (was wir per Konvention im Alltag tun) lassen sich sehr viele Zahlen kürzer als 4 Stellen abbilden. Aber keine braucht bei dieser Ersparnis deswegen mehr als 4 Stellen.

Es scheint Du interessierst Dich für die Materie:
Dann schau mal hier über die Kolgomorov-Komplexizität nach: https://de.wikipedia.org/wiki/Kolmog...mplexit%C3%A4t
Du erwähnst Chaos. Chaos-Theorie auch bekannt? Es gibt "Gläubiger" die sagen man kann zu jeder Datenmenge N eine rekursive Formel finden, die diese Datenmenge erzeugt. Diese Formel sollte kürzer sein als die Datenmenge. Gut, dass hat noch keiner geschafft.
Aber deswegen halte ich es nicht für unmöglich.

Zur Informationstheorie letztlich.
Diese wurde bekanntlich von Claude Shannon in's Felde geführt und in den wesentlichsten Teilen von ihm ausgearbeitet.
Aber imho ist Sie noch lange nicht vollständig und zudem fehlerhaft.
Ein sehr grundlegender Fehler in der Theorie ist sicherich das Bit als grundlegendste Informationseinheit zu bennenen. Das Bit heisst neuerdings ja auch Shannon.
Aber es ist imho falsch. Es basiert auf dem binären Zahlensytem und wird von Computern nachgerade impliziert.
Aber es gäbe auch noch das unäre Zahlensystem. Das nur die Zahl Null kennt.
Mathematisch wahrscheinlich wenig sinnvoll, aber Informationstheoretisch?:
Es gibt zig Situationen in denen wir nicht per Information Ja/Nein oder 1/0 kommunizieren.
Es gibt zig Situationen in denen wir einfach per Information, Zeichen x senden, oder gar nicht, kommunizieren.
Z.B.
- Die alten Wikinger pflegten in Fijorden zu leben. An der Aussenseite des Fjordes haben Sie Wachposten angebracht welche Feinde entdecken sollen. Sind solche im Anmarsch haben Sie Meldefeuer entzündet welche das Dorf in der Bucht warnten. Das "Nichtbrennen" des Feuers kann aber schwerlich als permanentes senden von Nullen betrachtet werden.
- Oder, etwas salopp, der Playboy-Pfiff. Man läuft an einer Person vorbei und tut entweder gar nichts. D.h. aber nicht 0 (Null - Du bist ein Arsch oder interessierst mich nicht). Es heisst einfach gar nichts,. Gar nichts gesendet - auch keine 0. Aber eben der Pfiff = 1 der heisst schon einiges.

Also die Zukunft hat noch potential.