基于 N-Gram 文本分类的语言检测器

文本分类是文档处理的一项基本任务，可以自动处理大量的电子文档流。处理某些类别文档的一个困难是存在不同类型的文本错误，例如电子邮件中的拼写和语法错误，以及通过 OCR 处理的文档中的字符识别错误。文本分类必须能可靠地处理所有输入，因此必须能容忍一定程度的此类问题。

基于 N-gram 的文本分类方法可容忍文本错误。该系统体积小、速度快、功能强大。该系统的语言分类效果非常好，在《N-Gram-Based Text Categorization》论文的实验中，对用不同语言撰写的 Usenet 新闻组文章的分类正确率达到 99.8%。该系统在根据主题对一些不同的面向计算机的新闻组中的文章进行分类时，也取得了相当不错的效果，正确分类率高达 80%。对于系统分类效果不佳的情况，也有几个明显的改进方向。

该系统的基础是计算和比较 N-gram 频率曲线。

• 对代表不同类别的训练集数据计算 N-Gram 频率
• 系统会为要分类的特定文档计算一个 N-Gram 频率。
• 系统会计算该文档的 N-Gram 频率与每个类别 N-Gram 频率之间的距离，选择与文档距离最小的类别。

在各种分类任务中，使用 N-gram 频率分布图为文档分类提供了一种简单可靠的方法。

1.引言

文本分类是自然语言处理中的一个重要任务，通常用于将文本归类到预定义的类别中。例如，垃圾邮件过滤器需要将邮件分类为“垃圾邮件”或“非垃圾邮件”；语言检测器需要识别文本的语言。N-Gram 模型是文本分类中常用的一种方法，通过分析文本中连续字符或单词的频率，可以构建出文本的特征向量，进而进行分类。

文档处理的一个基本类型是文本分类，即把收到的文档归入某个预先存在的类别。这种系统的一个应用是将新闻报道从新闻通讯社中分拣出来。对数字化纸质档案进行分类则是另一种应用。这些应用具有以下特点：

• 尽管存在文本错误，但分类工作必须可靠。
• 由于要处理的文件数量庞大，分类工作必须高效，尽可能减少存储和处理时间。
• 分类必须能够识别给定文档何时不符合任何类别，或何时介于两个类别之间。这是因为类别的界限几乎从来都不是一目了然的。

2. N-Gram

简介

在 N-gram 中，N 表示的是序列中单词或字符的数量。根据 N 的不同值，N-gram 可以分为以下几类：

• Unigram (1-gram): 单个词或字符
• Bigram (2-gram): 两个连续的词或字符
• Trigram (3-gram): 三个连续的词或字符
• 以此类推…

例如，对于字符串 “hello”，其 2-Gram（也称为 Bigram）集合为：

• “he”
• “el”
• “ll”
• “lo”

通过分析文本中的 N-Gram 频率，可以捕捉到文本的语言特征。不同语言的 N-Gram 频率分布是不同的，这也是语言检测的基础。

应用

N-Gram 模型在自然语言处理中有广泛的应用，除了文本分类，还包括拼写检查、文本生成和机器翻译等。通过对 N-Gram 频率的统计，可以帮助我们理解和处理语言中的模式和规律。

基于马尔科夫链的废话文学生成器：https://github.com/gobylor/Bullshit-Literature-Generator

通过分析文本中的 N-gram，可以预测下一个词的概率，从而生成连贯的文本。

3. 齐普夫定律

人类语言中总会有一些词比其他词出现得更频繁。表达这一观点的最常见方式之一就是齐普夫定律：人类语言文本中最常见的第 n 个词的出现频率与 n 成反比。

齐普夫定律 - 维基百科 — Zipf’s law - Wikipedia

齐普夫定律（Zipf’s Law）是由美国语言学家乔治·齐普夫（George Kingsley Zipf）在1930年代提出的一种统计规律。该定律描述了自然语言中词频分布的规律：一个文本中第n常用词的频率大约是最常用词频率的1/n。这意味着，第二常用词的频率大约是最常用词的一半，第三常用词的频率大约是最常用词的三分之一，以此类推。

例如，在美国英语文本的布朗语料库中，"the "是出现频率最高的单词，它本身就占所有单词出现次数的近 7%（100 多万次中的 69,971 次）。根据齐普夫定律，排在第二位的单词 "of"的出现率略高于 3.5%（36,411 次），其次是 “and”（28,852 次）。

source：皮特网

语言的使用是有规律性的，这是对3.5万亿份文稿分析后得出的字母和单词使用评率的分析报告。

这一规律的含义是，总有一组词在使用频率上支配着语言中的大多数其他词。这既适用于一般词汇，也适用于特定主题的词汇。此外，从使用频率最高的词到使用频率最低的词，它们之间存在一个平滑的连续关系。频率曲线的平滑性在某种程度上帮助了我们，因为这意味着我们不必过于担心特定的频率阈值。这一规律也是如此，至少近似于人类语言的其他方面。尤其是 N-grams 的出现频率，无论是作为词素形式还是作为词义成分的词素，都是如此。齐普夫定律意味着，使用 N-gram 频率统计法对文档进行分类时，在某一特定等级上切断分布并不十分敏感。这也意味着，如果我们要比较同一类别的文档，它们的 N-gram 频率分布应该相似。

齐普夫定律的成因至今仍未完全明确，但常见的解释包括：

1. 语言经济原则：人们倾向于使用尽可能少的词汇传达尽可能多的信息。
2. 权力法则分布：许多自然和社会现象服从权力法则分布，齐普夫定律正是其中一种特殊情况。

N-Gram 频率可视化：Google Ngram Viewer

4. 基于 N-Gram 的文本分类方法

source：《N-Gram-Based Text Categorization》

主要分为以下几个步骤：

4.1 构建 N-Gram 频率表

首先，从训练文本中提取 N-Gram，并统计其频率。对于每种语言或类别，我们需要构建一个 N-Gram 频率rank表。这个表格记录了每个 N-Gram 出现的频率 rank。例如，对于英语和西班牙语，我们可以分别构建如下频率表：

English: {"he": 10, "el": 8, "ll": 5, "lo": 7, ...}
Spanish: {"ho": 12, "ol": 9, "la": 6, "mu": 5, ...}

通过对大量文本进行统计，可以得到较为准确的 N-Gram 频率分布。这一步的目的是为了捕捉各语言的特征，以便后续进行比较。

4.2 生成特征向量

根据频率表生成特征向量。向量的每个维度对应一个 N-Gram，值为该 N-Gram 在文本中出现的频率 rank。例如，如果我们有一个包含 “ba”, “ab”, “na”, "n "的特征向量，那么对于一个新的文本 “banana”，我们可以生成如下特征向量：

["ba", "ab", "na", "n "]
[3, 1, 2, 4]

这个特征向量反映了新文本中的 N-Gram 分布情况。

4.3 计算相似度

接下来，我们需要比较待检测文本的 N-Gram 特征向量与各语言的特征向量。常用的距离度量方法有曼哈顿距离和欧几里得距离。这里我们以曼哈顿距离为例，计算两个向量之间的距离。假设有两个特征向量 A 和 B，曼哈顿距离的计算公式为：

distance = |A1 - B1| + |A2 - B2| + ... + |An - Bn|

距离越小，表示两个向量越相似，也就意味着待检测文本与该语言的特征向量越接近。

欧几里得距离： 两点之间的“直线”距离，源自于我们在日常生活中最直观的距离概念

曼哈顿距离: 又称为“城市街区距离”或“L1距离”，表示在一个网格状路径中两点之间的距离。这种度量方式类似于沿着城市街区的路径行走，而不是直线距离。

采用曼哈顿距离的原因：

1. 计算效率

曼哈顿距离的计算相对简单，只需要进行加法运算，而不涉及平方和开平方等操作。这使得在处理高维度的文本数据时，计算速度更快，资源消耗更低，尤其在大规模数据集上具有优势。

2. 易于稀疏数据的处理

文本数据通常是高维且稀疏的，即大多数特征的值为零。曼哈顿距离在处理稀疏数据时效果较好，因为它直接计算特征值的绝对差异，不会受到零值特征的影响。相比之下，欧几里得距离会因为平方和的存在，对稀疏数据中的零值特征计算产生累积的误差。

3. 鲁班行更强

曼哈顿距离对离群点的敏感度较低。由于文本数据中的特征值可能存在较大的差异，曼哈顿距离的绝对值差异计算方式能够更好地处理这种情况，避免因少数极端值对整体距离计算的显著影响。

4. 匹配特种

在文本分类任务中，不同的特征（如词或Ngram）对分类结果的重要性可能不同。曼哈顿距离在计算时，对所有特征都给予了相同的权重，这在一定程度上与文本分类任务中的特征权重分布相匹配，尤其是在没有特征加权的情况下。

4.4 分类

最后，选择相似度最高的语言或类别作为检测结果。即对于待检测文本，我们计算其与各语言特征向量的距离，并选择距离最小的语言作为最终分类结果。

5. 实现语言检测器

Repo: https://github.com/gobylor/language-detector

生成语料库：

• 对各语言的训练集生成 trigram 集合，并按频率排序

语言检测：

• 识别语言文字

• 使用 ngram 文本分类

5.1 生成预料库

对各语言的训练集生成 trigram 集合，并按频率排序

例子：

// 英语
Eng: []string{" th", "the", " an", "he ", "nd ", "and", "ion", " of", "of ", "tio", " to", "to "}
// 德语
Deu: []string{"en ", "er ", "der", " un", "nd ", "und", "ein", "ung", "cht", " de", "ich", "sch"}

5.2 识别文字

在 Unicode 中，文字（script）是字母和其他书写符号的集合，用于在一种或多种书写系统中表示文本信息。有些脚本只支持一种书写系统和语言，例如亚美尼亚语。其他脚本支持多种不同的书写系统；例如，拉丁字母支持英语、法语、德语、意大利语、越南语、拉丁语本身以及其他几种语言。

文字在 UTF-8 中以非重叠 unicode 范围的形式呈现。

我们只需按字符数遍历字符串，文本中占字符数最多的字母即为结果文字。根据不同的语言文字支持的语言进一步识别语言。

5.3 基于 trigram 的文本相似度计算

trigram

trigram是 n-gram 的一种特殊情况，由三个字符组成。

假设我们有以下文本： love it，这段文字的词组是lo、lov、ove、ve_、e_i、it、it。这里的下划线字符 _ 只代表单词的边界。

优点

• 简单
• 速度快
• 内存和 CPU 效率高
• 通用方法，适用于所有语言，无论其语法如何

缺点

• 对于短文本（小于 200-300 个字母），可能会出现错误结果。按单词分割输入文本，然后在语言词典中查找单词。这种方法可能会为短文本提供更好的结果，但实现起来要复杂得多，而且速度较慢。这就需要在数据库或 Bloom 过滤器中存储所有单词。
• 为了获得最佳的终极解决方案（但也相当复杂），可以采用混合方法：对长文本使用 trigram 算法，对短文本使用词典查询。

计算相似度

语料库保存了 300 个最常出现在每种语言中的 trigram，并按出现频率排序。

对于输入文本，我们会计算 trigram 并按频率排序，然后将其与已知的语言配置文件进行比较。

与输入文本的语言距离最相似的语言就是最可能的语言。

5.3 置信度

置信度取决于以下因素：

• 给定文本中的 trigram 数量
• 最可能的语言与次可能的语言之间的差异

它可以用阈值函数表示为一个二维空间，将其分为 "可信 "和 "不可信 "两个区域，这个函数是一个双曲线。

这意味着，给定文本中唯一的 N-grams 越多（与文本长度相关），我们就越有可能得到可靠的结果。