Text-based fuzzy search
An input feature vector is computed from an input text record, the input feature vector comprising one or more features, each feature including a subsequence of characters and a frequency of occurrence of the associated subsequence. A input fingerprint is generated out of the input feature vector by choosing one or more features with non-zero frequencies and alphabetizing the features chosen. One or more input indices are generated by alphabetizing features in the input fingerprint and concatenating features occurring in subsequent locations of the input fingerprint. The input text record is matched against a target text record if (1) one or more of the input indices match a target index corresponding to the target text record and (2) the corresponding input fingerprint matches a target fingerprint corresponding to the target text record. The target text record is outputted as a search result if it matches the input text record.
1. A method for performing a text-based fuzzy search, the method comprising:
performing, by a processor, the steps of:
receiving an input text record;
computing, from the input text record, an input feature vector comprising one or more text features, each text feature including a subsequence of text characters and a frequency of occurrence of the associated subsequence of text characters;
generating an input fingerprint out of the input feature vector by choosing one or more text features with non-zero frequencies and alphabetizing the text features chosen;
generating one or more input indices by alphabetizing a plurality of text features in the input fingerprint and concatenating text features occurring in subsequent locations of the input fingerprint; and
matching the input text record against a target text record if (1) one or more of the corresponding input indices match a target index corresponding to the target text record and (2) the corresponding input fingerprint matches a target fingerprint corresponding to the target text record, wherein the respective target text record is outputted as a search result if it matches the input text record.
2. The method of claim 1 , further comprising:
storing one or more target text records in a text database;
computing a target feature vector for each target text record, each target feature vector comprising one or more target features, each target feature including a subsequence of characters and a frequency of occurrence of the associated subsequence of characters;
generating a fingerprint for each target record out of the corresponding feature vector by choosing one or more features with non-zero frequencies and alphabetizing the features chosen;
generating one or more indices for each target text record by concatenating two or more target features occurring in subsequent locations of the target fingerprint; and
storing each target fingerprint in a fingerprint database and each target index in an index database.
3. The method of claim 1 , wherein generating the target fingerprint includes a step of selecting one or more target features with non-zero frequencies.
4. The method of claim 3 , wherein in the case that a respective target text record is over a set length threshold, only the K most frequently occurring target features are selected for the target fingerprint, with K being a number greater than 2.
5. The method of claim 3 , wherein in the case that a respective target text record is over a set length threshold, a median or mean of the total frequency count of the target features is computed, and only target features with frequencies above the median or mean are selected for the target fingerprint.
6. The method of claim 1 , wherein the input target text record is converted into a byte array representation prior to computation of the feature vector.
7. The method of claim 6 , wherein subsequences of characters of the byte array representation are mapped to integer representations.
8. An apparatus for performing a text-based fuzzy search, the apparatus comprising at least one processor communicatively coupled to a communication network, wherein the processor is configured to:
receive an input text record;
compute, from the input text record, an input feature vector comprising one or more text features, each text feature including a subsequence of text characters and a frequency of occurrence of the associated subsequence of text characters;
generate an input fingerprint out of the input feature vector by choosing one or more text features with non-zero frequencies and alphabetizing the text features chosen;
generate one or more input indices by alphabetizing a plurality of text features in the input fingerprint and concatenating text features occurring in subsequent locations of the input fingerprint; and
match the input text record against a target text record if (1) one or more of the corresponding input indices match a target index corresponding to the target text record and (2) the corresponding input fingerprint matches a target fingerprint corresponding to the target text record, wherein the respective target text record is outputted as a search result if it matches the input text record.
9. The apparatus of claim 8 , wherein the processor is further configured to:
store one or more target text records in a text database;
compute a target feature vector for each target text record, each target feature vector comprising one or more target features, each target feature including a subsequence of characters and a frequency of occurrence of the associated subsequence of characters;
generate a fingerprint for each target record out of the corresponding feature vector by choosing one or more features with non-zero frequencies and alphabetizing the features chosen;
generate one or more indices for each target text record by concatenating two or more target features occurring in subsequent locations of the target fingerprint; and
store each target fingerprint in a fingerprint database and each target index in an index database.
10. The apparatus of claim 8 , wherein generation of the target fingerprint includes a step of selecting one or more target features with non-zero frequencies.
11. The apparatus of claim 10 , wherein in the case that a respective target text record is over a set length threshold, only the K most frequently occurring target features are selected for the target fingerprint, with K being a number greater than 2.
12. The apparatus of claim 10 , wherein in the case that a respective target text record is over a set length threshold, a median or mean of the total frequency count of the target features is computed, and only target features with frequencies above the median or mean are selected for the target fingerprint.
13. The apparatus of claim 8 , wherein the input target text record is converted into a byte array representation prior to computation of the feature vector.
14. The apparatus of claim 13 , wherein subsequences of characters of the byte array representation are mapped to integer representations.
15. A non-transitory computer-readable storage medium having stored thereon sequences of instructions, which cause a processor to perform:
receiving an input text record;
computing, from the input text record, an input feature vector comprising one or more text features, each text feature including a subsequence of text characters and a frequency of occurrence of the associated subsequence of text characters;
generating an input fingerprint out of the input feature vector by choosing one or more text features with non-zero frequencies and alphabetizing the text features chosen;
generating one or more input indices by alphabetizing a plurality of text features in the input fingerprint and concatenating text features occurring in subsequent locations of the input fingerprint; and
matching the input text record against a target text record if (1) one or more of the corresponding input indices match a target index corresponding to the target text record and (2) the corresponding input fingerprint matches a target fingerprint corresponding to the target text record, wherein the respective target text record is outputted as a search result if it matches the input text record.
16. The computer-readable medium of claim 15 , wherein the processor is further caused to perform:
storing one or more target text records in a text database;
computing a target feature vector for each target text record, each target feature vector comprising one or more target features, each target feature including a subsequence of characters and a frequency of occurrence of the associated subsequence of characters;
generating a fingerprint for each target record out of the corresponding feature vector by choosing one or more features with non-zero frequencies and alphabetizing the features chosen;
generating one or more indices for each target text record by concatenating two or more target features occurring in subsequent locations of the target fingerprint; and
storing each target fingerprint in a fingerprint database and each target index in an index database.
17. The computer-readable medium of claim 15 , wherein generating the target fingerprint includes a step of selecting one or more target features with non-zero frequencies.
18. The computer-readable medium of claim 17 , wherein in the case that a respective target text record is over a set length threshold, only the K most frequently occurring target features are selected for the target fingerprint, with K being a number greater than 2.
19. The computer-readable medium of claim 17 , wherein in the case that a respective target text record is over a set length threshold, a median or mean of the total frequency count of the target features is computed, and only target features with frequencies above the median or mean are selected for the target fingerprint.
20. The computer-readable medium of claim 15 , wherein the input target text record is converted into a byte array representation prior to computation of the feature vector.
21. A method for populating databases for a search, the method comprising:
performing, by a processor, the steps of:
storing one or more target text records in a text database;
computing a target feature vector for each target text record, each target feature vector comprising one or more target text features, each target text feature including a subsequence of text characters and a frequency of occurrence of the associated subsequence of text characters;
generating a fingerprint for each target text record out of the corresponding target feature vector by choosing one or more text features with non-zero frequencies and alphabetizing the text features chosen;
generating one or more indices for each target text record by concatenating two or more target text features occurring in subsequent locations of the target fingerprint;
storing each target fingerprint in a fingerprint database and each target index in an index database.