2

我有一个字母表{A, B, C}和这个字母表上的（大量）单词：（
AAABBCABBCCCCAA, ABBBCCC, BBBBCACAC, ...不同的长度，不同的组合）

我正在寻找一组可以描述这些词的正则表达式（越小越好）。我更喜欢紧凑（(BC)+over BCBC）。这不是家庭作业。

  1. 有什么好方法可以做到这一点？
  2. 是否有一个 Python 包已经这样做了？

我发现这个问题是相关的。

更新：当我说我更喜欢时，我可能会(BC)+匆忙BCBC。我更喜欢使用尽可能少的表达式（在最坏的情况下，每个字符串有一个正则表达式），因此对 , 或 describe 之一的偏好A+（AA例如AA+）AA应该取决于其他字符串显示的模式。

4

2 回答 2

1

如果我正确理解您的问题，那么您有一个字母表和该字母表上的字符串列表，并且您想要构建一个与这些字符串完全匹配的模式。

您可能可以为每个字符串构造一个确定性有限自动机，从中构造一个非确定性有限自动机，它是所有这些DFA的组合。然后将DFA简化为NFA。然后只需将 NFA 转换为模式。

如果您已经有模式而不是字符串，这甚至会起作用。但是，不能保证您会得到尽可能小的图案。

我不知道有任何库可以在 Python中操作DFA或NFA 。

于 2013-02-15T22:21:16.140 回答
0

以下是处理带有这些单词的字符串的几种方法，但只有第一种需要正则表达式：

strings =['AAABBCABBCCCCAA', 'ABBBCCC', 'BBBBCACAC']

import re
for string in strings:
    matches = re.findall(r'([A-C]+)', string)
    if matches:
        print matches[0]

输出：

AAABBCABBCCCCAA
ABBBCCC
BBBBCACAC

或者，您可以使用类似这样的东西，具体取决于您打算对单词的正则表达式做什么：

from itertools import groupby
results = [(string, [''.join(g) for k, g in groupby(string)]) for string in strings]
print
for result in results:
    print '{}: {}'.format(*result)

输出：

AAABBCABBCCCCAA: ['AAA', 'BB', 'C', 'A', 'BB', 'CCCC', 'AA']
ABBBCCC: ['A', 'BBB', 'CCC']
BBBBCACAC: ['BBBB', 'C', 'A', 'C', 'A', 'C']
于 2013-02-15T23:43:25.880 回答