When processing texts written in a human-readable language, typically a first step is tokenization, where we have a dictionary of tokens (words) and we collapse each substring in that dictionary into a single token. For a language like English, the dictionary is known in advance.
In my case, I want to parse files with a format not based on any human language. I don't have a dictionary of known tokens; instead, I want to learn this dictionary. I do have lots of sample data I can analyze.
Are there techniques for generating a dictionary, given many example files?
I expect that any common substring that appears in many files is a good candidate for a token, so an obvious approach is to look for all common substrings and add them to the dictionary. However, a complication is that there is no equivalent of whitespace that separates tokens, so it seems like some filtering might be needed to avoid treating phrases (sequences of multiple tokens) as a new token. For example, imagine if we had a large corpus of English writing, except that all spaces and punctuation are omitted, and we tried to infer a dictionary of English words from that. We might naturally infer that "ARE", "THE", and "HER" are reasonable tokens, as they occur frequently as substrings. All well and good so far. However, we wouldn't want the algorithm to add "ARETHE" to the dictionary, even though "ARETHE" appears fairly frequently, as "ARETHE" is just the concatenation of the two tokens "ARE" and "THE". I suspect it might be possible to detect this, because the frequency of "ARETHE" is not much more than the product of the frequencies of "ARE" and "THE", but I'm not sure. Is there a clean way to handle this wrinkle?
