在Python中匹配最长子串

Question

假设我有一个字符串，其中左边和右边之间有一个制表符，这个字符串保存在一个文本文件里：

The dreams of REM (Geo) sleep         The sleep paralysis

我想在另一个文件的每一行中找到同时匹配左边和右边部分的字符串：

The pons also contains the sleep paralysis center of the brain as well as generating the dreams of REM sleep. 

如果找不到完全匹配的字符串，就尝试找部分匹配的。

我想从最左边和最右边的模式开始搜索。

比如说（最左边的情况）：

The dreams of REM  sleep     paralysis
The dreams of REM  sleep     The sleep

比如说（最右边的情况）：

REM  sleep    The sleep paralysis
The dreams of   The sleep paralysis

非常感谢任何形式的帮助。

Answer 1

好的，你已经澄清了大部分你想要的内容。让我重新说一下，然后解释一下我下面列出的仍然不清楚的点……另外，把我给你的起始代码调整一下，发给我们结果。

你想要逐行搜索，不区分大小写，找到与一对匹配模式的最长连续匹配。所有的模式似乎是不重叠的（即不可能同时匹配模式X和模式Y，因为它们使用不同的短语，比如不能同时匹配“前额叶”和“前额皮层”）。

你的模式是以一对对的形式提供的('dom','rang')，=> 我们就用它们的下标[0]和[1]来称呼它们，你可以用字符串的split('\t')来获取这些。

重要的是，匹配的行必须同时匹配 dom和rang模式（完全匹配或部分匹配）。顺序是无关的，所以我们可以先匹配rang再匹配dom，或者反过来 => 每行使用两个独立的正则表达式，测试d和r是否匹配。

模式有可选部分，用括号表示 => 所以只需用(optionaltext)?语法将它们写成正则表达式，例如：re.compile('Frontallobes of (leftside)? the brain', re.IGNORECASE)

返回值应该是到目前为止最长的子字符串匹配的字符串缓冲区。

现在有几个地方需要进一步澄清 - 请编辑你的问题来解释以下内容：

• 如果你找到任何一对模式的完整匹配，就返回那个。
• 如果找不到完整匹配，那么就搜索这对模式的部分匹配。这里的“部分匹配”是指“最多的单词”或“单词的最高比例(%)”？显然我们要排除像“the”这样的无关匹配，这样我们就可以简单地从搜索模式中省略“the”，这样可以确保所有对任何模式的部分匹配都是有意义的。
• 我们给部分匹配打分（某种方式），例如“包含模式X的大多数单词”或“包含模式X的最高%单词”。我们应该对所有模式都这样做，然后返回得分最高的模式。你需要考虑一下，是匹配5个单词模式中的2个单词（40%），例如'dreams of'，好，还是匹配2个单词中的1个（50%），例如'prefrontal BUT NOT cortex'更好？我们怎么解决平局等问题？如果我们匹配了'sleep'但没有其他匹配，怎么办？

以上每个问题都会影响解决方案，所以你需要为我们回答这些问题。写很多代码来解决最一般的情况是没有意义的，当你只需要一些简单的东西时。一般来说，这被称为“NLP”（自然语言处理）。你可能最终会使用一个NLP库。

到目前为止，代码的一般结构听起来像：

import re

# normally, read your input directly from file, but this allows us to test:
input = """The pons also contains the sleep paralysis center of the brain as well as generating the dreams of REM sleep.
The optic tract is a part of the visual system in the brain.
The inferior frontal gyrus is a gyrus of the frontal lobe of the human brain.
The prefrontal cortex (PFC) is the anterior part of the frontallobes of the brain, lying in front of the motor and premotor areas.
There are three possible ways to define the prefrontal cortex as the granular frontal cortex as that part of the frontal cortex whose electrical stimulation does not evoke movements.
This allowed the establishment of homologies despite the lack of a granular frontal cortex in nonprimates.
Modern  tracing studies have shown that projections of the mediodorsal nucleus of the thalamus are not restricted to the granular frontal cortex in primates.
""".split('\n')

patterns = [
    ('(dreams of REM (Geo)? sleep)', '(sleep paralysis)'),
    ('(frontal lobe)',            '(inferior frontal gyrus)'),
    ('(prefrontal cortex)',       '(frontallobes of (leftside )?(the )?brain)'),
    ('(modern tract)',            '(probably mediodorsal nucleus)') ]

# Compile the patterns as regexes
patterns = [ (re.compile(dstr),re.compile(rstr)) for (dstr,rstr) in patterns ]

def longest(t):
    """Get the longest from a tuple of strings."""
    l = list(t) # tuples can't be sorted (immutable), so convert to list...
    l.sort(key=len,reverse=True)
    return l[0]

def custommatch(line):
    for (d,r) in patterns:
        # If got full match to both (d,r), return it immediately...
        (dm,rm) = (d.findall(line), r.findall(line))
        # Slight design problem: we get tuples like: [('frontallobes of the brain', '', 'the ')]
        #... so return the longest match strings for each of dm,rm
        if dm and rm: # must match both dom & rang
            return [longest(dm), longest(rm)]
        # else score any partial matches to (d,r) - how exactly?
        # TBD...
    else:
        # We got here because we only have partial matches (or none)
        # TBD: return the 'highest-scoring' partial match
        return ('TBD... partial match')

for line in input:
    print custommatch(line)

并且在你提供的7行输入上运行目前的结果是：

TBD... partial match
TBD... partial match
['frontal lobe', 'inferior frontal gyrus']
['prefrontal cortex', ('frontallobes of the brain', '', 'the ')]
TBD... partial match
TBD... partial match
TBD... partial match
TBD... partial match