SYSTEM AND METHOD FOR SEARCHING STRINGS OF RECORDS

• US 20090012957A1
• Filed: 05/08/2005
• Published: 01/08/2009
• Est. Priority Date: 05/07/2004
• Status: Active Grant

• Current Assignee: RoboGroup T.E.K Ltd.
• Original Assignee: RoboGroup T.E.K Ltd.
• Inventors: Villaret, Yves, Ben Haim, Shaul
• Granted Patent: US 7,904,429 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

System and method for detecting the inclusion of strings of words (records) in an input string of words. In a preparation phase, the records are pre-processed. Each record is represented by a string of chunks, each chunk composed of a pre-defined number of words. Each chunk found in at least one record is assigned a number of attributes, such as a “Begin of Record” attribute and an “End of Record” attribute. In the searching phase the input string is also divided in chunks, and for each input chunk, an Incremental Hash Function (IHF) is calculated for comparing with a prerecorded value ΔI. If the two values IHF and ΔI coincide for matching chunks with certain predefined attributes, a “probable match” is set, indicating a very high probability that a chunk was found in the records.

Claims

1. A method of detecting the inclusion of records in an input string of words comprising:

a. pre-processing the records such that at least a portion of the records are represented by a string;

said string comprising a plurality of sections wherein each of the said sections (chunks) comprises a pre-defined number of elementary words, in the manner that when a chunk is the first chunk in the chunk representation of a record a “

Begin of Record”

attribute is assigned to the said chunk and when a chunk is the last chunk in the chunk representation of a record, an “

End of Record”

attribute is assigned to it;

b. searching said string in the manner that the input string is divided into a plurality of chunks and each of said chunks is searched in the records so that if a searched chunk is found to be present in at least one record, a Partial Match Flag is set according to a logic calculation; and

,

c. calculating an Incremental Hash Function (IHF) for each input chunk;

characterized by that whenever a chunk from the input string is found to be in at least one of the records, and the said chunk is associated with an End of Record and the Partial Match is set for this chunk (End of Record chunk), the difference values between the value of the IHF at that “

End of Record”

chunk and the value of the IHF at each of the previous chunks of the said string, to which a “

Begin of Record”

is associated (Begin of Record Chunk), is calculated and compared with all pre-recorded values Δ

I, calculated during the pre-processing for each record having the said End of Record chunk as last chunk, and associated to the said End of Record chunk;

and further characterized by that whenever any of the said pre-recorded value Δ

I coincides with at least one of the said difference values, a “

probable match”

is set, indicating a very high probability for an exact match.

2. The method according to claim 1, wherein calculating the Incremental Hash Function (IHF) comprises:

a. starting with an arbitrary initial value;

b. processing sequentially each chunk of the record; and

,

c. calculating the IHF for each of said processed chunks as an arbitrarily first predefined function of the said chunk and the previously calculated IHF value where the said chunk has not been associated with a “

Begin of Record”

attribute, and as a reversible operation of a second predefined function of the said chunk and the previously calculated IHF value where the said chunk has been associated with a “

Begin of Record”

attribute.

3. The method according to claim 1, wherein at least a portion of the records are words, numbers, notes, characters or any combination thereof.

4. The method of claim 1, wherein a conventional Hash function and a Hash table is used to check whether a sequentially processed chunk of the input string of chunks is present in the chunk table, the Hash table comprising a data field and a chain index field for the purpose of finding an exact match between the said sequentially processed chunk and a chunk of the chunk table.

5. The method of claim 1, wherein a simplified Hash table is used for checking whether a sequentially processed chunk of the input string of chunks is present in the chunk table, characterized in that the Hash table does not comprise a data field, all chunks having the same Hash function point to the same row, and a chunk is assumed to be present in the chunk table if the hash function of that chunk points to a non empty row of the hash table, wherein the Begin of Record attribute is set and stored in the Hash table row if one chunk of the list of chunks has a Hash function pointing to that row and is the first chunk of one record, and wherein an End of Record attribute is set and stored in the Hash table if one chunk of the list of chunks has a hash function pointing to that row and is the last chunk of one record.

6. The method of claim 1, wherein additional attributes are associated to each chunk of the list of chunks, the said additional attributes representing specific values or properties of each chunk in a record, the said additional attributes having a specific “

null”

value if a particular chunk has different attribute values in different records, and wherein a Partial Match for a sequentially processed chunk is set if the said chunk appears in the said list of chunks and if either the said Chunk has a “

Begin of Record”

attribute, or if a Partial Match Flag was set for a previous sequentially processed chunk and an additional logic relation of the attributes of the sequentially processed chunk and the previous sequentially processed chunk is verified.

7. The method of claim 6 wherein additional attributes are associated to each row of the Hash table, the said additional attributes representing specific values or properties of each chunk in a record, the said additional attributes having a specific “

null”

value if a particular row has different attribute values correspondent to several chunks having a hash function pointing to that row, and wherein the Partial Match is set if the hash function of the said chunk points to a valid row of the hash table and if either the said row has a “

Begin of Record”

attribute, or if the Partial Match Flag was previously set and an additional logic relation of the attributes of the rows pointed to by the hash functions of the sequentially processed chunk and the previous sequentially processed chunk is verified.

8. The method of claim 7 wherein the additional attributes are the previous and next chunk in the record.

9. The method of claim 8, wherein the additional attributes at a row of the hash table are the hash functions of the preceding chunk and the consecutive chunk to the chunk of a record having a hash function pointing to that row.

10. The method of claim 1, wherein chunks of the chunk representation of records are not overlapping, and where starting complementary and ending complementary data are used to verify final Partial match.

11. The method of claim 1, wherein the Δ

I function for each record is obtained by calculating the inverse of a reversible operation of the IHF value at the last chunk of the record, and the initial value of the IHF for that record.

12. The method of claim 11 wherein the reversible operation is addition.

13. The method of claim 11 wherein the reversible operation is multiplication.

14. The method of claim 11 wherein the reversible operation is division.

15. A method of detecting the inclusion of at least one record comprising string of words from a list of pre-defined records in an input string of words, comprising:

a. pre-processing the list of records in the manner that each record is represented by a string comprising a plurality of sections wherein each of the said sections (chunks) comprises a pre-defined number of elementary words, creating a list of chunks, comprising all chunks of said pre-defined records, wherein if a chunk appears in more than one record this chunk is included only once in the said list of chunks;

b. associating to each chunk a “

Begin of Record”

attribute whenever the said chunk is the first chunk in the chunk representation of a record;

c. associating to each chunk a “

End of Record”

attribute whenever the said chunk is the last chunk in the chunk representation of a record;

d. calculating for each record an Incremental Hash Function (IHF);

said calculating compromising;

i. starting with an arbitrary initial value;

ii. processing sequentially each chunk of the record; and

,

iii. calculating the IHF for each of said processed chunks as an arbitrarily first predefined function of the said chunk has not been associated with a “

Begin of Record”

attribute, and as a reversible operation of a second predefined function of the said chunk and the previously calculated IHF value where the said chunk has been associated with a “

Begin of Record”

attribute;

e. calculating a Δ

I function for each record as the inverse of the said reversible operation of the IHF value at the last chunk of the record, and the said initial value of the IHF for that record;

f. associating to each chunk having an “

End of Record”

attribute, the values of all Δ

I function for all records for which that chunk is the last chunk;

g. representing the input string as a string of chunks (input string of chunks);

h. processing sequentially each chunk of the said input string of chunks, and for each said chunk

i. setting a Partial Match Flag if the said chunk appears in the said list of chunks and if either the said Chunk has a “

Begin of Record”

attribute, or the Partial Match Flag was previously set;

ii. calculating an Incremental Hash Function;

said calculating comprising;

1. starting with an arbitrary initial value; and

2. calculating the IHF for each of said chunks as the said first predefined function of the said chunk and the previously calculated IHF value where the said chunk has not been associated with a “

Begin of Record”

attribute, and as a reversible operation of the said predefined function of the said chunk and the previously calculated IHF value where the said chunk has been associated with a “

Begin of Record”

attribute;

i. if said chunk has an “

End of Record”

attribute, calculating a set of Δ

J function values, each one being the result of the inverse of the said reversible operation of the IHF value at the said chunk of the input string of chunks, and the IHF value obtained immediately before calculating the IHF for a chunk having a “

Begin of Record”

attribute; and

,

j. asserting a “

Probable Match”

in case the said chunk has an “

End of Record”

attribute and at least one of the Δ

J functions from the said set of Δ

J functions equals one of the Δ

I functions associated to the said chunk wherein a “

Probable Match”

indicates a high probability that at least one record is included in the input string.

16. The method according to claim 15, wherein at least a portion of the records comprises words, numbers, notes, characters or any combination thereof.

17. The method according to claim 15, wherein a conventional Hash function and a Hash table is used to check whether a sequentially processed chunk of the input string of chunks is present in the chunk table, the Hash table comprising a data field and a chain index field for the purpose of finding an exact match between the said sequentially processed chunk and a chunk of the chunk table

18. The method according to claim 15 wherein a simplified Hash table is used to check whether a sequentially processed chunk of the input string of chunks is present in the chunk table, characterized in that the Hash table does not comprise a data field, all chunks having the same hash function point to the same row, and a chunk is assumed to be present in the chunk table if the hash function of that chunk points to a non empty row of the hash table, wherein the Begin of Record attribute is set and stored in the Hash table row if one chunk of the list of chunks has a hash function pointing to that row and is the first chunk of one record, and wherein an End of Record attribute is set and stored in the Hash table if one chunk of the list of chunks has a hash function pointing to that row and is the last chunk of one record.

19. The method according to claim 15, wherein a conventional Hash function and a Hash table is used with additional attributes associated to each chunk of the list of chunks, the said additional attributes representing specific values or properties of each chunk in a record, the said additional attributes having a specific “

null”

value if a particular chunk has different attribute values in different records, and wherein the Partial Match is set if the said chunk appears in the said list of chunks and if either the said Chunk has a “

Begin of Record”

attribute, or if the Partial Match Flag was previously set and an additional logic relation of the attributes of the sequentially processed chunk and the previous sequentially processed chunk is verified.

20. The method according to claim 15 wherein a conventional Hash function and a Hash table is used with additional attributes associated to each row of the hash table, the said additional attributes being the previous and next chunk in the record.

21. The method according to claim 15 wherein chunks of the chunk representation of records are not overlapping, and where starting complementary and ending complementary data are used to verify final Partial match.

22. The method according to claim 15 wherein the reversible operation is addition.

23. The method according to claim 15 wherein the reversible operation is multiplication.

24. The method according to claim 15 wherein the reversible operation is division.

25. The method of claim 18 wherein chunks of the chunk representation of records are not overlapping, and where starting complementary and ending complementary date are used to verify final Partial match.

26. The method according to claim 18 wherein the reversible operation is addition.

27. The method according to claim 18 wherein the reversible operation is multiplication.

28. The method according to claim 18 wherein the reversible operation is division.

29. (canceled)

30. A system for detecting the inclusion of strings of records in an input string of words comprising:

a. means for pre-processing the records such that at least a portion of the records are represented by a string;

said string comprising a plurality of sections (chunks) wherein each of the said sections comprises a pre-defined number of elementary words, in the manner that when a chunk is the first chunk in the chunk representation of a record a “

Begin of Record”

attribute is assigned to the said chunk and when a chunk is the last chunk in the chunk representation of a record, an “

End of Record”

attribute is assigned to it;

b. means for searching said string in the manner that the input string is divided into a plurality of chunks, and each of said chunks is searched in the records so that if a searched chunk is found to be present in at least one record, a Partial Match Flag is set according to a logic calculation; and

,

c. means for calculating and Incremental Hash Function (IHF) for each input chunk;

characterized by that whenever a chunk from the input string is found to be in at least one of the records, and the said chunk is associated with an End of Record and the Partial Match is set for this chunk (End of Record chunk), the difference values between the value of the IHF at that “

End of Record”

chunk and the value of the IHF at each of the previous chunks of the said string, to which a “

Begin of Record”

is associated (Begin of Record chunk), is calculated and compared with all pre-recorded values Δ

I, calculated during the pre-processing for each record having the said End of Record chunk as last chunk, and associated to the said End of Record chunk;

and further characterized by that whenever any of the said pre-recorded value Δ

I coincides with at least one of the said difference values, a “

probable match”

is set, indicating a very high probability for an exact match.