[LinuxOB] [OT] Textkomprimierung

[Daniel Dombrowski]

On 2003.12.21 00:10, Alexander Müller wrote:
> Hi,
> 
> Ich weiss, das ist x-treme Off-Topic, aber evt. kann mir
> ja jemand helfen.
> 
> Also...
> 
> Ich bastel gerade an einem Projekt, bei dem ich
> teils sehr lange Texte in Dateien und die Datei-
> namen in einer Datenbank speicher.
> Nun moechte ich eine Suchfunktion in den Texten
> ermoeglichen. Ich nehme an, dass es sich spaeter
> um sehr viele, sehr lange Dokumente handeln
> wird. Daher wird es schwierig sein, jedes Dokument
> zu oeffnen und nach Zeichenketten zu durchsuchen.
> Da dachte ich mir, dass ich einen Cache der Texte
> anlege, indem eine komprimierte Form des Textes
> vorliegt.
> 
> Das Problem ist, dass ich es nicht einfach mit dem
> MD5 Algorithmus verschlueseln kann, da ich dann
> keine Chance mehr haette im Cache nach Strings zu
> suchen.
> -> keine Einwegverschluesselungen
> -> keine Einwegkomprimierungen
> 
> Dann dachte ich mir, dass ich die Texte mit einer RLE-
> Kompression [1] cache.
> Dabei ist mir die Komprimierung jedoch zu schwach
> und die Cachedatenbank wuerde die Festplatten-
> kapazitaet sprengen.
> 
> Daraufhin habe ich mich mit der Huffman-Kompression [2]
> beschaeftigt. Dabei gibt es jedoch das Problem, dass
> es, egal ob der statische Huffmanalgorithmus oder der
> dynamische Huffmanalgorithmus, immernoch zu einer zu
> schwachen Komprimierung fuehrt.
> Der adaptive Huffmanalgorithmus aendert bei dieser
> Tatsache auch nichts.
> 
> Spaeter habe ich mich dann mit dem LZW-Kompressions-
> algorithmus [3] beschaeftigt. Jedoch ist diese Kompression
> nicht geeignet, da sprachspezifische Code-"Woerter-
> buecher" generiert werden wuerden. Und dazu kommt
> noch, dass die Sprache(n) der Suchstrings in weniger als
> 50% der Faelle identisch mit der Sprache des Textes sind.
> 
> Mir ist bei der Sache egal, ob der komprimierte Cache
> dekomprimiert wird und dann mit dem Suchstring verglichen
> wird oder ob der Suchstring komprimiert und dann im
> komprimierten Cache gesucht wird.
> 
> Ich habe noch einige einfache Kompressionsalgorithmen
> auf Tauglichkeit ueberprueft, aber die sind alle _absolut_
> nicht geeignet.
> 
> Ich bin mit meinem Latein am Ende... Evt. gibt es noch
> leichtere Moeglichkeiten eine Volltextsuche zu realisieren,
> ohne alle Dateien oeffnen zu muessen.
> 
> [1] http://de.wikipedia.org/wiki/Laufl%E4ngenkodierung
> [2] http://de.wikipedia.org/wiki/Huffman-Code
> [3] http://de.wikipedia.org/wiki/LZW

Was spricht denn dagegen, die Dateien komplett die Datenbank zu  
schieben und dann so Sachen wie die MySQL-Volltextsuche zu verwenden?  
Hätte auf jeden Fall den Vorteil, dass du die Daten nur einmal  
speichern müsstest. Und es wäre gewährleistet, dass du auch  
Suchprozeduren verwendest, die tendenziell performanter sind als  
irgendwas selbstgebautes - und fehlerfreier vermutlich auch.

In jedem Fall stell ich es mir aber nicht sonderlich performant vor,  
wenn du einen komprimierten Cache erstellst und den jedes mal wieder  
entpacken musst ... da kannst du wohl wirklich eher jedesmal alle  
Dateien öffnen.

Gruss

Daniel