Patent Document ID: 20150142853
Application ID: 14083483
Patent Flag: 0

Claim One:
1. A method for reconstruction comprising: providing a directed input graph generated from a set of n-grams and statistics for the n-grams, edges of the graph being joined through nodes of the graph, each edge having an associated label and a multiplicity of at least one, each of the n-grams in the set being represented by a respective one of the labels, whereby a Eulerian cycle through the graph traverses each edge the respective multiplicity of times; with a processor, iteratively applying a plurality of reduction rules to generate a refined graph, the reduction rules comprising: a first reduction rule configured for identifying a division point node of the input graph, or of a refined graph generated therefrom, which divides the respective graph into at least two connected components and wherein there is a unique incoming edge to the division point node in the first connected component and a unique outgoing edge from the division point node in the second connected component, the first reduction rule configured for generating a new edge with a label which is derived from the labels of the unique incoming edge and the unique outgoing edge; and a second reduction rule configured for identifying a node of the input graph or of a refined graph generated therefrom which includes a first incoming edge and a first outgoing edge for which the multiplicity of one of the first incoming edge and the first outgoing edge is greater than a degree of the node minus the multiplicity of the other of the first incoming edge and the first outgoing edge, where the degree of the node is a sum of incoming edges of the node multiplied by their multiplicities, the second reduction rule configured for merging the first incoming edge and the first outgoing edge to create a new edge with a label which is derived from the first incoming edge and the first outgoing edge; and after the applying of the plurality of reduction rules, outputting information based on the labels of the refined graph.