65.9K
CodeProject 正在变化。 阅读更多。
Home

Gibberish 分类算法及其在 C# 和 Python 中的实现

Thomas Daniels
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.92/5 (15投票s)

2015年4月8日

CPOL

8分钟阅读

viewsIcon

52665

downloadIcon

1198

用于判断文本是否为乱码的算法，以及在 C# 和 Python 中的实现。

引言

此乱码分类算法旨在检测文本是否有效，或是否为键盘随机输入的文本。它会返回一个百分比，低值表示有效文本，高值表示乱码文本。该算法仍处于早期阶段，因此仍可能返回一些不正确的值。

如果结果低于 50%，则文本很可能是有效的。如果结果高于 50%，则文本很可能是乱码。该算法针对英语和较长文本进行了优化；对于较短文本（例如，一句话），它仍然有效，但结果准确性会降低。除非输入字符串为 null 或为空（此时返回 0%），否则该算法不会返回低于 1% 的百分比。

C# 实现可用于 .NET Framework 4.0 及更高版本（下载中的二进制文件目标为 .NET 4.5）。Python 实现可用于 Python 2.x 和 Python 3.x。

源代码也可在 GitHub 上找到：C# 实现，Python 实现。

算法

该算法会检查三项内容，然后计算最终得分

  • 它检查唯一字符的数量（以百分比表示，按 35 个字符的块计算）是否在正常范围内。
  • 它检查元音字母在字母中所占的比例（以百分比表示）是否在正常范围内。
  • 它检查单词/字符比例（以百分比表示）是否在正常范围内。

检查唯一字符

为了检查唯一字符的百分比，我们首先将字符串分成 35 个字符的块。这样做时，最后一个块可能不足 35 个字符——在这种情况下，如果块的大小小于 10 个字符，则将这些字符添加到倒数第二个块中，并删除最后一个块。（仅当有两个或更多块时才可能）

将字符串分成块后，创建一个空列表。然后遍历所有块。计算当前块中唯一字符的数量。然后将其除以块中字符的总数，并将其添加到列表中。

完成上述步骤后，计算列表的平均值，乘以 100，然后返回。

这计算了块中唯一字符的百分比；是否在正常范围内将在之后进行检查。

检查元音

在检查元音数量时，首先初始化整数 vowels 和 total。我们遍历给定字符串中的每个字符。如果该字符不是字母，则继续执行，不对该字符做任何处理。如果它是字母，则 total 增加 1，并检查它是否为元音：如果是，则 vowels 增加 1。遍历完所有字符后，返回 vowels / total * 100。

检查单词/字符比例

要检查单词/字符比例，请使用正则表达式 [\W_] 分割字符串（按所有非单词字符和下划线分割）。然后从结果数组中删除所有仅包含空格/空项。之后，将单词数量除以字符数量，乘以 100，然后返回。

计算“偏差得分”

以上函数都返回百分比，但我们不能直接使用它们来计算最终得分——我们必须先计算百分比与正常范围的偏差程度，然后给出一个得分。得分越高，偏差越大。

计算此得分的函数必须接受三个参数：给定的百分比、正常范围的下限和上限。

  1. 如果百分比低于下限，则返回 log(lower_bound - percentage, lower_bound)（其中第二个参数是基数）。
  2. 如果百分比高于上限，则返回 log(percentage - upper_bound, 100 - upper_bound)。
  3. 如果百分比既不低于下限也不高于上限（即在正常范围内），则返回 0。

计算最终得分

使用以上所有函数，我们可以计算出最终得分！首先，我们使用前三个函数计算百分比。然后，我们为每个函数调用偏差得分函数。

  • 对于元音百分比，下限是 45，上限是 50 -> deviation_score(percentage, 45, 50)
  • 对于唯一字符百分比，下限是 35，上限是 45 -> deviation_score(percentage, 35, 45)
  • 对于单词/字符比例，下限是 15，上限是 20 -> deviation_score(percentage, 15, 20)

这些界限是从哪里来的？仅仅是通过测试和运行从互联网上获取的一些段落，通过所有 3 个函数得出的。

在计算出这些偏差得分后，我们对其进行处理，如果得分低于 1，则将其设置为 1。原因是我们将对这些得分进行 log10 计算；得分低于 1 可能导致负对数（或在为零时出现错误），这是不希望的。

下一步是计算所有偏差得分的以 10 为底的对数，然后除以 6。（6 是因为 log10 操作的最大可能结果是 2，而我们这里有三个操作）。我们返回 max(final_score, 1)。如果最终得分低于 1，我们不返回精确的最终得分，因为即使最终得分是 0%，输入的文本也并非不可能乱码；只是不太可能。最终得分越高，字符串是乱码的可能性就越大。

C# 和 Python 实现

在 C# 实现中，所有方法都是静态的，并放在一个 GibberishClassifier 类中。在 Python 实现中，所有方法都放在一个 gibberishclassifier 模块中。Python 版本可在 Python 2.x 和 Python 3.x 中使用。由于 Python 2.x 的除法默认会截断，因此我们必须在文件顶部添加此内容

from __future__ import division

完成此操作后，Python 2.x 中的除法将不再截断。

第一个实现的方法是将字符串分割成块。C# 方法使用 for 循环和 Substring 来获取适量的字符。Python 方法使用 for 循环、range 和切片表示法。

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);
        chunks.Add(text.Substring(i, size));
    }
    int lastIndex = chunks.Count - 1;
    if (chunks.Count > 1 && chunks[lastIndex].Length < 10)
    {
        chunks[chunks.Count - 2] += chunks[lastIndex];
        chunks.RemoveAt(lastIndex);
    }
    return chunks;
}

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

然后实现获取每个块的唯一字符百分比的方法。它使用了上面的方法。C# 实现使用 .Distinct().Count() 来获取一个块中唯一字符的数量，并使用 .Average() 来计算块中所有唯一字符百分比的平均值。Python 实现使用 len(set(chunk)) 来获取一个块中唯一字符的数量，并使用 sum 来获取所有百分比的总和，然后除以百分比的总数。

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;
}

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

下一个方法是获取元音字母百分比的方法。

C# 方法使用 !Char.IsLetter 来检查字符是否不是字母；在这种情况下，我们转到字符串中的下一个字符。如果它是字母，它会增加 total 变量，并检查它是否为元音，使用 "aeiouAEIOU".Contains(c)。如果是元音，它会增加 vowels 变量。在方法结束时，如果 total 不为零，则返回百分比；如果为零，则方法返回 0。

Python 方法使用 not c.isalpha() 来检查字符是否不是字母；在这种情况下，我们转到字符串中的下一个字符。如果它是字母，它会增加 total 变量，并使用 c in "aeiouAEIOU" 检查它是否为元音。如果是元音，它会增加 vowels 变量。在方法结束时，如果 total 不为零，则返回百分比；如果为零，则方法返回 0。

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;
    }
}

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

在该方法之后，是计算单词/字符比例的方法。

C# 方法使用 Regex.Split 方法（位于 System.Text.RegularExpressions 中）来分割字符串。然后使用 LINQ 的 .Where 方法删除所有仅包含空格的项（它使用 String.IsNullOrWhitespace 方法来检查），并使用 Count() 方法获取单词数量。

Python 方法使用 re.split（需要 import re）来分割字符串，并使用 x for x in ... if ... 来删除所有仅包含空格的项。它使用 x.strip() != "" 来检查字符串是否仅包含空格或为空。然后使用 len 方法找出单词数量。

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;
}

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

下一个方法是计算偏差得分的方法。C# 实现使用 Math.Log，而 Python 实现使用 math.log（需要 import math）。

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;
    }
}

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

最后一个方法是进行实际分类的方法。如果输入的字符串为空或 null (C#) 或 None (Python)，则返回 0%。它调用上述方法，计算偏差得分，并计算最终得分，如算法所述。

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);
}

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)

历史

  • 2015 年 4 月 17 日：对空字符串返回 0%。
  • 2015 年 4 月 9 日：当字符串中没有字母时，避免除以零（在计算元音百分比的方法中）。
  • 2015 年 4 月 8 日：第一个版本。
乱码分类算法及 C# 和 Python 实现 - CodeProject - 代码之家
© . All rights reserved.