前言

基于 LLM （Large Language Model）最火热的应用技术是什么，检索增强生成（RAG，Retrieval Augmented Generation）技术必占据重要的一席。RAG 最初是为了解决 LLM 的各类问题的产生的，但后面大家发现在现阶段的很多企业痛点上，使用RAG好像是更好的解决方案。

LLM的问题

尽管LLM拥有令人印象深刻的能力，但是它们还面临着一些问题和挑战：

• 幻觉问题：大模型的底层原理是基于概率，在没有答案的情况下经常会胡说八道，提供虚假信息。

• 时效性问题：规模越大（参数越多、tokens 越多），大模型训练的成本越高。类似 ChatGPT3.5，起初训练数据是截止到 2021 年的，对于之后的事情就不知道了。而且对于一些高时效性的事情，大模型更加无能为力，比如帮我看看今天晚上有什么电影值得去看？这种任务是需要去淘票票、猫眼等网站先去获取最新电影信息的，大模型本身无法完成这个任务。

• 数据安全：OpenAI 已经遭到过几次隐私数据的投诉，而对于企业来说，如果把自己的经营数据、合同文件等机密文件和数据上传到互联网上的大模型，那想想都可怕。既要保证安全，又要借助 AI 能力，那么最好的方式就是把数据全部放在本地，企业数据的业务计算全部在本地完成。而在线的大模型仅仅完成一个归纳的功能，甚至，LLM 都可以完全本地化部署。

解决这些挑战对于 LLMs 在各个领域的有效利用至关重要。一个有效的解决方案是集成检索增强生成（RAG）技术，该技术通过获取外部数据来响应查询来补充模型，从而确保更准确和最新的输出。主要表现方面如下：

• 有效避免幻觉问题：虽然无法 100% 解决大模型的幻觉问题，但通过 RAG 技术能够有效的降低幻觉，在软件系统中结合大模型提供幂等的API接口就可以发挥大模型的重要作用。

• 经济高效的处理知识&开箱即用：只需要借助信息检索和向量技术，将用户的问题和知识库进行相关性搜索结合，就能高效的提供大模型不知道的知识，同时具有权威性。

• 数据安全：企业的数据可以得到有效的保护，通过私有化部署基于 RAG 系统开发的AI产品，能够在体验AI带来的便利性的同时，又能避免企业隐私数据的泄漏。

什么是RAG

RAG 是检索增强生成（Retrieval Augmented Generation ）的简称，它为大语言模型 (LLMs) 提供了从数据源检索信息的能力，并以此为基础生成回答。简而言之，RAG 结合了信息检索技术和大语言模型的提示功能，即模型根据搜索算法找到的信息作为上下文来查询回答问题。无论是查询还是检索的上下文，都会被整合到发给大语言模型的提示中。

RAG 的架构如图中所示。它既不是一个特定的开源代码库，也不是某个特定的应用，是一个开发框架。

完整的 RAG 应用流程主要包含两个阶段：

数据准备阶段：（A）数据提取–> （B）分块（Chunking）–> （C）向量化（embedding）–> （D）数据入库

检索生成阶段：（1）问题向量化–> （2）根据问题查询匹配数据–> （3）获取索引数据 –> （4）将数据注入Prompt–> （5）LLM生成答案

向量数据库

GPT 的缺陷

GPT-3.5/4 带给我们无限震撼的同时，其天然的缺陷和诸多的限制也让开发者头痛不已，例如其输入端上下文（tokens）大小的限制困扰着很多的开发者和消费者，像 gpt-3.5-turbo 模型它的限制是 4K tokens(～3000字)，这意味着使用者最多只能输入 3000 字给 GPT 来理解和推理答案。

向量数据库的崛起

在 GPT 模型的限制下，开发者们不得不寻找其他的解决方案，而向量数据库就是其中之一。向量数据库的核心思想是将文本转换成向量，然后将向量存储在数据库中，当用户输入问题时，将问题转换成向量，然后在数据库中搜索最相似的向量和上下文，最后将文本返回给用户。

当我们有一份文档需要 GPT 处理时，例如这份文档是客服培训资料或者操作手册，我们可以先将这份文档的所有内容转化成向量（这个过程称之为 Vector Embedding），然后当用户提出相关问题时，我们将用户的搜索内容转换成向量，然后在数据库中搜索最相似的向量，匹配最相似的几个上下文，最后将上下文返回给 GPT。这样不仅可以大大减少 GPT 的计算量，从而提高响应速度，更重要的是降低成本，并绕过 GPT 的 tokens 限制。

RAG的挑战

一个基本的 RAG 通常集成了一个向量数据库和一个 LLM，其中向量数据库存储并检索与用户查询相关的上下文信息，LLM 根据检索到的上下文生成答案。虽然这种方法在大部分情况下效果都很好，但在处理复杂任务时却面临一些挑战，如多跳推理（multi-hop reasoning）或联系不同信息片段全面回答问题。

以这个问题为例：“What name was given to the son of the man who defeated the usurper Allectus?”

一个基本的 RAG 通常会遵循以下步骤来回答这个问题：

1. 识别那个人：确定谁打败了 Allectus。
2. 研究那个人的儿子：查找有关这个人家庭的信息，特别是他的儿子。
3. 找到名字：确定儿子的名字。

通常第一步就会面临挑战，因为基本的 RAG 根据语义相似性检索文本，而不是基于在数据集中没有明确提及具体细节来回答复杂的查询问题。这种局限性让我们很难找到所需的确切信息。解决方案通常是为常见查询手动创建问答对。但这种解决方案通常十分昂贵甚至不切实际。

为了应对这些挑战，微软研究院引入了 GraphRAG，这是一种全新方法，它通过知识图谱增强 RAG 的检索和生成。

GraphRAG的诞生

与使用向量数据库检索语义相似文本的基本 RAG 不同，GraphRAG 通过结合知识图谱（KGs）来增强 RAG。知识图谱是一种数据结构，它根据数据间的关系来存储和联系相关或不相关的数据。

GraphRAG 流程通常包括两个基本过程：索引和查询。

GraphRAG的优势

基础 RAG 和 GraphRAG 都被问到了同样的问题，这需要汇总整个数据集中的信息来构成答案。

问：What are the top 5 themes in the dataset?

下图为答案。基础 RAG 提供的结果与战争主题无关，因为向量搜索检索到了无关的文本，导致了答案的不准确。相比之下，GraphRAG 提供了一个清晰且高度相关的答案，识别了主要的主题和相关细节。结果与数据集一致，并引用了源材料。

上述例子展示了 GraphRAG 如何通过结合知识图谱和向量数据库，更有效地处理需要跨数据集整合信息的复杂查询，从而提高答案的相关性和准确性。

GraphRAG 在多跳推理和复杂信息总结方面性能明显更佳。研究表明GraphRAG 在全面性和多样性方面都超过了基础 RAG：

• 全面性：答案覆盖问题的所有方面。
• 多样性：答案提供的观点和见解具有多样性和丰富性。

参考文献

大模型RAG入门及实践（非常详细）零基础入门到精通，收藏这一篇就够了-CSDN博客

向量数据库｜一文全面了解向量数据库的基本概念、原理、算法、选型-腾讯云开发者社区-腾讯云

GraphRAG 详解: 通过知识图谱提升 RAG 系统 - Zilliz 向量数据库

论文： https://arxiv.org/pdf/2404.16130

GraphRAG：知识图谱+RAG、更高质量的检索_哔哩哔哩_bilibili

微软开源的GraphRAG代码： https://github.com/microsoft/graphrag

视频异常检测初步了解

传统方法检测异常样本：

• 高斯分布 Gaussian Distribute
• 高斯混合模型 Gaussian Mixture Model

深度学习方法下的异常检测：

• 两种主流的异常检测任务：
  • 重构任务 Reconstruction：图像通过深度神经网络DNN输出一张重构图像，通过损失函数，先训练调整DNN，测试结果由AUC评判（AUC（Area Under the Curve）是用于评估分类模型性能的一个重要指标）
  • 预测任务 Prediction：连续输入图像，预测新图像，用预测与非预测比较
• 自动编码器 Auto-Encoder：U-Net 是一种用于图像分割的深度学习模型，主要特点是采用了编码器-解码器结构（也叫对称结构），并在编码器和解码器之间引入了跳跃连接（skip connections）

编码器（Contracting Path）：这一部分类似于卷积神经网络（CNN），用于提取输入图像的特征。

瓶颈层（Bottleneck）：编码器和解码器之间的连接层，负责处理最深层次的特征。

解码器（Expansive Path）：这一部分用于将编码器提取的特征还原回原始图像的大小。

跳跃连接（Skip Connections）：解码器部分会与编码器的对应层进行直接连接，从而帮助模型在恢复空间分辨率的过程中更好地保留细节信息。

根据学习方法分类：

• 无监督学习 unsupervised learning 只有正常样本训练
• 半监督学习 weakly spervised learning 以不平衡的样本比例训练
• 监督学习 spervised learning 都训练

视频异常检测领域未来挑战：

• 异常检测视频大部分采用mini-batch训练方法，非常消耗时间和资源，无法实时进行视频检测
• 现实的数据集，模型难以训练
• 异常的情况定义模糊
• 模型的迁移性差，shanghaiTech的数据集是多摄像头融合的数据集，大部分数据集表现一般

了解yolo

YOLO（You Only Look Once）系列算法是计算机视觉领域中重要的目标检测技术。凭借其高效的实时处理能力，YOLO被广泛应用于视频监控、自动驾驶等多个领域。

论文一：Human Action Recognition from Various Data Modalities: A Review

概述

人类动作识别（Human Action Recognition, HAR）旨在理解人类的行为，并为每个行为分配一个标签。

多种不同的数据形态都可以用来表示人类的动作和行为。这些模态可以分为2类：视觉模态和非视觉模态

视觉模态和非视觉模态的主要区别在于：视觉模态的数据对人类行为的表示相对直观，但是非视觉模态的数据则不是。视觉模态主要包括：如RGB，骨架，深度，红外，点云，事件流（event stream）等数据模态，而非视觉模态则主要包括音频，加速度，雷达，wifi信号等数据模态

然而，由于不同的模态对 HAR 具有不同的优势和局限性，因此多种数据模态的融合和跨模态的知识传递以提高 HAR 的准确性和稳健性，近年来也受到了极大的关注 [23]，[24]。更具体地说，融合是指将两种或多种模态的信息组合起来，以识别动作

该综述对基于不同数据模态的深度学习HAR方法的最新进展做了一个综合调研。介绍调研的主要内容分为三部分

• 当前主流的单模态深度学习方法
• 当前主流的多模态深度学习方法，包括基于融合（fusion）和协同学习（co-learning）的学习框架
• 当前HAR任务的主流数据集

单一模态 SINGLE MODALITY

RGB模态 RGB MODALITY

RGB 模态通常是指由 RGB 相机捕获的图像或视频（图像序列），旨在重现人眼所见。

RGB模态优点主要有：（1）RGB数据容易收集，通常是最常用的数据模态。（2）RGB模态包含所捕获的场景上下文的信息。（3）基于RGB的HAR方法也可以用来做pretrained model。

缺点主要有：（1）由于RGB数据中存在背景、视点、尺度和光照条件的变化，所以在RGB模态中进行识别通常具有挑战性。（2）RGB 视频通常具有较大的数据量，导致在为 HAR 的时空环境建模时会产生高计算成本。

下面介绍面向基于 RGB 的 HAR 的高级深度学习，主要可分为四大类，即双流 2D 卷积神经网络 （CNN）、递归神经网络 （RNN）、3D CNN 和基于 Transformer 的方法

骨骼模态 SKELETON MODALITY

骨骼序列编码人体关节的轨迹，这些轨迹表征了信息丰富的人体运动。因此，骨架数据也是 HAR 的合适模式。

骨架数据提供的是身体结构与姿态信息，其具有两个明显的优点：（1）具有比例不变性。（2）对服装纹理和背景是鲁棒的。

但同时也有两个缺点：（1）骨架信息的表示比较稀疏，存在噪声。（2）骨架数据缺少人-物交互时可能存在的形状信息。

深度模态 DEPTH MODALITY

深度图其中像素值表示从给定视点到场景中的点的距离信息。深度模态通常对颜色和纹理的变化具有鲁棒性，提供了可靠的人体三维结构和几何形状信息，因此可用于 HAR。随着技术的发展，现在已经有多种设备可以捕获场景中的深度图。现有的对深度数据学习的方法大多数还是利用CNN提取深度图中的feature。深度数据可以提供几何形状信息，但是对外观数据的提供是缺失的，所以深度数据通常不单独使用，而是与其他模态的数据融合使用。

红外模态 INFRARED MODALITY

通常，红外传感器不需要依赖外部环境光，因此特别适用于夜间 HARat。红外传感技术可分为有源和无源两种。一些红外传感器（如 Kinect）依赖于主动红外技术，该技术发射红外线并利用目标反射光线来感知场景中的物体。在目前基于深度学习的方法中，比较多的做法是把红外图像作为其中一个stream输入双流或多流网络中。红外数据以其不需要依赖外部环境的可见光的特点，特别适合于夜间的HAR，但是，红外图像也有着对比度低和信噪比低的固有缺点。

点云模态 POINT CLOUDMODALITY

点云数据由许多点集合组成，这些点表示空间参考系统下目标的空间分布和表面特征。获取 3D 点云数据有两种主要方法，即 （1） 使用 3D 传感器，例如 LiDAR 和 Kinect，或 （2） 使用基于图像的 3D 重建。点云作为一种 3D 数据模态，具有强大的能力来表示主体的空间轮廓和 3D 几何形状，因此可以用于 HAR。但是点云中通常存在噪声和高度不均匀的点分布。

事件流模态 EVENT STREAM MODALITY

事件照相机（event camera）可以捕捉照明条件的变化并为每个像素独立产生异步事件。传统的摄像机通常会捕捉整个图像阵列，而事件摄像机仅响应视觉场景的变化。事件照相机能够有效地滤除背景信息，而只保留前景运动信息，这样可以避免视觉信息中的大量冗余，但是其捕捉到的信息通常在时间和空间维度上是稀疏的，而且是异步的。因此一些现有的方法主要聚焦于设计事件聚合策略，将事件摄像机的异步输出转换为同步的视觉帧。

音频模态 AUDIO MODALITY

音频信号通常与视频信号一起提供，由于音频和视频是同步的，所以音频数据可以用定位动作。因为音频信号中的信息量是不足的，所以单独使用音频数据执行HAR任务相对比较少见。更常见的情况是音频信号作为HAR的补充信息，与其他模态（如rgb图像）一起使用。

后续

还有加速度模态，雷达模态，wifi模态，我先不了解，后续若有需要再完善知识

多模态 MULTI-MODALITY

在现实生活中，人类经常以多模态认知方式感知环境。同样，多模态机器学习是一种建模方法，旨在处理和关联来自多种模态的感觉信息[358]。通过聚合各种数据模态的优势和功能，多模态机器学习通常可以提供更强大、更准确的 HAR。

多模态学习方法主要有两种，融合（fusion）和协同学习（co-learning）。其中融合指的是对来自两个或更多模态的信息进行集成，并将其用于训练或推理，而协同学习指的则是对不同模态之间的知识进行迁移。图4展示了多模态学习方法的分类

HAR任务中的多模态融合

模态融合的目的是利用不同数据模态的互补优势，以达到更好的识别性能。现有的多模态融合方案主要有两种：（1）评分融合（score fusion），即对不同模态输出的score做融合，例如使用加权平均或学习一个分数融合模型。（2）特征融合，即对来自不同模态的特征进行组合。数据融合（在特征提取之前就融合不同模态的输入数据）可以看成是特征融合，因为某一模态的数据数据可以被视为该模态的原始特征。

依据输入模态的不同，现有的多模态融合方法大概可以分为视觉模态之间的融合，与视觉+非视觉模态之间的融合两种

视觉模态之间的融合

1. RGB+深度模态：RGB和深度模态分别能够捕捉外观信息和3D形状信息，因此它们具有比较强的互补性。
2. RGB+骨架模态：骨架模态可以提供身体位置和关节运动信息，同样和RGB模态是互补的。[28]提出了一个双流深度网络，两个stream分别是CNN和RNN，用以分别处理RGB和骨架数据，融合方式同时尝试了特征融合和分数融合，并发现应用特征融合策略可以取得更好的效果。
3. 深度图+骨架模态：[31]将身体的每个部分与其他部分之间的相对几何关系作为骨架特征，将不同身体部分周围的深度图像块作为外观特征，以编码身体-对象和身体部分-身体部分之间的关系，进而实现可靠的HAR。
4. RGB+深度图+骨架模态：这类方法大多是前文提到了三类多模态融合方法的扩展。

视觉模态+非视觉模态的融合

1. 视频与音频的融合：前文中已经提到，音频可以为视频的外观和运动信息提供补充信息。所以目前已经有一些基于深度学习的方法来融合这种模态的数据
2. 视频与加速度模态的融合
3. 其他类型的模态融合：[43]的核心思想是将非RGB模态的数据，包括骨架、加速度和wifi数据都转换成彩色图像，然后送入CNN中。

HAR任务中的多模态协同学习

多模态协同学习旨在探索如何利用辅助模态学习到的知识帮助另一个模态的学习，希望通过跨模态的知识传递和迁移可以克服单一模态的缺点，提高性能。多模态协同学习与多模态融合的一个关键区别在于，在多模态协同学习中，辅助模态的数据仅仅在训练阶段需要，测试阶段并不需要。所以多模态协同学习尤其适用于模态缺失的场景。此外对于模态样本数较小的场景，多模态协同学习也可以起到一定的帮助作用。

视觉模态的协同学习

1. RGB和深度模态的协同学习
2. RGB和骨架模态的协同学习。如[48]利用CNN+LSTM执行基于RGB视频的分类，并利用在骨架数据上训练的LSTM模型充当调节器，强制两个模型的输出特征相似。

视觉和非视觉模态的协同学习

第一种类型是在不同模态之间进行知识的迁移，如[50]中的teacher network使用非视觉模态训练，而student network使用RGB模态作为输入，通过强制teacher和student的attention map相似以弥补模态间的形态差距，并实现知识的提炼。

第二种类型是利用不同模态之间的相关性进行自监督学习，比如[51]分别利用音频/视频模态中的无监督聚类结果作为视频/音频模态的监督信号。[52]使用视频和音频的时间同步信息作为自监督信号。

论文二：RWF-2000: An Open Large Scale Video Database for Violence Detection

mchengny/RWF2000-Video-Database-for-Violence-Detection：一个用于暴力检测的大型视频数据库，其中包含 2,000 个包含暴力或非暴力行为的视频剪辑。

摘要

近年来，监控摄像头在公共场所广泛部署，由于这些无处不在的设备，总体犯罪率已显著降低。通常，这些摄像头会在犯罪发生后提供线索和证据，而很少用于及时预防或制止犯罪活动。手动监控来自监控摄像头的大量视频数据既费时又费力。因此，从视频信号中自动识别暴力行为变得至关重要。

本文总结了几个现有的用于暴力检测的视频数据集，并提出了 RWF-2000 数据库，其中包含监控摄像头在真实场景中捕获的 2,000 个视频。此外，我们还提出了一种同时利用 3D-CNN 和光流优点的新方法，即流门控网络。所提出的方法在我们提出的数据库的测试集上获得了 87.25% 的准确率。数据库和源代码目前对 Access 1 开放。

概述

通常，基于视频的暴力检测的定义是检测视频数据中的暴力行为。它是人类动作识别的一个子集，旨在识别常见的人类动作。与静止图像相比，视频数据具有额外的时间序列。一组连续的帧表示连续的运动，而相邻的帧由于帧间相关性高而包含冗余信息。

一些早期的方法依赖于检测高度相关物体（例如，枪击、火焰、血腥、爆炸）的存在，而不是直接识别暴力事件

此前数据的劣势：尽管存在一些用于暴力检测的视频数据集，但它们仍然存在规模小、多样性少和图像分辨率低的缺点。此外，一些具有高图像质量的相关数据集来自电影，这些电影与真实场景不够接近。为解决真实暴力活动中高质量数据不足的问题

本文工作：

1. 为了解决真实暴力活动中高质量数据不足的问题，我们收集了一个新的视频数据集 （RWF-2000） 并将其免费发布给研究界。该数据集规模较大，包含从监控视频中提取的 2,000 个剪辑
2. 我们提出了一种新的具有自学习池机制的模型，该模型可以很好地兼顾外观特征和时间特征。

先前数据集

根据注释方法，仍然存在两种用于暴力检测的视频数据集：修剪和未修剪。裁剪后的数据集中的视频都是几秒长的短片，每个视频都有一个视频级标注。而视频未修剪的数据集通常具有更长的持续时间。此外，暴力活动的开始时间和结束时间都有帧级注释。

总结这些提议的数据集，每个数据集都至少具有以下一个或多个限制：

• 图像质量低;缺乏足够的数据量
• 视频时长但注释粗糙
• 与现实暴力不够接近的视频混合来源

为了解决上述问题，我们从 YouTube 网站收集了一个新的 RWF 2000（真实世界格斗）数据集，其中包括 2,000 个由监控枪式摄像机从真实场景中拍摄的修剪视频剪辑。

先前方法

传统方法通常会尝试找到一个 powfer 特征提取算法，并实现一个基于机器学习的分类器来完成暴力检测任务。

总之，基于深度学习的方法通常优于传统的基于特征提取的模型。此外，大多数最先进的结果都使用多通道输入（例如，原始 RGB 图像、光流、加速度图）。同时，复杂模型对过拟合不是很鲁棒。

在本文中，我们只采用 RGB 图像和光流来构建神经网络，它可以处理空间和时间信息。此外，我们提出的 Flow-Gated 架构可以通过自学习来减少输入视频的时间通道，而不是传统的池化策略。

RWF-2000 数据库和建议的方法

数据采集

为了使暴力检测在现实应用中更加实用，我们从 YouTube 平台收集了一个新的真实世界格斗 （RWF） 数据集，其中包含监控摄像头在真实场景中拍摄的 2,000 个视频剪辑。

拟议的数据集有 2,000 个视频剪辑，分为两部分：训练集 （80%） 和测试集 （20%）。一半的视频包含暴力行为，而其他视频属于非暴力活动。

Flow Gated Network

以前的大多数方法都探索从单个帧中提取外观特征，然后将它们融合以对时间信息进行建模。由于粗略的池化机制，运动信息可能毫无用处，我们的目标是设计一种通过网络自学习实现的时间池化机制

由四个部分组成：RGB 通道、光流通道、合并块和全连接层。RGB 通道和光流通道由级联的 3D CNN 组成，它们具有一致的结构，因此它们的输出可以融合。Merging Block 也由基本的 3D CNN 组成，这些 CNN 在自学时间池化后处理信息。最后，全连接层生成输出。

该模型的亮点是利用光流通道的一个分支来帮助构建池化机制。

后续学习

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的暴力行为检测系统（深度学习模型+UI界面+Python代码+训练数据集）-CSDN博客

YOLO8实战：暴力行为检测系统_yolov8 打架检测-CSDN博客

参考文献

科研分享|视频异常检测_哔哩哔哩_bilibili

[领域综述] TPAMI 2022 | Human Action Recognition from Various Data Modalities: A Review - 知乎

RWF-2000 暴力行为检测视频数据集 - 知乎

另一个暴力行为数据集XD-暴力

实验1 门电路逻辑功能测试

内容一：与非门和异或门逻辑功能的测试

74LS20双4输入与非门逻辑功能测试

74LS20功能：四输入双与非门，其内部结构及真值表如图

电路图如下

全1出0，有0出1

74LS86四2输入异或门逻辑功能测试

74LS86功能：二输入端四异或门，其内部结构及真值表如图

电路图如下

内容二：根据电路图写出逻辑关系表达式

用74LS00按图接线，将输入输出逻辑关系分别填入表中。

74LS00功能：二输入端四与非门，其内部结构及真值表如图

题目如下

电路图如下

电路图如下

写出两个电路逻辑表达式

电路逻辑表达式为 ĀB + B̄A

电路逻辑表达式为 Y = ĀB + B̄A  Z = AB

内容三：利用与非门控制输出

用一片74LS00按图接线，S接任一电平开关，用示波器观察S对输出脉冲的控制作用

第一题

电路图如下

第二题

电路图如下

内容四：用与非门组成其它门电路并测试验证

第一题：组成或非门

用一片2输入端四与非门组成或非门

电路图如下

第二题：组成异或门

同内容二

内容五：逻辑门传输延迟时间的测量

用六反相器（非门）按图接线，输入200KHz连续脉冲，用双踪示波器测量输入、输出相位差，计算每个门的平均传输延迟时间的值。

74LS04功能：六反相器，其内部结构及真值表如图

电路图如下

内容六：用基本门电路组装一个译码电路：将BCD8421码转换成格雷码

BCD8421码：二进制编码的十进制数，简称BCD码

一位不产生进位的加法电路用异或门就可以实现，下图左边为一个二进制-格雷码转换器器，右边为一个格雷码-二进制码转换器。

参考文献

数字电路逻辑与设计实验一 门电路逻辑功能及测试_数电实验-CSDN博客

为何需要专一

以下源自网络

精神层次越高的人对感情越专一，因为善于处理自己内心欲望，因而不会把类似找备胎、和谁玩、玩过谁，这种肤浅的价值观当作得意的谈资。他们更愿意跟某个人担起生活的风雨，因为时间都用来做正经的事情，所以左顾右盼不代表你赢了，花哨是因为你层次太低。欲望是人性，克制是教养，新欢旧爱迎来送往，你以为的魅力难挡实则廉价百搭，得陇望蜀、骑驴找马、悲凉的让人生厌且鄙弃。道德不能杀掉带给我痛苦的人，所以我只能杀死理智和感性的自己。忠诚和专一是最基本的原则和底线，但它也只是三观正且有教养的人对感情中的自我约束

数据结构——中缀表达式

利用中缀表达式直接求值

要实现中缀表达式直接求值，必须设置两个栈，一个栈用于存放操作数，记作 OPND； 另一个栈用于存放操作符，记作 OPTR。

中缀表达式求值算法步骤如下：

1. 初始化：操作符栈中放置一个元素 @。
2. 依次读取中缀表达式中的每一个字符，对于不同类型的字符按以下情况处理：
   1. 若读到的是操作数，则压入操作数栈，并读取下一个字符。
   2. 若读到的是操作符 c，则将操作符栈的栈顶元素 pre_op与之进行比较，会出现以下 3 种情况：
      • 若 pre_op < c，则将 c 入栈，并读取下一个字符。
      • 若 pre_op = c，则将 pre_op 出栈，并读取下一个字符。
      • 若 pre_op > c，则将 pre_op 出栈，并在操作数栈中退栈 2 次，依次得到操作数 b 和 a，然后进行 a pre_op b 运算，将运算结果压入操作数栈。
3. 扫描完毕时，操作数栈中只有一个元素，即计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

//中缀表达式，实数
double Expression_Eval2()
{
	SeqStack<char, 100> OPTR;
	SeqStack<double, 100> OPND;
	OPTR.Push('@');
	char ch = getchar();
	while (ch != '@' || OPTR.Top() != '@')
	{
		if (isdigit(ch) || ch == '.')
		{
			// 处理多位数和小数
			string number;
			while (isdigit(ch) || ch == '.')
			{
				number += ch;
				ch = getchar();
			}
			OPND.Push(stod(number));
		}
		else
		{
			char pre_op = OPTR.Top();
			switch (Precede(pre_op, ch))
			{
			case '<':
				OPTR.Push(ch);
				ch = getchar();
				break;
			case '=':
				OPTR.Pop();
				ch = getchar();
				break;
			case '>':
				char pre_op = OPTR.Pop();
				double b = OPND.Pop();
				double a = OPND.Pop();
				OPND.Push(Operate(a, pre_op, b));
				break;
			
			}
		}
	}
	return OPND.Top();
}

Precede(pre_op, ch)为进行算符优先级比较的函数

Operate(a, pre_op, b)为计算函数

利用后缀表达式求值

优点

后缀是指把操作符放在两个操作数的后面。采用后缀表示的算术表达式被称为后缀表达式或后缀算。 在后缀表达式中，完全按照操作符出现的先后顺序进行计算过程，不存在括号，也不存在优先级的差别。

将中缀表达式转换成等价的后缀表达式求值时，不需要再考虑操作符的优先级，只需从左到右扫描一边后缀表达式即可。只需设置一个OPND栈用于存放操作数

先将中缀表达式转成后缀表达式

把中缀表达式转换为后缀表达式算法的基本思路如下：

1. 初始化：操作符栈中放置一个元素 @。

2. 依次读入中缀表达式中的每个字符

   ，对于不同类型的字符按不同情况进行处理：

   1. 若读到的是操作数，则输出该操作数，并读取下一个字符。
   2. 若读到的是左括号 (，则把它压入 OPTR 栈中，并读取下一个字符。
   3. 若读到的是右括号 )，则表明括号内的中缀表达式已经扫描完毕，将 OPTR 栈从栈顶直到左括号之前的操作符依次出栈并输出，然后将左括号出栈，并读取下一个字符。
   4. 若读到的是操作符 c，则将操作符栈的栈顶元素 pre_op与之进行比较：
      • 若 pre_op < c，则将 c 入栈，并读取下一个字符。
      • 若 pre_op >= c，则将 pre_op 出栈并输出。
   5. 若读到的是结束符 @，则把栈中剩余的操作符依次出栈并输出，即可得到转换成的后缀表达式。

后缀表达式求值

后缀表达式求值算法的基本思路如下

1. 依次读入后缀表达式中的每个字符

   ，直至表达式结束。

   • 若读到的是操作数，则入 OPND 栈。
   • 若读到的是操作符，则在 OPND 栈中退栈两个元素（先退出的是操作符右侧，后退出的是操作符左侧），然后用该操作符进行运算，并将运算结果压入 OPND 栈中。

2. 后缀表达式扫描完毕时，若 OPND 栈中仅有一个元素，即为运算结果。

数据结构——线性表

线性表的定义

线性表（List）：零个或多个数据元素的有限序列。

顺序存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#ifndef SEQLIST_H
#define SEQLIST_H

#include <iostream>
using namespace std;

// 模板类定义，表示顺序表
template <class T, int MaxSize>
class SeqList {
    T data[MaxSize];  // 存储顺序表数据的数组
    int length;       // 顺序表的长度
public:
    
};

#endif

链式存储结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#ifndef LINKLIST_H
#define LINKLIST_H

#include <iostream>
using namespace std;

template <class T>
struct Node {
    T data;
    Node<T>* next;
};

template <class T>
class LinkList {
    Node<T>* head;

public:

};
#endif // LINKLIST_H

归并排序

[归并排序 | 菜鸟教程](https://www.runoob.com/data-structures/merge-sort.html#:~:text=归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法 (Divide,and Conquer）的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。 若将两个有序表合并成一个有序表，称为二路归并。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

// 友元函数：合并两个有序顺序表
template <class T, int MaxSize1, int MaxSize2>
SeqList<T, MaxSize1 + MaxSize2> Merge(const SeqList<T, MaxSize1>& list1, const SeqList<T, MaxSize2>& list2) {
    SeqList<T, MaxSize1 + MaxSize2> MergedList;  // 创建一个新的顺序表
    int i = 0, j = 0, n = 0;                    // 定义三个指针，分别表示 list1、list2 和合并表的当前索引

    // 获取两个顺序表的长度
    int length1 = list1.length;
    int length2 = list2.length;

    // 合并两个有序顺序表
    while (i < length1 && j < length2) {
        if (list1.data[i] <= list2.data[j]) {
            MergedList.data[n++] = list1.data[i++];
        }
        else {
            MergedList.data[n++] = list2.data[j++];
        }
    }

    // 将 list1 中剩余的元素插入到 MergedList 中
    while (i < length1) {
        MergedList.data[n++] = list1.data[i++];
    }

    // 将 list2 中剩余的元素插入到 MergedList 中
    while (j < length2) {
        MergedList.data[n++] = list2.data[j++];
    }

    MergedList.length = n;  // 设置合并后的顺序表长度
    return MergedList;
}

数字逻辑电路——CMOS逻辑门电路

MOS管

MOSFET全称金属-氧化物-半导体场效应三极管

从载流子极性来看，分为NMOS（电子型）管和PMOS（空穴型）管两种

按照导电机制的不同，MOS管又可以分为增强型和耗尽型

因此MOSFET共有四种：E型NMOS管、D型NMOS管、E型PMOS管、D型PMOS管

NMOS和PMOS区别

MOS管的管脚有三个：源极S（source）、栅极G（Gate）和漏极（Drain）

MOS管有两种：一个是PMOS管，一个是NMOS管；PMOS管就是positive管，是积极的管，而NMOS管是negative管，是消极的管。积极的管就是顺应潮流，顺势而为；消极的管就是违背趋势，逆流而上。 很显然，电流从源极（输入端）到漏极（输出端），那就是顺势而为，因为源极就是源头嘛，因此这种管就是PMOS管；而电流要是从漏极（输入端）到源极（输出端），那就是逆流而上，是NMOS管。

判定是N沟道MOS还是P沟道MOS： 箭头指向G极的是N沟道 箭头背向G极的是P沟道

从导通特性上区分：

NMOS：当电压高于阈值电压可以导通；当电压低于阈值电压不能导通

PMOS：当电压高于阈值电压不能导通；当电压低于阈值电压可以导通

增强型和耗尽型的区别

以NMOS管为例：

当 V_GS = 0时没有导电沟道，需要依靠 V_GS的作用才能产生导电沟道，称为增强型FET。

当 V_GS = 0时有导电沟道，需要依靠 V_GS的作用是削弱导电沟道，称为耗尽型FET。

CMOS逻辑门电路

由N沟道和P沟道增强型MOS管组成的电路称为互补MOS或CMOS电路。

非门

或门和或非门

与门和与非门

异或门和同或门

参考文献

【硬核科普】带你认识CPU第00期——什么是MOSFET_哔哩哔哩_bilibili

【硬核科普】带你认识CPU第01期——什么是逻辑门_哔哩哔哩_bilibili

NMOS管与PMOS管的区别与总结_pmos和nmos的区别-CSDN博客

数据结构——类模板

类模板

类模板是一种用于创建通用类的机制，它可以让程序员编写一次类，然后让它适用于多种数据类型，在实际编程中非常实用。

优点：使用类模板时，可以为同一个类使用不同的数据类型，这使得代码更加灵活。例如，一个通用的栈类模板可以用于int、double、char等不同类型，而不需要为每种类型分别定义栈类。

定义方式

1
2
3
4
5
6
7
8
9

template <class T>
class MyStack {
public:
    // 构造函数、析构函数、入栈、出栈等函数
private:
    T* data;
    int top;
};

template 关键字用于声明类模板

函数声明与定义

类内定义

如果是在类内进行函数定义，则不需添加template<>，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 类模板
template <class T1,class T2>
class Data {
private:
	T1 a;
	T2 b;
public:
	Data(T1 a, T2 b){
		this->a = a;
		this->b = b;
		cout << "Data的有参构造" << endl;
	}
	void showData()
	{
		cout << a << " " << b <<endl;
	}
};

类外定义

如果成员函数在类外定义

• 在每个成员函数前必须添加template<>。
• 作用域需要添加<>修饰。

1
2
3
4
5

template<class T1,class T2>
void Data<T1,T2>::showData()
{
	cout << a << " " << b << endl;
}

友元函数

1
2
3
4
5
6
7
8
9

//类内声明
friend void MyPrint(Data<T3, T4> &ob);

//类外定义
template <typename T3,typename T4>
void MyPrint(Data<T3, T4> &ob)
{
	cout << "函数模板友元：" << ob.a << " " << ob.b << endl;
}

模板类分文件书写问题

方案一

将类的声明和成员函数的定义全部写在一个.h文件中，如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#ifndef _DATA_H_
#define _DATA_H_
#include <iostream>
using namespace std;

// 类模板
template <class T1, class T2>
class Data {
private:
	T1 a;
	T2 b;
public:
	void showData();
};

template<class T1, class T2>
void Data<T1, T2>::showData()
{
	cout << a << " " << b << endl;
}

#endif // !_DATA_H_

方案二

若将函数的定义写在.cpp文件中，main.cpp中调用时，一定要同时include”.h”和“.cpp”文件，否则编译错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//main.cpp
#include <iostream>
using namespace std;

#include "Data.h"
#include "Data.cpp"
int main()
{
	// 类模板实例化对象
	
	Data<int, char> ob2(100,'A');
	ob2.showData();
	return 0;
}

参考文献

【035】深入理解C++类模板（最全讲解）：从基础到实战-CSDN博客

数据结构——广义表

广义表的定义和相关概念

广义表是线性表的推广，其中的元素可以是原子（即不可再分的基本数据项），也可以是子表。广义表的一些常用术语包括： - 长度：广义表的长度是其顶层元素的个数。 - 深度：广义表中元素嵌套的最大深度。 - 表头：广义表中的第一个元素。 - 表尾：去掉表头后剩下的部分。

例子

• A = ()
• B = (a, b, c)c)`
• C = (a, (b, c, d), e)
• D = (a, b, (e, f, g))
• E = ((a, b), c, (d, e, (f, g)))
• F = ((), ((), ()))

下表展示了图片中的几个广义表的长度、深度、表头和表尾的具体值：

广义表的存储结构

由于广义表中的每个元素可能是原子或子表，因此在广义表的存储结构中存在两类结点：

1. 原子节点：用于存储单个元素。
2. 子表节点：用于存储子表的指针。

为了区分元素是原子还是子表，结构中还设置了一个标识域 type

1

enum GListNodeType { ATOM, LIST }; // 结点类型：原子或子表

当type值为1，说明存入原子的值；为2，说明存入子广义表的头指针

广义表定义如下：

1
2
3
4
5
6
7
8
9

typedef char ElemType; // 原子的类型定义为字符类型
typedef struct GListNode {
    GListNodeType type; // 类型域，表示该节点是原子还是子表
    union {
        ElemType data; // 如果是原子节点，则存储数据
        struct GListNode *sublist; // 如果是子表节点，则存储指向子表的指针
    };
    struct GListNode *next; // 指向下一个表节点的指针
} GListNode, *GList; // GList 表示广义表的指针类型

代码

求广义表长度

1
2
3
4
5
6
7
8
9
10

// 求广义表的长度
int LengthGList(GList list) {
    int length = 0;
    GList current = list;
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

求广义表深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 求广义表的深度
int DepthGList(GList list) {
    if (list == NULL) {
        return 1;  // 空表深度为 1
    }
    int maxDepth = 1;
    GList current = list;
    while (current != NULL) {
        if (current->type == LIST) {
            int sublistDepth = DepthGList(current->value.sublist) + 1;
            if (sublistDepth > maxDepth) {
                maxDepth = sublistDepth;
            }
        }
        current = current->next;
    }
    return maxDepth;
}

打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 打印广义表
void PrintGList(GList list) {
    if (list == NULL) {
        printf("()");
        return;
    }
    printf("(");
    GList current = list;
    while (current != NULL) {
        if (current->type == ATOM) {
            printf("%c", current->value.data);
        } else if (current->type == LIST) {
            PrintGList(current->value.sublist);
        }
        if (current->next != NULL) {
            printf(", ");
        }
        current = current->next;
    }
    printf(")");
}

线性表章节小结

数据结构——矩阵压缩

特殊矩阵的压缩

对称矩阵

关键点：

• 是选择上三角行主序存储还是下三角列主序存储
• 组的下标是从1开始还是0开始存储

三件矩阵

注意点：

• 理解下三角列序和下三角行序的差异，后者是计算a[i][j]后面的元素数量和，再用总数减去后面，得到前面元素数量；前者是直接计算a[i][j]前面元素数量

• 一位数组空间为n(n+1)/2+1，数组最后一位为0

对角矩阵

稀疏矩阵的压缩存储

三元组表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 用于表示稀疏矩阵中非零元素的结构体
struct Triplet {
    int row;
    int col;
    int value;
};

// 用于表示稀疏矩阵的类
class SparseMatrix {
private:
    int rows;
    int cols;
    vector<Triplet> triplets; 

public:
    // 构造函数，用于初始化矩阵的维度
    SparseMatrix(int rows, int cols) : rows(rows), cols(cols) {}

    // 添加非零元素到矩阵的方法
    void add_element(int row, int col, int value) {
        if (value != 0) {
            triplets.push_back({ row, col, value });
        }
    }

    // 以三元组形式显示稀疏矩阵的方法
    void display() const {
        for (const auto& triplet : triplets) {
            cout << "行: " << triplet.row << ", 列: " << triplet.col << ", 值: " << triplet.value << endl;
        }
    }

    // 将稀疏矩阵转换为密集矩阵表示的方法
    vector<vector<int>> to_dense() const {
        vector<vector<int>> dense_matrix(rows, vector<int>(cols, 0));
        for (const auto& triplet : triplets) {
            dense_matrix[triplet.row][triplet.col] = triplet.value;
        }
        return dense_matrix;
    }
};

朴素转置

因为矩阵A的列是矩阵B的行，所以以此遍历A的列，将其存入新的三元组顺序表

不能直接交换i和j的值的原因：因为三元组表是行优先顺序，如果直接交换就是列优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

vector<Triplet> transposeTripletMatrix(const vector<Triplet>& tripletMatrix) {
    // 获取原始三元组矩阵的行数、列数和非零元素个数信息
    int rows = tripletMatrix[0].row;
    int cols = tripletMatrix[0].col;
    int numNonZero = tripletMatrix[0].value;

    // 创建转置矩阵的三元组顺序表
    vector<Triplet> transposedMatrix;
    transposedMatrix.push_back({cols, rows, numNonZero});

    // 通过列的顺序插入非零元素到转置矩阵中
    if (numNonZero > 0) {
        for (int col = 0; col < cols; ++col) {
            for (int i = 1; i <= numNonZero; ++i) {
                if (tripletMatrix[i].col == col) {
                    transposedMatrix.push_back({tripletMatrix[i].col, tripletMatrix[i].row, tripletMatrix[i].value});
                }
            }
        }
    }

    return transposedMatrix;
}

快速转置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

vector<Triplet> fastTransposeTripletMatrix(const vector<Triplet>& tripletMatrix) {
    // 获取原始三元组矩阵的行数、列数和非零元素个数信息
    int rows = tripletMatrix[0].row;
    int cols = tripletMatrix[0].col;
    int numNonZero = tripletMatrix[0].value;

    // 创建转置矩阵的三元组顺序表
    vector<Triplet> transposedMatrix(numNonZero + 1);
    transposedMatrix[0] = {cols, rows, numNonZero};

    if (numNonZero > 0) {
        // 初始化每一列中非零元素的个数和位置
        vector<int> count(cols, 0);
        vector<int> index(cols + 1, 2);

        // 统计每一列中非零元素的个数
        for (int i = 1; i <= numNonZero; ++i) {
            count[tripletMatrix[i].col]++;
        }

        // 计算每一列在转置矩阵中的起始位置
        for (int i = 1; i < cols; ++i) {
            index[i + 1] = index[i] + count[i - 1];
        }

        // 填充转置矩阵的三元组顺序表
        for (int i = 1; i <= numNonZero; ++i) {
            int col = tripletMatrix[i].col;
            int pos = index[col];
            transposedMatrix[pos] = {tripletMatrix[i].col, tripletMatrix[i].row, tripletMatrix[i].value};
            index[col]++;
        }
    }

    return transposedMatrix;
}

十字链表

定义

类中定义了两个链表数组，用于存储每一行和每一列的头节点指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 节点定义
struct OLNode {
    int row;         // 行号
    int col;         // 列号
    int value;       // 元素值
    OLNode* right;   // 指向右边的节点
    OLNode* down;    // 指向下面的节点

    OLNode(int r, int c, int val) : row(r), col(c), value(val), right(nullptr), down(nullptr) {}
};

// 十字链表类
class OrthogonalList {
private:
    int rows, cols;
    vector<OLNode*> row_heads; // 行头链表数组
    vector<OLNode*> col_heads; // 列头链表数组
}

构造函数

row_heads.resize(rows, nullptr); 是用于调整 row_heads 向量的大小，使其包含 rows 个元素，并将每个元素初始化为 nullptr。

1
2
3
4

OrthogonalList(int rows, int cols) : rows(rows), cols(cols) {
        row_heads.resize(rows, nullptr);
        col_heads.resize(cols, nullptr);
    }

插入函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// 插入元素
void insert(int r, int c, int value) {
    if (value == 0) return;

    // 检查是否已存在节点，若存在则更新值
    OLNode* current = row_heads[r];
    while (current && current->col < c) {
        current = current->right;
    }
    if (current && current->col == c) {
        current->value = value; // 更新已有节点的值
        return;
    }

    OLNode* newNode = new OLNode(r, c, value);

    // 插入到行链表中
    if (!row_heads[r]) {
        //如果该行没有头节点，则成为该行头节点
        row_heads[r] = newNode;
    }
    else {
        current = row_heads[r];
        OLNode* prev = nullptr;
        //current向下遍历，直到遍历到该行链表的最后一个，或者到达插入的列的位置
        //注意，该插入方式如果遇到该位置已有节点存在的情况，会用新节点覆盖旧节点
        while (current && current->col < c) {
            prev = current;
            current = current->right;
        }
        //若prev存在，则说明头节点不为零，若为空则说明插在链表最前面
        if (prev) {
            prev->right = newNode;
        }
        else {
            row_heads[r] = newNode;
        }
        newNode->right = current;
    }

    // 插入到列链表中
    if (!col_heads[c]) {
        col_heads[c] = newNode;
    }
    else {
        current = col_heads[c];
        OLNode* prev = nullptr;
        while (current && current->row < r) {
            prev = current;
            current = current->down;
        }
        if (prev) {
            prev->down = newNode;
        }
        else {
            col_heads[c] = newNode;
        }
        newNode->down = current;
    }
}

打印函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

   // 打印矩阵
    void print() {
        for (int i = 0; i < rows; ++i) {
            OLNode* current = row_heads[i];
            for (int j = 0; j < cols; ++j) {
                if (current && current->col == j) {
                    cout << current->value << " ";
                    current = current->right;
                } else {
                    cout << "0 ";
                }
            }
            cout << endl;
        }
    }
};

参考文献

【数据结构】特殊矩阵的压缩存储/对称矩阵/三角矩阵/对角矩阵（含经典题讲解）_哔哩哔哩_bilibili

【每个人都听得懂的】稀疏矩阵的快速转置算法_哔哩哔哩_bilibili