Komprimierungstyp, der durchsucht werden kann

7

Gibt es ANY Komprimierungstyp, der eine Datei komprimieren kann, und dann die komprimierte Datei durchsucht werden kann , ohne Entpacken Sie die Datei?

search-algorithms strings data-compression Albert Renshaw
quelle
3
Sie können die Suche im laufenden Betrieb dekomprimieren. Abgesehen davon bezweifle ich es sehr, es sei denn, Sie haben eine ungewöhnliche Formatierung der Daten und des gesuchten Materials. Was genau versuchst du zu tun?
vonbrand
4
Ich ermutige Sie, die Frage zu bearbeiten, um auf Ihre speziellen Anforderungen einzugehen. Interessieren Sie sich nur für Standardkomprimierungsschemata oder sind Sie bereit, ungewöhnliche Komprimierungsschemata in Betracht zu ziehen, die die Suche unterstützen sollen? Sind Sie bereit, ein Komprimierungsschema in Betracht zu ziehen, das auch einen Index auf der Seite speichert, der zur Beschleunigung der Suche verwendet werden kann? Stellen Sie außerdem klar, mit welcher Art von Suche Sie einverstanden sind. Gilt das sofortige Komprimieren für die Suche als gültige Lösung? Wenn nicht, warum nicht? Gibt es bestimmte Laufzeitziele, die Sie erreichen möchten?
DW
1
Diese Bearbeitung brachte nicht viel Klarheit. Es scheint, als hätten Sie beschlossen, eine komprimierte Datei zu durchsuchen, um ein anderes Problem zu lösen. Was ist das Problem, das Sie lösen möchten, indem Sie eine komprimierte Datei durchsuchen?
Schwern
1
@Schwern Überhaupt kein Problem, nur einfach neugierig, ob die Techniken bereits existieren, für buchstäblich alles. Ich konnte mir nichts vorstellen. :) Sogar "any" in Fettdruck setzen haha. Ich habe es im wörtlichen Sinne gemeint.
Albert Renshaw
3
Ich sehe keinen Grund, diese Frage zu schließen, die vernünftige Antworten zu finden scheint . Anscheinend versucht das Poster, Einstiegspunkte zu bekommen, und er bekommt sie. Bilder sind de facto komprimierte Daten (dies ist immer eine Annäherung), es gibt jedoch Suchtechniken, um Muster in Bildern zu finden, selbst wenn die Auflösung nicht gleich ist.
Babou

Antworten:

12

Komprimierte Selbstindizes wie der FM-Index ermöglichen eine beliebige Suche nach Teilzeichenfolgen in einem nahezu entropiekomprimierten Raum. Dies sind im Wesentlichen komprimierte Suffix-Arrays oder Suffix-Bäume, die viel Literatur enthalten.

Die grundlegende Suche nach Teilzeichenfolgen kann zeitlich o (k) oder o (k log n) für die Länge k sein, je nachdem, welche Datenstrukturen ausgewählt wurden (verschiedene Arten von Rang- / Auswahldatenstrukturen). Es gibt eine Reihe von Problemen, die auftreten, je nachdem, ob einfache Prädikate für die boolesche Eindämmung, der Versatz jedes Auftretens oder kompliziertere Suffixbaumoperationen gewünscht werden. Ersteres kann in weniger Raum und Zeit als Letzteres durchgeführt werden.

Es gibt auch ein ganzes Buch über das Suchen und selektive Dekomprimieren von Zeichenfolgen : "Komprimierte Datenstrukturen für Zeichenfolgen: Über das Suchen und Extrahieren von Zeichenfolgen" von Rossano Venturini, veröffentlicht 2014 Springer Science & Business Media.

KWillets
quelle
1
Bitte geben Sie Referenzen auf eine Weise an, die robust gegen Link Rot ist. Für Bücher sind Autor (en), Titel, Verlag und Jahr das akzeptierte Minimum.
Raphael
3

KWillets erwähnte den FM-Index. Es ist erwähnenswert, dass der FM-Index auf der Burrows-Wheeler-Transformation (auch die Basis von bzip) basiert , zusammen mit einem Index, der effiziente "Rang" -Abfragen unterstützt.

BWT-basierte Indizes sind in dem Sinne selbstindizierend, dass der Index auch eine komprimierte Darstellung der Quellzeichenfolge ist und in die Originaldatei dekomprimiert werden kann. Die Dekomprimierung kann schneller durchgeführt werden, indem ein Auswahlindex zusammen mit dem Rangindex hinzugefügt wird. Rank / Select-Indizes sind ein interessantes Thema und einen Besuch wert. Es gibt einige hervorragende Ressourcen für praktische Implementierungen .

Der Hauptpunkt, den ich ansprechen möchte, ist jedoch, dass dies ein Sonderfall der allgemeineren Idee komprimierter Datenstrukturen ist. Eine komprimierte Datenstruktur muss nicht dekomprimiert werden (oder der erforderliche Dekomprimierungsgrad ist begrenzt), um effiziente Operationen daran ausführen zu können.

Komprimierte Datenstrukturen können hinsichtlich ihres Overheads relativ zu einer theoretischen Grenze weiter analysiert werden. Beispielsweise haben prägnante Datenstrukturen einen relativen Overhead, der mit zunehmender Datenstruktur abnimmt. Dies ist derzeit ein sehr aktives Forschungsgebiet.

Die BWT-Technik kann auf andere Datenstrukturen als Zeichenfolgen angewendet werden. Beispielsweise wurde dieselbe Idee auf beschriftete Bäume ausgedehnt , was zu einer komprimierten durchsuchbaren Darstellung führte.

Wenn Sie also Daten haben, die Sie komprimieren und finden müssen, denken Sie nicht unbedingt an Dateien. Ihre Daten haben möglicherweise eine übergeordnete Struktur, die Sie ausnutzen können.

Pseudonym
quelle