Datasets for String Classification

Question

I would like to test an experimental algorithm for string classification. More precisely, the dataset should be split into a set GOOD of good strigs and a set BAD of bad strings. The algorithm should learn a model that is consistent with the dataset, in the sense that the output model always answers Yes for strings in GOOD, No for strings in BAD. The algorithm can behave arbitrarily on strings that are neither in GOOD nor in BAD.

Note that I'm not interested in prediction for strings not in the dataset. The only important thing is to obtain a model that is consistency with the given dataset. What makes the problem interesting is the fact that the model can be much smaller than the dataset. For instance, if the model is an automaton, then in some cases one can find automata that are exponentially smaller than the number of bits necessary to represent the dataset.

I would like to test our heuristics against known algorithms/datasets.

1. What are standard datasets used for testing new experimental heuristics in this area?
2. What are the standard tools used for such classification tasks on strings.

Note: The goal is to classify strings, not large texts. In particular, a typical size for the strings being considered is 1000 characters (at most). Additionally, one can assume these strings have the same length.

Answer 1

Your description corresponds to the general problem of grammatical inference (or grammar induction): as opposed to statistical models, the goal is to learn the exact language represented as a formal grammar. Importantly this is symbolic learning, i.e. there is no concept of minimizing error because errors are not acceptable at all.

As far as I know the field is rather theoretical, as opposed to statistical ML: one formally proves that some classes of languages can or cannot be learnt under specific constraints. A type of learning framework which used to be studied in this context (not sure if it's still active) is language identification in the limit. A quite different framework is Probably approximately correct learning (PAC), but in this is more general and not strictly about grammatical inference (to the best of my knowledge).

So I'm not aware of any real dataset: in general arbitrary datasets don't have the kind of formal constraints which are relevant for this kind of problem. But it's possible that some parts of the literature contain at least artificial datasets.