Matching engine for querying relevant documents

1. A computer-implemented method for generating an output of documents having a predetermined relevance, the method being performed by a relevance detection engine at a server and comprising:

receiving an initial document comprising text;

receiving a list of documents, each document comprising text, for matching;

receiving a minimum substring match length M;

normalizing the text of the initial document to form string str, and normalizing the text of the documents of the list of documents to form corresponding strings str k of lengths L k , where k=1 to m;

sorting suffixes of the string str with an array to record suffix string positions;

calculating a similarity SIM(k) between the string str and each string str k ;

searching for a maximal matching length V of the string str and a suffix S(str k ,P) during the calculation of the similarity SIM (k), wherein the suffix S(str k , P) is a suffix of str k starting at position P;

determining whether condition V>M is met;

if V>M is not met, then incrementing the position P by one;

if V>M is met, then adding V/L k to the similarity SIM(k) and incrementing the position P by V; and

outputting the similarity SIM(k) between the string str and each string str k .

2. The method of claim 1 , further comprising:

determining whether condition P<L k is met;

if P<L k is met, then looping back to search for the maximal matching length V of the string str and the suffix S(str k ,P); and

if P<L k is not met, then determining whether condition k<m is met.

3. The method of claim 2 , further comprising:

if k<m is met, then incrementing k by one and looping back to search for the maximal matching length V of the string str and the suffix S(str k ,P); and

if k<m is not met, then performing said outputting.

4. The method of claim 1 , wherein the list of documents comprises a plurality of documents.

5. A tangible computer readable medium structured to store instructions executable by a processor, the instructions when executed causing a processor to:

receive an initial document comprising text;

receive a list of documents, each document comprising text, for matching;

receive a minimum substring match length M;

normalize the text of the initial document to form string str and the text of the documents of the list of documents to form corresponding strings str k of length L k , where k=1 to m;

sort suffixes of the string str with an array to record suffix string positions;

calculate a similarity SIM(k) between the string str and each string str k ;

search for a maximal and a suffix S(str k ,P) during the calculation of the similarity SIM(k), wherein the suffix S(str k , P) is a suffix of str k starting at position P;

determine whether condition V>M is met;

if V>M is not met, then incrementing the position P by one; and

if V>M is met, then add V/Lk to the similarity SIM(k) and increment the position P by V; and

output the similarity SIM(k) between the string str and each string str k .

6. The tangible computer readable medium of claim 5 , further including instructions stored on the tangible medium that cause the processor to:

determine whether condition P<L k is met;

if P<L k is met, then loop back to search for the maximal matching length V of the string str and the suffix S(str k ,P); and

if P<L k is not met, then determine whether condition k<m is met.

7. The tangible computer readable medium of claim 6 , further including instructions stored on the tangible medium that cause the processor to:

if k<m is met, then increment k by one and looping back to search for the maximal matching length V of the string str and the suffix S(str k ,P); and

if k<m is not met, then perform said outputting.

8. The computer readable medium of claim 5 , wherein the list of documents comprises a plurality of documents.

9. An apparatus for determining relevant documents from a document depository, the apparatus comprising:

a data storage system configured to store computer-readable instructions and data;

a processor configured to execute computer-readable instructions; and

a network interface configured to communicatively interconnect the apparatus to a data network;

computer-readable instructions stored in the data storage system that are configured to receive an initial document comprising text;

computer-readable instructions stored in the data storage system that are configured to receive a list of documents, each document comprising text, for matching;

computer-readable instructions stored in the data storage system that are configured to receive a minimum substring match length M;

computer-readable instructions stored in the data storage system that are configured to normalize the text of the initial document to form string str of length L and the text of the documents of the list of documents to form corresponding strings str k of length L k , where k=1 to m;

computer-readable instructions stored in the data storage system that are configured to assign a prime number Q which is larger than L;

computer-readable instructions stored in the data storage system that are configured to allocate a hash table H with size Q;

computer-readable instructions stored in the data storage system that are configured to calculate a similarity SIM(k) between the string str and each string str k ;

computer-readable instructions stored in the data storage system that are configured to calculate a hash value h of a substring of the string str k which starts at position P and with a length M;

computer-readable instructions stored in the data storage system that are configured to determine whether H[h] is empty;

computer-readable instructions stored in the data storage system that are configured to increment P if H[h] is empty;

computer-readable instructions stored in the data storage system that are configured to determine a maximum matching length V of the string str and a suffix S(str k , P) during the calculation of the similarity SIM(k), wherein the suffix S(str k , P) is a suffix of str k starting at position P;

computer-readable instructions stored in the data storage system that are configured to determine whether condition V greater than or equal to M is met;

computer-readable instructions stored in the data storage system that are configured to increment the position P by one if V greater than or equal to M is not met;

computer-readable instructions stored in the data storage system that are configured to add V/L k to the similarity SIM(k) and increment the position P by V if V greater than or equal to M is met; and

computer-readable instructions stored in the data storage system that are configured to output the similarity SIM(k) between the string str and each string str k .

10. The apparatus of claim 9 , further comprising:

computer-readable instructions stored in the data storage system that are configured to determine whether condition P<L k −M is met;

computer-readable instructions stored in the data storage system that are configured to, then loop back to search for the maximal matching length V of the string str and the suffix S(str k ,P) if P<L k −M is met; and

computer-readable instructions stored in the data storage system that are configured to determine whether condition k<m is met if P<L k −M is not met.

11. The apparatus of claim 10 , further comprising:

computer-readable instructions stored in the data storage system that are configured to increment k by one and looping back to search for the maximal matching length V of the string str and the suffix S(str k ,P) if k<m is met; and

computer-readable instructions stored in the data storage system that are configured to perform said output said similarity S(k) if k<m is not met.