<p>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.</p>

<p>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.)</p>

<p>My question then is fairly simple: Is there an efficiently computable function $F(s)$ such that $F(s_x) &gt; 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.</p>

<p>To me, at least, the natural candidates seem to be based on <a href="http://en.wikipedia.org/wiki/N-gram" rel="nofollow">N-grams</a>, 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$. </p>

<p>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?</p>

CC BY-SA 3.0
2011-08-02T21:29:30.753Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-02T21:46:52.200Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-03T00:40:51.917Z
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](http://en.wikipedia.org/wiki/Language_identification) might be applicable. However, given your comment on n-gram analysis, maybe not? Also, what is $k_i$?
mhum
CC BY-SA 3.0
2011-08-03T00:55:03.327Z
@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.
Joe Fitzsimons
CC BY-SA 3.0
2011-08-03T05:31:27.470Z
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](http://www.xs4all.nl/~ajwp/langident.pdf) linked in the wikipedia article, you'll see that almost all of the most common trigrams in several languages contain word boundary markers.
mhum
CC BY-SA 3.0
2011-08-03T05:32:14.943Z
Also, regarding the cr.crypto-security tag, I wonder if the concept of [unicity distance](http://en.wikipedia.org/wiki/Unicity_distance) might somehow be relevant?
mhum
CC BY-SA 3.0
2011-08-03T11:53:06.073Z
@mhum: in this case the whitespace is stripped, but even if it weren't it wouldn't necessarily be constant between strings, and so you could have 'i i i i a a a ...'
Joe Fitzsimons
CC BY-SA 3.0
2011-08-03T12:15:09.843Z
@mhum: also, for the case I care about it is well above the unicity distance.
Joe Fitzsimons
CC BY-SA 3.0
2011-11-28T00:19:36.867Z
since the question did not generate answers here, it might be worthwhile to take parts of it (like asking for a definition of meaningful string) over to [ling.SE](http://linguistics.stackexchange.com/).
Artem Kaznatcheev
<cr.crypto-security><terminology><cryptographic-attack>
What is the best fitness function for detecting natural language?
Joe Fitzsimons
# What is the best fitness function for detecting natural language?

(Asked by: username_0 on 2011-08-02)

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](http://en.wikipedia.org/wiki/N-gram), 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?

**Tags:** cr.crypto-security, terminology, cryptographic-attack
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: 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](http://en.wikipedia.org/wiki/Language_identification) might be applicable. However, given your comment on n-gram analysis, maybe not? Also, what is $k_i$?  
> **username_0**: @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.  
> **username_2**: 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](http://www.xs4all.nl/~ajwp/langident.pdf) linked in the wikipedia article, you'll see that almost all of the most common trigrams in several languages contain word boundary markers.  
> **username_2**: Also, regarding the cr.crypto-security tag, I wonder if the concept of [unicity distance](http://en.wikipedia.org/wiki/Unicity_distance) might somehow be relevant?  
> **username_0**: @mhum: in this case the whitespace is stripped, but even if it weren't it wouldn't necessarily be constant between strings, and so you could have 'i i i i a a a ...'  
> **username_0**: @mhum: also, for the case I care about it is well above the unicity distance.  
> **username_3**: since the question did not generate answers here, it might be worthwhile to take parts of it (like asking for a definition of meaningful string) over to [ling.SE](http://linguistics.stackexchange.com/).  

---

## 0 answers

