二叉查找树

二叉查找树的特征(递归) ——或者是一棵空树或者是具有如下特性的二叉树：

• 若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
• 它的左、右子树也分别是二叉排序树。
• 中序遍历二叉排序树可得到一个关键字的有序序列。

在一般情况下，查找和插入的时间复杂度为logN, 但是在极端情况下会退化为链表，此时查找变为顺序遍历，失去了排序树的意义。——构造的二叉查找树的形状依赖于数据项，且依赖于它们加载的顺序

二叉查找树平衡性很差（即失衡）时，可用AVL树、红黑树和伸展树进行改进。其中AVL树和红黑树是高度平衡的，伸展树是加权平衡的(将常用的数据项放在树中接近根部的位置)

捣腾了一晚上的caffe。。环境配置什么的，真的是很容易上头。

官方安装文档

以下为踩坑过程。

【如果你的VS是2017版本，请直接看下一部分】

首先下载windows适用的caffe版本

在下载好的文件中 Copy .\windows\CommonSettings.props.example to .\windows\CommonSettings.props

打开该配置文件，按自己的电脑情况对GPU支持，CuDNN及Python支持进行配置。由于我的破本本没有独显，所以只能用CPU了。。

1
2

<CpuOnlyBuild>true</CpuOnlyBuild>
<UseCuDNN>false</UseCuDNN>

使用VS打开sln 文件，我的是VS2017版本而官网要求的是13或15版本，暂时不知后面将会遇到什么 问题。。

对项目的错误检查做一下设置，VS的报错有多烦人。。用过的都知道。。libcaffe项目→属性→C/C++→常规→将警告视为错误 设置为否。如果不设置的话在编译boost库的时候会由于文字编码的警告而报错。选择编译环境为Release，x64

辩论赛打输了，挺难受的。确实一开始就没对队友报太大希望，结果真的也没让我”失望”。

安排的一辩，上去东拉西扯3分钟，我在后面听了都觉得尴尬，不知所云，然后留给我的二辩时间不够，稿子念了不到三分之二。一辩在自由辩论的环节，也没有回答任何问题。我的室友，回答了一个问题，我已经很满足了。还有一个女生，从头到尾，一言不发。就我跟师兄在那，尽力去反驳对方观点。我觉得好累啊。怎么能这样？

最后53:57输了。我原本对这个辩题信心十足的，可是对于队友的表现，我真的非常非常失望。

结束后一辩过来跟我道歉，我跟他说：没事。看着他愧疚的样子，我也说不出别的话来。

早两周让他们准备好反方论点，以及反驳的例子，结果昨天晚上才发来材料，短短几段。我就知道要凉了。

结束了，看着我的三页材料，特意买的一本书，觉得好气啊，又无处发作。很想问我是来请你们看戏的吗？转念一想，算了算了，一场辩论赛而已，也不是八强淘汰课。可能就是，只有我和师兄俩看得比较重要吧，其他三人都觉得无所谓。

长叹一声，没办法，人只能控制自己的行为，而无法控制别人的态度。

所以还是只能万事准备好PlanB。

认真准备了两天系统建模的期中考试，结果简单地一匹。不过总算有时间清空一下脑子，想点别的东西了。

回顾这三个月，真快，最大的感受莫过于：东西没怎么学到，各种群倒是加了一大堆。。

人把自己置身忙碌之中，有一种麻木的充实，但是丧失了真实，你的青春不过也只有这些日子。

没错了，是被各种deadline推着走的。

看系统建模的PPT时，我注意到下面的脚注写了一个：2003 。 真可笑，十几年前的东西，我学这些究竟有什么意义？

想想自己的时间都去了哪里？上课，简单的不想听，难的跟不上…；写作业，磨磨唧唧；写实验，全靠悟性；看工程实践的东西，理论弄了一大堆，真正要开始做了，又觉得前面的工作跟本没有抓住核心；确定了自己的方向，而没有对应的计划；说着要提高编程能力，然而跟我一年前刚拿起数据结构开始看的时候根本没有什么区别…所以，我究竟在干什么…？

还有不分主次，不求甚解的恶习。总是把简单的先斗志昂扬地做完了，剩下看不懂的困难的一直拖一直拖，最后虎头蛇尾。

赵老师在高网考试完，同学们纷纷吐槽题目太难时曾说：

工作以后，大多数人才会发现考试、读书都是相对简单的，因为都是在跟随学习。难的是有些工作，有些设计，你首先得先想出来这是个什么性质的问题，什么范畴的问题，再去找参考。跟着别人做，或者做既定的工作很简单，自己独当一面时，才是真正的动脑筋。

我表示看完这两个匹配算法，头顶有点凉…

BM算法与KMP算法的主要区别在于：采用从右向左进行字符的匹配比较。

BM算法中的关键问题是， 如何确定目标串中的下一轮匹配的开始位置？即如何决定目标串中指针向右跳跃的距离？——利用P中的重复模式 和 T中的失配字符

假设出现失配时， T[i]≠P[k]。则 此时坏字符为x(=T[i])，好后缀P’=P[(k+1) … (len(P)-1)]（好后缀，是已匹配的部分字符串）

如何确定目标串中查找指针的移动距离dist[i]？

采用2种启发式方法：无需检查目标串中的所有字符即可查找到是否存在匹配子串。

• 启发式方法#1： 跳过字符（“坏字符”规则）
  • CharJump[x]：依据T中的坏字符x，计算T中查找指针的跳跃距离
• 启发式方法#2： 重复模式（“好后缀”规则）
  • MatchJump[k] ： 依据P中的失配位置k， 计算T中查找指针的跳跃距离

为了避免朴素匹配算法需要向左回溯导致效率较低的缺点，引进了无需回溯的KMP算法。

KMP算法

利用模式串P自身的重复模式

关注：

• 匹配失败，是否发生在P的第一个字符处？
  • 若当前轮匹配在进行第一个字符比较时就失败，那么
    下一轮应该是比较T[i+1]和P[1]
• P中是否有重复模式？
  • 若P中在当前轮成功匹配的子串的后缀与子串的前缀
    无重复模式，那么下一轮应该是比较T[i]和P[1]
  • 若P中在当前轮成功匹配的子串的后缀与子串的前缀
    有重复模式，那么下一轮应该是比较T[i]和P[next[j]]
  • 模式串的next[j] = ？ next[j]就是第j个元素前j-1个元素首尾重合部分个数加1
    • 规定任何一个串，next[1]=0
    • next[i]= [P串中前 i-1 子串首尾最长匹配数 + 1] —— 首尾重合不包括本身
    • 其他情况，next[i]= 1

泛型的目的是为了实现类型的通用性，那为什么不用 Object 向上转型的方法呢？如果集合里面数据很多，某一个数据转型出现错误，在编译期是无法发现的。但是在运行期会发生java.lang.ClassCastException。泛型一方面让我们只能往集合中添加一种类型的数据，同时可以让我们在编译期就发现这些错误，避免运行时异常的发生，提升代码的健壮性。

Java 泛型（generics）是 JDK 5 中引入的一个新特性, 泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数

对于泛型，只是允许程序员在编译时检测到非法的类型而已。但是在运行期时，其中的泛型标志会变化为 Object 类型。

泛型方法

泛型方法既可以存在于泛型类中，也可以存在于普通的类中。如果使用泛型方法可以解决问题，那么应该尽量使用泛型方法。

定义泛型方法的规则：

• 所有泛型方法声明都有一个类型参数声明部分（由尖括号分隔），该类型参数声明部分在方法返回类型之前

  如 public static < E > void printArray( E[] inputArray ){}

• 每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。一个泛型参数，也被称为一个类型变量，是用于指定一个泛型类型名称的标识符。

• 类型参数能被用来声明返回值类型，并且能作为泛型方法得到的实际参数类型的占位符。

• 泛型方法体的声明和其他方法一样。注意类型参数只能代表引用型类型，不能是原始类型（像int,double,char的等）

  1 2 3

  Pair<int, char> p = new Pair<>(8, 'a'); // compile-time error Pair<Integer, Character> p = new Pair<>(8, 'a'); Pair<Integer, Character> p = new Pair<>(Integer.valueOf(8), new Character('a'));

网络层本质上一个软件包 —— 所以对我们来说，网络并不是完全抽象的

在异构的网络中，通信能力、分组长度限制和时延都是不一样的，所以采用面向连接的方式比较困难—— IP协议，无连接，尽最大努力交付，适合异构网络互连

对于路由器而言，其功能由于采用end - to - end 原则而被简化，只能尽最大努力交付，只关注与它相邻的路由 —— 进步空间：更多跳的路由

交付(delivery)——物理层和链路层

1. 用分组目的IP地址查路由表 Forwarding : 目的IP & 路由表项的掩码 ==？ 路由表项的IP地址
2. 找出匹配项中下一跳IP地址的物理地址：下一跳IP地址–> ARP –> 目的物理地址
   • ARP： 将IP与MAC地址进行绑定，完成从网络层到链路层的切换
3. 将IP分组和目的物理地址一起交给链路层

一次交付过程包含0或多个间接交付+1个直接交付（最后的交付）

分组:（源IP地址，目的IP地址）保持不变

帧:（源物理地址，目的物理地址）逐跳改变

通过上面的两种地址，解决了网关IP和目的IP冲突的问题

Java的异常处理本质上是抛出异常(创建异常对象，交给运行系统处理)和捕获异常。—— 针对可恢复异常

调用栈：main –> method with an exception handler –> method without an exception handler –> method where error occurred

当错误发生时(异常抛出)，会被反向传递至类型匹配的 exception handler 进行处理(捕获异常), 无法捕获将终止程序

使用异常处理的好处：将正常代码与错误处理代码分离开；通过调用栈传递错误对象；对错误类型进行组织和区分

异常分类

三种类型的异常：

• 检查性异常(编译异常)：最具代表的检查性异常是用户错误或问题引起的异常，这是程序员无法预见的。例如要打开一个不存在文件时，一个异常就发生了，这些异常在编译时不能被简单地忽略。—— IOException， 常见编译异常有：IOException（流传输异常），SQLException（数据库操作异常）等
• 运行时异常： 这类异常在代码编写的时候不会被编译器所检测出来，是可以不需要被捕获，但是程序员也可以根据需要进行捕获抛出。Java规定，运行时异常将由Java运行时系统自动抛出，允许应用程序忽略运行时异常。—— RuntimeException，常见的RUNtimeException有：NullpointException（空指针异常），ClassCastException（类型转换异常），IndexOutOfBoundsException（数组越界异常）等。
• 错误： 是指程序无法处理的错误，由 Java 虚拟机生成并抛出，大多数错误与代码编写者所执行的操作无关。例如jvm运行时出现的OutOfMemoryError以及Socket编程时出现的端口占用等程序无法处理的错误。—— Error

在进行核心步骤关系抽取之前，还需要经历一系列基础的NLP处理环节。

模型的预训练最初被用在图像和视频领域的深度学习中，能有效解决训练数据少的问题，同时还能极大加快任务训练的收敛速度。经过预处理后的数据再用于下游的分词、命名实体识别等任务时可以取得更好的效果。

语言模型是一串词序列的概率分布。具体来说，语言模型的作用是为一个长度为m的文本确定一个概率分布P，表示这段文本存在的可能性。在实践中，如果文本的长度较长，P(wi | w1, w2, . . . , wi−1)的估算会非常困难。因此，研究者们提出使用一个简化模型：n元模型（n-gram model）。在n元模型中，传统的方法一般采用频率计数的比例来估算n元条件概率。当n较大时，机会存在数据稀疏问题，导致估算结果不准确。为了缓解n元模型估算概率时遇到的数据稀疏问题，Bengio在2003年提出了神经网络语言模型（NLM），是为Word Embedding的想法的雏形。

Word Embedding

作为NLP里的早期预训练技术，词嵌入（Word Embedding）或者分布式向量（Distributional Vectors）是将自然语言表示的单词转换为计算机能够理解的向量或矩阵形式的技术。有了一个词的向量之后，各种基于向量的计算就可以实施，如用向量之间的相似度来度量词之间的语义相关性。其基于的分布式假设就是出现在相同上下文的词意思应该相近。Word Embedding也有其局限性，比如：难以对词组做分布式表达；无法解决多义词问题，这对情感分析任务的影响非常大。此外，Word Embedding对于应用场景的依赖很强，所以针对特殊的应用场景可能需要重新训练，这样就会很消耗时间和资源。