本文介绍计算大规模数据流中的元素出现频次的方法 CMS，以及其简单改进Count-Mean-Min-Sketch

Intro & Scene

在大数据场景下，比如网页的 TopK 问题，爬虫的是否访问过的问题，都是一种出现频次相关的问题，那么在系统设计的时候，如何选择策略和数据结构去存储相关的数据是最高效合适的呢？

@Reference: Jack Cui | Github-Markov Junior | Wiki Markov algorithm

第一篇文章简要介绍了一下该编程语言能实现什么效果；第二个是官方repo，其文档和代码都有很强的借鉴意义；第三个是wikipedia对马尔可夫算法的解释，在该编程语言的实现中有重要的意义。

markov algorithm

马尔可夫算法指的是字符串重写算法，其基本逻辑如下:

1. 自顶向下依次检查规则，看是否能在符号串中找到任何在箭头左边的字符串。
2. 如果没有找到，停止执行算法。
3. 如果找到一个或多个，把符号串中的最左匹配的文字替换为在第一个相应规则的箭头右边的字符串。
4. 返回步骤1并继续。（如果应用的规则是终止规则，则停止执行算法。） [1]

@Reference: Github-Mxgmn | zhihu

概念简介和复习

本质上该方法的底层思想就是条件概率的启发式随机生成算法。

波函数坍塌

在介绍算法之前首先需要明确几个概念，第一个就是“波函数坍塌”（名字的来源是量子力学中的概念），参考“薛定谔的猫”，可以理解成：在一系列的不确定像素（存在多种可能）的基础之上，通过确定的规则、相关关系，随机的将所有的像素变成确定的状态。（可以通过给定种子来启动，也可以通过随机规则来启动），实现在一定规则或者模式下的随机生成。

记录各种排序操作，暂时不补充最基础的排序方式和理论，只记录排序算法的拓展应用。

在理论分析的部分主要使用cpp进行撰写，而在具体使用的时候，目前会主要按照python来进行编写，这主要是面向的场景不同决定的。

基础的排序理论，包括快排等等算法的分析在另一篇文章中记录（当初实习准备的时候有整理过，后续重新整理出来）

排序算法和理论

placeholder

排序算法应用

placeholder

同步排序

常用于Machine Learning中，将数据集中的数据和标签进行同步排序，避免打乱其中的对应关系。

使用numpy的 argsort功能来进行排序：

1
2
3

idx = np.argsort(labels)
labels = labels[idx]
datas = datas[idx,...]

@AikenHong 2021
@Code: Scipy（repo）
@Reference: 匈牙利算法&KM算法

该篇笔记用来介绍匈牙利算法和KM算法(Kuhn-Munkres Algorithm)，这两个算法通常用来做目标之间的匹配问题。
常用于：多目标跟踪，和深度聚类中的标签匹配问题。

Method

这两种方法实际上解决的问题都是： 二分图的最大匹配问题；
首先需要对二分图有个基本的了解：

实际上就是将数据分为两组，各组的每一个点都去另一个组找对应的匹配，我们希望将两组中，相关的数据尽可能的准确的匹配起来。

可以想象成，是同一个数据在不同的映射下的不同表征需要做这样的匹配关系。

解决这种问题的方式就是使用匈牙利算法或者KM算法

匈牙利算法

匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法

匈牙利算法可以将二分图中的连线，看成是我们认为可能是相同的目标（不带权值），实际上就是从上到下假想成立，然后进行唯一匹配的搜索，有点像BackTrack的过程。

整体算法的成功率或者准确率实际上十分依赖与连线的准确率，对算法输出预测的准确度要求更高。

Trick：Hard Task

思路来源于Meta-Tranfer-Learning，基本思路是在Meta-Learning的每一次Meta-Test的时候，会从预训练错误率比较高的Task中再次采样，增加那些task的训练次数。也就是难题多做的策略。

基本思路

对比Adaboost

这样的思路其实和AdaBoost的想法是有一定的异曲同工之妙的，或者说其实就是AdaBoost的思路：

Adaboost

参考笔记，从该笔记中我们可以看到，AdaBoost的基本思路如下：

Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器.

和Meta-Transfer-Learning对比一下，我们可以发现，这个方法实际上就是讲Transfer Learning的与训练网络当成弱学习器1，然后通过弱学习器1的训练样本权重，来增大Hard-Task的配比（也就是增加任务的权重）完全一致。

具体实现

实现上主要是，样本sample的过程，就是如何在进行参数选择后和原本的Dataloader，结合起来。在这里我们主要参考MTL中的方法，进行网络的构建处理。

第一部分：sampler构建，为了后续Dataloader中进行数据的采样，需要构建一个这样的sampler，关键在于index的对应关系，以及最后输出的是index的集合。

A* 是一种在平面图形上计算最优路径的方法，通常用来做 2D 游戏的最短寻路，该算法是一种 Dijkstra 算法的变体，使用启发式的策略来提高算法的搜索效率。

wikipedia；medium；pythonf

基本思想

基于启发式的方法，基于BFS去做最短路径搜索，借助类似Manhattan距离作为启发，每次加入后续的多个点，然后按照后续点的属性去排序，不断的加入close的区间，直到第一次遍历到终点就是最短的路径。

f代表的是经过当前点，从起点到最终点的距离，g代表的是从起点到当前节点的距离，h代表的是启发式方法到终点的距离。

维护三个list：open(候选列表)、close（状态确定的列表）、children（等待操作的列表）

首先用 bfs 的方法，找到当前节点的可达后续节点，将这些节点加入 children，确定 child 不在 close_list 中后（即在 open 中）则判断哪个是最优解，然后更新 openlist 和 closelist 。

即：每次遍历的当前节点都从 open 中总距离最小的选，然后放入 close。直到 openlist 为空。