如果我们直接实现了某个数据库的协议，那么这款数据库的客户端就可以直接连接到我们的数据库上，这样的话，我们岂不是连客户端都可以不用写了。嘿嘿……

抱着这种想法，本人在网上进行了一番调研，最后决定使用 PostgreSQL 数据库的通信协议。

选择 PostgreSQL 主要是因为……

1. 社区活跃，资料丰富（不知道的能 Google）
2. 官网有较为详细的通信协议文档（我看得懂）
3. 版权属于社区，不会因为某些商业决定波及到自己（然后你就白写了）
4. 开源协议自由，允许基于它修改的代码商用（万一哪天我的项目成名了呢？）

还有一件值得一提的事情是，GitHub 上使用 Kotlin/Java 和 PostgreSQL 协议实现的项目不多，就算有，也都是作为客户端，因此我们的 MiniDB 是第一个这么干的（没有抄袭嫌疑！）

PostgreSQL 的通信协议文档在这里可以查阅：https://www.postgresql.org/docs/current/protocol.html

0x01 PostgreSQL 通信协议概览

翻到章节目录，我们可以看到它由以下几个部分组成：

• Message Flow - 定义每一种数据包在什么时候发送，期望得到什么样的回应
• Message Data Types - 定义数据包里会包含的数据类型
• Message Formats - 定义每一种数据包的结构和含义
• 通讯协议的更新日志
• 一些其他的高级的东西，这不是我们目前需要考虑的东西

要让一个普通的 PostgreSQL 客户端能连上我们的服务端，我们只需要了解握手阶段和查询阶段，至于别的细节，我们以后遇到了再考虑。

Start-up Phase：握手

最简单的握手流程如下图所示：

根据文档中的介绍，带有SSL支持的客户端在建立连接后，首先会发送一个 SSLRequest 数据包，询问服务端是否进行 SSL 加密。

服务端要么回复 S，然后双方进入 SSL 加密，或者回复 N，只进行明文通信。

接下来，客户端发送一个 StartupMessage，包含一些基本设置、用户名和数据库名字等信息，代表正式握手。

服务端会从 Authentication 系列的数据包中发送一个给客户端，表示请求客户端以某种方式进行认证。如果认证成功，则发送 AuthenticationOk 的数据包，代表认证成功。 如果认证失败，发送 ErrorResponse。

认证成功以后，客户端会等待服务端发送 ReadyForQuery 数据包，代表服务端准备完毕，可以进入查询阶段。在此期间，服务端可以发送一些 ParameterStatus 数据包给客户端，这些数据包中包含一些服务端的默认设置（如编码、时区等）。

Query Phase：查询阶段

PostgreSQL 有多种不同的查询模式，在这里我们先学习一下最简单的查询过程。

首先，客户端发送一个 Query 数据包，内含我们要查询的 SQL 语句（有可能是多条喔！）

服务端接到查询语句后进行查询，得到结果后返回。

如果得到的结果是一个表格（比如说执行了 SELECT 或者 EXPLAIN，服务端首先会发一个 RowDescription 的数据包介绍每一列的含义，然后每行数据一个 DataRow 数据包，然后以一个 CommandComplete 数据包作为结束，最后是一个 ReadyForQuery 等待下一条查询请求。

Message Formats: 数据包格式

通常来说，通信协议中的数据包一般要有这些信息：

• 数据包标识符 - 用于区分数据包之间的类型
• 数据包长度 - 用于告诉另外一端要准备多大的内存空间去接收数据
• 正文 - 实际要发的内容

PostgreSQL 的数据包格式正是由这些要素组成的。

0x02 Netty 下的简易实现

说了这么多，该开始写代码了。

MiniDB 的网络部分代码结构是这样的：

MiniDB
│
├─com
│  └─lss233
│      └─minidb
│          └─networking
│              │  MessageType.kt
│              │  NettyServer.kt
│              │  NettyServerInitializer.kt
│              │  Session.kt
│              │
│              │  ├─query
│              │  │      QueryHandler.kt
│              │  │
│              │  └─startup
│              │          SSLRequestRejectHandler.kt
│              │          StartupMessageHandler.kt
│              │
│              └─packets
│                      AuthenticationOk.kt
│                      AuthenticationSASL.kt
│                      CommandComplete.kt
│                      EmptyQueryResponse.kt
│                      ErrorResponse.kt
│                      NotificationResponse.kt
│                      ParameterStatus.kt
│                      PostgresSQLPacket.kt
│                      Query.kt
│                      ReadyForQuery.kt
│                      RowDescription.kt
│                      SSLRequest.kt
│                      StartupMessage.kt
│                      Terminate.kt
│
└─Main.kt

NettyServerInitializer

这个类定义了数据包的处理顺序。

    @Throws(Exception::class)
    public override fun initChannel(ch: SocketChannel) {
        val session = Session()
        val pipeline = ch.pipeline()
        pipeline.addLast(PostgreSQLDecoder(session), PostgreSQLEncoder(session))
        pipeline.addLast(SSLRequestRejectHandler(session), StartupMessageHandler(session))
        pipeline.addLast(QueryHandler(session))
        pipeline.addLast(TerminateHandler(session))
    }

在 Netty 中，服务端每收到一个新的连接，就会生成一个新的 SocketChannel，代表这个连接。

这个连接收发的数据包会像工厂中的流水线一样一个环节一个环节地处理下去，这里的流水线就是 pipeline。

PostgreSQL 的数据包都是有结构的，所以在这条流水线的最前端，我们添加了数据解析器 PostgreDecoder 和数据编码器 PostgreEncoder，实现我们的对象和数据包之间的转化。

Session

PostgreSQL 中绝大多数的数据包都是以 1 字节的标识符开头（通常是一个有含义的字符），然后是 4 字节的数据包长度，后面才是数据包的具体信息。 而按照文档中的说法， SSLRequest、 StartupMessage 和 CancelRequest 这几个数据包由于历史原因，它们一开头直接就是数据包的长度，没有数据包标识符。

所以，我们需要一个独立的对象来保存连接的状态，这个对象在连接创建时产生，连接断开时消亡。

class Session {
    var state = State.Startup
    var user: String? = null
    var database: String? = null
    val properties = HashMap<String, String>()
    enum class State {
        Startup, Authenticating, Query, Terminated
    }
}

在这里，我定义了  Startup 握手、 Authenticating 认证、Query 查询和 Terminated 终止四种不同的状态。

客户端与MiniDB建立连接以后，先进入握手状态。此时发送的数据都是开头没有数据包标识符的。

当客户端发送 StartupMessage 之后，进入认证状态。接下来发送的数据包都是开头有标识符的。

认证成功以后进入查询状态，接下来才允许客户端发送查询命令。

当连接断开以后，进入终止状态，释放资源。

后续过程中，可能会加入更多的状态。

PostgreDecoder

在 decode 方法中，我们先判断状态，然后根据状态来选择数据包类型。

            val mType = if(session.state == Session.State.Startup) {
                val position = `in`.readerIndex()
                val length = `in`.readInt()
                val magicNumber = `in`.readInt()
                `in`.readerIndex(position)
                if(length == 8 && magicNumber == 80877103) { // 这是他们规定好的
                    MessageType.SSLRequest
                } else {
                    MessageType.StartupMessage
                }
            } else {
                MessageType.getType(`in`.readByte())
            }

根据数据包类型，构造专门的数据包对象，然后把剩下的数据交给对象处理。

            fun parse(type: MessageType?, payload: ByteBuf): IncomingPacket? {
                return when(type) {
                    MessageType.SSLRequest -> SSLRequest().parse(payload)
                    MessageType.StartupMessage -> StartupMessage().parse(payload)
                    MessageType.Query -> Query().parse(payload)
                    MessageType.Terminate -> Terminate().parse(payload)
                    else -> null
                }
            }

数据包

按照数据的传输方向，MiniDB 把数据分成了两个类型：IncomingPacket 和 OutgoingPacket，分别表示服务端会收到的数据包和服务端会发送的数据包。

interface PostgreSQLPacket {
}
interface OutgoingPacket: PostgreSQLPacket {
    fun write(buf: ByteBuf): OutgoingPacket
}
interface IncomingPacket: PostgreSQLPacket {
    fun parse(buf: ByteBuf): IncomingPacket
}

IncomingPacket#parse 方法将从数据流中读取数据，复制到自身的成员中；

OutgoingPacket#write 将根据自身成员变量的值往数据流中写入数据。

这两个方法的返回值都是对象自身，方便链式调用（完全是个人喜好）。

一个具体的类就像下面这样：

class ParameterStatus(private val key: String, private val value: String): OutgoingPacket {
    override fun write(buf: ByteBuf): OutgoingPacket {
        buf.writeCharSequence(key, StandardCharsets.UTF_8)
        buf.writeByte(0)
        buf.writeCharSequence(value, StandardCharsets.UTF_8)
        buf.writeByte(0)
        return this
    }
}

PostgreSQLEncoder

在编码过程中，我们先将数据存入一个空的数据流中（仅仅是为了知道它到底有多长）。

然后我们按照官方文档中描述的顺序往输出流写数据就行了。

    override fun encode(ctx: ChannelHandlerContext?, msg: OutgoingPacket?, out: ByteBuf?) {
        val mType = msg?.javaClass?.simpleName?.let { MessageType.valueOf(it) }

        val buf = Unpooled.buffer()
        msg?.write(buf)

        val type = mType?.type?.toInt() ?: '?'.code
        // '?' 代表未知标识符
        val len = buf.writerIndex() + 4
        println("<- ${msg?.javaClass?.simpleName}(${type.toChar()}) len $len")

        out?.writeByte(type)
        out?.writeInt(len)
        out?.writeBytes(buf, buf.writerIndex())
    }

Handlers

说完了数据包和编解码器，接下来就剩下包处理器了。

Netty 可以很聪明地把一些包只交给一些特定的处理器来处理。

我们只要根据包的类型来作出正确的反应，就可以让客户端成功地连接上我们。

举几个例子。

在刚开始握手的时候，客户端会问我们要不要 SSL 加密。

这种事情对我们来说为时尚早，所以我们果断回 NO！

class SSLRequestRejectHandler(private val session: Session) : SimpleChannelInboundHandler<SSLRequest>() {
    override fun channelRead0(ctx: ChannelHandlerContext?, msg: SSLRequest?) {
       // 咱们这幼小的 MiniDB 可玩不来 SSL 这种东西
        ctx?.writeAndFlush(Unpooled.copiedBuffer("N", StandardCharsets.UTF_8))?.sync()
    }

}

接下来客户端会给我们发送一个 StartupMessage 的数据包，里面会包含用户名和数据库名。

理论上，我们应该让客户端证明一下自己能访问数据库，我们会切换到认证阶段，给它发一个认证方法，然后等它的回复。

不过，因为这个过程比较复杂，我不想让繁琐的认证流程破坏我诱骗客户端的兴致，所以我决定很敷衍地告诉它：行了行了，你登录成功了。

并进入查询阶段。

class StartupMessageHandler(private val session: Session) : SimpleChannelInboundHandler<StartupMessage>() {
    override fun channelRead0(ctx: ChannelHandlerContext?, msg: StartupMessage?) {
//        session.state = Session.State.Authenticating
//        ctx?.writeAndFlush(AuthenticationSASL(listOf("SCRAM-SHA256")))?.sync()
//        极其敷衍告诉客户端：你登录成功了
        ctx?.writeAndFlush(AuthenticationOk())?.sync()
        ctx?.writeAndFlush(ParameterStatus("client_encoding", "UTF8"))?.sync()
        ctx?.writeAndFlush(ParameterStatus("DataStyle", "ISO, YMD"))?.sync()
        ctx?.writeAndFlush(ParameterStatus("TimeZone", "Asia/Shanghai"))?.sync()
        ctx?.writeAndFlush(ParameterStatus("server_encoding", "UTF8"))?.sync()
        ctx?.writeAndFlush(ParameterStatus("server_version", "14.5"))?.sync()
        session.state = Session.State.Query
        ctx?.writeAndFlush(ReadyForQuery())?.sync()
    }
}

QueryHandler

进入了查询阶段之后，我们的MiniDB就要处理客户端发过来的 SQL 语句了。

SQL 语句的解析部分由我的队友完成。我只要负责将 SQL 语句喂给他写好的 SQL 解析器，然后读取它的解析结果就行了。

按照官方文档的介绍，我们的服务端收到客户端的 SQL 语句之后要做出反应，否则客户端会一直傻傻地等待。

但由于我们的引擎部分啥也没写，所以现在就只能假惺惺回两句啦。

class QueryHandler(private val session: Session) : SimpleChannelInboundHandler<Query>() {
    private val REGEX_STMT_SET = Regex("set (.+) to (.+)");
    override fun channelRead0(ctx: ChannelHandlerContext?, msg: Query?) {
        try {

            var queryString = msg?.queryString

            // 先把查询语句转化为 MySQL 风格
            if(REGEX_STMT_SET.matches(queryString!!)) {
                queryString = queryString.replace(REGEX_STMT_SET, "SET $1=$2")
            }

            // 交给词法解析器
            val ast = SQLParserDelegate.parse(queryString)
            println("  Q(${ast.javaClass.simpleName}: $queryString")

            // 分析解析后的 SQL 语句，作出不同的反应
            when(ast) {
                is DMLSelectStatement -> {
                    // 这是一条查询语句
                    ctx?.writeAndFlush(RowDescription())?.sync()
                    //  查到了 0 条结果也是一种查
                    ctx?.writeAndFlush(CommandComplete("SELECT 0"))?.sync()
                }
                is DALSetStatement -> {
                    // 这是一条设置语句
                    for (pair in ast.assignmentList) {
                        // 更新设置
                        session.properties[(pair.key as SysVarPrimary).varText] =
                            pair.value.evaluation(emptyMap()).toString()

                        // 告知客户端设置成功
                        ctx?.writeAndFlush(CommandComplete("SET"))?.sync()
                        ctx?.writeAndFlush(ParameterStatus(
                            (pair.key as SysVarPrimary).varText,
                            session.properties[(pair.key as SysVarPrimary).varText]!!
                        ))?.sync()
                    }
                }
            }

        } catch (e: SQLSyntaxErrorException) {
            System.err.println(" Q(Error): ${msg?.queryString}")
            e.printStackTrace()
            // 告诉客户端你发的东西有问题
            val err = ErrorResponse()
            err.message = e.message!!
            ctx?.writeAndFlush(err)?.sync()
        }
        // 等待下一条语句
        ctx?.writeAndFlush(ReadyForQuery())?.sync()
    }

}

0x03 测试

使用 Navicat 连接我们的 MiniDB，没有出现任何报错就算成功！

不过在服务端，我们能看见 MiniDB 和 Navicat 聊得很开心！

虽然 Navicat 没有显示出任何数据库，但是根据他俩的聊天记录来看， Navicat 读取数据库列表其实是通过一条 SELECT 语句来实现的。

这提示我们在实现数据库引擎的时候，可以把数据库信息写到一个表里，这样就不需要再做额外的工作了。

0x04 花絮

在实际编写的过程中，我发现实际中的客户端和服务器会发一些文档里没提到的信息（或者说我没翻到），导致我写的服务端不能被正常连接。

遇到这种情况时，我们需要搭建一个真正的服务器，然后使用抓包工具来找到不一样的数据包。

在这里，我使用的是 sokit 的中继模式。上图为 Navicat 连接 PostgreSQL 数据库时双方的数据，下图是 Navicat 连接 MiniDB 时双方的数据。

至此， MiniDB 的网络通信部分先告一段落了。接下来就进入数据库引擎的开发，然后实现真正的数据库了。

简单思考了一下，我认为这个数据库应该分为以下几个部分：

看起来是一个挺复杂的工程，但慢慢实现一定是能成功的。

对于网络通信这一部分，因为自己一直想试试 Netty 这个网络框架，但是又觉得 Java 写着无聊，于是便选择了 Kotlin 作为后端服务器的编程语言，顺便学习一下它的使用方式。

SQL 解析可以使用 ANTRL 来实现， GitHub 上也有大量的资料，应该不是很大的问题。

我希望这款数据库不仅可以作为像 MySQL 这样的分布式数据库服务器，还可以作为像 SQLite 这样的内嵌式数据库，因此还准备了一种数据库驱动和服务端代码一起打包并直接调用的方式，不过这个事情可以后面再说。

数据库引擎应该是整个系统最具有技术含量的部分，由于我没有系统地学习过任何一款数据库引擎实现，所以我对这部分内容是完全没有一点头绪——那也放到后面去吧！

此外，这个系统将由我和另外一位队友一起完成，为了确保我们可以在完成课程要求的前提下实现一些花里胡哨的功能，我们打算先从简单的功能写起，然后再让它逐渐变得复杂。

我认为实现这个数据库的过程也很有意思，所以打算写一系列开发手札，把这个过程记录下来，希望可以帮助到其他人去写类似的项目。

最后，附上我们的项目地址：

GitHub - lss233/MiniDB

Contribute to lss233/MiniDB development by creating an account on GitHub.

GitHublss233

OpenVINO 是一套深度学习工具库，它可以对你的神经网络模型进行优化、使用他们的推理引擎加速运算。

在使用 OpenVINO 之前，我们需要先有一个能用的模型，因此，本文的前半部分将讲述普通的神经网络模型的制作，后半部分再讲述如何把它与 OpenVINO，以及我们的项目结合。

本文将以 ultralytics 实现的 YOLOv5 神经网络算法识别 RoboMaster比赛中机器人的装甲板为例。

0x01 素材整理

转码

我们的素材一般由安装在机器人上的工业相机录制。由于编码问题，会导致录制出来的文件比较大，浪费硬盘存储空间。

你可以使用 ffmpeg -i record_x.avi record_x.mp4 这样的命令将视频转为 H.264 MP4 视频，一般情况下能在画质不会降低很离谱的情况下节省 95% 左右的空间。

存储与备份

这一部分放到前面来说。其实不仅仅对于素材，包括数据集文件、模型结果和源码，都需要特别注意。每个步骤产生的文件都会花费一定的成本，有些文件消失了就没有机会重新找回来了。所以，在你决定使用某个贵重文件前，最好都应该先备份，再使用。

一个比较妥善的方法是本地+远程备份。本地备份是指将文件拷到U盘或者移动硬盘上。但是较小的U盘可能会因为各种原因失踪，移动硬盘有可能会因为碰撞而损坏。所以，你最好再把文件复制一份到诸如百度云这样的网盘上。虽然它下载速度不快，但是如果你误删了文件，至少有个办法可以让它回来。

剪辑

我们的场景是对视频进行数据标注，但我们的视频里与我们要标注的内容有关的帧其实不是很多。过多的无关帧会给我们下一步的标注带来麻烦，所以在开始标注之前，我们需要对视频进行剪辑，只保留我们想要的部分。

对于剪辑这一块，你可以使用专业的 Adobe Premiere Pro， 也可以找一些免费开源的软件。

本人随便找了个叫 OpenShot Video Editor 的软件举个例子。

打开软件后，把你的视频拖到软件底部的时间线上。

播放视频，在你想剪的地方点击添加标记。

当你觉得有效的帧数已经足够的时候，用分割工具把之前标记过的视频段剪开，删除不要的部分，把视频在一起放到开头。

最后一步是导出，这个软件的导出视频功能在 文件 > Export Project > 导出视频。

导出时一般需要设置一些参数，比如说导出的视频编码，以及视频尺寸（配置）。

这里我们使用 MP4(h.264) 和 640x480 大小的分辨率，因为这样的视频既不会丢失我们想要识别目标的特征，又可以让文件体积变小。

0x02 数据标注：CVAT

为了让我们的神经网络能知道什么是我们感兴趣的东西，它叫什么名字，我们需要先手工标注一些数据给它，做成让它学习用的数据集。

数据集一般由标签和图片组成。标签是一段文本，用来告诉神经网络图片中的东西叫什么名字。

数据标注是最让人痛苦的环节，但也是最重要的环节。这个神经网络在我们项目中能不能达到论文写的预期效果，和你的数据集有着非常大的关系。如果你的数据集敷衍了事，那么神经网络产生的结果也是非常敷衍的。

对于 AI 项目来说，成功的最重要的影响因素之一是你可以使用的“优质数据”的数量。
所谓的计算机视觉应用的“优质数据”是指:

• 每个图片/标注都有一个恰当的标签。
• 每个边界框或多边形都紧致地包围着要训练的物体。

数据标注的软件有很多，你在这里就可以看见很多。

本人选择的是 OpenVINO Toolkit 下的 CVAT。选择它的原因是它支持自动化插值、多人同时标注、跨平台，而且它也没有传说中的那么难。开始的时候你会觉得不太习惯，但标注得多了你就能发现它的使用技巧。

CVAT 是一个 Web 程序，所以你只需要有一个浏览器就能用。他们有一个官方的演示型网站，在 cvat.org。如果你单纯想试试，可以直接打开，注册一个账号就能使用。

官方手册地址：https://openvinotoolkit.github.io/cvat/

安装

对于一个团队来说，安装一个 CVAT 实例就可以了。

本节参考：https://openvinotoolkit.github.io/cvat/docs/administration/basics/installation/

CVAT 被封装在了一个 Docker 环境里，所以首先你要安装 Docker，如果你使用 Ubuntu，你的 Ubuntu 版本至少得是 18.04。

sudo apt-get update
sudo apt-get --no-install-recommends install -y \
  apt-transport-https \
  ca-certificates \
  curl \
  gnupg-agent \
  software-properties-common
curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo apt-key add -
sudo add-apt-repository \
  "deb [arch=amd64] https://download.docker.com/linux/ubuntu \
  $(lsb_release -cs) \
  stable"
sudo apt-get update
sudo apt-get --no-install-recommends install -y docker-ce docker-ce-cli containerd.io
# 安装好之后，把你的用户添加到 docker 组中，以便使用 docker 有关的命令
sudo groupadd docker
sudo usermod -aG docker $USER

然后你需要安装 docker-compose，这是一个管理 docker 容器之间互相交互的程序。

sudo apt-get --no-install-recommends install -y python3-pip python3-setuptools
sudo python3 -m pip install setuptools docker-compose

到这里才是安装 CVAT 的步骤。首先，搞到源码。

sudo apt-get --no-install-recommends install -y git
# 如果你的网络访问 GitHub 比较困难，可以用换下面这个命令
# git clone https://hub.fastgit.org/opencv/cvat
git clone https://github.com/opencv/cvat
cd cvat

首次启动时，docker 会下载容器镜像，这可能需要比较长的时间。

docker-compose up -d

上面那个命令执行完之后，说明容器已经启动了，你的 CVAT 也会在几秒之后可以访问。打开 http://localhost:8080，你就可以看见你的 CVAT。先别急着登录，在首次使用之前，你需要执行下面的命令来创建一个管理员用户。

docker exec -it cvat bash -ic 'python3 ~/manage.py createsuperuser'

下面这个命令可以帮你安装好 Chrome 浏览器。

curl https://dl-ssl.google.com/linux/linux_signing_key.pub | sudo apt-key add -
sudo sh -c 'echo "deb [arch=amd64] http://dl.google.com/linux/chrome/deb/ stable main" >> /etc/apt/sources.list.d/google-chrome.list'
sudo apt-get update
sudo apt-get --no-install-recommends install -y google-chrome-stable

如果你希望你的 CVAT 可以被其他电脑访问到，在启动 CVAT 之前，你需要先设置环境变量 CVAT_HOST 为访问的域名或者 IP。下面几个命令也许你会用得到：

# 在你的 CVAT 目录下
docker-compose down # 关掉 CVAT
export CVAT_HOST=192.168.1.3 # 然后大家在地址栏输入 192.168.1.3:8080 来访问
docker-compose up -d # 启动 CVAT

CVAT 还可以设置一个公用位置来读取你的素材。

你需要编辑 docker-compose.yaml，改成这样：

version: '3.3'

services:
  cvat:
    environment:
      CVAT_SHARE_URL: 'Mounted from /mnt/share host directory'
    volumes:
      - cvat_share:/home/django/share:ro

volumes:
  cvat_share:
    driver_opts:
      type: none
      device: /mnt/share # 在这台电脑上的位置
      o: bind

把你的素材放到里面， 你就可以在创建任务的时候直接选择那个文件，而不用手动上传。

准备标注

登录 CVAT 之后，你会发现它有 Projects 和 Tasks 两个标签页。 我们先创建一个 Project。

然后去创建 Task 的时候，我们就可以选择之前那个 Project。

Subset 这个项可以选择 Train 、 Test和 Validation。说明这个task生成的训练集是做什么用的。

打开 Advanced configuration，下面也有一些东西需要你注意。

• Copy data into CVAT 如果你的素材文件待会要删掉了，或者它是网络挂载的（比如说 rclone），那么记得勾这个选项。
• Image quality 没必要太高。 CVAT 会把你的视频剪成一张张图片再进行标注。如果你的图片质量太高，到时候会导出好几 GB 的数据集文件。这会导致…… 不方便转移。
• Segment size 会把你的视频按那个数字分成不同的 jobs。然后大家就可以找还没完成的 jobs 去标注了。

最后它大概是这样的：

之后点击 Submit 就可以啦！

标注

在这一步，你最好主要一下这些事：

1. 快捷键很好用。CVAT 很贴心地把快捷键写在每个按键的提示上了。使用快捷键可以加快标注流程。
2. 对移动的目标使用 Track。 Track 和 Shape 的区别是， Shape 的框在下一帧会消失，而 Track 不会。如果目标在图片里是连续移动的，那么你可以不用每一帧都调整框的位置！！继续往下切几帧，然后再调整位置。接下来往回切，你会发现你没调整的帧也会自动跟着改变。
3. 如果 Track 的目标消失了，点击 Switch Outside Property。
4. 记得随手保存一下。

当前的 job 完成之后，点菜单的 Finish the job 来标记完成这个job。

如果你找了工具人来帮你标注，而你不能保证他的质量，你可以让它选择 Request a review，这样你就可以自己再过一遍，以防万一。数据集里掺屎是一件非常痛苦的事情。

导出

标注页面和 Task 页面都可以 Export as a dataset。如果你要导出整个 Task 的数据集，那就在 Task 页面的 Action 下选 Export as a dataset。

你可以选择导出的格式。对于 YOLOv5 来说，我们选 YOLO 就可以了。

附 - 数据集格式转换：Roboflow

如果你手上有一份其他格式的数据集，让你不方便使用，那要怎么快速转换成你能用的格式呢？

这个时候我们可以使用 Roboflow 这个平台。

把数据集里的标签文件和图片文件放进去，它就可以自动读取。在 Export 的时，你可以选择你想要的格式。

show download code 可以生成让 Jupyter Notebook 直接执行的代码，这对于下一步如果使用 Google Colab 进行训练来说非常方便。

0x03 模型训练

如果说数据标注让人痛苦，那么模型训练就是让机器痛苦。

模型训练是一个耗时很长的事情，你有可能会遇到程序爆炸、显存爆炸等各种白给的情况。它对机器的配置也有要求。一般来说 GPU 训练的速度会比 CPU 训练的速度要快一些，如果你的电脑配置不够，那么你有两个选择：

白嫖 Google Colab

Google Colaboratory 是 Google 提供的一个在线编辑执行环境。它是一个运行着 Jupyter Notebook 的虚拟机。它可以让你在网页里写代码，然后点击就可以运行。运行结果和代码、说明等都会以 .ipynb 格式的文件保存，叫笔记本。别人打开的时候可以直接看见你的运行结果。

最重要的是， Colab 可以提供免费的 GPU 服务器让你实验你的神经网络项目。

首先，你需要有一个 Google 账号，然后打开下面这个链接：https://colab.research.google.com/drive/11LiUAPeFOlMwtp99aD8D9bOeVViuHDWu

这是本人之前测试用的一份笔记本，它是从 YOLOv5 官方提供的那份笔记本简化而来的。你可以把代码中读取训练集的部分换成自己的链接，其他地方应该不用修改太多。

Colab 可以和你的 Google Drive 传输文件。你可以点击左边菜单的 装载 Google 云端硬盘。

根据它的提示来。

临时租用 GPU 服务器

矩池云是一个可以低价租到 GPU 服务器的地方。它提供 SSH 和 HTTP 两种访问方式。

通过 SSH 访问，操作就和日常使用 Linux 系统差不多。

通过 HTTP 访问，它会提供一个 Jupyter Notebook，操作就和上面使用 Colab 差不多。

你可以在这里学习如何使用他们的产品：https://www.matpool.com/supports/doc-img-recognition-case/

在这里选择服务器：https://www.matpool.com/host-market/gpu

你可以使用我的邀请码 Y1LZPj7h6iO0AJB ，可以奖励代金券。、

使用攻略

1. 如果你是学生，可以在这里申请学生认证。认证需要1-2个工作日的时间，通过之后可以得到一些优惠。
2. 首次注册成功后去微信公众号绑定你的账号，可以获得5元代金券。
3. 在选择配置的时候，可以在系统镜像中选择你会用到的库，这样可以节省时间。
4. 如果你选了系统镜像，还可以勾选 Tmux，这样通过 ssh 登录之后将会自动连接到一个 Tmux 会话中，它可以让你的任务在 ssh 断开的情况下继续执行。

下单之后，等待系统启动完成，你可以看到这样的画面：

此时就可以用 ssh 或者 VSCode 连接了。

首次登录时别忘了使用他们的专有工具来更换 apt 和 pip 的镜像源：

无论是使用 Colab 还是租用 GPU 服务器，你都可以执行 nvidia-smi 来查看当前服务器的 GPU 状态。

训练

有关模型训练的步骤我已经写在了 Colab 的那个链接里，

下载 YOLOv5的源码，读取训练集，训练、验证。

使用 Roboflow 导出的训练集压缩包包含一个 data.yaml 文件，它的内容很简单：

train: ../train/images # 用来训练的图片
val: ../valid/images   # 用来验证的图片 validation。如果没有的话，就和 train 一样吧

nc: 1                  # 标签的个数
names: ['red_5']       # 标签名字

如果你使用 CVAT 导出数据集，可能要自己来写这个文件，你也可以在 yolov5/data 下面找到他们提前写好的一些文件。

留意一下 训练之后的输出：

Optimizer stripped from runs/train/exp/weights/last.pt, 42.4MB
Optimizer stripped from runs/train/exp/weights/best.pt, 42.4MB

这是生成的权重文件，人类知识的结晶。best.pt 就是训练最好的一次权重， last.pt 是最后一次训练的权重，接下来，我们要用的就是这个东西。

你还应该注意的是 runs/train/exp/result.png 里的图标。 precision 和 recall 是模型训练结果的重要指标。它越接近 1， 你的模型越准确。

如果你的模型看起来训练得很糟糕，可以考虑换一个预训练模型、增加 epochs 等。

0x04 模型转化

训练得到的模型格式为 . pt 格式，为了实现 OpenVINO 部署，需要首先转换为 . onnx 的文件格式，之后再转化为 OpenVINO 需要的 . xml 和 . bin 的文件格式。

.pt 转 .onnx

这部分可以直接使用 Yolov5 自带的转换脚本，由于 OpenVINO2021.1 还为未支持 opset=12, 需要指定 opset 为 10.

python export.py --weights runs/train/exp/weights/best.pt --img 640 --batch 16 --opset 10  # export at 640x640 with batch size 16

然后你就可以在 runs/train/exp/weights/best.onnx 这里找到生成的文件。

.onnx 转 OpenVINO 格式

首先， 你需要安装 OpenVINO，安装的方式可以参考这里： https://docs.openvinotoolkit.org/2021.4/openvino_docs_install_guides_installing_openvino_images.html

接下来是安装模型转化工具的依赖。

sudo bash /opt/intel/openvino/deployment_tools/model_optimizer/install_prerequisites/install_prerequisites_onnx.sh

之后，你就可以用下面的命令来转换上一步生成好的 .onnx 模型为 OpenVINO 食用的 .xml 和  .bin 格式文件。

python /opt/intel/openvino/deployment_tools/model_optimizer/mo_onnx.py --input_model .onnx文件路径  --output_dir 转换后的输出路径

0x05 模型部署

请参考：http://www.giantpandacv.com/部署优化/AI 部署及其它优化算法/OpenVINO/c%2B%2B实现yolov5的OpenVINO部署/#openvino

当我在自己的 vps 上和其他人成功 peer 后，我就在想应该如何让自己的其他计算机可以在不与其他人 peer 的情况下可以随意地访问 DN42 内的计算机，同时让 dn42 内的其他节点也可以访问到我的计算机。

如果你想和我 peer, 请点下面的链接！

DN42

Hi, I’m AS4242421826, looking for peers on DN42 network now. If you are interested in peering with me, please send the following informationto i@lss233.com: * Your ASN * Your Clearnet IP * Your DN42 IP * Your Link-Local IP * Your WireGuard endpoint * Your WireGuard public key I prefer Mult…

Lss233's.Blog()Lss233

安装 Tinc

Tinc 是一个轻量级的跨平台 full-mesh VPN 软件，它可以让节点之间互相建立隧道，从而让流量直接到达目标计算机。

各发行版软件仓库应该都有这个软件，所以你可以直接安装稳定版：

sudo apt install tinc

如果你想在 Ubuntu 上使用最新的 1.1 预览版，建议从 GitHub 获取源码手动编译：

sudo apt install -y autoconf textinfo
git clone https://github.com/gsliepen/tinc -b 1.1
cd tinc
autoreconf -fsi
./configure \
    --bindir=/usr/bin \
    --sbindir=/usr/sbin \
    --with-systemd \
    --enable-jumbograms \
    --disable-legacy-protocol \
    --datadir=/etc/tinc 
 make
 sudo make install

需要注意的是， Tinc 1.0.35 以前和 1.1-pre17 以前的版本有协议漏洞，而在 tinc-vpn.org 下载的 1.1-pre17 源码不支持 openssl1.1.1a 以上的版本，

否则程序在运行的时候会提示 Error while decrypting: error:060A7094:digital envelope routines:EVP_EncryptUpdate:invalid operation 。 这个问题在 GitHub 上已经被修复，但是官方还没有放出新的 release，具体情况是这样的。

准备

目前我有 172.20.143.48/28 这段IP，我将拆出一段IP 172.20.143.56/29 并分配到以下几个设备上：

master   -  172.20.143.57 -     网关，与其他 DN42 节点通讯
lax2     -  172.20.143.58 -     另外一台 Ubuntu 服务器
lap      -  172.20.143.59 -     电脑
rpi      -  172.20.143.60 -     树莓派
and      -  172.20.143.61 -     手机

master 可以访问其他 dn42 节点，所以可以让其他设备通过 master 访问 dn42 网络，那么就通过 VPN 组建一个虚拟内网，其他设备把 master 作为网关就好了。

配置

对于 Ubuntu系统，在 /etc/tinc 下新建一个目录，取名为 intern。然后在里面建立 hosts 文件夹和 tinc.conf （如果你是手动编译的 tinc，那么你可能要找的是 /usr/local/etc/tinc）

对于 Windows 系统，你可以在 Tinc 的安装目录下建立 intern文件夹。

对于 Android 系统，你可以使用 Tinc App。

在本例中，intern 是你的网络名字，你可以改成别的。

配置服务端 master

编辑 /etc/tinc/intern/tinc.conf, 写入以下内容：

Name = intern_master # 节点的名称
Mode = switch        # switch 模式
Interface = intern0  # 网卡名称

然后是 /etc/tinc/intern/hosts/intern_master,

Address = 服务器公网IP
Subnet = 172.20.143.57/32   # 这里的 172.20.143.57 就是在这个内网中 master 的 IPv4 地址

接下来生成密钥：

# 如果是 Tinc 1.0.x:
tincd -n intern -K
# 如果是 Tinc 1.1+
tinc -n intern generate-ed22519-keys

保持默认设置，一路回车就好了。

编写网卡初始化脚本 /etc/tinc/intern/tinc-up:

#!/bin/bash
ip link set up $INTERFACE
ip addr add 172.20.143.57/29 dev $INTERFACE

网卡关闭脚本 /etc/tinc/intern/tinc-down：

#!/bin/bash
ip addr del 172.20.143.57/29 dev $INTERFACE
ip link set $INTERFACE down

设置执行权限：

sudo chmod +x /etc/tinc/intern/tinc-up
sudo chmod +x /etc/tinc/intern/tinc-down

配置 Linux 客户端 - lax2

服务端和客户端的配置基本上相同，编辑 /etc/tinc/intern/tinc.conf, 写入以下内容：

Name = intern_lax2
Mode = switch
Interface = intern0
ConnectTo = intern_master

然后是 /etc/tinc/intern/hosts/intern_lax2 :

Subnet = 172.20.143.58/32

在网卡初始化的时候，需要额外添加一条路由。

/etc/tinc/intern/tinc-up:

#!/bin/bash
ip link set up $INTERFACE
ip addr add 172.20.143.58/29 dev $INTERFACE
# 与 dn42 有关的 IP 全部走咱 master 网关
ip route add 172.20.0.0/14 via 172.20.143.57 dev $INTERFACE

然后在断开时，把路由也删掉。/etc/tinc/intern/tinc-down:

#!/bin/bash
ip addr del 172.20.143.58/29 dev $INTERFACE
ip route del 172.20.0.0/14 via 172.20.143.57 dev $INTERFACE
ip link set down dev $INTERFACE

生成密钥、设置脚本执行权限与上一步相同。

配置 Windows 客户端 - lap

在这里下载 Windows 版的客户端，安装时三项全选。安装完成后，进入 tinc 安装目录。

接下来的步骤和上面 Linux 客户端基本上一样，无非是创建目录，编写 tinc.conf，创建 hosts 和 intern_lap，以及生成密钥。

但是对于网卡的配置有一些不同。在安装目录的 tap-win64 文件夹下有一个名为 add-tap.bat 的文件，右键以管理员身份运行，即可添加网卡。

接下来在控制面板中找到一个写着 TAP-Win32 Adapter V9 的网卡，将其重命名为 tinc.conf 中 Interface的值，在这里是 intern0。

右键它，点属性设置 IPv4 地址，将 IP 地址和子网掩码修改为 intern_lap 中的 Subnet的值。 DNS服务器也可以设置为 dn42 中的 dns 服务器 IP，这样你就可以直接在浏览器中访问 .dn42 的域名。

对于网关的设置，你可以选择在这个窗口中填入网关地址，但会造成你计算机上非 dn42 的数据包也会被发往服务器。

或者，也可以选择手动设置网关的路由，只需要以管理员身份启动 cmd，然后执行

route -p add 172.20.0.0/14 172.20.143.57

这里的 -p 参数会让这条路由设置在计算机重启后仍然存在（也就是说你不加它，重启后就会消失。）

如果你想删除路由，可以执行

route delete 172.20.0.0/14 172.20.143.57

在 Windows 上，你可以在类似的位置创建 tinc-up.bat 和 tinc-down.bat 来执行启动和关闭时的脚本。

测试 & 运行

在正式启动 tinc 之前，你还需要交换每个节点的配置文件。将服务端 hosts 里的文件复制到各个客户端里， 客户端的 hosts 里的文件也复制到服务端，如果你想让客户端之间也能连接，那么客户端之间也需要有对方 hosts 里的文件。

你可以在每个计算机上执行 tincd -n intern -D -d3 在前台以调试模式启动 tinc，并且观察运行状态。 如果你觉得不错，使用 Ctrl + \ 关闭程序，然后把它添加到服务中：

sudo systemctl enable tinc@intern
sudo systemctl start tinc@intern

对于 Windows 系统，你需要在管理员身份启动的 cmd 下进入 tinc 安装目录， 然后执行 tincd -n intern ，如果成功的话会出现一个开机自动启动的服务 tinc.intern。

如果一切正常的话，你现在就能在任意一台计算机上访问 dn42 的网络了。

先试试我们的虚拟内网：

(奇怪，怎么延迟变低了？)

再看看 dn42 里的服务器：

瞧这扭曲的路由

不出意外的话，在 master 节点上使用 tcpdump -I intern0 也可以看到从那台计算机上路过的 ICMP 请求。

通过其他人的 Looking Glass， 也可以直接访问到我们内网：

写在最后

你可以用这样的方式来让自己的所有设备全部加入 DN42 网络。访问的延迟取决于你和网关服务器的延迟。不过，如果你的网络内有其他延迟更低的 BGP router，也可以直接把它作为网关。

把自己家的电脑送上公共网络是不安全的。如果你要让自己的电脑或者手机加入 DN42 网络，最好还是把防火墙给设置好。或者通过 NAT 的方式上网。

这题也是线段树

单组数据，第一行一个正整数n。（1<=n<=10^5)

第二行n个数 a1,a2...an。（0<= |a[i]| <=10^7)

第三行一个整数m,表示m个操作。 （1<=m<=10^5)

接下来m行，每行第一个数表示操作类型，其余数表示操作对应的参数，对应题面。 （1<=l<=r<=n,0<=|v|<=10^7）

输入

单组数据，第一行一个正整数n。（1<=n<=10^5)

第二行n个数 a1,a2...an。（0<= |a[i]| <=10^7)

第三行一个整数m,表示m个操作。 （1<=m<=10^5)

接下来m行，每行第一个数表示操作类型，其余数表示操作对应的参数，对应题面。 （1<=l<=r<=n,0<=|v|<=10^7）

输出

对于每一个3操作，输出一行三个整数，表示区间和，最大值，最小值。

样例输入

5
1 2 3 4 5
7
1 1 1 -2
3 1 2
1 3 5 1
3 1 5
3 3 3
2 3 3 3
3 3 3

样例输出

1 2 -1
16 6 -1
4 4 4
3 3 3

题解

这题应该算是线段树的模板题了吧。最大值、最小值、求和、区间改值都有了。
所以特此记录一下。

代码

#include <bits/stdc++.h>
#define L(x) (x << 1)
#define R(x) (x << 1 | 1)
typedef long long ll;
const int MAX_N = 2e5 + 10;
struct leaf
{
    ll max, min, sum;
    leaf()
    {
        max = 0, min = 0, sum = 0;
    }
} tree[MAX_N * 4];
ll data[MAX_N], lazy_add[MAX_N * 4], lazy_set[MAX_N * 4];
bool is_lazy_set[MAX_N * 4];
void push_up(int k)
{
    tree[k].sum = tree[L(k)].sum + tree[R(k)].sum;
    tree[k].max = std ::max(tree[L(k)].max, tree[R(k)].max);
    tree[k].min = std ::min(tree[L(k)].min, tree[R(k)].min);
}
void push_down(int k, int a, int b)
{
    int m = (a + b) >> 1;
    if(is_lazy_set[k]) {
        lazy_add[L(k)] = lazy_add[R(k)] = 0;
        lazy_set[L(k)] = lazy_set[R(k)] = lazy_set[k];
        is_lazy_set[L(k)] = is_lazy_set[R(k)] = is_lazy_set[k];
        tree[L(k)].sum = (m - a + 1) * lazy_set[k];
        tree[L(k)].max = lazy_set[k];
        tree[L(k)].min = lazy_set[k];

        tree[R(k)].sum = (b - m) * lazy_set[k];
        tree[R(k)].max = lazy_set[k];
        tree[R(k)].min = lazy_set[k];
        is_lazy_set[k] = false;
    }
    if(lazy_add[k]) {
        lazy_add[L(k)] += lazy_add[k];
        lazy_add[R(k)] += lazy_add[k];
        tree[L(k)].sum += (m - a + 1) * lazy_add[k];
        tree[L(k)].max += lazy_add[k];
        tree[L(k)].min += lazy_add[k];

        tree[R(k)].sum += (b - m) * lazy_add[k];
        tree[R(k)].max += lazy_add[k];
        tree[R(k)].min += lazy_add[k];
        lazy_add[k] = 0;
    }
}
void build(int k, int l, int r)
{
    if (l == r)
    {
        tree[k].max = tree[k].min = tree[k].sum = data[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(L(k), l, mid);
    build(R(k), mid + 1, r);
    push_up(k);
}
void update(int k, int a, int b, int l, int r, int op, ll val)
{
    if (a <= l && r <= b)
    {
        if (op == 1) // add
        {
            tree[k].max += val;
            tree[k].min += val;
            tree[k].sum += val * (r - l + 1);
            lazy_add[k] += val;
        }
        else if (op == 2) // set
        {
            tree[k].max = val;
            tree[k].min = val;
            tree[k].sum = val * (r - l + 1);
            lazy_set[k] = val;
            lazy_add[k] = 0;
            is_lazy_set[k] = true;
        }
        return;
    }
    int mid = (l + r) >> 1;
    push_down(k, l, r);
    if (a <= mid)
    {
        update(L(k), a, b, l, mid, op, val);
    }
    if (mid < b)
    {
        update(R(k), a, b, mid + 1, r, op, val);
    }
    push_up(k);
}
leaf query(int k, int a, int b, int l, int r)
{
    if (a <= l && r <= b)
    {
        return tree[k];
    }
    push_down(k, l, r);
    int mid = (l + r) >> 1;
    leaf ans;
    if (a <= mid && mid < b)
    {
        leaf resA = query(L(k), a, b, l, mid);
        leaf resB = query(R(k), a, b, mid + 1, r);
        ans.max = std ::max(resA.max, resB.max);
        ans.min = std ::min(resA.min, resB.min);
        ans.sum = resA.sum + resB.sum;
        return ans;
    }
    if (a <= mid)
    {
        return query(L(k), a, b, l, mid);
    }
    if (mid < b)
    {
        return query(R(k), a, b, mid + 1, r);
    }
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &data[i]);
    }
    build(1, 1, n);
    int m;
    scanf("%d", &m);
    while (m--)
    {
        int op, l, r;
        scanf("%d%d%d", &op, &l, &r);
        if (op < 3)
        {
            ll val;
            scanf("%lld", &val);
            update(1, l, r, 1, n, op, val);
        }
        else
        {
            leaf res = query(1, l, r, 1, n);
            printf("%lld %lld %lld\n", res.sum, res.max, res.min);
        }
    }
}

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
   In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

题解

题目会输入一组数字。要求任意一组数字不得是另外一组的前缀。
比如说：

91125426
911

或者

812345
8123456

这样的话只需要线段树在插入的时候，判断经过的节点是否被标记为 end，
或者在插入结束后，判断最后一个节点是否为第一次被插入就好了。

另外，本题的内存限制比较小，
所以在一组数据的结束，需要释放内存（就算你不说我也会这么做的，因为一个 delete 清空字典树超方便呀）。

#include <bits/stdc++.h>
const int MAX_CHILDREN = 11;
struct node
{
    bool end;
    node *children[MAX_CHILDREN];
    int count = 0;
    ~node() {
        for (int i = MAX_CHILDREN - 1; i >= 0; i--)
        {
            if(children[i]) {
                delete children[i];
            }
        }
    }
    node()
    {
        end = false;
        for (int i = 0; i < MAX_CHILDREN; i++)
            children[i] = NULL;
    }
};
node *root;
bool yes = true;
/**
 * 插入一个新的字符串
 * @param str 字符串数组
 * @param len 字符串长度
 **/
void insert(char *str, int len)
{
    node *location = root;
    for (int i = 0; i < len; i++)
    {
        if (!yes)
            return; // Thereisnoneed.
        if (str[i] == 0 || str[i] == '\n')
            continue;
        int id = str[i] - '0';
        if (location->children[id] == NULL)
        {
            location->children[id] = new node;
        }
        if (location->end)
        {
            yes = false;
            return;
        }
        location = location->children[id];
        location->count++;
    }
    location->end = true;
    if (yes)
    {
        yes = location->count == 1;
    }
}
char str[20];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        root = new node;
        yes = true;
        int n;
        scanf("%d", &n);
        while (n--)
        {
            scanf("%s", str);
            int len = strlen(str);
            insert(str, len);
        }
        printf("%s\n", yes ? "YES" : "NO");
        delete root;
    }
}

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

输入

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

输出

对于每个提问,给出以该字符串为前缀的单词的数量.

样例输入

banana
band
bee
absolute
acm

ba
b
band
abc

样例输出

2
3
1
0

题解

所以，所谓的字典树就是把一个字符串都存进一棵树，每个节点都放一个字符。所以，对于每个节点至多会有 26个子节点。
然后我们可以在节点上存一点别的玩意，来满足题目想要的效果。
比如说， end 表示这是最后一个字符，那么从根节点到这个节点所经过的字符就正好构成了这个
词。
count 表示这个字符在同样的位置出现了多少次。
etc.

代码

#include<bits/stdc++.h>
#include <stdio.h>
struct node {
    bool end;
    node * children[26];
    int count = 0;
    ~node() {
        for (int i = 25; i >= 0; i--)
        {
            if(this->children[i] != NULL) {
                this->children[i]->~node();
                delete this->children[i];
            }
        }
    }
    node() {
        end = false;
        for(int i = 0; i < 26; i++)
            children[i] = NULL;
    }
};
node * root;
/**
 * 插入一个新的字符串
 * @param str 字符串数组
 * @param len 字符串长度
 **/
void insert(char* str, int len) {
    if(!root) {
        root = new node;
    }
    node *location = root;
    for(int i = 0; i < len; i++) {
        if(str[i] == 0 || str[i] == '\n') continue;
        int id = str[i] - 'a';
        if(location->children[id] == NULL) {
            location->children[id] = new node;
        }
        location = location->children[id];
        location->count++;
    }
    location->end = true;
}
/**
 * 查找指定字符串在树中的长度
 * @param str 字符串数组
 * @param len 字符串长度
 **/
int search(char * str, int len) {
    node * location = root;
    for (int i = 0; i < len; i++)
    {
        int id = str[i] - 'a';
        if(location->children[id] == NULL)
            return 0;
        location = location->children[id];
    }
    return location->count;
}
char str[20];
int main() {
    while (1)
    {
        fgets(str, 15, stdin);
        int len = strlen(str);
        if(len == 1) {
            break;
        }
        insert(str, len);
    }
    while (~scanf("%s", str))
    {
        int len = strlen(str);
        if(len == 0) {
            break;
        }
        printf("%d\n", search(str, len));
    }
    
}

0x0000 起因

在昨天(2月8日) 17时，本人收到了Cloudcone发来的春节优惠邮件。

在一番激烈的思想斗争下，下单了一个看上去更便宜的套餐。打算把服务器迁移过去。

0x0001 噩梦

几分钟后，服务器创建完毕。

发现控制面板居然没有像搬瓦工那样方便的服务器迁移菜单，自己又懒得手动迁移，于是就发了份工单给客服询问有没有什么办法。

17:30

技术人员小哥开始帮我迁移数据。

他的操作非常简单粗暴，直接把旧服务器的硬盘挂载到新服务器上，再把新服务器的硬盘挂载到旧服务器上。

听起来是没什么问题，那位小哥也没继续回复我。

然而他没有料到，两台服务器的IP地址是静态设置的，写死在`/etc/networks/interfaces`里，这位小哥没有给我改过来，这导致两台服务器都不能访问网络。

无奈之下，我只好回复他，请他帮忙修改地址，顺便帮我调整好硬盘大小。

次日0:00

距离我的回复已经过去3个小时，

那位技术人员小哥没有回复。

见鬼了，怎么办？！

我打开面板，看见有一个开启IPv6的选项。 开启IPv6应该会重新配置网络，说不定能把IP问题修好呢？

抱着侥幸的心理，我点了。服务器重新启动。

几分钟后，成功了。服务器可以上网了！

然而，咱又遇到了新的问题。这个服务器的IP地址比较特殊，它在国内访问会显示连接超时，而在其他地方却没有问题。很明显，这个服务器的IP被[数据删除]了。

0:30

我还没有睡。在百度上稍微搜索了一下，得到两种解决方法：

1. 删除服务器，重新购买。
2. 发工单申请更换IP,但需要$2。

由于之前的技术小哥帮我把硬盘挂载在了新服务器上，如果直接删除，那么数据也肯定跟着一起没掉了，所以排除方法1。

我创建了一个Urgent工单，申请更换IP，。

几分钟后

很快，就有一个工程师回复我了。他是这样说的：Your request is sent to our network team, please allow some time while they get it processed for you.

我的内心：诶，不错啊这服务态度。

抱着侥幸的心理，我在这个工单里问能不能帮我把硬盘大小的问题也给处理了。

我刚刚回复完。刷新了一下浏览器，就看见另外一个工程师回复我：Your request is sent to our dev-ops team, please allow some time while they get it processed for you.

我：？？？

完了。这俩人是机器人没跑了。

看自己的账户，$2也没有扣掉。先睡觉吧，说不定明天早上就好了呢。

睡之前回复了一句：Thank you, please be quick. My service have been shutdown for over 8 hours, my users are complaining, please understand.

10:00

我大概是这个时候醒的。登录网站看看情况解决了没有。

最早帮我迁移的小哥还是没有回复我。第二个工单在我回复没多久之后就回复了一句：你可以在我们dev-ops回复之前照常使用你的服务器。

照常个鬼啊，根本用不了啊。这都什么鬼回复模板。

11:00

不等了，估计他们是打算直接把我凉着了。

现在我有两台服务器：

1. 本来就有的一台 chocolate，挂载硬盘30GB，无法访问网络。
2. 前面下单的一台 darksky，挂载硬盘25GB，可以访问网络。

想了一个简单的思路:

1. 重新安装chocolate上的系统，腾出空间。
2. 使用 ssh 和 dd 把 darksky上的硬盘复制到 chocolate 上。
3. 删除 darksky。
4. 重新下单一台服务器。
5. 把在chocolate上的数据迁移到新下单的服务器上。

看上去挺简单的，就像写程序的时候交换两个变量一样。

11:18

下单了新的服务器，系统安装好之后惊呆了，IP地址和之前的居然是一样的。

删除，重新下单。

又是一样的。

看来他们还是按顺序提供分配IP的，也就是说，必须要有一个倒霉鬼下单得到那个IP之后，我下单才会得到新的IP。

这大中午的，谁会买啊。

11:22

我想到了一个绝妙的好主意。

先下单一个价格最低的服务器，它会分配到那个不能用的IP。再下单我想要的服务器，这样就可以啦！

0x0002 第二个噩梦

复制数据很简单是吧？我一开始也是这样想的。

在百度上搜索了一下，原来有种东西叫 SSHFS。 它可以通过SSH协议把远程的服务器挂载到本地上。

于是我的做法是：把硬盘镜像mount到chocolate的 /mnt上，再通过SSHFS把chocolate的 /mnt 挂载到新服务器的 /mnt上。

11:52

重启新服务器，发现使用旧的用户名和密码可以登陆。

太棒了！

诡异的事情来了，登陆成功之后，还没有看见bash，就重新退回到登陆界面了。现在想想，应该是某个支持库没有复制过来，导致bash无法启动。

看来SSHFS这条道不行，重新安装。 对了，新的服务器叫vanilla。

很久以前曾经用tar配合netcat迁移过数据。通过管道，分别在发送端和接收端执行：

# 接收端
netcat -l -p 7000 | tar x
# 发送端
tar cf - * | netcat 接收服务器 7000

试试吧。

14:46

我把MobaXterm自带的小游戏玩了个遍。终于知道为什么一个好好的终端软件带这么多游戏干什么了。

我重试了好几次，每次都是执行到一半，ssh断开连接，Vanilla整个系统无法响应。

看来这个方法也是不行了。应该是因为在覆盖的某个重要lib文件的时候整个系统崩溃。

这个服务商提供的服务器都是KVM，可以访问Recovery模式，看来只能用这种方法了。

Recovery模式和Windows的PE系统差不多，是挂载到内存上的系统。因此我们怎么修改硬盘都和它没有关系。

16:00

Recovery的系统可真是简洁。没有apt，也没有gcc。这意味着我用不了SSHFS这种方法了。

不过ssh和scp倒是能用。我挂载了本地硬盘，使用scp把远程上的服务器复制到本地。

问题#1

SCP复制的时候进度一直是0%,而且最后的文件大小居然超过了25GB!

一看才发现，整个程序卡在复制虚拟设备 /dev/core 上。

问题#2

历尽千辛万苦终于复制完数据，回到面板把Recovery模式关闭。这个按钮点了半天没有反应。他们面板的开发人员怕不是写了个假的按钮吧。

好在本人对Html和JavaScript也略知一二，打开F12看了一下，是一个表单。手动执行一下submit();完事。

16:15

成功进入系统了，但是发现好像少了很多东西，和没有复制几乎没区别。

什么玩意啊。

无奈，还是只能走SSHFS的方法。

0x0003 重新上线

功夫不负有心人，在走了N次弯路之后，服务器终于恢复正常了。

16:25

在复制lib文件夹的时候。第一次把文件复制错了位置。从 /mnt/usr/lib 复制到了 /usr/lib/里。第二次执行到一半，发现在覆盖 libglib的时候，SSHFS废了。

庆幸自己第一次复制错了没有删除，为了安全起见我在VNC下完成了覆盖。

18:09

MySQL不知道因为什么原因无法启动，日志报错Could notcreate unix socket lock file /var/run/mysqld/mysql.sock.lock。

在尝试了各种方法之后，发现把socket的路径指向 /tmp 里面就可以了。

/tmp 和 /var/run 都挂载在tmpfs下。我在复制的时候没有注意，覆盖了 /var/run。

也就是说，重启可以解决问题。

18:11

网站成功上线！

截止至网站上线，两个工单还是没有人回复，之前换IP的申请也没有扣款。

虽然网上很多人表示Cloudcone的工单都是秒回，但这次的事件真的让我担心日后的使用。

就这样吧。

2019-2-9 20:34:19