Need some info regarding string matching algorithms?

Question

Let me explain a scenario to better explain my question,

Assume I am working in a credit-card related company in which people uploads their receipts every month, I want to check if that person bought fruits or not. Let's assume we used OCR to extract only the names of items bought and stored in a list.

First thing I did is web scrape all the names of fruits found everywhere and I stored the names of each of them in a big text file.

Now I want to know how can I match/lookup and make a decision that person bought fruits.

1) Any search/match algorithms that works on huge amounts of data.

I'm just looking for advice on what to implement in this type of scenario. Thanks in advance.

Answer 1

Try the simplest approach first - deterministic check looking for intersection overlap between the set of fruit names and the set of items bought.

Set comparisons are scalable because the look-up time for each item is constant.

If scaling is an issue with regular set membership check, bloom filter is an option.

Answer 2

For string matching I normally use jellyfish library. If you want to calculate string similarity between two fruits (to check which one is similar) you can use Levenshtein. There is more methods in the documentation here.

Levenshtein distance

Levenshtein distance represents the number of insertions, deletions, and subsititutions required to change one word to another.

Answer 3

One of the default algorithms to use for this use case (set of search strings to be searched simultaneously in a text) is Aho Corasick. From the Wikipedia page: "The complexity of the algorithm is linear in the length of the strings plus the length of the searched text plus the number of output matches." Implementations of this algorithm exist in all common programming languages. If this is not efficient enough for you, you'll need to use some sort of hashing trick to get faster performance.