Integer (1 Byte) Datentransformation DCT (FFT) gesucht

[Michael II]

Zitat von Möbius:

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 von Möbius:

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 von 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?

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
Für die reinen "Daten Freaks" aber ev. interessant...

[Michael II]

Zitat von Möbius:

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!