xljのblog

排序

查找 之前的内容已经介绍了关于线性、树形和网状的数据结构，本章介绍数据结构的重要操作：查找 基本概念 数据表：数据元素的有限集合 关键字：在数据表中可以最为查找排序的数据元素 查找：根据给定数据元素查找其在数据表中的位置 静态查找表和动态查找表：查找的数据不在数据表中，根据之后是否会将该元素插入到数据表中来判断是动态查找表还是静态查找表 查找效率：衡量指标,平均查找长度（ASL)，含义是关键字比较次数的数学期望。 ASL=∑i=1nPi∗CiASL=\displaystyle\sum_{i=1}^n P_i*C_iASL=i=1∑n​Pi​∗Ci​ 装载因子:数据表中装载元素的情况，计算公式 α=nm\alpha=\frac{n}{m}α=mn​ 顺序表的查找 顺序表的查找有两类：顺序查找和折半查找 顺序查找： n个元素的表从头查找到尾，边查找边比较 在pip_ipi​等概率的情况下，平均查找长度为ASL=n−12ASL=\frac{n-1}{2}ASL=2n−1​ 如果概率不同，可以从概率较高的一端开始查找，以提高查找效率 同样，如果是按照链式存储的方式存储数据表的，查找方式和 ...

BERT模型MRCP任务实践 AI炼丹三境界 伫倚危楼风细细，conda环境有问题。 衣带渐宽终不悔，调参调到人憔悴。 众里寻他千百度，炉中有丹似无丹。 无聊想到的小诗，作为我第一个AI实践练习的开头，conda环境配置了很长时间，一直没有搞定TensorFlow的环境。 实际过程中的问题 TensorFlow环境安装 本次是我第一次利用anaconda在Windows系统的虚拟环境内安装TensorFlow,所以出现了很多问题，这些问题包括环境的配置，参数的设置，也包括我对于错误的误判。 Bert模型Github源代码是基于TensorFlow 1.x版本实现的，所以在虚拟环境中必须使用TensorFlow 1.x,而不能会用TensorFlow 2.x。 TensorFlow是有GPU版本，而GPU的加速是可以极大加快结果的运算，但是我在配置环境时，总是发生错误，pycharm无法识别环境中的第三方tensorflow-gpu的库，所以还是使用了CPU版本的TensorFlow。后面一定会再尝试使用GPU进行运算的。 最新修改（2022.5.6）：使用Tensor ...

树和森林 本文主要复习树和森林的内容，树和森林的所有操作都和二叉树有关，所以树和森林也会涉及到存储结构、树和森林与二叉树的转换、树和森林的变量。森林其实就是由好几棵树组成的，所以我们先讨论树。 树的存储结构 树主要有四种存储结构，分别为：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法。其中最重要的是 孩子兄弟表示法，虽然这种表示法不太符合正常逻辑，但是解决了许多操作上的问题。 双亲表示法 双亲表示法使用一个数组来存放树的结点，结点内包含两个域，分别是数据域和双亲域，双亲域存放自己的双亲结点索引，根结点双亲域为-1。 双亲表示法对于自己父亲结点的搜索较快，存储空间也比较节约，但是如果要找自己的孩子就必须遍历整个数组，比较耗时。同时找兄弟的操作也比较困难。 对于双亲表示法的改进就是对于结点增加两个数据域，一个是第一个孩子的索引，第二个是右兄弟的索引。 孩子表示法 孩子表示法有两种方式，一个是多重链表，另一个是孩子链表。多重链表法类似于双亲表示法的改进，不大采用这种方法。孩子链表法其实是将一个一位数组顺序存储结点信息，然后在每个数组后面连一个孩子链表，具体形式如下： 双亲孩子表示 ...

BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding BERT(Bidirectional Encoder Representations from Transformer)是近几年最重要的NLP的模型，正是由于该模型的建立，使得NLP领域也能够使用到预训练的通用大模型，使得较小的问题得到了更好的解决，极大地推动了NLP的发展。 BERT模型是基于Transformer模型所设计的，他的设计思路是依赖同时期的两个模型ELMo和GPT，BERT是融合了ELMo和GPT的优点而创建。ELMo考虑到了序列前后的信息来预测中间内容，但是架构是比较老的RNN；GPT使用了Transformer，但是他只是考虑了左边的信息，利用之前的序列预测之后内容。因此BERT使用Transformer模型实现了双向的预测，可以说BERT的成功是站在巨人的肩膀上的。 如果读过Transformer那一篇论文的话可以知道，整个Transformer模型是有encoder和decoder两个部分组成的，dec ...

二叉树 基本概念 树的基本概念 特点 当n = 0时，T称为空树； 如果n > 0，则树有且仅有一个特定的被称为根（root）的结点，树的根结点只有后继，没有前驱； 当n>1时，除根结点以外的其余结点可分为m(m>0)个互不相交的非空有限集T1、T2、…、Tm，其中每一个集合本身又是一棵非空树，并且称它们为根结点的子树（subtree）。 术语 结点（node） 结点的度（degree of node） 终端结点(terminal node)—叶子(leaf) 非终端结点(nonterminal node) —分支结点 树的度（degree of tree） 孩子(child)和双亲(parent) 兄弟(sibling) 堂兄弟 祖先(ancestor) 子孙（descendant） 结点的层次（level） 树的深度（depth）—高度（height） 有序树 无序树 森林(forest) 表示方式 嵌套集合 广义表 凹入表示 二叉树的基本概念 定义 二叉树BT是有限个结点的集合。当集合非空时，其中有一个结点称为二叉树的根结点，用BT表示， ...

Attention is All You Need(Transformer模型) Transformer模型是近5年最有名的NLP模型，它只使用self-attention(自注意力)机制，而非 Convolutional Neural Networks (CNN，卷积神经网络） 或者Recurrent Neural Network（ RNN，循环神经网络）。该模型的提出解决了原本在RNN难并行、较长距离的记忆效果不佳的问题。 受限于个人的知识储备并且是第一次读这篇论文，本文只从整个模型的结构和和效果上进行解读，不涉及具体的应用。同时由于是初读这篇文章，解读可能会有偏差与错误，希望大家指正。由于这篇论文太过有名，后期还会反复阅读和理解，这次只是初读后的理解记录。 模型结构 Transformer模型最早被提出是用于解决翻译问题，后来也被用于包括计算机视觉等领域。他的整个模型结构分为两个部分：Encoder(编码器)和Decoder(解码器)。这两个部分又含有四个小的模块。接下来会逐一进行解释。 编码器和解码器 大多数的竞争性神经序列传到模型都是利用了编码器和解码器的结构。在本论文中编 ...

广义表 基本概念 定义：由n≥0个表元素α1 ,α2 , … , αn 组成的有限序列，其中表元素αi (1≤i≤n) 或者是一个数据元素 (可称为单元素或原子)，或者是一个表(称为子表)。记作 LS = (α1 ,α2 , … , αn ) 广义表的数据元素可以是单独一个元素也可以是一个表，所以其为多层次结构。 α1为表头，其余的为表尾。 广义表中括号的重数为广义表的深度。 广义表的定义是递归的，所以广义表的深度可以是无穷。 广义表的操作有取表头，取表尾。 广义表最高一层的结点个数即为表长。 广义表中每个表都是带表头的，表头主要放引用次数信息。 广义表的存储 广义表采用链式存储方式，他的结点设计有一定的特殊性（采用联合体设计方式），包含三类数据，分别为1）表头的引用计数 2）单元素的元素值 3）表的指针 结点设计如图 广义表例子如图 problem:表的深度怎么求？ 利用递归求所有的字表层数加一。 广义表的结点和类定义 类定义 class genlist //广义表类定义{ protected: glnode * first; ...

图 图是一种一对多，多对多的非线性结构，在离散数学中是非常重要的内容，他的应用非常广泛，他的最重要的功能是寻找最短路径。数据结构中的图除了会介绍离散数学中基本的内容，更加注重图的存储结构，基本操作和一些关于图的重要算法。 基本概念 定义：G=（V,E），其中V是数据元素的集合（可以理解为顶点集合），E是数据元素的关系集合（可以理解为边集合。<v,w>表示从v到w的一条路径。 无向图与有向图：顶点对是否是有序的，有序为有向图<v,w>，无序为无向图(v,w)。数据结构这里要设置一些限制，数据结构的图不含环(<v,v>)和多重边的情况 图的一些术语 完全图：n个顶点，n(n+1)/2条边 权 邻接点：一条弧两端的点 子图 顶点的度 路径 简单路径和回路：经过顶点不重复的路径是简单路径；路径开始和结束是同一个顶点则为回路 连通图和连通分量（无向图，极大连通子图） 强连通图和强连通分量（有向图） 生成树：极小连通子图 基本操作 插入顶点 插入边 删除顶点和附属边 删除边 取边上权 取邻接点 取下一个邻接点 遍历图 图判空 图的存储结构 作为一 ...

数组 数组是长度受限的线性表 数组的定义：存储相同数据类型的一块连续的存储空间。 数组的存储 顺序存储 无论是高维数组还是一维数组，最终落实到具体的存储上都是一维的形式，只是地址搜索格式不太一样。 一维数组寻址公式 Loc(i)=Loc(0)+i∗sLoc(i)=Loc(0)+i*s Loc(i)=Loc(0)+i∗s 0≤i≤n−10≤i≤n-1 0≤i≤n−1 其中，p为首地址，s为每个元素占的空间 二维数组寻址公式 高维数组的寻址就会涉及到是按照什么顺序排列的，设二维数组A[m][n],数组有m行，n列。如果是按照行排列，寻址公式为： Loc(i,j)=Loc(0,0)+(i∗n+j)∗sLoc(i,j)=Loc(0,0)+(i*n+j)*s Loc(i,j)=Loc(0,0)+(i∗n+j)∗s 0≤i≤m−1,0≤j≤n−10≤i≤m-1, 0≤j≤n-1 0≤i≤m−1,0≤j≤n−1 其中，s为每个元素占的空间。如果是按照列排序则i,j互换即可。 高维数组寻址公式 高维数组寻址就是类比二维数组。 稀疏矩阵 矩阵不一定都是放满数据的，对于那种没有放满的矩阵可 ...