I have a long dictionary of terminology about biomedical entities. Each term (key) has a list of identifiers (value).
I have to find this terminology in free text. I have several dictionaries around 300,000 terms, and for this task I am using Python and Java to evaluate speed.
The algorithm is like to (in Python):
for sentence in text_list:
terms = dictionary.keys()
pattern = re.compile("|".join(terms))
matches = pattern.finditer(sentence)
for m in matches:
ini = m.start()
end = m.end()
match = m.group(1)
save_result(ini, end, match)
I am using pypi.python.org/pypi/regex package because the standard re package can not compile my long regular expression. Also, I have done the same algorithm in Java.
I am using around 650,000 sentences and in Python, the compilation takes 3-4minuts, and the algorithm can finish in 3-4 hours.
Java compile the regex in seconds but the algorithm takes 16-18hours...O_o
I have been reading different websites and http://swtch.com/~rsc/regexp/regexp1.html has an interesting information, but I do not know how to handle.
My question is... I have achieved to do all sentences in ~3 hours, do you know another way to achieve the same in less time? Maybe in other language, or using other library or package? (in Java, I am using the standard library java.util.regex.*
). The above website talks about Thonpson NFA algorithm, there are libraries or packages of this algorithm for Java, Python or whatever? grep
(Linux) is a powerful tool, do you think that I can use it?