Method to identify and extract fragments among large collections of digital documents using repeatability and semantic information

A fragment extraction and reconstruction system comprising:

• one or more processors;
• a sequencer, executed by the one or more processors, configured to serialize document elements extracted from a document, and generate a document element identifier (ID) sequence that comprises a list of the serialized document elements;
• an indexer, executed by the one or more processors, configured to (a) generate a suffix array that includes a plurality of suffixes of the document element ID sequence arranged according to a defined order and (b) generate a longest common prefix (LCP) array including a LCP between ith and (i+1)th elements of the suffix array;
• a fragment manager, executed by the one or more processors, configured to (a) update a generalized longest common prefix (GLCP) array that indicates a maximum size of the plurality of suffixes that occur at least a min_occur number of times between the ith and the (ith+min_occur) elements in the LCP array, and (b) identify, from the plurality of suffixes in the GLCP array having the maximum size of the plurality of suffixes that occur at least the min_occur number of times, a particular fragment candidate having a fragment size greater than a minimum fragment size;
• and
• a reconstruction engine, executed by the one or more processors, configured to use the particular fragment candidate to reconstruct the document.

A computer program product including one or more non-transitory machine-readable mediums encoded with instructions that when executed by one or more processors cause a process to be carried out for performing fragment extraction and reconstruction, said process comprising:

• receiving a document comprising a set of document elements;
• extracting and serializing the document elements to generate a document element identifier (ID) sequence that comprises a list of the document elements;
• generating a suffix array that includes a plurality of suffixes of the document element ID sequence arranged according to a defined order;
• generating a longest common prefix (LCP) array including a LCP between ith and (i+1)th elements of the suffix array;
• updating a generalized longest common prefix (GLCP) array that indicates a maximum size of the plurality of suffixes that occur at least a min_occur number of times between the ith and the (ith+min_occur) elements in the LCP array;
• identifying, from the plurality of suffixes in the GLCP array having the maximum size of the plurality of suffixes that occur at least the rnin_occur number of times, a particular fragment candidate having a fragment size greater than a minimum fragment size;
• and
• using the particular fragment candidate to reconstruct the document.