Apparatus and method for comparing data groups

• US RE35,861 E
• Filed: 05/09/1996
• Issued: 07/28/1998
• Est. Priority Date: 03/12/1986
• Status: Expired due to Term

• Current Assignee: Advanced Software, Inc.
• Original Assignee: Advanced Software, Inc.
• Inventors: Queen, Cary L.
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US08/638,722
• Time in Patent Office: 810 Days
• Field of Search: 364/419.01, 364/419.08, 364/419.1, 364/419.13, 364/419.14, 364/419.17, 364/927.2, 364/927.61, 364/927.63, 364/934, 364/941, 364/941.5 , 364/943, 364/943.44, 364/943.5, 364/947, 364/947.1, 364/947.2, 364/955, 364/955.6, 364/957, 364/957.1, 364/957.3, 364/960, 364/960.1, 364/962 , 364/962.4, 364/DIG. 2, 395/144-146, 395/772, 395/792, 395/761, 395/793, 395/340, 395/602, 395/619
• US Class Current: 715/210
• CPC Class Codes: G06F 17/27 Automatic analysis, e.g. parsing speech recognition, analysis or synthesis G10L

Abstract

Method and apparatus for comparing original and modified versions of a document. The system of the present invention utilizes a hash number generator CPU to generate hash numbers for lines and sentences contained in the documents. Matching hash numbers are defined as anchorpoints and stored in an anchorpoint memory. A comparator CPU performs a character-by-character comparison of the respective documents radiating outward from each anchorpoint. This comparison generates identity blocks which are defined as blocks which are the same in both documents. Non-identity blocks are defined as difference blocks and are characterized as insertions or deletions depending on their status. A portion of the original and modified document is displayed in a split-screen format on a display, such as a CRT. Cursors on the top and bottom half of the screen identify corresponding portions of the documents. The second cursor is generated by taking advantage of the timer interrupt sequence of a CPU to direct the CPU to program instructions to generate the second cursor.

Claims

1. An automated .Iadd.text .Iaddend.comparison system, comprising:

input means for receiving commands, and for providing electronic signals representing a plurality of characters . .including.!. .Iadd.representing .Iaddend.words.Iadd., short groups of words or phrases, .Iaddend.and sentences;

memory means coupled to said input means for storing as binary representations at least first and second groups of said characters;

processing means coupled to said memory means and to said input means for detecting and identifying differences between said words.Iadd., short groups of words or phrases, .Iaddend.and sentences in said first and second groups of said characters .Iadd.when said differences do not consist of a line of text or a group of lines of text and regardless of whether or not the text wraps around an end of a line or a plurality of lines.Iaddend.;

display means coupled to said processing means for providing a display of said differences .Iadd.by displaying the text with the differences designated within the text lines.Iaddend..

2. The system of claim 1 wherein said processing means includes reading means for reading and comparing said first and second groups of characters from said memory means.

3. The system of claim 2 wherein said processing means includes writing means for writing said groups of characters from said memory means to said display means.

4. The system of claim 3 wherein said processing means includes first logic means for generating hash numbers, said hash numbers being derived from said binary representations of said characters in said first and second groups of characters such that identical groups of characters will result in identical hash numbers.

5. The system of claim 4 wherein said processing means includes comparison means for comparing hash numbers generated from sentences, words and characters of said first and second groups.

6. The system of claim 5 wherein said processing means includes second logic means for creating lists of data in said memory means.

7. The system of claim 6 wherein said processing means includes searching means for identifying and retrieving selected information from said lists of data.

8. The system of claim 7 wherein said processing means includes interrupt detection means for detecting the presence of an interrupt signal and transferring control to a selected location in said memory means.

9. The system of claim 8 wherein said processing means further includes timer means for generating a signal at designated intervals.

10. The system of claim 1 wherein said display means comprises a Cathode Ray Tube.

11. The system of claim 1 wherein said display means comprises a printer. . .12. A method for identifying and displaying the differences between first and second documents, said documents comprising groups of alphanumeric characters including words, lines and sentences comprising the steps of:

storing each of said documents in a memory;

generating hash numbers from said lines and sentences of each of said documents, such that identical lines and identical sentences produce identical corresponding hash numbers;

comparing hash numbers generated for said first document with hash numbers generated from said second document;

creating lists of anchorpoints in said memory, said anchorpoints representing matching hash numbers from each of said documents;

defining blocks of identical text in both documents containing at least one anchorpoint;

defining difference blocks of text not contained in said identity blocks;

storing in memory the location in each document of said identity and difference blocks;

classifying said identity and difference blocks into one of a plurality of classifications and storing said classifications in memory;

displaying said identity and difference blocks and said

12. classifications..!. 3. . .The.!. .Iadd.A .Iaddend.method . .as identified by claim 12 further comprising the step of.!. .Iadd.for identifying and displaying the differences between first and second documents, said documents comprising groups of alphanumeric characters, including words, lines and sentences comprising the steps of:

storing each of said documents in a memory;

generating hash numbers from said lines and sentences of each of said documents, such that identical lines and identical sentences produce identical corresponding hash numbers;

comparing hash numbers generated for said first document with hash numbers generated from said second document;

creating lists of anchorpoints in said memory, said anchorpoints representing matching hash numbers from each of said documents;

.Iaddend.

defining identity blocks .Iadd.of identical text in both documents containing at least one anchorpoint .Iaddend.by comparison of the characters in each document radiating outward from said anchorpoints;

.Iadd.defining difference blocks of text not contained in said identity blocks;

storing in memory the location in each document of said identity and difference blocks;

classifying said identity and difference blocks into one of a plurality of classifications and storing said classifications in memory;

displaying said identity and difference blocks and said

13. classifications.Iaddend.. 14. The method as defined by claim 13 further comprising the step of deleting from memory all anchorpoints contained

14. within each of said identity blocks. 15. The method as defined by claim 14 further comprising the step of associating a location of difference blocks in said first document with a corresponding location in said second

15. document. 16. The method as defined by claim 15 further comprising the step of repeating all above steps on successively smaller blocks or characters within said difference blocks to identify small identity blocks

16. within said difference blocks. 17. The method as defined by claim 16 wherein said small identity blocks comprise a selected number of

17. characters. 18. The method as defined by claim 17 further comprising the step of stimultaneously displaying selected portions of each document.

18. The method as defined by claim 18 further comprising the step of displaying said classifications of said identity and difference blocks.

19. The method as defined by claim 19 further comprising the step of simultaneously displaying corresponding blocks from said first and second

20. documents. 21. In a computer controlled display system having a display wherein first and second groups of characters are simultaneously displayed and differences between said first and second groups are indicated on said display, a method for displaying said groups and said differences comprising the steps of:

generating and displaying said first group of characters on a first region of said display;

generating and displaying said second group of characters on a second region of said display;

controlling the scrolling of said first and second regions so that the group of characters in said second region correspond to the group of characters in said first region;

determining differences between said first and second groups of characters;

generating and displaying indicators in said first and second regions, said indicators identifying said differences between said first and second groups of characters;

whereby said first and second groups of characters and said differences are

21. displayed. 22. The method of claim 21 further including the step of providing first and second cursors on said display, said first cursor displayed in said first region and said second cursor displayed in said second region, the position of said second cursor corresponding to the

22. position of said first cursor. .Iadd.23. An automated text comparison system, comprising:

input means for receiving commands, and for providing electronic signals representing a plurality of characters representing words, short groups of words or phrases, and sentences;

memory means coupled to said input means for storing as binary representations at least first and second groups of said characters;

processing means coupled to said memory means and to said input means for detecting and identifying differences and identities between said words, short groups of words or phrases, and sentences which are represented by said first and second groups of said characters;

said processing means for detecting and identifying differences and identities including means for detecting and identifying words, short groups of words or phrases, and sentences which are identical in said first and second groups of characters when said differences and identities do not consist of a line of text or a group of lines of text and regardless of whether or not the text wraps around an end of a line or a plurality of lines, wherein when said identities have been determined, the remaining characters are differences;

display means coupled to said processing means for providing a display of said differences by displaying the text with the differences designated

23. within the text lines..Iaddend..Iadd.24. An automated text comparison system according to claim 23 wherein said processing means further includes means operable when an identical word, short groups of words or phrase or sentence is detected in said first and second group of characters, for identifying the longest possible identical sequence of characters in said first and second group of characters which contain said identical word, short groups of words or phrase, or sentence..Iaddend..Iadd.25. An automated text comparison system, comprising:

input means for receiving commands, and for providing electronic signals representing a plurality of characters representing words, short groups of words or phrases, and sentences;

memory means coupled to said input means for storing as binary representations at least first and second groups of said characters when said words and short groups of words or phrases which are identical do not consist of a line of text or a group of lines of text;

processing means coupled to said memory means and to said input means for detecting and identifying differences between said words, short groups of words or phrases and sentences which are represented by said first and second groups of said characters;

said processing means for detecting and identifying differences including means for detecting and identifying words and short groups of words or phrases which are identical in said first and second group of characters and regardless of whether or not the text wraps around an end of a line or a plurality of lines, said words and short groups of words or phrases being contained in sentences that are not necessarily identical in said first and second groups of characters;

display means coupled to said processing means for providing a display of said differences by displaying the text with the differences designated

24. within the text lines..Iaddend..Iadd.26. An automated text comparison system, comprising:

input means for receiving commands, and for providing electronic signals representing a plurality of characters representing words, short groups of words or phrases, and sentences;

memory means coupled to said input means for storing as binary representations at least first and second groups of said characters;

processing means coupled to said memory means and to said input means for detecting and identifying differences and identities between said words, short groups of words or phrases, and sentences which are represented by said first and second groups of said characters;

said processing means for detecting and identifying differences and identities including means for detecting and identifying words and short groups of words or phrases which are different in said first and second groups of characters when said words and short groups of words or phrases which are different do not consist of a line of text or a group of lines of text and regardless of whether or not the text wraps around an end of a line or a plurality of lines, said words and short groups of words or phrases being contained in sentences that are otherwise identical in said first and second groups of characters;

display means coupled to said processing means for providing a display of said differences by displaying the text with the differences designated

25. within the text lines..Iaddend..Iadd.27. An automated text comparison system comprising:

input means for receiving commands and for providing electronic signals representing a plurality of characters representing words, short groups of words or phrases, and sentences;

memory means coupled to said input means for storing as binary representations at least first and second groups of said characters;

processing means coupled to said memory means and to said input means for detecting and identifying differences between said words and said short groups of words or phrases which are represented by said first and second groups of said characters, said processing means for detecting and identifying differences including means for detecting and identifying words and short groups of words or phrases which are identical in said first and second group of characters when said words and short groups of words or phrases which are identical do not consist of a line of text or a group of lines of text and regardless of whether or not the text wraps around an end of a line or a plurality of lines, said words and short groups of words or phrases being contained in short groups of words or phrases that are not necessarily identical in said first and second groups of characters; and

a display means coupled to said processing means for providing a display of said differences by displaying the text with the differences designated within the text lines..Iaddend..Iadd.28. An automated text comparison system comprising;

input means for receiving commands and for providing electronic signals representing a plurality of characters representing words, short groups of words or phrases, and sentences;

memory means coupled to said input means for storing as binary representations at least first and second groups of said characters;

processing means coupled to said memory means and to said input means for detecting and identifying differences and identities between said words and said short groups of words or phrases which are represented by said first and second groups of said characters, said processing means for detecting and identifying differences and identities including means for detecting and identifying words and short groups of words or phrases which are different in said first and second group of characters when said words and short groups of words or phrases which are different do not consist of a line of text or a group of lines of text and regardless of whether or not the text wraps around an end of a line or a plurality of lines, said words and short groups of words or phrases being contained in short groups of words or phrases that are otherwise identical in said first and second groups of characters; and

a display means coupled to said processing means for providing a display of said differences by displaying the text with the differences designated within the text lines..Iaddend.