AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Integer (1 Byte) Datentransformation DCT (FFT) gesucht

Integer (1 Byte) Datentransformation DCT (FFT) gesucht

Ein Thema von Möbius · begonnen am 17. Okt 2021 · letzter Beitrag vom 10. Nov 2021
Antwort Antwort
Seite 2 von 3     12 3   
Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
703 Beiträge
 
Delphi 11 Alexandria
 
#11

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 27. Okt 2021, 14:53
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 (?)...
Michael Gasser
  Mit Zitat antworten Zitat
Möbius

Registriert seit: 19. Sep 2021
Ort: Schwarzwald
12 Beiträge
 
Delphi 10.4 Sydney
 
#12

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 27. Okt 2021, 16:10
@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.
Reto Crameri
  Mit Zitat antworten Zitat
Möbius

Registriert seit: 19. Sep 2021
Ort: Schwarzwald
12 Beiträge
 
Delphi 10.4 Sydney
 
#13

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 27. Okt 2021, 19:51
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;
Reto Crameri
  Mit Zitat antworten Zitat
Benutzerbild von Sinspin
Sinspin
Online

Registriert seit: 15. Sep 2008
Ort: Dubai
608 Beiträge
 
Delphi 10.3 Rio
 
#14

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 28. Okt 2021, 10:18
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.
Stefan
Nur die Besten sterben jung
A constant is a constant until it change.
  Mit Zitat antworten Zitat
Möbius

Registriert seit: 19. Sep 2021
Ort: Schwarzwald
12 Beiträge
 
Delphi 10.4 Sydney
 
#15

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 28. Okt 2021, 14:22
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.
Reto Crameri
  Mit Zitat antworten Zitat
venice2
(Gast)

n/a Beiträge
 
#16

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 28. Okt 2021, 14:31
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.
  Mit Zitat antworten Zitat
freimatz
Online

Registriert seit: 20. Mai 2010
1.377 Beiträge
 
Delphi 11 Alexandria
 
#17

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 28. Okt 2021, 15:17
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?
  Mit Zitat antworten Zitat
Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
703 Beiträge
 
Delphi 11 Alexandria
 
#18

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 28. Okt 2021, 16:17
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
Michael Gasser
  Mit Zitat antworten Zitat
Möbius

Registriert seit: 19. Sep 2021
Ort: Schwarzwald
12 Beiträge
 
Delphi 10.4 Sydney
 
#19

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 28. Okt 2021, 21:11
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...
Reto Crameri
  Mit Zitat antworten Zitat
Michael II

Registriert seit: 1. Dez 2012
Ort: CH BE Eriswil
703 Beiträge
 
Delphi 11 Alexandria
 
#20

AW: Integer (1 Byte) Datentransformation DCT (FFT) gesucht

  Alt 5. Nov 2021, 15:09
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!
Michael Gasser

Geändert von Michael II ( 6. Nov 2021 um 09:22 Uhr)
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 18:03 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz