Bytes zu 12 Bits und anders herum. (Fehlerhafter LZW Source)

[FlowPX2]

Hmm... sehe jetzt leider nicht sonderlich viele änderungen in dem Code ^^

Das hier hab ich auch schon probiert bei mir ^^ Aber da werden nur die ersten paar KB schneller geschrieben... der rest wieder auf gewohntem Schneckentempo.

Code: Alles auswählen

For i = 256 To WordBookIndex ;4095 

irgendwie ärgerlich die Geschwindigkeit. Traue mich nichtmals zu versuchen eine MB File damit zu packen. Ob es Geschwindigkeit bringen würde erstmal alles im Ram zu lassen und ganz am Ende in die Datei schreiben!?

mfg.
FlowPX2

[Helle]

Die Zuweisungen

Code: Alles auswählen

Wert1.w = ByteA 
Wert2.w = ByteB 

zu Beginn der Repeat-Schleife müssen weg, denn Wert1 bekommt im 2.Durchlauf den Wert von ehemals Wert2!
Der Speed ist natürlich nicht berauschend, ich denke mal, die Profi-Programme verwenden Hash-Tabellen und müssen so nicht das Wörterbuch durchforsten sondern finden gezielt den Treffer.

Gruß
Helle

[NicknameFJ]

Stelle erstmal sicher dass der Algo passt und die komprimierte Datei den korrekten Inhalt hat, d.h. dass sie auch wieder in die Ursprungsdatei zurückverwandelt werden kann.

Anschließend die ganzen Operationen innerhalb der Schleife auf Speed optimieren.

Du musst Dir vor Augen halten, wie oft diese Schleife durchlaufen wird.

z.B. Datei 1 Mio Byte x ca. 3800 Druchläufe (4095-256) pro Byte um deine Wörterbucheinträge zu checken das sind 3,8 Mrd. Durchläufe. Wenn hier irgendwo ein paar Millisekunden verschenkt werden summiert sich das auf !

Wie gesagt, ich würde erst sicherstellen dass der Algo läuft und die restlichen Speedoptimierungen erstmal hinten anstellen.

Bei mir wird eine Datei mit 830 KB in knapp 9 Sekunden auf 1160 KB "komprimiert", habe die ein paar Änderungen vorgenommen.

Poste ich dann später

Grüße

Joachim

[FlowPX2]

In 9 Sekunden!? Das Ding brauch bei mir Minuten lang! Und das schon bei 300KB...

[NicknameFJ]

Noch ein Verbesserungsvorschlag für Deine endgültige Version

Ich würde im ersten Schritt die Wörterbuchtabelle anlegen, ohne die Datei zu schreiben, bis die 4096 Einträge voll sind. Anschließend die Tabelle sortieren und dann erst die Datei komprimieren !

Wozu ??? Momentan musst Du die komplette Wörterbuchliste durchgehen, bis zu 3840 Durchläufe pro Byte der Ausgangsdatei, liegt die Liste sortiert vor kannst Du einen Binären Suchalgorythmus anwenden, dann brauchst Du max. 11 Durchläufe pro Byte der Ausgangsdatei

Weiterhin brauchst Du die drei Byte nicht immer einzeln in die Datei schreiben, ich würde den Weg über einen Buffer gehen und die Daten in einem Rutsch auf den Datenträger schreiben.


Nun zu meinem Code:
Ich habe die Wörterbuchliste, da Sie ja nur aus zwei Byte besteht nicht als Stringfeld sondern als Zahlenfeld definiert, das erspart die aufwendigen Stringkonvertierungen mit STR(). Weiterhin habe ich die Ermittlung des Vergleichswertes vor die Schleife gezogen (Dummy) und nicht wie Du bei jedem Schleifendurchlauf neu berechnet (Str(ByteA)+Str(ByteB))

Mein Algo funzt so wie er steht natürlich nur mit einem Wörterbuch mit 2 Zeichen. Ich würde aber auch wenn es mehr Zeichen pro Eintrag werden nicht mit langsamen Stringoperationen arbeiten. Lieber einem Speicherbereich reservieren und die Bytewerte eintragen und dann eine optimierte Such- und Vergleichsroutine schreiben.

Habe noch irgendwas geändert, weiß aber nicht mehr was *man wird alt*, und jetzt ist er nicht mehr ganz so schnell, ich schaffe die 9 Sek. nicht mehr, sind jetzt 16, aber mit weiteren Optimierungen wohl noch deutlich zu drücken.

Hier nun mein Code

Code: Alles auswählen

DisableDebugger


#SourceFile=0 
#EndFile=1 

Procedure.s Compress(FromFile.s,ToFile.s) 
  
  
  ;Dateien öffnen 
  OpenFile(#SourceFile,FromFile.s) 
  OpenFile(#EndFile,ToFile.s) 
  
  ;Wörter Buch 
 ; Dim WordBook.s(4096) 
  Dim NumWordBook(4095)
  
  For i = 0 To 255 
 ;   WordBook.s(i) = Str(i) 
    NumWordBook(i) = i
  Next 
  
  ;Byte und Word Variablen 
  Global Wert1.w = 0 
  Global Wert2.w = 0 
  Global Byte1.b = 0 
  Global Byte2.b = 0 
  Global Byte3.b = 0 
  Global Result.l = 0 
  
  WordBookIndex = 256 
  WordBookExist = 0 
  
  ;Zu komprimierende Datei laden 
  SourceFileSize = FileSize(FromFile.s)+1 
  Dim SourceBytes(SourceFileSize) 
  
  LoadCurPos = 0
  
  Repeat 
    SourceBytes(LoadCurPos.l) = ReadByte(#SourceFile)&$FF 
    LoadCurPos +1
  Until Eof(#SourceFile) 
  
  CurPos.l = 0 
  dummy.w = 0
  Repeat 
    WriteInFile = WriteInFile + 1 
    
    ByteA.b = SourceBytes(CurPos.l)      
    ByteB.b = SourceBytes(CurPos.l+1) 
    
    WordBookExist = 0 
  
    dummy = ByteA * 256 + ByteB 
    
    
    ;Prüfe ob in Wörterbuch schon vorhanden 

    For i = 256 To WordBookIndex-1
      
   ;   If WordBook(i) = Str(ByteA)+Str(ByteB)
    
      
      If NumWordBook(i) = dummy 
      
      If WriteInFile = 1 
        Wert1.w = i 
      Else 
        Wert2.w = i 
      EndIf 
      
      WordBookExist = 1 
      CurPos +1    ;Wenn im Wörterbuch vorhanden, dann nächstes Byte nicht nochmal verarbeiten 

        
        Break 
      EndIf 
    Next 
    
    
    If WordBookExist = 0
      
      
      ;Wenn nicht im Wörterbuch vorhanden 
      If WordBookIndex < 4096 
    ;    WordBook(WordBookIndex) = Str(ByteA)+Str(ByteB)
        NumWordBook(WordBookIndex) = ByteA * 256 + ByteB 
        WordBookIndex = WordBookIndex + 1 
      EndIf 
      
      If WriteInFile = 1 
        Wert1.w = ByteA 
      Else 
        Wert2.w = ByteA 
      EndIf 
    EndIf 
    
    
    
    ;Schreibe in Datei wenn genug Bits da sind um 3Bytes zu füllen 
    If WriteInFile = 2 
      
      !MOVZX Eax,[v_Wert1] 
      !MOV dx,[v_Wert2] 
      !SHL Edx,12 
      !OR Eax,Edx 
      !MOV [v_Result],Eax 
      !MOV [v_Byte2],ah 
      !MOV [v_Byte3],al 
      !SHR Eax,8 
      !MOV [v_Byte1],ah 
      
      ;Schreibe kompremierte version in Datei 
      
      WriteByte(#EndFile,Byte1.b&$FF); 
      WriteByte(#EndFile,Byte2.b&$FF); 
      WriteByte(#EndFile,Byte3.b&$FF); 
      
      WriteInFile = 0 
    EndIf 
    
    CurPos + 1 
    
  Until CurPos >= SourceFileSize 
  
  
  ProcedureReturn RetVal.s 
EndProcedure 



Start = gettickcount_()
Compress("C:\Test.wav","C:\Test.dat") 

Zeit = gettickcount_()-Start

MessageRequester("verstrichene Zeit",Str(Zeit)+" ms")

Wie vorhin schon gepostet würde ich vor allen anderen Optimierungen erst sicherstellen dass der Algo passt.

Ich hoffe, dass ich aus Versehen nichts am Algo geändert habe und sowohl mit meiner als auch mit Deiner Version der gleiche Output (=Datei)auf die Platte geschrieben wird.

Grüße

Joachim

[FlowPX2]

Das klingt alles irgendwie sehr einleuchtend... Werde es dann mal testen weiß jetzt nicht wann ich dazu komme... vll. erst nach dem wocheende.

mfg.
FlowPX2

[NicknameFJ]

Ändere die Stelle wo Du den Schleifenbeginn hast mal so, das bringt bei mir bei einer Quelldatei mit 1 MB ca. 3 Sekunden, bin dann bei 10 Sekunden

Habe meinen Rechner neu gestartet und war dann doch wieder schneller als die o.g. 16 Sekunden für 830 KB

Code: Alles auswählen

    ;Prüfe ob in Wörterbuch schon vorhanden 

    Endloop = WordBookIndex -1
    
    For i = 256 To Endloop

Und ich habe Dir vorhin noch was erzählt von "Berechnungen" vor die Schleife ziehen und selbst mach ich es auch nicht konsequent.

[FlowPX2]

Hab es gerade mal Probiert mit einer 1,02MB File hat 7516ms gebraucht. Muss es unter der Woche dann mal auf meinem Heimrechner probieren, wie gut es läuft. jedenfalls scheint es wirklich schon um einiges schneller zu sein...

mfg.
FlowPX2