0

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?

2 Answers 2

2

Regular expressions are a wrong tool for this job. Create a dictionary (Python's name for a hash table) with your terms, split your text into words (using string.split and string.rstrip to remove punctuation), and check each word in the text against this dictionary.

2
  • One term can have several words. I have several rules to trasform each term and sentence (lowercase, delete puntmarks...). I would like to do soft-matching too. Do you think that a hash table (in python or Java) would be better?
    – nathan
    Jul 30, 2012 at 14:03
  • @nathan: a dict is a hash table.
    – Fred Foo
    Jul 30, 2012 at 15:12
0

You're rebuilding and recompiling the RE for every sentence of your text. Compile it once outside the loop:

terms = dictionary.keys()              # why are you using a dict?
pattern = re.compile("|".join(terms))

for sentence in text_list:
    matches = pattern.finditer(sentence)
    # etc.

That should save you some time.

If you want an RE library with the algorithms described by Cox, look around for Python or Java bindings to his RE2 library. Alternatively, use egrep or Awk.

5
  • Yeeees!!! I am sorry, it was a typographical error, my compilations is outside the loop!!! Can I use egrep in JAVA or Python?
    – nathan
    Jul 30, 2012 at 15:25
  • @nathan: For Python, see the subprocess module, for Java, you're on your own. Be careful with escaping, and be aware that you will encounter extra overhead due to interprocess communication.
    – Fred Foo
    Jul 30, 2012 at 15:32
  • Thanks!!! Should I be to use Lucene as an alternative? Could Lunece improve something? Or it is better, a first filter with egrep to get sentences with entities and after finditer to find offsets?
    – nathan
    Jul 30, 2012 at 15:38
  • @nathan: this is getting a bit out of hand. Lucene is an indexing and FTS toolkit, not a grep replacement.
    – Fred Foo
    Jul 30, 2012 at 15:43
  • But Lucene can search words in full text (with sotf-matching I think...), no?
    – nathan
    Jul 30, 2012 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.