[go: up one dir, main page]

Shapira et al., 2004 - Google Patents

In-place differential file compression of nonaligned files with applications to file distribution, backups, and string similarity

Shapira et al., 2004

View PDF
Document ID
10464901683046575175
Author
Shapira D
Storer J
Publication year
Publication venue
Data Compression Conference, 2004. Proceedings. DCC 2004

External Links

Snippet

We consider in-place differential file compression; that is, compressing a file T of size n with respect to an existing file S of size m, where decompression is in-place by overwriting S with T, using at most MAX (m, n)+ O (1) space. In previous work we presented the IPSW algorithm …
Continue reading at pages.cs.brandeis.edu (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30067—File systems; File servers
    • G06F17/30129—Details of further file system functionalities
    • G06F17/3015—Redundancy elimination performed by the file system
    • G06F17/30156—De-duplication implemented within the file system, e.g. based on file segments
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30067—File systems; File servers
    • G06F17/30129—Details of further file system functionalities
    • G06F17/3015—Redundancy elimination performed by the file system
    • G06F17/30153—Redundancy elimination performed by the file system using compression, e.g. sparse files
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3086—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing a sliding window, e.g. LZ77
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/4031—Fixed length to variable length coding
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/20—Handling natural language data
    • G06F17/21—Text processing
    • G06F17/22—Manipulating or registering by use of codes, e.g. in sequence of text characters
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Error detection; Error correction; Monitoring responding to the occurence of a fault, e.g. fault tolerance
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F8/00—Arrangements for software engineering
    • G06F8/60—Software deployment
    • G06F8/65—Update
    • G06F8/68—Incremental; Differential

Similar Documents

Publication Publication Date Title
CN107210753B (en) Lossless reduction of data by deriving data from prime data units residing in a content association filter
US7079051B2 (en) In-place differential compression
US6526574B1 (en) System for finding differences between two computer files and updating the computer files
JP4364790B2 (en) Byte-level file difference detection and update algorithm
US8120516B2 (en) Data compression using a stream selector with edit-in-place capability for compressed data
Bentley et al. Data compression using long common strings
US20110119240A1 (en) Method and system for generating a bidirectional delta file
Balkenhol et al. Universal data compression based on the Burrows-Wheeler transformation: Theory and practice
CN107682016B (en) Data compression method, data decompression method and related system
González et al. Locally compressed suffix arrays
Manzini The Burrows-Wheeler Transform: Theory and Practice: Invited Lecture
US7379940B1 (en) Focal point compression method and apparatus
Shapira et al. In place differential file compression
Shapira et al. In-place differential file compression of nonaligned files with applications to file distribution, backups, and string similarity
Zavadskyi et al. Binary mixed-digit data compression codes
US8244677B2 (en) Focal point compression method and apparatus
Yu Data compression for PC software distribution
Shapira Direct merging of delta encoded files
Shapira Compressed transitive delta encoding
Ferragina et al. On updating suffix tree labels
Mäkinen et al. Run-length compressed indexes for repetitive sequence collections
Ferragina et al. Data Compression
Larsson Attack of the mutant suffix trees
Zhang Tutorial on Lempel-Ziv Data Compression Algorithm
Gupta et al. Compressed Differential Encoding for Semi-Static Compressors