Gibt es einen Algorithmus, der aus einer Menge von Zeichenfolgen einen regulären Ausdruck (möglicherweise auf eine vereinfachte Grammatik beschränkt) erzeugen kann, sodass die Auswertung aller möglichen Zeichenfolgen, die mit dem regulären Ausdruck übereinstimmen, die ursprüngliche Menge von Zeichenfolgen reproduziert?

Es ist wahrscheinlich unrealistisch, einen solchen Algorithmus für Grammatiken von regulären Ausdrücken mit einer sehr "komplizierten" Syntax (einschließlich willkürlicher Wiederholungen, Behauptungen usw.) zu finden. Beginnen wir also mit einer vereinfachten, die nur eine zulässtOR von Teilstrings:

foo(a|b|cd)bar sollte passenfooabar, foobbar undfoocdbar.

Beispiele

Angesichts der Menge der Zeichenfolgenh_q1_a, h_q1_b, h_q1_c, h_p2_a, h_p2_b, h_p2_cwäre die gewünschte Ausgabe des Algorithmush_(q1|p2)_(a|b|c).

Angesichts der Menge der Zeichenfolgenh_q1_a, h_q1_b, h_p2_awäre die gewünschte Ausgabe des Algorithmush_(q1_(a|b)|p2_a). Beachten Sie, dassh_(q1|p2)_(a|b) würde nichtrichtig sein, weil das zu 4 Zeichenfolgen erweitern, einschließlichh_p2_b, die nicht in der ursprünglichen Reihe von Saiten war.

Anwendungsfall

Ich habe eine lange Liste von Labels, die alle durch Zusammenstellen von Teilstrings erstellt wurden. Anstatt die umfangreiche Liste der Zeichenfolgen zu drucken, möchte ich eine kompakte Ausgabe haben, in der angegeben wird, welche Beschriftungen in der Liste enthalten sind. Da die vollständige Liste programmgesteuert erstellt wurde (mit einem endlichen Satz von Vor- und Nachsätzen), erwarte ich, dass die kompakte Notation (möglicherweise) viel kürzer ist als die ursprüngliche Liste.

(Der (vereinfachte) reguläre Ausdruck sollte so kurz wie möglich sein, obwohl ich mehr an einer praktischen Lösung als an der besten interessiert bin. Die triviale Antwort ist natürlich, einfach alle Zeichenfolgen wie A | B | C | D | ... zu verketten, die ist aber nicht hilfreich.)