Menu
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:
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.
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.
756
The testing of a single substring in a string has been discussed many times. But sometimes, we have a list of potential substrings and check which ones occur in a target string as a substring. Let’s discuss certain ways in which this task can be performed. Using list comprehension is the naive and brute force method to perform this particular task.
1. String substring () : This method has two variants and returns a new string that is a substring of this string. The substring begins with the character at the specified index and extends to the end of this string. Syntax : public String substring (int begIndex) Parameters : begIndex : the begin index, inclusive.
The substring begins with the character at the specified index and extends to the end of this string or up to endIndex – 1 if the second argument is given. Syntax : public String substring (int begIndex, int endIndex) Parameters : beginIndex : the begin index, inclusive. endIndex : the end index, exclusive.
Write the code in a function to match the sub-string within the input string and return True/False. Call the function with the 2 parameters, array and sum, from the main () method.
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.
159
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:
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.
1
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
