Apparatus and method for comparing data groups

• US 4,807,182 A
• Filed: 03/12/1986
• Issued: 02/21/1989
• Est. Priority Date: 03/12/1986
• Status: Expired

• Current Assignee: Advanced Software, Inc.
• Original Assignee: Advanced Software, Inc.
• Inventors: Queen, Cary L.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Nguyen, Viet Q.
• Application Number:
  US06/839,326
• Time in Patent Office: 1,077 Days
• Field of Search: 340/721, 364/419, 364/200 MS File, 364/900 MS File
• US Class Current: 715/210
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

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 comparison system, comprising:

input means for receiving commands, and for providing electronic signals representing a plurality of characters including words 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 indentifying differences between said words and sentences first and second groups of said characters;

display means coupled to said processing means for providing a display of said differences.

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

13. The method as defined by claim 12 further comprising the step of defining identity blocks by comparison of the characters in each document radiating outward from said anchorpoints.

14. The method as defined by claim 13 further comprising the step of deleting from memory all anchorpoints contained 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 correspoonding location in said second 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 within said difference blocks.

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

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

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

20. The method as defined by claim 19 further comprising the step of simultaneously displaying corresponding blocks from said first and second 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 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 position of said first cursor.