Hexo

项目链接

CLRNC: https://github.com/MonadicLabs/trevi
Streamc: https://github.com/yeliqseu/streamc

码包结构

编码器

1. 编码器创建函数为trevi_create_encoder，返回值为trevi_encoder *，trevi_encoder为一个结构体，包含两个变量；

• 函数作用：在堆上分配 trevi_encoder 结构体大小的内存空间，将 encoderRef 指向新建的 Encoder 对象【Encoder 初始化是将_curGlobalIdx参数置为0】，并将 streamEncoderRefs 数组内的值置为空指针

结构体内变量如下：

1
2
3
4

typedef struct {
    void *encoderRef;   // 用于装载Encoder对象的索引
    void *streamEncoderRefs[32];    // 用于装载流编码器的索引，最多可装载32个不同的流编码器
} trevi_encoder;

2. 编码器添加数据流函数为trevi_encoder_add_stream，传入的主要参数为streamID，encodingWindowSize，num_source_block_per_code_block，num_code_block_per_source_block；

• 参数解析：
  • streamID说明使用的是哪一个流编码器，每个流编码器和ID绑定；
  • num_source_block_per_code_block说明编码完成该数量的信息包后，开始编码保护包；
  • num_code_block_per_source_block说明编码完成该数量的保护包后，开始编码信息包
• 函数作用：
  • 在堆上分配 StreamEncoder 的内存空间，并通过encodingWindowSize，num_source_block_per_code_block和num_code_block_per_source_block三个参数进行初始化；
  • 将该流编码器放入流编码器索引内；
  • 使用 Encoder 的addStream函数将 streamID 和该流编码器绑定

StreamEncoder初始化如下：

1
2
3
4
5
6
7
8

_curSeqIdx = 0;         // 当前信息包的序号
_RepairId = 0;          // 当前保护包的序号
inorder = 0;            // 发送端待更新的按序信息包的序号
feedback_inorder = 0;   // 接收端传回的按序接收到的信息包序号
srand( time(NULL) );
generator.seed(std::chrono::system_clock::now().time_since_epoch().count());
degree_generator.seed(std::chrono::system_clock::now().time_since_epoch().count());
constructField(8);      // 构建伽罗瓦域，传入的参数是2的多少次方

3. 对数据包进行编码，使用trevi_encode函数，传入的主要参数为trevi_encoder *encoder，streamID，buffer和buffersize；

• 函数作用：
  • 将encoder->encoderRef取出，强制转换为trevi::Encoder*类型，并使用Encoder类的addData函数进行编码，传入参数为streamID，buffer和buffersize；
  • addData函数传入buffer和buffersize作为SourceBlock共享指针的初始化参数【初始化过程是分配信息包的头部6字节，尾部2字节和负载的空间，将buffer的内容复制到负载的空间内，并且设置信息包的头部开始2字节为payloadSize=bufferSize】，生成共享指针sb，因为SourceBlock类是继承自DataBlock类，所以DataBlock类也同样进行初始化，将DataBlock类中的_bufferSize置为整个包的大小，_data是一个智能指针，存储指向整个包大小的内存空间地址，再使用addData函数进行编码，传入参数为streamID和sb【Encoder类有两个addData函数】；
  • addData函数通过streamID参数寻找对应的流编码器，将信息包头部的SOURCEBLOCK_GLOBAL_SEQ_IDX_OFFSET位置填入_curGlobalIdx++，然后使用流编码器的addData函数进行编码，传入sb和streamID；

4. 如果进入信息包编码，首先调用sb的updataCRC函数，在信息包尾部放置CRC校验值，在使用pushSourceBlock函数，传入cb【也就是前文提到的se，因为最后都会被封装成保护包，只不过信息包和保护包会在头部有区分】和streamID两个参数；

• 函数作用：
  • 先通过feedback_inorder与inorder进行比较，将接收端已经按序接收到的信息包序号和所占内存空间指针弹出编码窗口_encodingWindow和存放指向信息包内存空间指针_sourceBlockBuffer【二者均为deque队列类型，里面存放的分别是uint32_t和std::shared_ptr< trevi::SourceBlock >】，以避免不必要的资源浪费，并将新的信息包序号和指向信息包内存空间指针放入；
  • 创建保护包的智能指针d1cb，传入整个信息包所占的内存空间大小和其指针，即SourceBlock类继承的DataBlock类的buffer_size()【整个信息包大小】，buffer_ptr()【指向整个信息包所占内存空间地址】和buffer_size()三个参数进行CodeBlock类的初始化【初始化是分配保护包的头部19字节，尾部2字节和负载的空间，将buffer_ptr()所指向的空间复制到负载的空间内，并且设置保护包的头部字节为payloadSize=buffer_size()】；
  • 在保护包头部CODEBLOCK_STREAM_ID_OFFSET=0字节处填入streamID【uint8_t】；
  • 在保护包头部CODEBLOCK_RepairId_OFFSET=1字节处填入-1【uint32_t】；
  • 在保护包头部CODEBLOCK_SourceId_OFFSET=5字节处填入_curSeqIdx【uint32_t】；
  • 在保护包头部CODEBLOCK_STREAM_SEQ_IDX_OFFSET=9字节处填入0【uint32_t】；
  • 在保护包头部CODEBLOCK_STREAM_LAST_SEQ_IDX_OFFSET=13字节处填入0【uint32_t】；
  • 在保护包尾部置入CRC校验值【uint16_t】；
  • 在存放指向保护包内存空间指针的deque队列_codeBlocks中放入d1cb，并将_curSeqIdx自增

5. 如果进入保护包编码，会首先检测编码窗口_encodingWindow内是否还有信息包存在，并且通过检测_curSeqIdx % _numSourceBlockPerCodeBlock是否为0的形式，来达成将_numSourceBlockPerCodeBlock个数量的信息包编码完成后，进行保护包的编码，保护包编码的个数为_numCodeBlockPerSourceBlock个，主要使用createEncodedBlock函数进行保护包编码，该函数返回一个保护包的智能指针polbak，类型为std::shared_ptr< trevi::CodeBlock >；

• 函数作用：
  • 首先在堆内创建编码窗口内信息包个数 × 1字节大小的内存空间，并使用保护包序号_RepairId参与进行伪随机数生成【因为每次保护包生成后，保护包的序号都会自增，所以该序号是唯一的】；
  • 通过比较编码窗口内信息包所占空间的最大值，决定 MTU(Maximum Transmission Unit，最大传输单元) 的大小，设定两个临时缓存数组tmpBuffer_A[maxBlockSize]和tmpBuffer_B[maxBlockSize]，将编码窗口内的每个信息包整体复制进入tmpBuffer_B，并与tmpBuffer_A进行伽罗瓦域的相加，最后将tmpBuffer_A和MTU作为参数，传递进入CodeBlock类进行初始化，并产生智能指针cbcode；
  • 在保护包头部CODEBLOCK_RepairId_OFFSET=1字节处填入_RepairId【uint32_t】；
  • 在保护包头部CODEBLOCK_SourceId_OFFSET=5字节处填入-1【uint32_t】；
  • 在保护包头部CODEBLOCK_STREAM_SEQ_IDX_OFFSET=9字节处填入oldestSeqIdx()【uint32_t】，即为编码窗口的起始信息包序号；
  • 在保护包头部CODEBLOCK_STREAM_LAST_SEQ_IDX_OFFSET=13字节处填入latestSeqIdx()【uint32_t】，即为编码窗口的终止信息包序号；
  • 在保护包尾部置入CRC校验值【uint16_t】；
  • 将_RepairId自增；
  • 若该保护包指针polbak不为空，则在保护包头部CODEBLOCK_STREAM_ID_OFFSET=0字节处填入streamID【uint8_t】，并在存放指向保护包内存空间指针的deque队列_codeBlocks中放入polbak;

6. 使用trevi_encoder_get_encoded_data函数来获取已编码包的数据，用于发送，如果_codeBlocks队列内元素不为空，则弹出最先进入的编码包指针，将该编码包的数据传出并通过 UDP 协议发送给接收端

译码器

1. 译码器创建函数trevi_create_decoder，返回值类型为trevi_decoder *，trevi_encoder为一个结构体，包含两个变量；

• 函数作用：在堆上分配 trevi_decoder 结构体大小的内存空间，将 decoderRef 指向新建的 Decoder 对象【Decoder 初始化是将Decoder类中的_buffer指向一个智能指针，类型为std::make_shared< ReorderingBuffer >，传入参数64作为ReorderingBuffer类的初始化参数，令ReorderingBuffer类的_windowSize参数等于传入的参数】，并将 streamDecoderRefs 数组内的值置为空指针

结构体内变量如下：

1
2
3
4

typedef struct {
    void *decoderRef;      // 用于装载 Decoder 对象的索引
    void *streamDecoderRefs[32];    // 用于装载流译码器的索引，最多可装载32个不同的流译码器
} trevi_decoder;

2. 译码器添加数据流函数trevi_decoder_add_stream，传入参数decoder，streamID和decodingWindowSize，在堆上分配StreamDecoder类大小的内存空间，并传入decodingWindowSize作为StreamDecoder类的初始化参数，将_decodingWindowSize的值置为传入的参数，将_parent的值置为空指针，类型为Decoder *，在streamDecoderRefs[streamID]置入新创建的StreamDecoder的内存空间地址，并且将streamID和该流译码器绑定

StreamDecoder初始化如下：

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

// dc为 StreamDecoder 类的私有变量 struct Ldecoder *dc
dc = (struct Ldecoder*)calloc(1, sizeof(struct Ldecoder));
dc->active = 0;       // 0代表译码器未激活
dc->inorder = -1;     // 表示按序接收到的信息包的序号
dc->win_s = -1;       // 译码窗口的起始序号
dc->win_e = -1;       // 译码窗口的终止序号
dc->dof = 0;          // 译码矩阵的秩
dc->row = (ROW_VEC**)calloc(WIN_ALLOC, sizeof(ROW_VEC*));         // 存储译码矩阵
dc->message = (uint8_t**)calloc(WIN_ALLOC, sizeof(uint8_t*));     // 存储译码矩阵内元素的数据
dc->recovered = (uint8_t**)calloc(DEC_ALLOC, sizeof(uint8_t*));   // 存储已接收到的 / 已恢复的信息包数据
dc->prev_rep = -1;
constructField(8);    // 构建伽罗瓦域GF(2^8)

// 分配单个数据包内存空间以保存数据包解序列后的数据包信息
dc->pbuf = (struct packet*)calloc(1, sizeof(struct packet));
dc->pbuf->coes = NULL;

_buffer = std::make_shared<ReorderingBuffer>( _decodingWindowSize );

struct Ldecoder结构体如下：

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

struct Ldecoder {
    struct packet *pbuf;        // 存放解序列化后数据包信息的变量
    int         active;         // 判断译码器是否激活
    int         inorder;        // 按序接收到的最后一个信息包序号
    int         win_s;          // 译码窗口的起始位置序号
    int         win_e;          // 译码窗口的终止位置序号
    int         dof;            // 译码矩阵的秩
    ROW_VEC** row;
    uint8_t** message;
    uint8_t** recovered;
    int         prev_rep;       // 先前接收到的保护包的ID
    MT19937     prng;
};

struct packet结构体如下：

1
2
3
4
5
6
7
8
9

struct packet {
    int     sourceid;         // 信息包序号
    int     repairid;         // 保护包序号，如果为-1则表示为信息包
    int     pktsize;          // 负载的大小
    uint32_t    win_s;        // 编码窗口的起始序号
    uint32_t    win_e;        // 编码窗口的终止序号
    uint8_t* coes;            // 共有 win_e-win_s+1 个编码参数
    uint8_t* syms;            // 保护包的整体数据
};

2. 通过 UDP 协议接收到数据包，并将数据包和其大小传入trevi_decode函数，传入decoder，buffer和bufferSize三个参数

• 函数作用：
  • 首先强制转化decoder->decoderRef的类型为reinterpret_cast< trevi::Decoder* >，使用Decoder类的addCodeBlock函数，传入buffer和bufferSize两个参数；
  • 该函数将buffer和bufferSize传入CodeBlock类进行初始化，创建了一个该类的智能指针cb【因为CodeBlock类是继承自DataBlock类，其初始化过程先调用了DataBlock的initMemory函数，传入bufferSize，将DataBlock类的_bufferSize=bufferSize，在堆上创建一块大小为bufferSize的内存空间，并将DataBlock类的_data的值置为指向该内存空间地址的智能指针，然后将buffer的数据复制到该内存空间】，而后将cb传入Decoder的addBlock函数【Decoder类有两个addCodeBlock函数】；
  • 该函数首先调用了cb->get_stream_id()函数，查看了该保护包的streamID，通过该ID查找到了与之绑定的流译码器，并调用了StreamDecoder的addCodeBlock函数，传入参数cb

3. 在StreamDecoder的addCodeBlock函数内，首先调用了deserialize_packet函数获取保护包的信息，传入参数cb，返回值为rpkt，类型为struct packet*

• 函数作用：
  • 将StreamDecoder内的私有变量pkt指向dc->pbuf，类型为struct packet *，通过pkt来为dc->pbuf添加保护包的信息；
  • 获取保护包的repairID，通过cb->get_RepairId()函数；
  • 获取保护包的sourceid，通过cb->get_SourceId()函数；
  • 获取保护包的win_s【编码窗口的起始位置序号】，通过cb->get_stream_sequence_idx()函数；
  • 获取保护包的win_e【编码窗口的终止位置序号】，通过cb->get_stream_last_sequence_idx()函数；
  • 获取保护包内负载所占的内存大小pktsize【若为信息包，则该位置就是信息包数据；若为保护包，则该位置就是编码窗口内信息包的伽罗瓦域和数据】，通过cb->payload_size()；
  • 将syms指向一块在堆上分配的大小为pktsize的内存空间地址，并将整个保护包的数据复制到该内存空间；
  • 如果该保护包为信息包，在_Sourcepktsize[pkt->sourceid % PKT_ALLOC]置入pkt->pktsize；
  • 如果该保护包不为信息包，将pkt->coes指向一块在堆上分配的大小为width=win_e-win_s+1的内存空间，并利用保护包序号【保护包序号是唯一的】作为种子输入伪随机数生成器，得到编码窗口内每个信息包的编码系数pkt->coes[i]=co, i = 0...width-1，最后返回pkt

4. 继续讲addCodeBlock函数，接下来检测接收到的包是否为信息包，如果是信息包并且信息包序号 % 设定值 == 0【此处设定值为10，这并不代表每收到10个包更新一次feedback，而是收到的信息包序号如果是10的倍数则更新反馈】则更新一次反馈feedback=dc->inoder，然后进入receive_packet函数，传入参数rpkt

可能会存在先发送一个序号为10的包，在发送一个序号为20的包，但序号为20的包先收到，而后收到序号为10的包，导致反馈并不等于按序递送的最大信息包序号？

5. receive_packet函数是流译码器的重要函数，其包含了对于信息包和保护包的处理，传入参数rpkt，类型为struct packet *，首先判断该包是否为保护包，若为保护包就先更新dc->prev_rep为该保护包的序号，随后检查流译码器是否激活，查看dc->active【未激活(0)代表按序接收，激活(1)代表有丢包】，接下来说明如果流译码器未激活的情况

• 函数作用：
  • 如果流译码器未激活，意味着仍然是按序接收，那么需要首先检查信息包和保护包的序号，如果接收到的是信息包
    • 检查信息包的序号是否为流译码器已经按序接收到的序号+1，即dc->inorder + 1，是的话表示为按序接收到的信息包，如果接收到的信息包序号小于dc->inorder，则直接返回【意味着先发送，晚到达的信息包直接丢弃】
      • 检查dc->recovered[pkt->sourceid % DEC_ALLOC]位置处是否有值，dc->recovered的类型为uint8_t **，如果有值则释放该位置的指针，在堆上分配一块大小为pktsize的内存空间，如果没有值则直接在堆上分配一块大小为pktsize的内存空间，而后将信息包整个包的数据拷贝到dc->recovered[pkt->sourceid % DEC_ALLOC]内；
      • 将信息包整个包的数据和其大小传入SourceBlock类进行初始化，并生成一个智能指针d1sb，类型为std::make_shared< trevi::SourceBlock >；
      • 创建一个trevi::DecodeOutput类型的变量doutput，将doutput结构体内的三个变量都分别赋值，然后将doutput放到StreamDecoder类的deque队列_outputBuffer中，类型为std::deque< trevi::DecodeOutput >；
      • 将dc->inorder自增，表示已经按序接收到了下一个信息包
    • 如果信息包的序号不等于流译码器已经按序接收到的序号+1，则进入active_decode函数，即激活流译码器，传入参数pkt，即前文提到的rpkt，装载有保护包信息的数据包结构体
  • 如果接收到的是保护包，首先检查pkt->win_e是否小于等于dc->inorder，如果为真，直接返回即可【意味着该保护包用于编码的信息包，接收端都已经按序接收到了，也就没有必要使用该保护包去帮助恢复丢失的信息包】，如果为假，则进入active_decode函数，即激活流译码器，传入参数pkt，即前文提到的rpkt，装载有保护包信息的数据包结构体【意味着该保护包用于编码的信息包，接收端并没有全部按序接收到】

DecodeOutput结构体如下：

1
2
3
4
5
6

typedef struct
{
    std::shared_ptr< trevi::SourceBlock > block;    // 用来存放信息包指针
    uint32_t stream_idx;    // 存放streamID
    uint32_t global_idx;    // 存放当前信息包的序号
} DecodeOutput;

6. active_decoder函数是为process_packet函数作前期的准备工作

_Messagepktsize[PKT_ALLOC]数组起始位置是译码窗口的起始位置；
_Sourcepktsize[PKT_ALLOC]数组则是从信息包序号0开始；
dc->row和dc->message起始位置是译码窗口的起始位置

ROW_VEC结构体如下：

1
2
3
4

typedef struct row_vector {
    int       len;      // 存放译码矩阵内某行的编码系数的长度
    uint8_t   *elem;    // 存放译码矩阵内某行的编码系数数据
} ROW_VEC;

• active_decoder函数作用：
  • 首先判断接收到的这个数据包是信息包还是保护包，如果是信息包的话，意味着dc->inorder + 1，dc->inorder + 2，…，sourceID - 1这么多个信息包都丢失了，所以将流译码器的译码窗口起始位置序号win_s和译码窗口终止位置序号win_e分别设置为dc->inorder + 1和sourceID【可以理解为译码窗口原本应该是需要译码恢复出dc->inorder + 1到sourceID - 1这些信息包，译码窗口终止位置序号为sourceID - 1，而后收到了序号为sourceID的信息包，所以译码窗口的终止位置序号更新为sourceID】；
    • 设置index为该信息包序号相较于译码窗口起始位置序号的偏移量，在dc->row[index]位置置入一个ROW_VEC *类型的指针，该指针指向堆上分配的一块大小为ROW_VEC的内存空间；
    • 设置dc->row[index]->len=1【因为是单个信息包】；
    • 在dc->row[index]->elem位置置入一个uint8_t *类型的指针，该指针指向堆上分配的一块大小为dc->row[index]->len的内存空间；
    • 设置dc->row[index]->elem[0] = 1【表示该信息包的编码系数为1】；
    • 在dc->message[index]位置置入一个uint8_t *类型的指针，该指针指向堆上分配的一块大小为pkt->pktsize的内存空间，并且将信息包整个包的数据拷贝到该内存空间；
    • 在_Messagepktsize[index]位置置入pkt->pktsize【这是StreamDecoder类中一个记录数据包大小的数组，大小为PKT_ALLOC】；
    • 在_Sourcepktsize[pkt->sourceid % PKT_ALLOC]位置置入pkt->pktsize【这是StreamDecoder类中一个记录信息包大小的数组，大小为PKT_ALLOC】；
    • 设置dc->dof=1【表示译码矩阵的秩为1，因为当前译码矩阵内只有一个信息包】

保护包

• active_decoder函数作用：
  • 如果是保护包的话，首先将n_repair自增【代表保护包的数量】，将dc->win_s【译码窗口起始位置序号】设为dc->inorder + 1，将dc->win_e【译码窗口终止位置序号】设为pkt->win_e【编码窗口终止位置序号】，将dc->dof=0【译码窗口的秩】；
    • 首先把从pkt->win_s到dc->inorder范围内的信息包，与保护包的负载部分【payload】进行伽罗瓦域加法，因为该范围内的信息包都是接收端已经按序接收到的，该操作完成后该pkt-syms指向的就是dc->inorder + 1到pkt->win_e这个范围内信息包的伽罗瓦域加法结果，并且将参与消除的信息包的编码系数置为0，即将pkt->coes内参与消除的信息包的编码系数置为0；
    • 设定offset = dc->win_s - pkt->win_s，该偏置为译码窗口起始位置序号相较于编码窗口起始位置序号的偏移量，目的是为定位到pkt->coes剩余不为0的编码系数的起始位置【在编码系数数组中定位译码窗口起始位置信息包序号对应的编码系数下标】，设定局部变量指针coes指向剩余不为0的编码系数的起始位置，设定dww为编码窗口大小【decode window width】；
    • 使用循环，寻找编码系数不为0的位置i，在dc->row数组内的该位置i置入类型为ROW_VEC *的指针，设置len = dww - i，elem则置入该位置i到译码窗口终止位置范围内的编码系数数组数据，并将dc->message[i]置入一个指针，指向一块堆上分配的大小为pkt->pktsize的内存空间，将pkt->syms指向的数据【经过消除后的保护包的payload数据】拷贝到该内存空间，然后break退出循环，将dc->active=1，代表激活流译码器，检测dc->dof是否为译码窗口大小，如果是的话，代表译码矩阵满秩，可以恢复出译码窗口内所有的信息包，就调用deactivate_decoder函数；

编码系数不为0的位置是否始终为起始位置？

7. 如果检测到dc->active不为0，意味着流译码器已经激活，则进入到process_packet函数中，传入参数pkt，类型为struct packet *，结束后检测dc->dof是否为译码窗口大小，如果是的话，代表译码矩阵满秩，可以恢复出译码窗口内所有的信息包，就调用deactivate_decoder函数；

offset和index的图解：
情况①

情况②

• process_packet函数作用：
  • 首先接收到的数据包是信息包还是保护包，如果是信息包的话，检测该信息包序号是否比dc->win_s要小【这说明该信息包是先发送，晚到达的类型，可以舍弃】，如果是保护包的话，检测该保护包的pkt->win_e是否比dc->win_s要小【这说明该保护包是对已按序接收到的信息包进行的编码，可以舍弃】，这两种情况直接返回；
  • 如果是信息包，并且该信息包的序号比dc->win_e更大，意味着译码窗口的终止位置序号需要更新，设定index = pkt->sourceid - dc->win_s【index表示该信息包在译码窗口内的位置，是相对于译码窗口而言的】，而后在dc->row[index]位置置入一个类型为ROW_VEC *的指针，指向一块堆上分配的内存空间，将dc->row[index]->len和dc->row[index]->elem[0]填入值【因为是信息包，所以编码系数elem只为1，编码系数数组的长度len也为1】，在dc->message[index]位置放入该信息包的数据，在_Messagepktsize[index]位置放入该信息包的大小，并且将dc->dof【译码矩阵的秩】自增，将dc->win_e更新为pkt-sourceid；
  • 如果是保护包，首先仍然是将pkt->win_s到dc->inorder范围内的信息包，与该保护包的负载部分进行伽罗瓦域加法，并且将参与消除的信息包的编码系数置为0，检测pkt->win_e和dc->win_e大小，看是否需要更新译码窗口终止位置的序号；
  • 设定dww为译码窗口大小，index为新接收到的信息包在译码窗口中的位置 / 新收到的保护包的编码系数矩阵在dc->row中的起始位置，offset为保护包内未参与消除的编码系数的起始位置相较于编码系数矩阵起始位置的偏移量；
  • 如果是信息包的话，coes[0] = 1，如果是保护包的话，width是有效的【也就是未参与消除的】编码系数数组起始位置到译码窗口结束位置的宽度【主要是为了有些保护包的编码窗口终止位置序号等于译码窗口终止位置序号的情况，即pkt->win_e = dc->win_e】，将pkt->coesp[offset]位置往后的，长度为(pkt->win_e - pkt->win_s + 1) - offset【也就是未参与消除的编码系数矩阵宽度】的编码系数拷贝到coes内；
  • 设定quotient为商，是编码参数之间进行高斯消元所需要计算的商，下面这个for循环的目的是为了将获得的信息包/保护包填充进译码矩阵内，并进行高斯消元，使得译码矩阵变成上三角矩阵，通过图解来说明

图解说明：

因为coes指向的第一个位置是序号为3的信息包，编码系数为D，所以检测dc->row[i + index]的位置是否为空，像现在这种情况，dc->row[i + index]指向的是序号为3的信息包，而dc->row[i + index]->len = 3说明参与的信息包序号为3，4，5，目的是为了确认应该将coes插入到dc->row中哪个位置，因为dc->row[i + index]位置不为空，所以要对coes进行高斯消元，把其中序号为3的信息包消去，再查看dc->row中序号为4的信息包的位置是否为空，如果为空，则进行插入

因为该译码矩阵满秩，所以可以进入deactivate_decoder函数

8. deactivate_decoder函数是对已经是上三角矩阵的译码矩阵进行高斯消元，从对角线右下角的元素开始向上进行高斯消元，完成后将该位置的元素变为1，然后将该位置的信息包数据存入dc->recovered内，然后往对角线左上角移动，如此往复，结束之后将该译码窗口内的每个恢复出来的信息包生成SourceBlock类的指针，然后存入到结构体trevi::DecodeOutput变量doutput内，将参数设置好后，压入_outputBuffer内，然后把dc相关参数重置，dc->inorder = dc->win_e

图解：

十字链表——针对有向图

原先对于有向图的链式存储而言，我们有邻接表和逆邻接表两种表示方法，但这两种方式都有缺陷，如果我们想要求得某个结点（Vertex）的度，那么就需要统计该结点的入度和出度，而邻接表只能以较低的时间复杂度去获得出度信息，要以遍历全表的时间来获得入度信息，逆邻接表也遭遇同样的问题。那么通过构建新的结构——十字链表就可以解决这个问题。

其实十字链表是邻接表和逆邻接表的结合，实线箭头是邻接表的部分，而虚线箭头则是逆邻接表的部分。

taillink是继续连接以tailvex结点为弧尾（即起始点）的结点，headlink是继续连接以headvex结点为弧头（即终点）的结点

对于顶点表结构而言，firstin指的是入度，firstout指的是出度

邻接多重表——针对无向图

对于无向图的链式存储而言，可以沿用原先的邻接表结构，但在这种结构中，我们删除某个结点时，需要对两个结点进行删除，比较繁琐。所以，我们可以对十字链表进行改进，修改其定义的边表结点结构。

由于是无向图，ivex和jvex如果相反也是没有问题，接下来只需要理解边表结点之间如何连接即可。

其中，ivex和jvex是某条边依附的两个结点，ilink指的是依附于ivex的结点，jlink指的是依附于jvex的结点

所有ivex相同的结点需要通过ilink连接在一起，所有jvex相同的节点需要通过jlink连接在一起

序言

KMP算法相较于朴素模式匹配算法（也称为Brute-Force算法）在时间复杂度方面有所提升，由原先的O((n-m+1)m)降低为O(n+m)，n和m分别是文本串长度和模式串长度。

在学习KMP算法过程中，对其中get_next函数代码有所疑惑，在查找资料后豁然开朗，在此做下记录，以便以后查看。

具体内容

get_next函数目的是为了求得next数组，该数组说明了当我们遇到模式串中字符与文本串中字符不匹配时，能够在尽量减少重复匹配次数的情况下，在何处继续进行匹配。

比如说，我们在第一次匹配完成后，发现模式串B中字符f与文本串A中字符x不匹配，按照朴素模式匹配算法，我们应当将模式串右移一位，继续进行单个字符的匹配，若仍有字符不匹配，则继续将模式串右移，直至匹配成功或遍历完字符串A仍未匹配成功。

但通过观察可得：

• 在第一次匹配时，前5个字符匹配成功，在字符串aabaa中，第一个字符a与与第三个字符b是不同的，这也就意味着我们在朴素模式匹配时，将模式串B右移2位进行匹配的操作是可以省略的，而第二个字符a与第一个字符a相同，但与第三个字符b是不同的，那么将模式串B右移1位进行匹配的操作也是可以省略的；

• 在字符串aabaa中，前缀aa和后缀aa是相同的，这也就意味着我们在朴素模式匹配时，将模式串右移3位后的，前两次匹配是可以省略的，可以从模式串B的第三个字符开始匹配；

总结：如果第k个字符匹配不成功，可观察前k-1个字符，里面是否具有相同的前后缀，如果存在的话，则可以省去许多右移和匹配的步骤，大大节省时间。因此，如果获得模式串每个位置前（包括该位置）字符串的最大相同前后缀长度就很重要，这可以使我们知道该将模式串右移到哪个位置，以及从第几个字符开始匹配。

next数组就存储了这个信息，而get_next函数就是为了求得next数组的。

1
2
3
4
5
6
7
8
9
10
11

void get_next(String S, int* next) {
    int i;              // 代表后缀末尾字符下标
    int j = 0;          // 代表前缀末尾字符下标 && 代表最大相同前后缀长度
    next[0] = 0;
    for (i = 1; i < S.size(); i++) {
        while (j > 0 && S[j] != S[i])
            j = next[j-1];      // ？
        if (S[j] == S[i]) j++;  // 匹配成功需要将相同前后缀长度加1
        next[i] = j;
    }
}

比较难理解的就是这段代码内注释打问号的部分，为什么j是回溯到next[j-1]的位置呢？
通过下面几张图来进行解释。

其中，红色部分是已经匹配成功的前缀和后缀，a和b是下一个要匹配的字符，我们发现其不相同，那么按照get_next函数，我们应该跳转到j=next[j-1]的位置在进行匹配，而这个位置，其实是**B[模式串前j-1个字符的最长相同前后缀长度]**，字符串B的下标是从0开始的；

因为红色部分是相同的，所以对其再找最长相同前后缀，就相当于对红色部分进行分割，而因为寻找的是相同的前后缀，所以此时分割后的四个红色区域都是相同的；

如果此时j下标的字符和i下标的字符匹配，则可以直接将j加1来作为最长相同前后缀长度，若仍然不相同，则继续当前的操作，直到j变为0。

这样就可以清楚我们为什么需要回溯到j=next[j-1]的位置在匹配了，目的是为了利用先前已经匹配成功的相同前后缀长度，来获得最长相同前后缀长度。

第二章、算法

算法就是解决特定问题的步骤描述，可以理解为我们将某个特定问题的求解步骤，每一步都用具有意义的，在一定时间内能够完成的代码进行描述。

算法的特性

• 输入：无 / 多个
• 输出：至少一个
• 有穷性：会在执行完有限步骤后自动结束，不陷入死循环
• 确定性：每一步具有确定意义，不具有歧义
• 可行性：每一步能够执行有限次数完成

算法设计要求

• 正确性：①没有语法错误；②对于合法输入，能有对应输出；③对于非法输入，也能有对应输出（错误提示）
• 健壮性：能够对非法输入做出处理
• 可读性：便于理解
• 时间效率高和存储量低

算法时间复杂度

程序运行时间，依赖于算法好坏和问题输入规模。我们考察算法的时间复杂度，是看随着问题输入规模的增大，算法运行时间会呈现何种方式的增加。通常使用O（）来记录时间复杂度。

用如下的步骤，我们就可以求得算法的时间复杂度

1
2
3
4

推导O()的步骤
1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中，只保留最高阶项；
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

例如，下面这个算法的时间复杂度为什么是O(1)而不是O(3)，就是因为第一条原则

下面是常见的时间复杂度

序言

从今天开始，开始拜读《大话数据结构》一书，这本书已经听过许多人推荐，听说是图文并茂，生动有趣，比直接看教科书来学习，我倒是更愿意看这种类似漫画性质的书，至少不显得无趣，也更能够坚持下去吧！

个人认为，读一本书应当有所记录，在读完一章后，合上书本，脑海里能够浮现出许多这一章内知识点的印象，这就说明有些理解了，但记录始终比阅读会步调更慢，在记录的过程中，也更能够去细细体会。

第一章、数据结构绪论

数据

此处需要提及四个概念，数据，数据元素，数据项和数据对象

数据本身是符号集合，具有两个特点，①可输入给计算机；②可由计算机进行处理；
数据元素是具有一定意义，构成数据的基本单位；
数据项是不可再分的最小单位，是组成数据元素的单位；
数据对象是具有相同性质（具有相同数量和类型的数据项）的数据元素的集合

数据元素，例如畜类中的数据元素就是猪，狗，羊等等；
数据项，例如人可以有许多的项来说明其特点，如姓名，身高，体重等等；
数据对象，比如人有生日，姓名，身高等相同的数据项，可以视为相同性质

结构

即研究相互之间存在一种或多种特定关系的数据元素的集合，分为逻辑结构和物理结构（存储结构）

• 逻辑结构：集合（元素之间没有联系，是平等的），线性（一对一），树（一对多），图（多对多）
• 存储结构：顺序存储和链式存储

抽象数据类型

可理解为结构体，是【一组性质相同数据元素的集合 + 定义再此集合上的一些操作】

序言

这是记录我第一次搭建个人博客时所遇到的问题。参考资料是攻城狮杰森的保姆级教程，这位大佬在博客内介绍地很详细，既有配置过程截图，也有知识科普，对于新人小白来说还蛮合适的。

我只进行到教程的GitHub Pages配置部分，后面服务器选购及域名部分未进行。

推荐指数：⭐⭐⭐⭐⭐。

遇到的问题

本机情况
① 系统：Windows 11 家庭中文版
② 可科学上网
③ 图床使用 Picgo + Github

问题一、Picgo配置

• Github默认分支名自2020年6月起由master变为main；
• 设定的存储路径若不存在会自动创建；
• 自定义域名格式为：https://cdn.jsdelivr.net/gh/[用户名]/[仓库名]@main

问题二、Git配置SSH公钥

使用如下代码配置，前两行代码是在本地配置设定的用户名和邮箱（可在git bash内，也可在webstorm的终端内进行）

1
2
3

$ git config --global user.name "用户名"
$ git config --global user.email "邮箱"
$ ssh-keygen -t rsa -C "邮箱"

随后回车三次，使用下面的代码获取密钥，复制密钥

1

cat ~/.ssh/id_rsa.pub

进入Github->Settings->SSH and GPG keys->New SSH key

Title可任取，密钥粘贴进Key内，使用如下代码进行连接测试

1

$ ssh -T git@github.com

若出现如下代码则说明连接成功

问题三、localhost:4000显示更新，Github仓库代码已更新，但github.io域名显示网页却未变化

原因：Github的render不是实时的，代码是先上传到Github仓库，然后过一段时间会从Github仓库拉文件，渲染成静态页面，所以需要一段时间更新。

结语

第一次成功把个人博客搭建完成，很有成就感，以后会在这里记录个人的学习历程。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment