Token stream differencing with moved-block detection

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.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS[0001]This application is a continuation application of and claims priority to U.S. application Ser. No. 10 / 272,858 filed on Oct. 16, 2002. The disclosure of the prior application is considered part of (and is incorporated by reference in) the disclosure of this application.BACKGROUND OF THE INVENTION[0002]The present application describes systems and techniques relating to token stream differencing, for example, comparison of text documents to identify document changes.[0003]Various techniques exist for comparing token streams. Such comparison is commonly referred to as differencing or as a diff operation. Differencing two token streams typically involves comparing two versions of a token stream, commonly referred to as the original stream and the modified stream, and looking for differences between them. In the context of text comparison, many differencing processes use individual text characters or words as the tokens. Such diff processes ar...

AI Technical Summary

Benefits of technology

The invention is about a system and method for identifying and matching tokens in a text document to represent changes in document flow. The system obtains a first and second token stream from the text document, compares them to identify common sub-sequences, and presents the matched information as a representation of the changes in document flow. The system can also identify additional matched blocks of tokens and present them for further analysis. The technical effects of the invention include improved accuracy in identifying changes in document flow and improved efficiency in analyzing text documents.

Problems solved by technology

Moreover, when such techniques actually do identify moved blocks, the displayed results can be very confusing because small additions and / or deletions within a moved block of text can create a checker-boarding effect in the generated results, where moved and unmoved words interleave each other, thus cluttering the results report.

Images