私は、通常の（形式言語理論の意味での）文法によって明確に生成された、人間が読める冗長な文字列を多数含む大規模な公開データセットの分析に取り組んでいます。
これらの文字列のセットを1つずつ見て、パターンを確認するのはそれほど難しくありません。残念ながら、これらの一意の文字列は33のカテゴリと1714のサブカテゴリに分割されており、約24,000あるため、手動でこれを行うのはやや面倒です。
基本的に、私は既存のアルゴリズム（できれば既存の参照実装を使用）を探して、文字列の任意のリストを取得し、生成に使用できる正規表現のいくつかの最小（最小の合理的な定義）にまたがるセットを推測しようとしますそれら（つまり、その文法によって生成された言語からの文字列の有限集合から正規文法を推測します）。
貪欲で最長の一般的な部分文字列の削除を繰り返すことを検討しましたが、完全一致以外は折りたたまれないため、これまでのところ、たとえば、の特定の位置で変化する数値文字列の一般的なパターンは検出されません。文法。
一般的な部分文字列の除去から外れないものをブルートフォースすることは可能ですが、おそらく計算上実行不可能です。（さらに、私はそれについて考えました、そしてあなたが最終的な文法をより圧縮されないようにすることになる貪欲な部分文字列の一致をするかもしれないので、部分文字列の除去に関する「フェーズ順序付け」および/または「ローカル最小」問題があるかもしれません/最初は最良の削減であるように見えますが、最小限です）。