使用正则表达式从单词列表中查找成对单词

Question

使用正则表达式从单词列表中查找成对单词

4

I have a list of words such as:

l = """abc
dfg
hij
jih
gfd
cba
cbd
jip
gfe
jiw
cbw"""

我希望你能协助我从这个列表中找到一些词语的配对，因此需要指定第一个单词：

.(.)(.)

第二个单词是：

\2\1.

因此，\1 和 \2 分别指代第一个单词中的字符。

我能想到的最佳正则表达式是：

re.findall('(^.(?P<A>.)(?P<B>.)$)(?=.*(^(?P=B)(?P=A).$))', l, re.DOTALL | re.MULTILINE)

但这个搜索只返回了一些匹配对(因为findall仅返回不重叠的结果...)。然后我想到使用正向零宽断言，但是它们只能用于固定长度的字符串...有没有办法使用正则表达式来解决这个问题？

- ItaiS

你能用文字解释一下这些词对之间的关系吗？我觉得你可能失去了一些精度。这些词总是像示例中展示的那样恰好有三个字母长吗？ - Karl Knechtel

在您的示例数据中，“abc”可以与“cba”，“cbd”或“cbw”配对。您有偏好吗？还是您想要全部获取？ - Alan Moore

@Alan：很明显他想获取它们的所有内容，否则正则表达式方法就能奏效了。 - Niklas B.

@KarlKnechtel：不是的。列表中的单词可以是任何长度。这对单词之间唯一的关系是它们之间重复出现的字符。我给出的示例寻找应用模式“.(.)(.)”、“\2\1.”的两个单词。 - ItaiS

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Niklas B. · Accepted Answer

我怀疑正则表达式不是解决这个问题的好方法（特别是在Python中，你不能像在Perl中那样简单地获取匹配字符串的所有可能方式，因此你必须在字符串的所有前缀上调用findall）。一个直接的替代方法是：

words = l.split()
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in words 
                      if w1[1:] == w2[1::-1])

结果为：

>>> map(tuple, pairs)
[('hij', 'jip'), 
 ('abc', 'cbd'), 
 ('dfg', 'gfd'), 
 ('dfg', 'gfe'), 
 ('jiw', 'hij'), 
 ('hij', 'jih'), 
 ('abc', 'cbw'), 
 ('abc', 'cba')]

你也可以通过先保存单词前缀的字典来快速解决这个问题，然后在第一轮中建立关联，在第二轮中构建相关性：

from collections import defaultdict

prefixes = defaultdict(list)
for w in words:
    prefixes[w[1::-1]].append(w) 
pairs = set(frozenset((w1, w2)) for w1 in words for w2 in prefixes[w1[1:]])

这将是一项非常难以被正则表达式引擎超越的性能。