Re-store: a system for compressing, browsing, and searching large documents
Alistair Moffat, Raymond Wan · 2005
We describe a software system for managing text files of up to several hundred megabytes that combines a number of useful facilities: effective text compression; phrase browsing; and fast interactive searching. Mechanisms for compressing text have been studied for many years, and a wide range of effective methods has been developed. But compression of text makes it unwieldy in other ways – it must be decompressed before being viewed, and it is harder to directly search. One way of addressing these concerns is to build an index for the source document, and search via a query interface [Witten et al., 1999]. Then the passages sought by the user can be identified using Boolean or ranked queries, and only those selected passages need be fetched and decompressed. Another alternative is to use a compression mechanism that is amenable to compressed pattern matching, and undertake the equivalent of an exhaustive linear search in the compressed text to locate passages of interest [de Moura et al., 2000]. Again, only small fragments of the source document might be eventually presented to the user. In this presentation we consider a third approach, and describe a software compression and searching system – dubbed RE-STORE – that supports browsing within the compressed text based on phrases extracted from the text, and fast identification and decompression of the passages in the text containing those phrases. In our system, the user selects one or more terms of interest from a static list that is somewhat akin to a vocabulary derived from the document, and is then free