What is the best way to match substring from a big string to a huge list of keywords

Question

Imagine you have millions of records containing text with average 2000 words (each), and also you have an other list with about 100000 items.

e.g: In the keywords list you a have item like "president Obama" and in one of the text records you have some thing like this: "..... president Obama ....", so i want to find this keyword in the text and replace it with some thing like this: "..... {president Obama} ...." to highlight the keyword in the text, the keywords list contains multi-noun word like the example.

What is the fastest way to this in such a huge list with millions of text records?

Notes:

1. Now I do this work in a greedy way, check word by word and match them, but it takes about 2 seconds for each text record, and I want some thing near zero time.

2. Also I know this is something like named-entity-recognition and I worked with many of the NER framework such as Gate and ..., but because I want this for a language which is not supported by the frameworks I want to to this manually.

Answer 1

Assumptions: Most keywords are single words, but there are som multi word keywords.

My suggestion.

Hash the keywords based on the first word. So "President","President Obama" and "President Clinton" will all hash to the same value.

Then search word-by-word by computing the hashes. On hash matches implement logic to check if you have a match on a multi word keyword.

Calculating the hashes will be the most expensive operation of this solution and should be linear in the length of the input string.

Answer 2

As for the exact keyword match:

10^6 * 2*10^3 words = billions of possible matches. Comparing this with 10^5 possible matches leads to over 10^6 * 2^3 * 10^5 = 2 * 10^14 operations (worst case: no match, probability no-match: big (because 100000 is small compared all possible words?).

and i want some thing near zero time

Not possible.

As for the NER, you must drop the keywords list and classify the grammar in categories you would like to highlight.

Things like:

• verbs
• adverbs
• nouns
• names
• quantities
• etc.

can be identified. After you have done that, you could define a special list containing special words by category. E.g.: President might be in such a (noun) list to highlight it with special properties. Because you'll end up with a much smaller special list, spitted into several catagories. You can decrease the number of operations needed.

(Just reallize, as you know all about NER you already know that.)

So,you could extract a NER like logic (or other non 100% match algorithm) for the language you're targeting.

Another try might be:

Put all your keywords in a hashtable or other (indexed) dictionary, check if the targeted word is existing in that hashtable. As it is indexed, it will be significant faster than the regular matching. You can store additional info for the keyword in the hashtable.