JP7529673B2 - Content-agnostic file indexing method and system - Google Patents

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
This application is a continuation-in-part of patent application Ser. No. 15/730,043, filed Oct. 11, 2017, and entitled "Method and System for Content Agnostic File Indexing," the contents of which are hereby incorporated by reference in their entirety for all purposes.

(Computer Program Listing - Sequence Listing)
The following computer program listing is submitted herewith and incorporated by reference. Each file is incorporated by reference. The computer program listing below is in the following format: <size in bytes><creationdate><filename>.

3864 May 16 2018 squeeze-master-README-md.txt*

83675 May 16 2018 squeeze-master-SqueezeReport-ipynb.txt*

4293 May 16 2018 squeeze-master-demo_app-py.txt*

98 May 16 2018 squeeze-master-gitignore.txt*

1383 May 16 2018 squeeze-master-requirements.txt*

2490 May 16 2018 squeeze-master-rpc_server-py.txt*

239 May 16 2018 squeeze-master-scripts-buildprotos.txt*

942 May 16 2018 squeeze-master-scripts-file_test-py.txt*

1391 May 16 2018 squeeze-master-scripts-generate_key-py.txt*

711 May 16 2018 squeeze-master-scripts-generate_keyset-py.txt*

629 May 16 2018 squeeze-master-scripts-keys_from_folder-py.txt*

377 May 16 2018 squeeze-master-scripts-lzw_test-py.txt*

107 May 16 2018 squeeze-master-scripts-runserver.txt*

3928 May 16 2018 squeeze-master-scripts-squeeze-bytes-report-py.txt*

63 May 16 2018 squeeze-master-scripts-squeeze_file-py.txt*

1060 May 16 2018 squeeze-master-scripts-squeeze_test-py.txt*

947 May 16 2018 squeeze-master-scripts-string_test-py.txt*

222 May 16 2018 squeeze-master-scripts-test_binary-py.txt*

1799 May 16 2018 squeeze-master-scripts-test_rpc-py.txt*

2736 May 16 2018 squeeze-master-scripts-time-squeeze-string-py.txt*

211 May 16 2018 squeeze-master-scripts-time_keygen-py.txt*

65 May 16 2018 squeeze-master-scripts-unsqueeze_file-py.txt*

80 May 16 2018 squeeze-master-setup-py.txt*

10657 May 16 2018 squeeze-master-squeeze- _ init _ -py.txt*

2783 May 16 2018 squeeze-master-squeeze-bitstring-py.txt*

9191 May 16 2018 squeeze-master-squeeze-keys-py.txt*

613 May 16 2018 squeeze-master-squeeze-performance-csv.txt*

22445 May 16 2018 squeeze-master-squeeze-squeeze_pb2-py.txt*

2232 May 16 2018 squeeze-master-squeeze-squeeze_pb2_grpc-py.txt*

3366 May 16 2018 squeeze-master-squeeze-proto.txt*

875 May 16 2018 squeeze-master-templates-layout-html.txt*

816 May 16 2018 squeeze-master-templates-upload_form-html.txt*

1513 May 16 2018 squeeze-master-templates-uploaded_file-html.txt*

200 May 16 2018 squeezerpc-master-Makefile.txt*

1131 May 16 2018 squeezerpc-master-README-md.txt*

7 May 16 2018 squeezerpc-master-gitignore.txt*

8995 May 16 2018 squeezerpc-master-main-go.txt*

21292 May 16 2018 squeezerpc-master-squeeze-squeeze-pb-go.txt*

3366 May 16 2018 squeezerpc-master-squeeze-proto.txt*

The present disclosure relates to a method for content agnostic file referencing. The method further relates to a method for content agnostic data compression.

File referencing techniques typically require knowledge of the type of data being stored in order to efficiently index the data in the file referencing system. Similarly, knowledge of the data in question is typically used in creating improved compression approaches to reduce the size of data for transmission, storage, etc.

There is a need in the industry for improved file referencing and data compression techniques to reduce the amount of data that must be stored and/or transmitted.

According to one embodiment, the present disclosure provides a method for improving computing technology using an enhanced content-agnostic file referencing system, which improves the operation of the computer itself.

The disclosed method has several important advantages. For example, the disclosed method allows file references of any content type.

The disclosed method may further significantly reduce the amount of information or data that must be persisted or transmitted because the data may be generated at the time of access, as opposed to being persisted.

Various embodiments of the present disclosure may have none, some, or all of these advantages. Other technical advantages of the present disclosure may be readily apparent to those skilled in the art.

For a more complete understanding of the present disclosure and its advantages, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:
The same reference numbers refer to the same parts or steps throughout the several views of the drawings.
1 is a flow chart outlining the steps of one embodiment of the present disclosure. 4 is another flowchart outlining the steps of another embodiment of the present disclosure. 1 is a flow chart outlining the steps of an alternative embodiment of the present disclosure.

This disclosure relates to a method for content-agnostic indexing of data. The method can be used for a variety of computer-specific needs, such as, for example, as a file referencing system or a compression system.

In the following disclosure, the invention is described with respect to compressing binary data as an example, but the teachings work equally well with any type of data that is better referred to as "n-ary" data. For example, the methods and systems also work with qubits and bits.

One embodiment of the present invention includes a method as described in the flow chart depicted in Figure 1. Binary data (n _i ) to be persisted or transmitted (e.g., a data file) is analyzed to determine its length in bits (l(n _i )). Using this information, in step 106, the method calculates all permutations of data of the identified length. For example, if the input data is:
01

The input data is 2 bits long. In step 106, all permutations of the 2 bits are generated, namely:
{00}{01}{10}{11}

At step 108, the method determines the index ( _nf ) of the input binary data file in the generated permutation. In the above example, the returned index ( _nf ) would be "1." Finally, rather than storing or transmitting the input binary data (i.e., "01"), the system instead stores the length (2) and index (1).

When the original input data needs to be decoded (e.g., a request to retrieve the original binary data from a disk or receiving data sent over a network), the method only requires the length (l(n _i )) and index (n _f ) as input. In the above example, the inputs are length (2) and index (1). As shown in Figure 2, the system computes all permutations of the input length. In the above example, the following permutations are generated:
{00}{01}{10}{11}

The system moves to the specified index (1 in the above example) and returns the permutation. Again, using the above example, the original binary data "01" is returned.

The above method is described in terms of a binary system (i.e., the input data is binary data) for illustrative purposes. The method and system work similarly for n-ary systems. Although the above binary system essentially operates in the Euclidean plane, for n-ary data, Hilbert space offers the same conceptual advantages. The method and process can be generalized to n-ary data as follows.
d^n=p(i)
(d^n)n=p(f)
d = system order n = length in n-ary units appropriate to the system order p(i) = initial index p(f) = final index

It should be noted that given two alternative ordered systems with the same input file, the system with the higher order will have a higher n-ary density compared to the alternative system with the lower order.

An example of this method is disclosed in the following Ruby code snippet: The following snippet illustrates the method as disclosed in FIG.

The following snippet illustrates the method disclosed in FIG. 2 for an input length (l(n _i )) of 16 and an index (n _f ) of 72,629.

In a preferred embodiment, an input byte string is converted into a bit string that corresponds to a representation of the input byte string. This bit string is then processed by the methods described herein.

In an alternative embodiment, rather than generating a table based on the length of the data, a table may be pre-generated with all permutations of data of a particular length. This pre-generated table may be persisted in memory, either non-volatile or volatile. In the above example, if the given length is 2 bits, the pre-generated table would include all permutations of 2-bit data such as:
{00}{01}{10}{11}

In one embodiment, this table may be stored in a correspondingly indexed array as follows:

This pre-generated table may be stored on disk, in RAM, etc. Preferably, this pre-generated table is stored on the computer system that reduces the file size (or squeezes the file) and on the computer system that expands the reduced file (or unsqueezes the data).

Upon receiving input data, the method "chunks" the data into smaller subsets. As used herein, "chunking" means taking a data string and creating smaller data strings that constitute subsets of the larger data string. All the chunks taken together make up the original data string. For example, if the input data is 011001110001
If,

It will be chunked into the following 4-bit chunks:
0010 0111 0001

Then each chunk is compared to the pre-generated table to see if there is a match. In the above example, if the chunk size is 4 bits, each chunk will not be found in the table since the table has all the permutations of the 2-bit chunks. Therefore, each chunk is re-chunked, as follows:
01 10 01 11 00 01

This method continues for each chunk until the particular chunk is placed in the pre-generated table. At that point, the chunk is associated with a respective index and preferably a series of tuples are generated indicating the chunk level and the corresponding index. In the above example, the system chunked twice, so the index associations are as follows:
{2,1}{2,2}{2,1}{2,3}{2,0}{2,1}

In this example, the original input data "011001110001" was ultimately split into 6 chunks of 2-bit length. As shown, each chunk is represented by its chunk level (2) and a corresponding index into the pre-generated table.

The data may be chunked in any number of ways. For example, the data may be chunked based on a pre-determined size, as in the example above (where the pre-determined size was 4 bits for purposes of the example). Alternatively, the input data may be recursively chunked into two separate data chunks until each data chunk is found in the pre-generated table. Using the same input data as above, the method of splitting and chunking the data would result in the following first level chunks:
011001 110001

Here, the dataset is not found in the pre-generated table and is therefore re-chunked.
011 001 110 001

Again, the chunked data cannot be found in the pre-generated table and must be re-chunked.
00 1 00 1 11 0 00 1

It is worth noting that some segments have been chunked into data smaller than the size of the pre-generated table (i.e. segments "1", "1", "0", "1"). These segments may be padded to make them comparable to the pre-generated table. As long as consistency is maintained, numbers may be stored in either big-endian or little-endian byte order. For example, using big-endian byte order, the above chunked data would be represented as follows:
00 10 00 10 11 00 00 10

The method then continues as above.

It is not necessary that all chunks of data be found in the pre-generated tables at the same data chunk level. For example, using the above pre-generated tables for 2-bit combinations, if the input data is:
0110011100

This data can be essentially chunked into sequences of 4 bits as described above.
0110 0111 00

Similar to above, the first two 4-bit sequences (i.e., “0110” and “0111”) must be re-chunked into smaller chunks in order to be placed into the pre-generated table, resulting in the following chunks:
01 10 01 11 00

Also, as above, chunks are associated with their chunk level and corresponding index as follows:
{2,1}{2,2}{2,1}{2,3}{1,0}

Note that the last tuple above indicates that the chunk level is 1, since the chunk did not require a second chunking.

Once the input data is reduced to a set of chunk levels and indices, the set of chunk levels and indices is used to identify the original data. The associations can be stored as a set of tuples, as individual bit strings, and in other ways.

To recreate (or unsqueeze) the data based on a set of chunk levels and indexes, the process works in reverse. In this case, the system still needs the same pre-generated tables. For each chunk level and index tuple, the system consults the pre-generated tables to unpack the squeezed chunk back into the original data.

This alternative embodiment is illustrated in the flow chart of FIG. 3. First, a pre-generated table is created in step 302 that contains all permutations of data of a particular length, such as: 1 x ...

While the present disclosure has been described in terms of specific embodiments and generally associated methods, modifications and permutations of these embodiments and methods will be apparent to those skilled in the art. Thus, the above description of exemplary embodiments does not constrain the present disclosure. Other changes, substitutions, and alterations are possible without departing from the spirit and scope of the present disclosure.
[Appendix 1]
1. A computer-implemented method for content-agnostic browsing of a binary data file, comprising:
pre-generating a table using an input seed, the table containing all permutations of bits of a predetermined length;
determining a length of the binary data file, the length comprising a number of bits in the binary data file;
chunking the binary data file into substrings, each substring being of a length less than a length of the binary data file;
for each chunk of the binary data file, determining whether the chunk is within the pre-generated table, and if the chunk is within the pre-generated table, associating with the chunk an index of the chunk's location within the pre-generated table, and if the chunk is not within the pre-generated table, splitting the chunked binary data into smaller chunks;
and indicating the binary data file using a number of chunks and associated indices of all chunks.
[Appendix 2]
indicating the binary data file using the number of chunks and associated indices of all chunks,
2. The method of claim 1, further comprising persisting the number of chunks and all associated indexes to a storage device in place of the binary data file.
[Appendix 3]
indicating the binary data file using the number of chunks and associated indices of all chunks,
2. The method of claim 1, comprising sending the number of chunks and associated indices of all chunks instead of the data file.
[Appendix 4]
4. The method of claim 3, wherein the transmitting step transmits the number of chunks and associated indices of all chunks over a network.
[Appendix 5]
4. The method of claim 3, wherein the transmitting step transmits the number of chunks and associated indices of all chunks over a bus.
[Appendix 6]
indicating the binary data file using the number of chunks and associated indices of all chunks,
2. The method of claim 1, comprising creating a tuple of ordered pairs, each ordered pair indicating a chunk level and an associated index.
[Appendix 7]
2. The method of claim 1, wherein the step of indicating the binary data file using the number of chunks and associated indexes of all chunks includes persisting the number of chunks and associated indexes of all chunks on a storage device.
[Appendix 8]
8. The method of claim 7, wherein the storage device is a disk.
[Appendix 9]
2. The method of claim 1, wherein the pre-generated table is a hash table.
[Appendix 10]
2. The method of claim 1, wherein the pre-generated table is a matrix.
[Appendix 11]
2. The method of claim 1, wherein the pre-generated table is persisted in volatile memory.
[Appendix 12]
2. The method of claim 1, wherein the pre-generated table is persisted in non-volatile memory.
[Appendix 13]
Chunking the binary data file into substrings further comprises:
2. The method of claim 1, comprising chunking the binary data into chunks of a predetermined length.
[Appendix 14]
14. The method of claim 13, wherein the predetermined length is 2 megabytes.
[Appendix 15]
14. The method of claim 13, wherein the predetermined length is less than 2 megabytes.
[Appendix 16]
14. The method of claim 13, wherein the predetermined length is greater than 2 megabytes.
[Appendix 17]
Chunking the binary data file into substrings further comprises:
2. The method of claim 1, comprising recursively splitting the binary data file into two chunks of equal size.
[Appendix 18]
1. A method for retrieving data based on a number of chunks and associated indexes of all chunks, comprising:
pre-generating a table using an input seed, the table containing all permutations of bits of a given length, and generating a number of chunks and associated indexes using the pre-generated table;
The method includes the steps of: for each chunk, locating data in a table at an index associated with the chunk; and returning data associated with each chunk.
[Appendix 19]
The steps to return the data associated with each chunk are:
19. The method of claim 18, comprising concatenating data associated with each chunk into a single bitstream.

Claims (17)

1. An information processing method for content-agnostic referencing of binary data files executed on a computer system, comprising:
using said computer system to pre-generate a table using an input seed, the table containing all permutations of bits of a predetermined length;
using the computer system to determine a length of the binary data file, the length comprising a number of bits in the binary data file;
using the computer system, chunking the binary data file into substrings, each substring being of a length less than a length of the binary data file;
using the computer system to determine, for each chunk of the binary data file, whether the chunk is within the pre-generated table, and if the chunk is within the pre-generated table, associating with the chunk an index of the chunk's location within the pre-generated table, and if the chunk is not within the pre-generated table, splitting the chunked binary data into smaller chunks;
and using the computer system to index the binary data file using a number of chunks and associated indices of all chunks. indicating the binary data file using the number of chunks and associated indices of all chunks,
The method of claim 1 , further comprising persisting the number of chunks and any associated indexes to a storage device in place of the binary data file. indicating the binary data file using the number of chunks and associated indices of all chunks,
The method of claim 1 , comprising transmitting a number of chunks and associated indices of all chunks in place of the binary data file . The method of claim 3, wherein the transmitting step transmits the number of chunks and associated indices of all chunks over a network. 4. The method of claim 3, wherein the transmitting step transmits the number of chunks and associated indices of all chunks over a bus. indicating the binary data file using the number of chunks and associated indices of all chunks,
The method of claim 1 , comprising creating a tuple of ordered pairs, each ordered pair indicating a chunk level and an associated index. The method of claim 1, wherein the step of indicating the binary data file using the number of chunks and associated indexes of all chunks includes persisting the number of chunks and associated indexes of all chunks on a storage device. The method of claim 7, wherein the storage device is a disk. The method of claim 1, wherein the pre-generated table is a hash table. The method of claim 1, wherein the pre-generated table is a matrix. The method of claim 1, wherein the pre-generated table is persisted in volatile memory. The method of claim 1, wherein the pre-generated table is persisted in non-volatile memory. Chunking the binary data file into substrings further comprises:
The method of claim 1 , comprising chunking the binary data into chunks of a predetermined length. The method of claim 13, wherein the predetermined length is 2 megabytes. The method of claim 13, wherein the predetermined length is less than 2 megabytes. The method of claim 13, wherein the predetermined length is greater than 2 megabytes. Chunking the binary data file into substrings further comprises:
2. The method of claim 1, comprising recursively splitting the binary data file into two chunks of equal size.

Images