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.

Leftwich

I suppose the language you are talking about is C#? How does your greedy way look rigth now? – Robichaux

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.

Moffatt

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.

Extine

10^14 operations is irrelevant. Even a simple search implementation based on a straight forward trie will eliminate most of this. – Moffatt

@Moffatt Stefan is right if there is no Match you will always search again the full string which will very time consuming ... – Council

@Council Yes, you will always search the full string. However, you will not compare the full string against each keyword. So 10^14 opertions is only possible in an extremely naive implementation. – Moffatt