Регулярное выражение, которое можно описать строку

Question

У меня есть алфавит {A, B, C} и (большое) число слов в этом алфавите:
AAABBCABBCCCCAA, ABBBCCC, BBBBCACAC, ... (разной длины, различные комбинации)

Я ищу набор регулярных выражения (чем меньше, тем лучше), которые могут описывать эти слова. Я предпочитаю компактный ((BC)+ за BCBC). Это не домашнее задание.

1. Что такое хороший способ сделать это?
2. Есть ли пакет Python, который уже делает это?

Я нашел this question для связи.

Обновление: Возможно, я помчался, когда говорил, что предпочитаю (BC)+ над BCBC. Я предпочитаю иметь как можно меньше выражений (в худшем случае существует одно регулярное выражение для каждой строки), поэтому предпочтение для одного из A+, AA или AA+ для описания AA (например) должно зависеть от того, какие шаблоны демонстрируют другие строки.

Answer 1

Если я правильно понимаю вашу проблему, у вас есть алфавит и список строк на этом алфавите, и вы хотите построить шаблон, который соответствует именно этим строкам.

Возможно, вы можете построить deterministic finite automata для каждой строки, построить из этого non-deterministic finite automata, что является комбинацией всех этих DFA. Затем упростите DFA до NFA. Затем просто преобразуйте NFA в шаблон.

Это будет работать, если вместо строк у вас уже есть шаблон. Однако нет никакой гарантии, что вы получите наименьший возможный шаблон.

Я не знаю никакой библиотеки для управления DFA или NFA в Python.

Answer 2

Вот несколько способов обработки строк с этими словами, но только первый требует регулярного выражения:

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']