6
$\begingroup$

First, let me apologise, as this question is far from my area of expertise, but is related to a side interest (read hobby), and so this question might be very naive. This may even be off-topic for the site, and if so I apologise.

You are given a set of $S$ strings $\{s_i\}$, each of length $n$. One of the strings (denoted $s_x$) is something a human would recognise as meaningful text in a specified language (we can assume English if that helps). Further, we can assume that all other strings $s_{i \neq x}$ have Hamming distance at least $c n$ from the nearest meaningful natural language string, for some finite constant $c$. (I'm not going to try to specify what 'meaningful' means here mathematically, and so please take it that I mean roughly something that a human would take to be a reasonable piece of natural language text. Indeed, a good definition for this might itself be the answer.)

My question then is fairly simple: Is there an efficiently computable function $F(s)$ such that $F(s_x) > F(s_i)$ for all $i \neq x$, with high probability, for sufficiently large $n$? In the case I care about $S$ is extremely large, but constant. Additionally, I care about the case where $s_i$ all have similar Kolmogorov complexity.

To me, at least, the natural candidates seem to be based on N-grams, either by computing some scalar function of N-gram frequency and computing the distance from the value for the target language (determined from a large collection of text in that language), or by computing the distance between vector formed by taking the N-gram frequences in order with that of the target language. However, a little experimentation has shown this intuition to be false, since there are many random looking strings with substantially better N-gram statistics than $s_x$.

Another approach which fails is to try to count the proportion of the string which is occupied with words in whatever language we are considering. However this fails badly because you can strings like "iiiiiiiaaaaiaiaaaaaaiiiiinoiaaaonionnoaiii" which are clearly not natural language, but which can be interpretted as a string of English language words. Potentially we could try imposing grammatical structures, but this seems like a bad (and inefficient) road to be going down. So I am wondering if there is a better approach? Is there any $F$ satisfying the above requirement which can be computed reasonably efficiently?

$\endgroup$
  • $\begingroup$ If you want to distinguish meaningful strings from random strings, my guess is that N-grams should work pretty well. If you want to distinguish meaningful strings from all strings that are far from meaningful strings, that must be very difficult. $\endgroup$ – Tsuyoshi Ito Aug 2 '11 at 21:29
  • $\begingroup$ @Tsuyoshi: Yes, I know it is not necessarily an easy task. I realise that perfectly separating meaningful from non-meaningful is probably not even a well defined task. I was hoping that perhaps by excluding the middle, and requiring the strings be 'far' from meaningful might mean that there is a practical solution. It is also why I ask for the 'best' fitness function, since I realise an ideal one is probably too much to hope for. This problem must have been studied for use in cryptanalysis, so I guess someone here will know something. $\endgroup$ – Joe Fitzsimons Aug 2 '11 at 21:46
  • 1
    $\begingroup$ Are the non-meaningful strings chosen by a malicious adversary or a product of some random/natural/non-malicious process? If the latter, it seems like the known work on language identification might be applicable. However, given your comment on n-gram analysis, maybe not? Also, what is $k_i$? $\endgroup$ – mhum Aug 3 '11 at 0:40
  • $\begingroup$ @mhum It is indeed the latter case, but $S$ is very large which means that in practice there are strings of gibberish in there with better N-gram statistics than $s_x$. $k_i$ shouldn't have appeared. I rewrote the question from my original draft and somehow forgot to remove it. I've updated the question above to reflect this. In any case, thanks for the pointer. $\endgroup$ – Joe Fitzsimons Aug 3 '11 at 0:55
  • $\begingroup$ Ok. Regarding your second proposed approach and the string "iiiiiiaaa...etc...", wouldn't you use some kind whitespace delimiter to mark word boundaries? Speaking of which, can you confirm that the N-gram statistics you're using do include whitespace/word boundaries? If you look at the first pdf linked in the wikipedia article, you'll see that almost all of the most common trigrams in several languages contain word boundary markers. $\endgroup$ – mhum Aug 3 '11 at 5:31

Your Answer

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

Browse other questions tagged or ask your own question.