File compression using sequence splits and sequence alignment
AssigneeDell Products L.P.
InventorsOfir Ezrielev, Ilan Buyum, Jehuda Shemer
Life of this patent
Estimating the term…
Abstract
Compressing files is disclosed. An input file to be compressed is first aligned. Aligning the file includes splitting the file into sequences that can be aligned. When splitting the file into sequences or when performing subsequent recursive splitting, the splitting is based on a longest sequence match. The result is a compression matrix, where each row of the matrix corresponds to part of the file. A consensus sequence is determined from the compression matrix. Using the consensus sequence, pointer pairs are generated. Each pointer pair identifies a subsequence of the consensus matrix. The compressed file includes the pointer pairs and the consensus sequence.
Claims18
A method, comprising:
- receiving an input file into a compression engine;
- aligning the input file to create a compression matrix that includes sequences arranged in rows of the compression matrix, wherein each of the sequences in the compression matrix corresponds to a different portion of the input file, wherein aligning the input file includes at least one iteration of splitting sequences associated with the input file, wherein splitting sequences comprises:
- identifying a repeated subsequence within a sequence, wherein the repeated subsequence is a longest matching subsequence that occurs more than once in the sequence;
- performing a split of the sequence before and after the repeated subsequence to produce two or more new sequences;
- and
- inserting gaps into at least one of the new sequences to enable alignment with one or more other sequences,
- wherein each column of the compression matrix includes a same entry or a gap after the sequences are aligned after splitting is completed;
- determining a consensus sequence from the compression matrix, wherein the consensus sequence includes an entry from each of the columns;
- and
- for each row of the compression matrix:
- generating one or more pointer pairs, wherein each pointer pair identifies a subsequence of entries in the row that does not include any gaps, wherein each pointer pair identifies a portion of the consensus sequence that corresponds to the subsequence of the row, wherein a first pointer in each of the pointer pairs for the row points to a different entry in the consensus matrix;
- and
- compressing the input file by generating a compressed input file from the input file, wherein the compressed input file includes the consensus sequence and the pointer pairs for all of the rows of the compression matrix.
A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
- receiving an input file into a compression engine;
- aligning the input file to create a compression matrix that includes sequences arranged in rows of the compression matrix, wherein each of the sequences in the compression matrix corresponds to a different portion of the input file, wherein aligning the input file includes at least one iteration of splitting sequences associated with the input file, wherein splitting sequences comprises:
- identifying a repeated subsequence within a sequence, wherein the repeated subsequence is a longest matching subsequence that occurs more than once in the sequence;
- performing a split of the sequence before and after the repeated subsequence to produce two or more new sequences;
- and
- inserting gaps into at least one of the new sequences to enable alignment with one or more other sequences,
- wherein each column of the compression matrix includes a same entry or a gap after the sequences are aligned after splitting is completed;
- determining a consensus sequence from the compression matrix, wherein the consensus sequence includes an entry from each of the columns;
- and
- for each row of the compression matrix:
- generating one or more pointer pairs, wherein each pointer pair identifies a subsequence of entries in the row that does not include any gaps, wherein each pointer pair identifies a portion of the consensus sequence that corresponds to the subsequence of the row, wherein a first pointer in each of the pointer pairs for the row points to a different entry in the consensus matrix;
- and
- compressing the input file by generating a compressed input file from the input file, wherein the compressed input file includes the consensus sequence and the pointer pairs for all of the rows of the compression matrix.
Dependencies are inferred from the claim text.