0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

Actually you can often just split on the white space, remove punctuation, and lowercase. This will provide your tokens. For example, if I had a string "jdf asdsa sdfr" (no English), then I could derive the tokens jdf, asdsa, and sdfr. The only thing that is known before hand would be the stopwords (and, be it the), which do come from the English dictionary. However, in this case, it does not sound like you would need stopwords. I would suggest looking at the following libraries available in python:

SpaCy

NLTK

Scikit-learn

$\endgroup$
  • $\begingroup$ Thanks for taking the time to write an answer! However, I suspect there has been a misunderstanding. Yes, this works for human languages, but as I wrote in the question, in my setting "a complication is that there is no equivalent of whitespace that separates tokens". My apologies if that was too hidden. Is there some way I could make that clearer in the question? $\endgroup$ – D.W. Jan 4 '17 at 21:56
1
$\begingroup$

Also, for words that appear together as one such as "wordsthatappeartogetherasone", I suggest using Microsoft Cognitive Services Bing Spell Check API. It has word break functionality. You can test it out here:

https://www.microsoft.com/cognitive-services/en-us/bing-spell-check-api

$\endgroup$
  • $\begingroup$ Thanks for taking the time to suggest another possible approach. However, that's not relevant to my question. That service only works because it has a built-in dictionary of known English words. However, I am dealing with a file format that is not English (or any other human-readable language), and where I don't have a dictionary. Instead, I'm trying to create a dictionary from the data. Once I have a dictionary I know how to split words based on the dictionary, but that doesn't help discover the dictionary in the first place. $\endgroup$ – D.W. Jan 4 '17 at 22:05
1
$\begingroup$

Do you have a way to evaluate the results? How can you know if a string is indeed a token in this language?

In order to get possible tokens, I recommend that you'll try Huffman coding, the compression algorithm. The tree that it builds will contain the tokens.

  • It will identify that "the" is more frequent that expected and worth compression.
  • It will identify the "ARETHE" is not significantly more frequent than "Are" "The" and won't waste representation space in order to compress it.
  • It is a classical algorithm so you'll probably find many suitable implementation and will be able to analyze your data quickly.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.