komprimieren lange Liste von kurzen Strings

Question

Ich habe lange Liste von kurzen Strings, die ich komprimieren möchte, aber ich möchte jederzeit eine beliebige Zeichenfolge in der Liste dekomprimieren, ohne die gesamte Liste zu dekomprimieren.

Ich kenne die Liste im Voraus und es spielt keine Rolle, wie viel Vorverarbeitung ist beteiligt. Es ist auch in Ordnung, wenn es einen signifikanten O (1) Speicher-Overhead gibt.

Ich weiß, dass ich jede Zeichenfolge unabhängig mit einem verlustfreien Komprimierungsalgorithmus komprimieren könnte, aber das wird nicht sehr gut funktionieren, da die Zeichenfolgen sehr kurz sind und nicht viel Redundanz enthalten. Auf der gesamten Liste gibt es jedoch eine Menge Redundanz.

Answer 1

Ich würde empfehlen zu komprimieren über 64K im Wert von Strings zu einer Zeit (etwa 32 Ihrer Zeichenfolgen), erfordern, dass Sie nur 16 Zeichen im Durchschnitt dekomprimieren, um die gewünschte zu bekommen. Im Gegensatz zu 1.000.000. Sie erhalten fast die gleiche Komprimierung mit deflate (die von gzip verwendete Komprimierungsmethode).

Eine Alternative, die ebenfalls Deflate verwendet, wäre ein 32K "Dictionary" zu konstruieren, das aus den am häufigsten gesehenen Sub-Strings in Ihren 2.000.000 Strings besteht. Dann kann jede Zeichenkette einzeln mit dem 32K komprimiert werden, von dem die Übereinstimmungen zu ziehen sind. Wenn Ihre Strings diese Art von Gemeinsamkeiten aufweisen, können Sie sich der gleichen Komprimierung annähern. (Siehe zlib'sdeflateSetDictionary() und inflateSetDictionary() Funktionen.)