# US 2004/0083091 A1 · Token stream differencing with moved-block detection

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0083091 A1
- Document ID: US20040083091A1
- Status: Published application
- Kind: A1
- Application number: 10/272,858
- Filed: 2002-10-16
- Published: 2004-04-29
- Earliest claimed: 2002-10-16
- Assignees: Adobe Systems Incorporated
- Inventors: William Ie; Adam E. Altman; Edward R. W. Rowe
- Web page: https://patentgrep.com/patent/US20040083091A1

## CPC

- G06F 40/284: Lexical analysis, e.g. tokenisation or collocates
- G06F 40/194: Calculation of difference between files
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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.

## Claims

### Claim 1

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 token; and
representing matched token information corresponding to the similar-tokens group to represent changes in document flow.

### Claim 2 (depends on 1)

The method of claim 1, wherein obtaining a first token stream and a second token stream comprises:
receiving text information; and
converting the text information into the first and second token streams.

### Claim 3 (depends on 2)

The method of claim 2, wherein the similar-tokens group comprises tokens corresponding to words in the text information, and wherein comparing the first and second token streams comprises:
using a predefined sequences differencing technique to identify sub-sequences of words common to the first and second token streams;
selecting a sub-sequence from the identified sub-sequences of words; and
extending the selected sub-sequence to include one or more additional sub-sequences and one or more intervening words from the first and second token streams in order to form the similar-tokens group.

### Claim 4 (depends on 1)

The method of claim 1, wherein obtaining a first token stream and a second token stream comprises:
receiving style information for one or more electronic documents; and
converting the style information into the first and second token streams.

### Claim 5 (depends on 1)

The method of claim 1, wherein obtaining a first token stream and a second token stream comprises:
receiving structure information representing structure of one or more electronic documents; and
converting the structure information into the first and second token streams representing structural elements of the one or more electronic documents.

### Claim 6 (depends on 1)

The method of claim 1, wherein:
representing matched token information includes presenting matched token information to a user.

### Claim 7 (depends on 6)

The method of claim 6, wherein:
presenting matched token information to a user includes displaying matched token information on a display device.

### Claim 8 (depends on 1)

The method of claim 1, wherein:
representing matched token information includes generating a third token stream incorporating tokens representing changes in document flow.

### Claim 9 (depends on 1)

The method of claim 1, further comprising:
obtaining additional common sub-sequences and one or more additional groups of tokens that are substantially similar in the first and second token streams;
combining matched sets of tokens based on their order in the first and second token streams while disregarding intervening tokens, the matched sets of tokens including the similar-tokens groups and the additional common sub-sequences; and
representing matched token information corresponding to the combined matched sets of tokens to represent changes in document flow.

### Claim 10 (depends on 9)

The method of claim 9, wherein combining matched sets of tokens comprises combining matched sets of tokens starting with a matched set of tokens having a longest common sub-sequence.

### Claim 11 (depends on 9)

The method of claim 9, wherein combining matched sets of tokens comprises combining matched sets of tokens starting with a longest of the matched sets of tokens.

### Claim 12 (depends on 9)

The method of claim 9, wherein representing matched token information based on the combined matched sets of tokens comprises displaying the first and second token streams using colors to designate the combined matched sets of tokens including the similar-tokens group that includes the at least one unmatched token.

### Claim 13 (depends on 12)

The method of claim 12, wherein displaying the first and second token streams using colors comprises displaying the first and second token streams side-by-side.

### Claim 14

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.

### Claim 15 (depends on 14)

The method of claim 14, further comprising:
grouping matched block pairs from the first and second token streams based on an order of the matched block pairs in the first and second token streams; and
representing matched block information based on the grouped matched block pairs.

### Claim 16 (depends on 15)

The method of claim 15, wherein the matched block pairs include identified common sub-sequences not included in any matched block pairs designated based on the difference threshold, and wherein grouping the matched block pairs comprises selecting the matched block pairs for grouping based on lengths.

### Claim 17 (depends on 16)

The method of claim 16, wherein selecting the matched block pairs for grouping comprises selecting the matched block pairs based on lengths of the identified common sub-sequences.

### Claim 18 (depends on 15)

The method of claim 15, wherein:
representing matched block information includes presenting matched block information to a user.

### Claim 19 (depends on 18)

The method of claim 18, wherein:
presenting matched block information to a user includes displaying matched block information on a display device.

### Claim 20 (depends on 18)

The method of claim 18, wherein:
representing matched block information includes generating a third token stream incorporating tokens representing changes between the first and second token streams.

### Claim 21 (depends on 14)

The method of claim 14, wherein the tokens in the first and second token streams comprise words in a language, and the first and second token streams correspond to a reading order for the words.

### Claim 22 (depends on 14)

The method of claim 14, wherein identifying the common sub-sequences comprises:
generating an editscript for the first and second token streams using a predefined sequences differencing technique; and
identifying the common sub-sequences using the generated editscript.

### Claim 23 (depends on 14)

The method of claim 14, wherein the difference threshold comprises a configurable difference threshold, and wherein designating the first and second blocks comprises designating the first and second blocks as a matched block pair based on a result of a comparison of the difference between the first and second blocks and the configurable difference threshold and based on a minimum length threshold.

### Claim 24 (depends on 23)

The method of claim 23, wherein the configurable difference threshold is configured based on a nature of the tokens in the first and second token streams.

### Claim 25 (depends on 14)

The method of claim 14, further comprising:
determining a quantity of the one or more intervening tokens that differ between the first block and the second block; and
determining the difference between the first block and the second block by dividing the quantity of differing tokens by a length of the two or more of the identified common sub-sequences.

### Claim 26

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.

### Claim 27 (depends on 26)

The software product of claim 26, wherein the operations further comprise:
grouping matched block pairs from the first and second token streams based on an order of the matched block pairs in the first and second token streams; and
presenting matched block information based on the grouped matched block pairs.

### Claim 28 (depends on 27)

The software product of claim 27, wherein the matched block pairs include identified common sub-sequences not included in any matched block pairs designated based on the difference threshold, and wherein grouping the matched block pairs comprises selecting the matched block pairs for grouping based on lengths.

### Claim 29 (depends on 26)

The software product of claim 26, wherein identifying the common sub-sequences comprises:
generating an editscript for the first and second token streams using a predefined sequences differencing technique; and
identifying the common sub-sequences using the generated editscript.

### Claim 30 (depends on 26)

The software product of claim 26, wherein the difference threshold comprises a configurable difference threshold, and wherein designating the first and second blocks comprises designating the first and second blocks as a matched block pair based on a result of a comparison of the difference between the first and second blocks and the configurable difference threshold and based on a minimum length threshold.

### Claim 31 (depends on 26)

The software product of claim 26, wherein the operations further comprise:
determining a quantity of the one or more intervening tokens that differ between the first block and the second block; and
determining the difference between the first block and the second block by dividing the quantity of differing tokens by a length of the two or more of the identified common sub-sequences.

### Claim 32

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 token; and
presenting matched token information corresponding to the similar-tokens group to illustrate changes in document flow.

### Claim 33 (depends on 32)

The software product of claim 32, wherein obtaining a first token stream and a second token stream comprises:
receiving text information; and
converting the text information into the first and second token streams.

### Claim 34 (depends on 33)

The software product of claim 33, wherein the similar-tokens group comprises tokens corresponding to words in the text information, and wherein comparing the first and second token streams comprises:
using a predefined sequences differencing technique to identify sub-sequences of words common to the first and second token streams;
selecting a sub-sequence from the identified sub-sequences of words; and
extending the selected sub-sequence to include one or more additional sub-sequences and one or more intervening words from the first and second token streams in order to form the similar-tokens group.

### Claim 35 (depends on 32)

The software product of claim 32, wherein the operations further comprise:
obtaining additional common sub-sequences and one or more additional groups of tokens that are substantially similar in the first and second token streams;
combining matched sets of tokens based on their order in the first and second token streams while disregarding intervening tokens, the matched sets of tokens including the similar-tokens groups and the additional common sub-sequences; and
presenting matched token information corresponding to the combined matched sets of tokens to illustrate changes in document flow.

### Claim 36 (depends on 35)

The software product of claim 35, wherein combining matched sets of tokens comprises combining matched sets of tokens starting with a matched set of tokens having a longest common sub-sequence.

### Claim 37 (depends on 35)

The software product of claim 35, wherein presenting matched token information based on the combined matched sets of tokens comprises displaying the first and second token streams using colors to designate the combined matched sets of tokens including the similar-tokens group that includes the at least one unmatched token.

### Claim 38

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 token, and the matched block of tokens being substantially similar in the first and second token streams.

### Claim 39 (depends on 38)

The system of claim 38, wherein the means for obtaining comprises:
means for receiving text information; and
means for converting the text information the first and second token streams.

### Claim 40 (depends on 38)

The system of claim 38, further comprising:
means for obtaining additional matched blocks of tokens from the first and second token streams, the additional matched blocks of tokens including at least one block having a single matched sub-sequence and no unmatched tokens;
means for grouping the matched blocks of tokens based on an order of the matched blocks of tokens in the first and second token streams while disregarding intervening tokens; and
means for presenting matched block information based on the grouped matched block pairs to illustrate changes in document flow.

### Claim 41 (depends on 40)

The system of claim 40, wherein the means for presenting matched block information comprises means for displaying the first and second token streams using colors to designate the grouped matched blocks of tokens including the matched block that includes the at least one unmatched token.
