在映射任务中，长正则表达式的最佳选择是什么？

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)

我正在使用pypi.python.org/pypi/regex包，因为标准re包无法编译我的长正则表达式。另外，我也用Java做了同样的算法。你知道吗

我使用了大约65万个句子，在Python中，编译需要3-4分钟，算法可以在3-4小时内完成。你知道吗

Java在几秒钟内编译regex，但是算法需要16-18小时

我一直在阅读不同的网站和http://swtch.com/~rsc/regexp/regexp1.html有一个有趣的信息，但我不知道如何处理。你知道吗

我的问题是。。。我已经在3小时内完成了所有的句子，你知道用别的方法在更短的时间内完成同样的句子吗？可能是其他语言，或者使用其他库或包？（在Java中，我使用的是标准库java.util.regex.*）。上面的网站讲的是Thonpson NFA算法，有Java、Python等算法库或包吗？grep（Linux）是一个强大的工具，你认为我可以使用它吗？你知道吗

Answer 1

你正在为你的每一句话重新编译。在循环外编译一次：

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

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

那会节省你一些时间。你知道吗

如果您想使用Cox所描述的算法重建库，可以四处寻找Python或Java绑定到他的RE2库。或者，使用egrep或Awk。你知道吗