Is there ANY compression type that can compress a file, and then that compressed file can be searched without uncompressing the file?
$\begingroup$
$\endgroup$
7
-
3$\begingroup$ You can uncompress on-the-fly for searching. Other than that, unless you have some rather unusual formatting of the data and the stuff being searched for, I very much doubt it. What exactly are you trying to do? $\endgroup$– vonbrandCommented Aug 12, 2015 at 21:11
-
4$\begingroup$ I encourage you to edit the question to elaborate on your particular requirements. Are you only interested in standard compression schemes, or are you willing to consider unusual compression schemes that are designed to support searching? Are you willing to consider a compression scheme that also stores an index on the side that can be used to help speed up searching? Also, clarify what kind of search you are OK with. Does uncompressing-on-the-fly for searching count as a valid solution? If not, why not? Are there specific running time goals you trying to hit? $\endgroup$– D.W. ♦Commented Aug 12, 2015 at 22:11
-
1$\begingroup$ That edit didn't add much clarity. It feels like you've decided searching a compressed file is a solution to some other problem you're having. What is that problem you're trying to solve by searching a compressed file? $\endgroup$– SchwernCommented Aug 13, 2015 at 5:26
-
1$\begingroup$ @Schwern No problem at hand at all, just simply curious if the techniques already existed, for literally anything. I couldn't think of any off the top of my head. :) Even put "any" in bold haha. I did mean it in the literal sense. $\endgroup$– Albert RenshawCommented Aug 13, 2015 at 9:26
-
3$\begingroup$ I do not see any reason to close this question which seems to be attracting reasonable answers. Apparently the poster is trying to get entry points is the matter, and he is getting them. Pictures are de facto compressed data (it is always an approximation), yet there are seach techniques to find pattrns in pictures, even when the resolution is not the same. $\endgroup$– babouCommented Aug 13, 2015 at 11:34
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
1
Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of literature.
Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/select data structures). There are a range of issues that arise depending on whether one wants simple boolean containment predicates, the offset of each occurrence, or more complicated suffix tree operations; the former can be done in less space and time than the latter.
There's also an entire book about searching and selective decompression of strings: "Compressed Data Structures for Strings: On Searching and Extracting Strings" by Rossano Venturini, published 2014 Springer Science & Business Media.
-
1$\begingroup$ Please give references in a way that are robust against link rot; for books, author(s), title, publisher and year are the accepted minimum. $\endgroup$– RaphaelCommented Aug 13, 2015 at 7:13
$\begingroup$
$\endgroup$
KWillets mentioned the FM index. It's worth noting that the FM index is based on the Burrows-Wheeler transform (also the basis of bzip), along with an index which supports efficient "rank" queries.
BWT-based indexes are self-indexing, in the sense that the index is also a compressed representation of the source string, and can be decompressed into the original file. The decompression can be performed more quickly by adding a select index along with the rank index. Rank/select indexes are an interesting topic, and are worth checking out. There are some excellent resources for practical implementations.
However, the main point that I want to bring up is this is a special case of the more general idea of compressed data structures. A compressed data structure is one that doesn't need to be decompressed (or the amount of decompression required is bounded) in order to perform efficient operations on it.
Compressed data structures can be further analysed in terms of their overhead relative to a theoretical limit. For example, succinct data structures have a relative overhead which decreases as the data structure grows. This is a very active research area at the moment.
The BWT technique can be applied to data structures other than strings. For example, the same idea has been extended to labelled trees, resulting in a compressed searchable representation.
So if you have data that you need to compress and find stuff in, don't necessarily think in terms of files. Your data may have a higher-level structure that you can exploit.
answered Aug 13, 2015 at 1:36