ngram模型中文语料实验step by step(2)-ngram模型数据结构表示及建立

2024-05-13 06:08
文章标签 数据结构 模型 中文 实验 建立 表示 step 语料 ngram

本文主要是介绍ngram模型中文语料实验step by step(2)-ngram模型数据结构表示及建立，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

n元ngram模型本质上就是trie树的结构

，逐层状态转移。在sun拼音中是采用的是逐层按照顺序用vector表示，查找的时候逐层二分查找。sun拼音的建立ngram模型的方法也是以按照字典序排好序的<ngram元组,次数>序列作为输入建立起来的。

利用顺序存储+二分查找应该是最节省空间的了。但是效率要受一定影响。其余的trie树实现包括可以利用map(hash_map更耗费空间一点），sun拼音也有一个基于map的trie树实现，sirlm是利用自己的一个LHash实现的类似。另外利用double array trie对于这种预先已经排好序不需要动态添加删除的情况也比较适合但是空间占用较大。TODO 以后会尝试比较下，目前我也是按照sun拼音的顺序存储实现的。

image

核心数据结构表示

struct Leaf //底层ngram level元素
{WordID id; //词的编号union{FREQ_TYPE freq; //建立的时候需要先统计次数,最后使用的时候只需要下面的概率值
            PR_TYPE pr;};
}
struct Node : Leaf //非底层ngram level元素
{int child;  //指向下一level的首地址PR_TYPE bow; //回退时候需要用到的系数，最底层叶子不需要
}
typedef std::vector<Node> NodeLevel;
typedef std::vector<Leaf> LeafLevel;
/**核心数据结构*/
vector<NodeLevel > m_nodeLevel; ///非底层 0root, 1gram- (n-1) gram
LeafLevel m_leafLevel; ///底层对应的ngram
为了节约内存空间，sun拼音的这种表示方法区别了底层的节点和上层节点，带来的麻烦是代码稍微烦了一点因为要区别处理了。
例如对于3元模型，m_nodeLevel[0]表示root m_nodeLevel[1], m_nodeLevel[2]表示第一二层，m_leafLevel表示第3层即底层。
注意这个模型是可以改进加速的，sunpinyin用了线索化的方法，P(ABC) P(BCD）那么P(ABC）到C的时候直接转移到P（B)省掉了去level1二分查找的过程，
其实吧我觉得一个简单的方法是直接把level1的存储改为大的vector然后直接按照id,下标索引O(1)访问即可了，因为level1占内存不多而其二分查找最耗时。
更好的优化以后再考虑吧，这个模型基本够用了，我用这样一个模型存储的占内存260M的ngram信息，进行简单的3元模型概率分词也能达到4-5/M每秒的速度。

ngram模型的建立算法

   /**
     * 初始化构建n gram模型的资源
     */void init(int n){//-------设置n元模型m_nLevel = n;//-------初始化核心数据结构空间m_nodeLevel.resize(n);for (size_t i = 1; i < n; i++){m_nodeLevel[i].reserve(kMemInitAllocSize);}m_leafLevel.reserve(kMemInitAllocSize);//        m_level.resize(n + 1, NULL);//添加根节点m_nodeLevel[0].push_back(Node(0, 0, 0));//-------初始化nr 二维数组m_nr.resize(n + 1);for (size_t i = 0; i < n + 1; i++){m_nr[i].resize(kNGramMaxCutR, 0);}//-------初始化剪枝数组m_cut.resize(n + 1, 0);}
 /**
     * 注意是按照word id字典排序输入的
     * 如果ngram[i] (0<i<=n-1) 为排除在外的词，则只统计ngram[0..i-1]的出现次数；
     * 如果ngram[i] (0<=i<=n-1) 为句子分割词的ID（我们在参数中指定为10），则只统计ngram[0..i]的出现次数。
     * 如果某个trigram为(9, x, y)，则直接就跳过了；
     * 如果是(x, 9, y)，则只统计unigram (x)；如果是(10, x, y)，则统计unigram (10),bigram(10,x),trigram(10,x,y)；
     * 如果是(x, 10, y)，则统计unigram(x)和bigram (x, 10)。
     */void addNGram(const WordID* ngram, FREQ_TYPE fr){int ch;bool brk = isExcludeID(*ngram);//如果是需要忽略的位置，特别是指标明岐义的位置，则不统计任何信息 (9,x,y)否则统计一元信息先if (!brk){m_nodeLevel[0][0].freq += fr; //统计1gram的总数目 对应0gram}elsereturn;//如果需要先手工增大空间reallocMem();bool branch = false;//i = 1 第1个level 对应 ngram[i - 1]即  ngram[0] 要求ngram[0]不是exclude id 9//如果ngram <100,200,300> 是按顺序 –> <100> <100,200><100,200,300>for (int i = 1; (!brk && i < m_nLevel); i++){NodeLevel & pv = m_nodeLevel[i - 1];NodeLevel & v = m_nodeLevel[i];//1.如果前面出现新状态则后面必定都是新状态  branch = branch ||     // 1,2,3 | 2,2,3 对于<2,2>来说这是一个新的状态需要push_back因为上一个level已经发现时新状态了//2.第一次addNGram且i==1时判断用  branch = (pv.back().child >= v.size()) ||//3.如果当前的 id变化了则必然是新状态 branch = (v.back().id != ngram[i - 1]) || // 1, 2, 3| 1, 4, 3对于 <1,4>来说是一个新状态因为本level中由 2 ->4// 另外举例:1 2 3, 1 2 4, 2 2 4, 2 4 4  注意level 2 的 第3个 2是一个新的level 2的状态 而第2个2不是！branch = branch || (pv.back().child >= v.size()) || (v.back().id != ngram[i - 1]);if (branch){if (i == m_nLevel - 1)ch = m_leafLevel.size();elsech = m_nodeLevel[i + 1].size();v.push_back(Node(ngram[i - 1], ch, fr));}else{v.back().freq += fr;}brk = (i > 1 && isBreakID(ngram[i - 1])) || isExcludeID(ngram[i]); //判断下一个 i+1 level对应的ngram[i]是否有效, 注意开头是break id的所有unigram,bigram,trigram都还要统计}//n元组加入到叶子levelif (!brk){if (fr > m_cut[m_nLevel]){m_leafLevel.push_back(Leaf(ngram[m_nLevel - 1], fr));}else //尽管没有添加次数少被剪掉的节点但是仍然统计其次数{m_nr[m_nLevel][0] += fr;m_nr[m_nLevel][fr] += fr;}}}

这样我们就建立好了ngram模型了，注意最后需要添加tail方便二分查找。比如再第一层的状态A位置迭代器为iter,则查找A->C状态 即第二层中对应前面是A当前状态是C的状态，只需要在m_nodeLevel[2]的下标为[iter->child,(iter + 1)->child)的范围内查找。

ngram简单频率模型和概率模型测试结果:

pr对应相对概率P(END|AB..) pr2对应绝对概率P(AB…END),如果概率为0标示为-1。这是一个完全按照最大似然概率的简单ngram模型，没有任何光滑，这会造成很多无概率情况出现，后面会继续介绍模型的光滑方法。

testNgram/test_freq.input
line ------- 美丽 的 一天
freq ------- 0
line ------- 最 伟大 的
freq ------- 0
line ------- 小红 读 了
freq ------- 1
line ------- 小明 读 了
freq ------- 1
line ------- 了 一本 书
freq ------- 0
line ------- b 美丽 的
freq ------- 3
line ------- 美丽 的
freq ------- 3
line ------- 美丽 的 世界
freq ------- 1
line ------- 美丽 的 心灵
freq ------- 2
line ------- 美丽
freq ------- 3
line ------- 本书 b
freq ------- 2
line ------- 本书
freq ------- 2
line ------- 一 本书 b
freq ------- 2
line ------- 的 心灵 b
freq ------- 2
line ------- b 小明 读
freq ------- 1
line ------- b b b
freq ------- 0
line ------- b b
freq ------- 0
line ------- b
freq ------- 11  //注意break id 10出现的次数统计为11，这里每个句子的结束和下一个句子的开始算作1个break id,另外最后一个句子的结束不统计,最终break id的个数其实=start pos的个数
i ------- 2
i ------- 1
i ------- 0
line ------- 美丽 的 一天
pr ------- -1
pr2 ------- -1
line ------- 最 伟大 的
pr ------- -1
pr2 ------- -1
line ------- 小红 读 了
pr ------- 1
pr2 ------- 0.025
line ------- 小明 读 了
pr ------- 1
pr2 ------- 0.025
line ------- 了 一本 书
pr ------- -1
pr2 ------- -1
line ------- b 美丽 的
pr ------- 1
pr2 ------- 0.075
line ------- 美丽 的
pr ------- 1
pr2 ------- 0.075
line ------- 美丽 的 世界
pr ------- 0.333333
pr2 ------- 0.025
line ------- 美丽 的 心灵
pr ------- 0.666667
pr2 ------- 0.05
line ------- 美丽
pr ------- 0.075
pr2 ------- 0.075
line ------- 本书 b
pr ------- 1
pr2 ------- 0.05
line ------- 本书
pr ------- 0.05
pr2 ------- 0.05
line ------- 一 本书 b
pr ------- 1
pr2 ------- 0.05
line ------- 的 心灵 b
pr ------- 1
pr2 ------- 0.05
line ------- b 小明 读
pr ------- 1
pr2 ------- 0.025
line ------- b b b
pr ------- -1
pr2 ------- -1
line ------- b b
pr ------- -1
pr2 ------- -1
line ------- b
pr ------- 0.275
pr2 ------- 0.275

这篇关于ngram模型中文语料实验step by step(2)-ngram模型数据结构表示及建立的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/984887。

相关文章

大模型研发全揭秘：客服工单数据标注的完整攻略

大模型研发全揭秘：客服工单数据标注的完整攻略

在人工智能（AI）领域，数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者，掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中，工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注，不仅能够帮助提升客服自动化系统的智能化水平，还能优化客户服务流程，提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
Andrej Karpathy最新采访：认知核心模型10亿参数就够了，AI会打破教育不公的僵局

Andrej Karpathy最新采访：认知核心模型10亿参数就够了，AI会打破教育不公的僵局

夕小瑶科技说 原创  作者 | 海野 AI圈子的红人，AI大神Andrej Karpathy，曾是OpenAI联合创始人之一，特斯拉AI总监。上一次的动态是官宣创办一家名为 Eureka Labs 的人工智能+教育公司 ，宣布将长期致力于AI原生教育。 近日，Andrej Karpathy接受了No Priors（投资博客）的采访，与硅谷知名投资人 Sara Guo 和 Elad G
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
Retrieval-based-Voice-Conversion-WebUI模型构建指南

Retrieval-based-Voice-Conversion-WebUI模型构建指南

一、模型介绍 Retrieval-based-Voice-Conversion-WebUI（简称 RVC）模型是一个基于 VITS（Variational Inference with adversarial learning for end-to-end Text-to-Speech）的简单易用的语音转换框架。 具有以下特点 简单易用：RVC 模型通过简单易用的网页界面，使得用户无需深入了
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
图神经网络模型介绍（1）

图神经网络模型介绍（1）

我们将图神经网络分为基于谱域的模型和基于空域的模型，并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络：谱图卷积网络、切比雪夫网络和图卷积网络。 （1）谱图卷积网络 卷积定理：函数卷积的傅里叶变换是函数傅里叶变换的乘积，即F{f*g}
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
【生成模型系列（初级）】嵌入（Embedding）方程——自然语言处理的数学灵魂【通俗理解】

【生成模型系列（初级）】嵌入（Embedding）方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入（Embedding）方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节：嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”，它将文本中的单词或短语转换成计算机能够理解的数学形式，即向量。 正如翻译机将一种语言
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2