Token stream differencing with moved-block detection
AssigneeAdobe Systems Incorporated
InventorsWilliam Ie, Adam E. Altman, Edward R. W. Rowe
Life of this patent
Estimating the term…
Abstract
Methods and apparatus implementing systems and techniques for differencing token streams and detecting moved blocks of tokens. In general, in one implementation, the technique includes: obtaining a first token stream and a second token stream, comparing the first and second token streams to identify a group of tokens that are substantially similar in the first and second token streams, the similar-tokens group including common sub-sequences, which are identical in the first and second token streams, and at least one unmatched token, and presenting matched token information corresponding to the similar-tokens group to represent changes in document flow.
Claims41
A method comprising:
- obtaining a first token stream and a second token stream;
- comparing the first and second token streams to identify a group of tokens that are substantially similar in the first and second token streams, the similar-tokens group including common sub-sequences, which are identical in the first and second token streams, and at least one unmatched intervening token separating the common sub-sequences;
- and
- representing matched token information corresponding to the similar-tokens group to represent changes in document flow.
A method comprising:
- identifying sub-sequences common to a first token stream and a second token stream;
- designating a first block of sub-sequences in the first token stream, the first block of sub-sequences including two or more of the identified common sub-sequences;
- designating a second block of sub-sequences in the second token stream, the second block of sub-sequences including the two or more of the identified common sub-sequences, wherein at least one of the first and second blocks includes one or more intervening tokens separating at least two of the two or more of the identified common sub-sequences;
- and
- designating the first and second blocks as a matched block pair based on a result of a comparison of a difference between the first and second blocks and a difference threshold.
A software product tangibly stored on a machine-readable medium, the software product comprising instructions operable to cause a programmable processor to perform operations comprising:
- identifying sub-sequences common to a first token stream and a second token stream;
- designating a first block of sub-sequences in the first token stream, the first block of sub-sequences including two or more of the identified common sub-sequences;
- designating a second block of sub-sequences in the second token stream, the second block of sub-sequences including the two or more of the identified common sub-sequences, wherein at least one of the first and second blocks includes one or more intervening tokens separating at least two of the two or more of the identified common sub-sequences;
- and
- designating the first and second blocks as a matched block pair based on a result of a comparison of a difference between the first and second blocks and a difference threshold.
A software product tangibly stored on a machine-readable medium, the software product comprising instructions operable to cause a programmable processor to perform operations comprising:
- obtaining a first token stream and a second token stream;
- comparing the first and second token streams to identify a group of tokens that are substantially similar in the first and second token streams, the similar-tokens group including common sub-sequences, which are identical in the first and second token streams, and at least one unmatched intervening token separating the common sub-sequences;
- and
- presenting matched token information corresponding to the similar-tokens group to illustrate changes in document flow.
A system comprising:
- means for obtaining a first token stream and a second token stream;
- and
- means for comparing the first and second token streams to detect a matched block of tokens including matched sub-sequences moved from first positions in the first token stream to second positions in the second token stream, the matched block of tokens also including at least one unmatched intervening token separating the matched sub-sequences, and the matched block of tokens being substantially similar in the first and second token streams.
Dependencies are inferred from the claim text.