Каков наилучший вариант для длинных регулярных выражений в задаче отображения?

Question

У меня есть длинный словарь терминов о биомедицинских сущностях. Каждый термин (ключ) имеет список идентификаторов (значение).

Я должен найти эту терминологию в свободном тексте. У меня есть несколько словарей около 300000 терминов, и для этой задачи я использую Python и Java для оценки скорости.

Алгоритм похож на (в 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)

Я использую пакет http://pypi.python.org/pypi/regex, потому что стандартный пакет re не может скомпилировать мое длинное регулярное выражение. Кроме того, я сделал тот же алгоритм в Java.

Я использую около 650 000 предложений, а в Python компиляция занимает 3-4 минуты, а алгоритм может закончиться за 3-4 часа.

Java компилирует регулярное выражение в считанные секунды, но алгоритм занимает 16-18 часов...O_o

Я читал разные сайты, и http://swtch.com/~rsc/regexp/regexp1.html содержит интересную информацию, но я не знаю, как с ней обращаться.

У меня вопрос... Я выполнил все предложения за ~3 часа, знаете ли вы другой способ добиться того же за меньшее время? Может быть, на другом языке, или с использованием другой библиотеки или пакета? (в Java я использую стандартную библиотеку java.util.regex.*). Сайт выше рассказывает об алгоритме Thonpson NFA, есть библиотеки или пакеты этого алгоритма для Java, Python или чего-то еще? grep (Linux) - мощный инструмент, вы думаете, что я могу его использовать?

Answer 1

Регулярные выражения - неправильный инструмент для этой работы. Создайте словарь (имя Python для хеш-таблицы) с вашими терминами, разбейте текст на слова (используя string.split и string.rstrip для удаления знаков препинания) и проверьте каждое слово в тексте на соответствие этому словарю.

Answer 2

Вы перестраиваете и перекомпилируете RE для каждого предложения вашего текста. Скомпилируйте его один раз вне цикла:

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

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

Это должно сэкономить вам время.

Если вам нужна библиотека RE с алгоритмами, описанными Коксом, поищите привязки Python или Java к его библиотеке RE2. В качестве альтернативы используйте egrep или Awk.