# US 2017/0255670 A1 · Method, apparatus, system, and computer program product for data compression

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2017/0255670 A1
- Document ID: US20170255670A1
- Status: Published application
- Kind: A1
- Application number: 15/444,256
- Filed: 2017-02-27
- Published: 2017-09-07
- Earliest claimed: 2016-03-02
- Assignees: Qijian Software (Beijing) Co., Ltd.
- Applicants: Qijian Software (Beijing) Co., Ltd.
- Inventors: Peng LEI
- Web page: https://patentgrep.com/patent/US20170255670A1

## CPC

- H03M 7/3097: {Grammar codes}
- H03M 7/3091: {Data deduplication}
- H03M 7/55: {Compression Theory, e.g. compression of random number, repeated compression}
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

According to one aspect of the present application, a method for data compression comprises: creating a first trie for a first set of strings, the first set of strings comprising a plurality of raw data strings, wherein a trie consists of a plurality of nodes linked through parent-child relation, and wherein each edge of the trie is of at least one character and the edge corresponds to a state transition from a parent node of the edge to a child node of the edge; collecting edges of the first trie longer than a predetermined length and making these edges a first subset of strings of the first trie; segmenting a string in the first subset of strings into two or more fragments when the string satisfies a predetermined condition and collecting all segmented fragments and all un-segmented strings in the first subset of strings as a segmented set of strings; and storing the first set of strings using the first trie and the segmented set of strings so as to compress the raw data strings.

## Claims

### Claim 1

A method for data compression, comprising:
(1) creating a first trie for a first set of strings, the first set of strings comprising a plurality of raw data strings, wherein a trie consists of a plurality of nodes linked through parent-child relation, and wherein each edge of the trie is of at least one character and the edge corresponds to a state transition from a parent node of the edge to a child node of the edge;
(2) collecting edges of the first trie longer than a predetermined length and making these edges a first subset of strings of the first trie;
(3) segmenting a string in the first subset of strings into two or more fragments when the string satisfies a predetermined condition and collecting all segmented fragments and all un-segmented strings in the first subset of strings as a segmented set of strings; and
(4) storing the first set of strings using the first trie and the segmented set of strings so as to compress the raw data strings.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of segmenting the string in the first subset of strings comprises:
identifying one or more predetermined characters of a string in the first subset of strings as a segmentation mark; and
segmenting the string into fragments based on one or more identified segmentation marks.

### Claim 3 (depends on 1)

The method of claim 1, wherein the step of segmenting the string in the first subset of strings comprises:
matching a string in the first subset of strings with a predetermined library of strings to find one or more fragments of the string that hit a match in the predetermined library; and
segmenting the string into matched fragments.

### Claim 4 (depends on 1)

The method of claim 1, wherein the predetermined condition is that a length of the string reaches a predetermined value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the step of storing the first set of strings comprises:
providing the segmented set of strings as a second set of strings;
creating a second trie and a second subset of strings for the second set of strings; and
storing the second set of strings using the second trie and the second subset of strings.

### Claim 6 (depends on 5)

The method of claim 5, wherein the step of storing the first set of strings further comprises:
reversing the segmented set of strings; and
providing the reversed segmented set of strings as the second set of strings.

### Claim 7 (depends on 5)

The method of claim 5, wherein the step of storing the first set of strings further comprises:
associating a respective node of the first trie with a corresponding node of the second trie.

### Claim 8 (depends on 5)

The method of claim 5, wherein the step of storing the first set of strings further comprises:
storing the second subset of strings as a string array, wherein each string in the second subset of strings is represented by a respective offset and length in the string array.

### Claim 9 (depends on 1)

The method of claim 1, wherein the plurality of raw data strings comprise characters, numbers, and symbols in one or more languages.

### Claim 10 (depends on 1)

The method of claim 1, wherein the plurality of raw data strings comprise search keywords and search suggestions matching the search keywords.

### Claim 11 (depends on 1)

The method of claim 1, wherein the plurality of raw data strings comprise instant messaging chat records.

### Claim 12 (depends on 1)

The method of claim 1, wherein the plurality of raw data strings comprise web-page contents.

### Claim 13 (depends on 1)

The method of claim 1, wherein the first trie supports reverse search to facilitate access of the first set of strings.

### Claim 14 (depends on 13)

The method of claim 13, wherein the first trie is implemented by a LOUDS (Level Ordered Unary Degree Sequence) trie.

### Claim 15 (depends on 14)

The method of claim 14, wherein the LOUDS trie is operated by rank and select operations in succinct data structure.

### Claim 16

An apparatus for data compression, comprising:
means for creating a first trie for a first set of strings, the first set of strings comprising a plurality of raw data strings, wherein a trie consists of a plurality of nodes linked through parent-child relation, and wherein each edge of the trie is of at least one character and the edge corresponds to a state transition from a parent node of the edge to a child node of the edge;
means for collecting edges of the first trie longer than a predetermined length and making these edges a first subset of strings of the first trie;
means for segmenting a string in the first subset of strings into two or more fragments when the string satisfies a predetermined condition and collecting all segmented fragments and all unsegmented strings in the first subset of strings as a segmented set of strings; and
means for storing the first set of strings using the first trie and the segmented set of strings so as to compress the raw data strings.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the means for segmenting the string in the first subset of strings comprises:
means for identifying one or more predetermined characters of a string in the first subset of strings as a segmentation mark; and
means for segmenting the string into fragments based on one or more identified segmentation marks.

### Claim 18 (depends on 16)

The apparatus of claim 16, wherein the means for segmenting the string in the first subset of strings comprises:
means for matching a string in the first subset of strings with a predetermined library of strings to find one or more fragments of the string that hit a match in the predetermined library; and
means for segmenting the string into matched fragments.

### Claim 19 (depends on 16)

The apparatus of claim 16, wherein the predetermined condition is that a length of the string reaches a predetermined value.

### Claim 20 (depends on 16)

The apparatus of claim 16, wherein the means for storing the first set of strings comprises:
means for providing the segmented set of strings as a second set of strings;
means for creating a second trie and a second subset of strings for the second set of strings; and
means for storing the second set of strings using the second trie and the second subset of strings

### Claim 21 (depends on 20)

The apparatus of claim 20, wherein the means for storing the first set of strings further comprises:
means for reversing the segmented set of strings; and
means for providing the reversed segmented set of strings as the second set of strings.

### Claim 22 (depends on 20)

The apparatus of claim 20, wherein the means for storing the first set of strings further comprises:
means for associating a respective node of the first trie with a corresponding node of the second trie.

### Claim 23 (depends on 20)

The apparatus of claim 20, wherein the means for storing the first set of strings further comprises:
means for storing the second subset of strings as a string array, wherein each string in the second subset of strings is represented by a respective offset and length in the string array.

### Claim 24 (depends on 16)

The apparatus of claim 16, wherein the plurality of raw data strings comprise characters, numbers, and symbols in one or more languages.

### Claim 25 (depends on 16)

The apparatus of claim 16, wherein the plurality of raw data strings comprise search keywords and search suggestions matching the search keywords.

### Claim 26 (depends on 16)

The apparatus of claim 16, wherein the plurality of raw data strings comprise instant messaging chat records.

### Claim 27 (depends on 16)

The apparatus of claim 16, wherein the plurality of raw data strings comprise web-page contents.

### Claim 28 (depends on 16)

The apparatus of claim 16, wherein the first trie supports reverse search to facilitate access of the first set of strings.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein the first trie is implemented by a LOUDS (Level Ordered Unary Degree Sequence) trie.

### Claim 30 (depends on 29)

The apparatus of claim 29, wherein the LOUDS trie is operated by rank and select operations in succinct data structure.

### Claim 31

A system for data compression, comprising:
a trie creation unit (1601) for creating a first trie for a first set of strings, the first set of strings comprising a plurality of raw data strings, wherein a trie consists of a plurality of nodes linked through parent-child relation, and wherein each edge of the trie is of at least one character and the edge corresponds to a state transition from a parent node of the edge to a child node of the edge, wherein edges of the first trie longer than a predetermined length are collected to form a first subset of strings of the first trie;
a determination/segmentation unit (1602) for segmenting a string in the first subset of strings into two or more fragments when the string satisfies a predetermined condition, wherein all segmented fragments and all unsegmented strings in the first subset of strings are collected to form a segmented set of strings of the first trie;
a string storage unit (1603) for storing the segmented set of strings; and
a trie storage unit (1604) for storing the first trie.

### Claim 32 (depends on 31)

The system of claim 31, wherein the determination/segmentation unit (1602) identifies one or more predetermined characters of a string in the first subset of strings as a segmentation mark and segments the string into fragments based on one or more identified segmentation marks.

### Claim 33 (depends on 31)

The system of claim 31, wherein the determination/segmentation unit (1602) matches a string in the first subset of strings with a predetermined library of strings to find one or more fragments of the string that hit a match in the predetermined library and segments the string into matched fragments.

### Claim 34 (depends on 31)

The system of claim 31, wherein,
the string storage unit (1603) provides the segmented set of strings to the trie creation unit (1601) as a second set of strings;
the trie creation unit (1601) creates a second trie and a second subset of strings for the second set of strings;
the string storage unit (1603) stores the second subset of strings; and
the trie storage unit (1604) stores the second trie.

### Claim 35 (depends on 34)

The system of claim 34, wherein the trie storage unit (1604) associates a respective node of the first trie with a corresponding node of the second trie.

### Claim 36 (depends on 34)

The system of claim 34, wherein the system further comprises:
a string array storage unit (1605) stores the second subset of strings as a string array, wherein each string in the second subset of strings is represented by a respective offset and length in the string array.

### Claim 37

An apparatus for data compression, comprising:
a memory;
a processor coupled to the memory, wherein the processor is configured to:
create a first trie for a first set of strings, the first set of strings comprising a plurality of raw data strings, wherein a trie consists of a plurality of nodes linked through parent-child relation, and wherein each edge of the trie is of at least one character and the edge corresponds to a state transition from a parent node of the edge to a child node of the edge;
collect edges of the first trie longer than a predetermined length and make these edges a first subset of strings of the first trie;
segment a string in the first subset of strings into two or more fragments when the string satisfies a predetermined condition and collect all segmented fragments and all unsegmented strings in the first subset of strings as a segmented set of strings; and
store the first set of strings using the first trie and the segmented set of strings so as to compress the raw data strings.

### Claim 38

A computer program product for data compression, comprising:
a non-transitory computer-readable medium comprising computer-executable codes for:
creating a first trie for a first set of strings, the first set of strings comprising a plurality of raw data strings, wherein a trie consists of a plurality of nodes linked through parent-child relation, and wherein each edge of the trie is of at least one character and the edge corresponds to a state transition from a parent node of the edge to a child node of the edge;
collecting edges of the first trie longer than a predetermined length and make these edges a first subset of strings of the first trie;
segmenting a string in the first subset of strings into two or more fragments when the string satisfies a predetermined condition and collecting all segmented fragments and all unsegmented strings in the first subset of strings as a segmented set of strings; and
storing the first set of strings using the first trie and the segmented set of strings so as to compress the raw data strings.
