15,038,855 members
Articles / General Programming / Algorithms
Article
Posted 7 Apr 2015

36.2K views
22 bookmarked

# Gibberish Classification Algorithm and Implementation in C# and Python

Rate me:
9 Apr 2015CPOL8 min read
An algorithm to classify whether text is gibberish or not, and an implementation in C# and Python.

## Introduction

This Gibberish Classification algorithm aims to detect whether text is valid, or randomly typed in a keyboard. It returns a percentage where a low one means valid text, and a high one means gibberish text. The algorithm is at a pretty early stage, so there are still some incorrect return values.

If a result is lower than 50%, it's likely that the text is valid. If a result is higher than 50%, it's likely that the text is gibberish. The algorithm is optimized for the English language and for longer text; it will still work for shorter text (for example, one sentence), but then the results will be less accurate. The algorithm won't give a percentage lower than 1%, except if the input string is null or empty, then it returns 0%.

The C# implementation can be used for the .NET Framework 4.0 and higher (the binary in the download targets .NET 4.5). The Python implementation can be used in both Python 2.x and Python 3.x.

The source code can also be found on GitHub: C# implementation, Python implementation.

## The Algorithm

The algorithm checks three things, then calculates the final score:

• It checks whether the amount of unique chars (in %, in chunks of 35 chars) is in a usual range.
• It checks whether the amount of vowels (in %) of the letters is in a usual range.
• It checks whether the word/char ratio (in %) is in a usual range.

### Checking the unique characters

To check the % of unique characters, we first split the string in chunks of 35 characters. When doing this, it can happen that the last chunk does not have 35 characters -- in this case, if the chunk size is less than 10 characters, add these chars to the chunk before the last and delete the last. (This is only possible if there are 2 chunks or more)

After splitting the string into chunks, create an empty list. Then loop over all chunks. Calculate the amount of unique characters in the current chunk. Then divide it by the total amount of characters in the chunk and add it to the list.

After doing the above, calculate the average of the list, multiply it by 100, and return it.

That calculates the percentage of unique characters in chunks; checking whether it is in a usual range is done later.

### Checking the vowels

When checking the amount of vowels, first initialize an integer `vowels` and `total`. We run over each character in the given string. If the character is not an alphabet letter, continue without doing something for that letter. If it is an alphabet letter, increase `total` by 1 and check whether it is a vowel: if it is, increase `vowels` by 1. After running over all characters, return `vowels / total * 100`.

### Checking the word/char ratio

To check the word/char ratio, split the string by the regex `[\W_]` (splitting by all non-word characters and an underscore). Then remove all whitespace-only/empty items from the resulting array. Thereupon, divide the amount of words by the amount of chars, multiply it by 100 and return it.

### Calculating "deviation score"

The above functions all return a percentage, but we cannot directly use these to calculate the final score -- first we have to calculate how much the percentage deviates from the usual range, and then give it a score. The higher this score, the more the percentage deviates.

The function to calculate this score has to accept three arguments: the given percentage, the lower bound of the usual range and the upper bound.

1. If the percentage is lower than the lower bound, return `log(lower_bound - percentage, lower_bound)` (where the second argument is the base).
2. If the percentage is higher than the upper bound, return `log(percentage - upper_bound, 100 - upper_bound)`.
3. If the percentage is none of the above (meaning that it's in the usual range), return `0`.

### Calculating the final score

Using all above functions, we can calculate the final score! First we calculate the percentages using the first three functions. Then, we call the deviation score for each of them:

• For the vowels %, the lower bound is 45 and the upper bound is 50 -> `deviation_score(percentage, 45, 50)`
• For the unique chars %, the lower bound is 35 and the upper bound is 45 -> `deviation_score(percentage, 35, 45)`
• For the word/char ratio, the lower bound is 15 and the upper bound is 20 -> `deviation_score(percentage, 15, 20)`

Where do I get these bounds from? Just from testing and running some paragraphs taken from the internet through all 3 functions.

After calculating these deviation scores, we go through them and we set them to 1 of they are lower than 1. The reason for this is that we are going to call `log10` on these scores; having a score lower than 1 can lead to a negative logarithm (or an error in case of zero), which is undesired.

The next step is to calculate the logarithm on base-10 for all deviation scores and divide this by 6. (6, because the max number we can get from the log10 operation is 2, and we have three operations here). We return `max(final_score, 1)`. We do not return the exact final score if it's below one because even if the final score is 0%, it's not impossible that the entered text is gibberish; it's just unlikely. The higher the final score, the higher the chance that a string is gibberish.

## C# and Python implementation

In the C# implemenation, all methods are static and put in a `GibberishClassifier` class. In the Python implementation, all methods are put in a `gibberishclassifier` module. The Python version works in both Python 2.x and Python 3.x. Because the Python 2.x division truncates by default, we have to add this at the top of the file:

Python
`from __future__ import division`

After doing that, division won't be truncating anymore in Python 2.x.

The first implemented method is the method to split a string into chunks. The C# method uses a `for` loop and `Substring` to take the appropriate amount of characters. The Python method uses a `for` loop, `range` and the slice notation.

C#
```public static List<string> SplitInChunks(string text, int chunkSize)
{
List<string> chunks = new List<string>();
for (int i = 0; i < text.Length; i += chunkSize)
{
int size = Math.Min(chunkSize, text.Length - i);
}
int lastIndex = chunks.Count - 1;
if (chunks.Count > 1 && chunks[lastIndex].Length < 10)
{
chunks[chunks.Count - 2] += chunks[lastIndex];
chunks.RemoveAt(lastIndex);
}
return chunks;
}```
Python
```def split_in_chunks(text, chunk_size):
chunks = []
for i in range(0, len(text), chunk_size):
chunks.append(text[i:i+chunk_size])
if len(chunks) > 1 and len(chunks[-1]) < 10:
chunks[-2] += chunks[-1]
chunks.pop(-1)
return chunks```

Then the method to get the percentage unique chars per chunk is implemented. It uses the above method. The C# implementation uses `.Distinct().Count()` to get the count of unique characters in one chunk, and `.Average()` to calculate the average of all percentages of unique characters in the chunks. The Python implementation uses `len(set(chunk))` to get the amount of unique characters in one chunk, and it uses `sum` to get the sum of all percentages, which gets divided by the amount of all percentages.

C#
```public static double UniqueCharsPerChunkPercentage(string text, int chunkSize)
{
List<string> chunks = SplitInChunks(text, chunkSize);
double[] uniqueCharsPercentages = new double[chunks.Count];
for (int x = 0; x < chunks.Count; x++)
{
int total = chunks[x].Length;
int unique = chunks[x].Distinct().Count();
uniqueCharsPercentages[x] = (double)unique / (double)total;
}
return uniqueCharsPercentages.Average() * 100;
}```
Python
```def unique_chars_per_chunk_percentage(text, chunk_size):
chunks = split_in_chunks(text, chunk_size)
unique_chars_percentages = []
for chunk in chunks:
total = len(chunk)
unique = len(set(chunk))
unique_chars_percentages.append(unique / total)
return sum(unique_chars_percentages) / len(unique_chars_percentages) * 100```

The next method is the method to get a percentage of the vowels.

The C# method uses `!Char.IsLetter` to check if a char is not a letter; in that case, we go to the next char in the string. If it is a letter, it increments the `total` variable and it checks whether it is a vowel using `"aeiouAEIOU".Contains(c)`. If it is a vowel, in increments the `vowels` variable. At the end of the method, it returns the percentage if `total` is not zero, and if it is zero, then the method returns `0`.

The Python method uses `not c.isalpha()` to check if a chat is not a letter; in that case, we go to the next char in the string. If it is a letter, it increments the `total` variable and it checks whether it is a vowel using `c in "aeiouAEIOU"`. If it is a vowel, in increments the `vowels` variable. At the end of the method, it returns the percentage if `total` is not zero, and if it is zero, then the method returns `0`.

C#
```public static double VowelsPercentage(string text)
{
int vowels = 0, total = 0;
foreach (char c in text)
{
if (!Char.IsLetter(c))
{
continue;
}
total++;
if ("aeiouAEIOU".Contains(c))
{
vowels++;
}
}
if (total != 0)
{
return (double)vowels / (double)total * 100;
}
else
{
return 0;
}
}```
Python
```def vowels_percentage(text):
vowels = 0
total = 0
for c in text:
if not c.isalpha():
continue
total += 1
if c in "aeiouAEIOU":
vowels += 1
if total != 0:
return vowels / total * 100
else:
return 0```

After that method, the method to calculate the word/char ratio comes.

The C# method uses the `Regex.Split` method (in `System.Text.RegularExpressions`) to split the string. Then it uses the LINQ `.Where` method to remove all parts that are whitespace-only (it uses the `String.IsNullOrWhitespace` method to check that), and the `Count()` method to get the amount of words.

The Python method uses `re.split` (requires `import re`) to split the string, and it uses `x for x in ... if ...` to remove all whitespace-only parts. It uses `x.strip() != ""` to check whether a string is whitespace-only or empty. Then it uses the `len` method to find out the amount of words.

C#
```public static double WordToCharRatio(string text)
{
int chars = text.Length;
int words = Regex.Split(text, @"[\W_]")
.Where(x => !String.IsNullOrWhiteSpace(x))
.Count();
return (double)words / (double)chars * 100;
}```
Python
```def word_to_char_ratio(text):
chars = len(text)
words = len([x for x in re.split(r"[\W_]", text) if x.strip() != ""])
return words / chars * 100```

The next method is the one to calculate the deviation score. The C# implementation uses `Math.Log` for this, and the Python one uses `math.log` (requires `import math`):

C#
```public static double DeviationScore(double percentage, double lowerBound, double upperBound)
{
if (percentage < lowerBound)
{
return Math.Log(lowerBound - percentage, lowerBound) * 100;
}
else if (percentage > upperBound)
{
return Math.Log(percentage - upperBound, 100 - upperBound) * 100;
}
else
{
return 0;
}
}```
Python
```def deviation_score(percentage, lower_bound, upper_bound):
if percentage < lower_bound:
return math.log(lower_bound - percentage, lower_bound) * 100
elif percentage > upper_bound:
return math.log(percentage - upper_bound, 100 - upper_bound) * 100
else:
return 0```

The last method is the one to do the actual classifying. If the inputted string is empty or `null (C#)` or `None` (Python), it returns 0%. It calls the above methods, calculates the deviation score and calculates the final score, as the algorithm describes.

C#
```public static double Classify(string text)
{
if (String.IsNullOrEmpty(text))
{
return 0;
}
double ucpcp = UniqueCharsPerChunkPercentage(text, 35);
double vp = VowelsPercentage(text);
double wtcr = WordToCharRatio(text);

double ucpcpDev = Math.Max(DeviationScore(ucpcp, 45, 50), 1);
double vpDev = Math.Max(DeviationScore(vp, 35, 45), 1);
double wtcrDev = Math.Max(DeviationScore(wtcr, 15, 20), 1);

return Math.Max((Math.Log10(ucpcpDev) + Math.Log10(vpDev) + Math.Log10(wtcrDev)) / 6 * 100, 1);
}```
Python
```def classify(text):
if text is None or len(text) == 0:
return 0.0
ucpcp = unique_chars_per_chunk_percentage(text, 35)
vp = vowels_percentage(text)
wtcr = word_to_char_ratio(text)

ucpcp_dev = max(deviation_score(ucpcp, 45, 50), 1)
vp_dev = max(deviation_score(vp, 35, 45), 1)
wtcr_dev = max(deviation_score(wtcr, 15, 20), 1)

return max((math.log10(ucpcp_dev) + math.log10(vp_dev) +
math.log10(wtcr_dev)) / 6 * 100, 1)```

## History

• April 17th, 2015: Return 0% for an empty string.
• April 9th, 2015: Don't divide by zero if there are no alphabet letters in the string (at the method to calculate vowels %).
• April 8th, 2015: First version.

## About the Author

 Student Belgium
Also known as ProgramFOX. I like programming, playing chess and astronomy. Administrator of Chess Variants Training[^].

Find me on:

## Comments and Discussions

 First Prev Next
 From where do you got this idea? Do some similar algorithms or approach exists? Have you update this? Member 1266320511-Aug-16 1:53 Member 12663205 11-Aug-16 1:53
 Re: From where do you got this idea? Do some similar algorithms or approach exists? Have you update this? Thomas Daniels14-Aug-16 5:27 Thomas Daniels 14-Aug-16 5:27
 Mixed letter case Member 1188929729-Nov-15 8:31 Member 11889297 29-Nov-15 8:31
 Re: Mixed letter case Thomas Daniels29-Nov-15 9:04 Thomas Daniels 29-Nov-15 9:04
 What do you think is the importance of this algorithm? Member 1188929717-Sep-15 3:01 Member 11889297 17-Sep-15 3:01
 Re: What do you think is the importance of this algorithm? Thomas Daniels17-Sep-15 5:20 Thomas Daniels 17-Sep-15 5:20
 chunk Carla Johnica D. Quilop12-Sep-15 18:38 Carla Johnica D. Quilop 12-Sep-15 18:38
 Re: chunk Thomas Daniels12-Sep-15 22:28 Thomas Daniels 12-Sep-15 22:28
 long sentences Carla Johnica D. Quilop4-Sep-15 4:43 Carla Johnica D. Quilop 4-Sep-15 4:43
 hi!, can you specify how long does long sentence do you mean in this algorithm? as to how many character do long sentences do you mean? thank you this is a big help
 Re: long sentences Thomas Daniels4-Sep-15 5:10 Thomas Daniels 4-Sep-15 5:10
 Is this applicable only for long sentences? Member 1188929716-Aug-15 20:50 Member 11889297 16-Aug-15 20:50
 Re: Is this applicable only for long sentences? Thomas Daniels16-Aug-15 21:04 Thomas Daniels 16-Aug-15 21:04
 Re: Is this applicable only for long sentences? Member 1188929718-Aug-15 10:45 Member 11889297 18-Aug-15 10:45
 Re: Is this applicable only for long sentences? Thomas Daniels18-Aug-15 20:51 Thomas Daniels 18-Aug-15 20:51
 a negative test case Marc VunKannon10-Apr-15 7:08 Marc VunKannon 10-Apr-15 7:08
 Re: a negative test case Thomas Daniels10-Apr-15 7:37 Thomas Daniels 10-Apr-15 7:37
 Re: a negative test case Kevin Bewley7-Jan-16 3:55 Kevin Bewley 7-Jan-16 3:55
 Not as simple as it seems! AndyHo9-Apr-15 5:29 AndyHo 9-Apr-15 5:29
 Re: Not as simple as it seems! Thomas Daniels9-Apr-15 5:31 Thomas Daniels 9-Apr-15 5:31
 Language Erlend Robaye9-Apr-15 2:17 Erlend Robaye 9-Apr-15 2:17
 Nice Idea Wastedtalent8-Apr-15 2:47 Wastedtalent 8-Apr-15 2:47
 Re: Nice Idea Thomas Daniels8-Apr-15 2:51 Thomas Daniels 8-Apr-15 2:51
 Great stuff! Brady Kelly8-Apr-15 0:04 Brady Kelly 8-Apr-15 0:04
 Re: Great stuff! Thomas Daniels8-Apr-15 0:06 Thomas Daniels 8-Apr-15 0:06
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Sep-21 3:05 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.