GB2440174A

GB2440174A - Determining similarity of electronic documents by comparing hashed alphabetically ordered phrases

Info

Publication number: GB2440174A
Application number: GB0614332A
Authority: GB
Inventors: Stephen Robinson
Original assignee: Chronicle Solutions UK Ltd
Current assignee: Chronicle Solutions UK Ltd
Priority date: 2006-07-19
Filing date: 2006-07-19
Publication date: 2008-01-23
Also published as: GB0614332D0; WO2008009991A1

Abstract

An electronic system for automatically comparing the similarity of a first electronic document with a second electronic document, comprising processing the electronic data representing each document by: (a) dividing the document into phrases by splitting the electronic data at each electronic signal representing a punctuation mark; (b) dividing each of the phrases into words; (c) discarding electronic signals representing glue, or stop, words; (d) within each phrase sorting the words into alphabetical order; (e) generating a hash code for each alphabetically ordered phrase; and (f) comparing the hash codes for the first document with the hash codes of the second document; and (g) generating a value indicating the proportion of hash codes which match in the first and second documents being compared. The document may be captured on a network and the value may be a percentage or represented on a logarithmic scale.

Description

SYSTEM

The present invention relates to a system for electronically comparing documents.

With the ever increasing dependency of organisations on computers to organise. store and communicate documentation, it is increasingly desirable to he able to control the distribution of electronic documentation. For example, it is desirable for an organisation to know who has received confidential documents, and/or to prevent unauthori sed persons receiving them Electronic documents are usually transmitted over a network in a packet fbrm so the actual data content of the document is mixed in each packet with other electronic information such as that which determines the type of data. routing information, check data and timing information. Thus, to determine the data content, the packets must be decoded.

One method currently used to monitor the electronic transmission of specified documents in data traffic over a network is to attach a packet sniffer (also known as network or protocol analyzer or Ethernet sniffer) to the network. Such a packet snifier copies each of the data packets transmitted over the network, stores the packets and subsequently decodes and analyses the content for comparison to one or more predetermined files, looking for a match.

A problem with known packet sniffers is that they are only able to match identical documents. If a document is modified or paraphrased in any way then the transmitted document would not match the watched document and therefore no action will he taken. In addition, known packet sniffers are slow and generally unable to operate fully in real time.

The present invention seeks to pros ide a system of comparing documents and determining how similar their content is to one or more pre-selected documents.

According to the first aspect of the present invention there is provided an electronic system for automaticaIl comparing the similarit ol a first electronic document with a second electronic document. the system comprising elements arranged for electronically processing the electronic data representing each document by: (a) dividing the document into phrases by splitting the electronic data at each electronic signal rcprcsdnting a punctuation mark; (b) dividing each of the phrases into words; (c) discarding electronic signals representing glue words; (d) within each phrase sorting the words into alphabetical order; (e) generating a hash code for each alphabetically ordered phrase: and (1) comparing the hash codes for the first document with the hash codes of the second document; and (g) generating a value indicating the proportion of hash codes which match in the first and second documents being compared.

Preferably each document is divided at electronic signals representing one or more of the punctuation symbols such as full stop, comma, semi-colon, colon, single quote, double quote, question mark and exclamation mark. The term words" is intended to 1 5 mean any continuous sequence of alphanumeric characters such as letters A to Z and numbers 0 to 9.

The invention has particular application in computer networks for comparing documents transferred over such networks in real time.

The comparison value may be generated as a percentage for ease of interpretation and is preferably converted to a logarithmic scale. l'he system can be adapted automatically to take action if the comparison value is higher than a predetermined value.

A corresponding method. computer program and computer are also provided.

The invention will now he described, by way of example, with reference to the accompanying drawing in which the single figure is a block diagram of a method according to the present invention for comparing the similarity of electronic documents according to the present invention.

Ihe single figure illustrates the steps involved in comparing electronic documents according to the system of the present invention. Electronic data representing a document to be tested is presented in a comparison step 10. The electronic data may he captured as raw packet data transmitted across a network, then decoded and recombined into its original form. If the document originates from network traffic then the comparison system should ideally be capable of processing each document in real-time, so that a backlog of documents does not build up. However the invention can be used in stand alone mode to compare documents.

The data representing the document is then divided in step 12 by dividing the text into phrases at punctuation symbols preferably including: full stop. comma, semi-colon, colon, single quotation marks, double quotation marks, question mark and exclamation mark.

Each of the phrases is then sub-divided into words in step 14. where words are defined as any continuous sequence of alphanumeric characters. i.e. of letters A to 7, and/or numbers 0 to 9. The phrases will thus be split into words at any character outside these ranges and all such characters are considered white-space and discarded in dividing the phrases into words.

Then at step 16 each of the words in each of the phrases is examined and all glue words are discarded. Glue words are those which do not add any intrinsic subject matter, such as, fbr example: a, the, and it. This advantageously reduces the number of words without significantly affecting the content.

Next at stage 18, the remaining words in each of the phrases are sorted into alphabetical order so that their position in the phrase is flO longer important.

Each alphabetically sorted phrase is then used to generate a hash code in stage 20.

Any hash algorithm could be used to create the hash code, for example the MI)4 algorithm would he suitable. It is advantageous to use a hash code to represent the contents of the phrase because it requires significantly less processing time to compare hash codes than to compare the alphabetically sorted phrases.

Once the hash codes for each phrase in a document have been created, they can he compared with the hash codes of one or more other documents at stage 22. For example with pre-selected documents where hash codes are already stored in the system such pre-selected documents may consist of documents that the administrator of the system has identified, for example confidential or classified documents. The pre-selected documents are processed in the same way as the document being tested before the system receives the first document to be tested.

The result of' the comparison between documents is preferably displayed in the form of a percentage value representing the number of matching phrases in the no documents. The more matching hash codes there arc in two documents being compared. the more likely it is that the documents are related. It is advantageous to display the percentages on a logarithmic scale since this makes it easier to visually identify similarities. It is also possible for the system to be configured to flag any documents which have a percentage match over a given threshold, so that appropriate action can be taken quickly. either manually, or automatically by the system, for example to block further dissemination of the document, to block future transmission of it, or to trace and log the source of the document.

Claims

CLAIMS

I. An electronic system for automatically comparing the similarity of a first electronic document with a second electronic document, the system comprising elements arranged for electronically processing the electronic data representing each document by: (a) dividing the document into phrases by splitting the electronic data at each electronic signal representing a punctuation mark: (b) dividing each of the phrases into words; (c) discarding electronic signals representing glue words; (d) within each phrase sorting the words into alphabetical order: (e) generating a hash code for each alphabetically ordered phrase; and (1) comparing the hash codes for the first document with the hash codes of the second document; and (g) generating a value indicating the proportion of hash codes which match in the first and second documents being compared.

2. A system according to claim 1 wherein each document is divided into phrases by dividing the electronic document text at each of the electronic signals representing the punctuation symbols: full stop. comma, semi-colon, colon, single quote, double quote, question mark and exclamation mark.

3. A system according to claim I or 2 wherein words are defined as any continuous sequence of alphanumeric characters comprising letters A to Z and numbers 0 to 9.

4. A system according to any one of the preceding claims wherein prior to dividing the document into phrases, the document is captured from a network.

5. A system according to claim 4 adapted to perform the comparing in real-time.

6. A system according to any one of the preceding claims comprising an additional element for taking action if the value of a document comparison is higher than a predetermined value.

7. A system according to any one of the preceding claims wherein the value is generated as a percentage.

8. A system according claim 7 comprising an additional element lbr converting the percentage value results to a logarithmic scale.

9. A method of comparing the similarit of a first electronic document with a second electronic document Comprising the steps of: (a) dividing the document into phrases by splitting the electronic data at each electronic signal representing a punctuation mark: (h) dividing each of the phrases into words; (c) discarding electronic signals representing glue words: (d) within each phrase sorting the words into alphabetical order; 1 5 (C) generating a hash code for each alphabetically ordered phrase: and (f) comparing the hash codes for the first document with the hash codes of the second document; and (g) generating a value indicating the proportion of hash codes which match in the first and second documents being compared.

1 0. A computer adapted to compare the similarity of a first electronic document with a second electronic document, comprising processing elements arrayed for processing the electronic data representing each document by: (a) dividing the document into phrases by splitting the electronic data at each electronic signal representing a punctuation mark: (b) dividing each of the phrases into words; (c) discarding electronic signals representing glue words; (d) within each phrase sorting the words into alphabetical order; (e) generating a hash code for each alphabetically ordered phrase; and (f) comparing the hash codes br the first document with the hash codes of the second document; and (g) generating a value indicating the proportion ob hash codes which match in the first and second documents being compared. f.)

II. A computer program arranged so that when loaded on a computer the computer will automatically compare the similarity of a first electronic document with a second electronic document by performing the steps of: (a) dividing the document into phrases by splitting the electronic data at each electronic signal representing a punctuation mark: (h) dividing each of the phrases into words: (c) discarding electronic signals representing glue words; (d) within each phrase sorting the words into alphabetical order: (e) generating a hash code for each alphabetically ordered phrase; and (f) comparing the hash codes For the first document with the hash codes of the second document: and (g) generating a value indicating the proportion of hash codes which match in the first and second documents being compared.