Accession Number : AD0771314

Title :   File Compression for Simple Associative Search.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD RESEARCH INST MENLO PARK CALIF

Personal Author(s) : Kautz,William H.

Report Date : NOV 1973

Pagination or Media Count : 70

Abstract : Large data files can often be compressed greatly for retrieval purposes if the family of questions to be asked of the file can be circumscribed in advance. The author investigates in the paper methods for compressing a file D, which consists of a single long list of words, with respect to simple associative search (exact match): is any given word q contained in D. A tight lower bound on the size of the compressed file is derived. Twelve engineering solutions to this problem are evaluated and compared, mainly on the basis of how closely they approach this bound. Other comparison criteria include the amount of time and additional hardware required both for searching and for updating the compressed life. (Modified author abstract)

Descriptors :   *Information theory, *Data compression, *Search theory, Coding, Boolean algebra, Logic circuits, Algorithms, Information retrieval

Subject Categories : Information Science
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE