Matching engine with signature generation
A system and a method generates at least one signature associated with document. In one embodiment, a document comprised of text is received and parsed to generate a token set. The token set includes a plurality of tokens. Each token corresponds to the text in the document that is separated by a predefined character characteristic. A score is calculated for each token in the token set based on a frequency and distribution of the text in the document. Each token is then ranked based on the calculated score. A subset of the ranked tokes is selected and a signature is generated for each occurrence of the selected tokens. The selected list of signatures is then output.
1. A method for generating a plurality of signatures associated with a document, the method comprising:
receiving a document comprising text;
parsing the document to generate a token set comprising a plurality of tokens, each token corresponding to the text in the document separated by a predefined character characteristic;
calculating a score for each token in the token set based on a frequency and distribution of occurrences of the text in the document;
ranking each token in the token set based on the calculated score;
selecting, from the ranked tokens, a predetermined number of top ranked tokens to limit a number of signatures generated for said document; and
generating a signature for each occurrence of the selected tokens,
wherein said score calculation is such that a more even distribution of the occurrences of the text in the document results in a higher score, and
wherein said score for each token is proportional to a first quantity divided by a second quantity, further wherein the first quantity comprises a position of a last occurrence of the text in the document minus a position of a first occurrence of the text in the document, and further wherein the second quantity comprises a square root of a sum of squares of differences in positions between adjacent occurrences of the text in the document.
2. The method of claim 1 , wherein the predefined character characteristic comprises a delimiter.
3. The method of claim 1 , further comprising outputting the predetermined number of top signatures in a list.
4. The method of claim 1 , wherein the document is an ASCII document.
5. The method of claim 1 , further comprising outputting a list of the generated signatures.
6. A computer readable storage medium storing instructions executable by a processor, the instructions when executed causing a processor to:
receive a document comprising text;
parse the document to generate a token set comprising a plurality of tokens, each token corresponding to the text in the document separated by a predefined character characteristic;
calculate a score for each token in the token set based on a frequency and distribution of the text in the document;
rank each token in the token set based on the calculated score;
select, from the ranked tokens a predetermined number of top ranked tokens to limit a number of signatures generated for said document; and
generate a signature for each occurrence of the selected tokens,
wherein said score calculation is such that a more even distribution of the occurrences of the text in the document results in a higher score, and
wherein said score for each token is proportional to a first quantity divided by a second quantity, further wherein the first quantity comprises a position of a last occurrence of the text in the document minus a position of a first occurrence of the text in the document, and further wherein the second quantity comprises a square root of a sum of squares of differences in positions between adjacent occurrences of the text in the document.
7. The computer readable storage medium of claim 6 , wherein the predefined character characteristic comprises a delimiter.
8. The computer readable storage medium of claim 6 , further comprising instructions to cause the processor to output a predetermined number of top signatures in a list.
9. The computer readable storage medium of claim 6 , wherein the document is an ASCII document.
10. The computer readable storage medium of claim 6 , wherein the instructions when executed by the processor further cause the processor to output a list of the generated signatures.