System and method for searching strings of records
First Claim
Patent Images
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 first chunk and when a chunk is the last chunk in the chunk representation of a record, an “
End of Record”
attribute is assigned to the last chunk;
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;
wherein calculating the Incremental Hash Function (IHF)includes;
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 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;
d. 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;
e. 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;
f. 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 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;
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
g. 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
28 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 first chunk and when a chunk is the last chunk in the chunk representation of a record, an “
End of Record”
attribute is assigned to the last chunk;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;wherein calculating the Incremental Hash Function (IHF)includes; 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 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;d. 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;e. 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;f. 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 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;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; andg. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. 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 Δ
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 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;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. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
-
-
28. A system for detecting the inclusion of strings of records in an input string of words comprising:
-
a dedicated hardware; a. means, executed by the dedicated hardware, 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 first chunk and when a chunk is the last chunk in the chunk representation of a record, an “
End of Record”
attribute is assigned to the last chunk;b. means, executed by the dedicated hardware, 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; c. means, executed by the dedicated hardware, for calculating and Incremental Hash Function (IHF) for each input chunk; and d. means, executed by the dedicated hardware, for calculating all pre-recorded values Δ
I wherein 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 wherein said means for calculating as set forth in (c) is adapted to make its calculation byi. 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; andsaid means for calculating as set forth in (d) is adapted to calculating said Δ
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;said means (c) and (d) being further adapted to associate 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;said means representing the input string as a string of chunks (input string of chunks); said means processing sequentially each chunk of the said input string of chunks, and for each said chunk 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;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
,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.
-
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeRoboGroup T.E.K Ltd.
-
Original AssigneeRoboGroup T.E.K Ltd.
-
InventorsVillaret, Yves, Ben Haim, Shaul
-
Primary Examiner(s)Rones; Charles
-
Assistant Examiner(s)Mahmood; Rezwanul
-
Application NumberUS11/568,746Publication NumberTime in Patent Office2,130 DaysField of Search707/999.01, 707/999.003, 707/999.101US Class Current707/687CPC Class CodesG06F 2207/025 String search, i.e. pattern...G06F 7/02 Comparing digital values G0...
