Back to results
US 12,511,260 B2Granted
File compression using 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. The result is a compression matrix, where each row of the matrix corresponds to part of the file. A consensus sequence id 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.
Claims20
A method, comprising:
- receiving an input file into a compression engine, wherein the compression engine comprises one or more hardware processors configured to perform alignment-based compression using a consensus-based pointer encoding scheme;
- aligning the input file to create a compression matrix that includes rows of sequences, wherein aligning the input file includes splitting the input file into multiple sequences and inserting gaps into at least some of the sequences such that each column of the compression matrix includes identical data or a gap, wherein each entry in the sequences represents n bits of the input file, and wherein the alignment disallows mismatches and allows gaps;
- determining a consensus sequence from the compression matrix, wherein the consensus sequence includes an entry from each of the columns and does not include any gaps;
- 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 each pointer pair comprises either (i) a first pointer and a second pointer that identify, respectively, starting and ending entries of the portion in the consensus sequence, or (ii) a first pointer and a length of the portion starting from the first pointer, and
- determining whether each pointer pair requires fewer bits to encode than a corresponding literal subsequence;
- and
- using pointer pairs instead of corresponding literal subsequences when the pointer pairs require fewer bits to encode;
- and
- 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, wherein the input file is processed in a hierarchical manner by dividing the input file into portions, compressing each portion separately to generate respective intermediate compressed files including consensus sequences and pointer pairs, and combining the intermediate compressed files to produce the compressed input file.
8 more elements
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, wherein the compression engine comprises one or more hardware processors configured to perform alignment-based compression using a consensus-based pointer encoding scheme;
- aligning the input file to create a compression matrix that includes rows of sequences, wherein aligning the input file includes splitting the input file into multiple sequences and inserting gaps into at least some of the sequences such that each column of the compression matrix includes identical data or a gap, wherein each entry in the sequences represents n bits of the input file, and wherein the alignment disallows mismatches and allows gaps;
- determining a consensus sequence from the compression matrix, wherein the consensus sequence includes an entry from each of the columns and does not include any gaps;
- 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 each pointer pair comprises either (i) a first pointer and a second pointer that identify, respectively, starting and ending entries of the portion in the consensus sequence, or (ii) a first pointer and a length of the portion starting from the first pointer,
- determining whether each pointer pair requires fewer bits to encode than a corresponding literal subsequence;
- and
- using pointer pairs instead of corresponding literal subsequences when the pointer pairs require fewer bits to encode;
- and
- 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, wherein the input file is processed in a hierarchical manner by dividing the input file into portions, compressing each portion separately to generate respective intermediate compressed files including consensus sequences and pointer pairs, and combining the intermediate compressed files to produce the compressed input file.
8 more elements
Dependencies are inferred from the claim text.