Matching

本文介绍计算大规模数据流中的元素出现频次的方法 CMS，以及其简单改进Count-Mean-Min-Sketch Intro & Scene 在大数据场景下，比如网页的 TopK 问题，爬虫的是否访问过的问题，都是一种出现频次相关的问题，那么在系统设计的时候，如何选择策略和数据结构去存储相关的数据是最高效合适的呢？ 计算元素的出现频次，如果出现与普通的场景下，简单的方案就是用 hashmap 来记录元素出现的次数： cpp std::unordered_map<std::string, int> freq; for(const auto& e: elements){ if (freq.find(e) == freq.end()){ freq[e] = 1; }else{ freq[e] += 1; } } 但是这种方式在大量数据流的情况下，如果存在大量唯一元素的情况下，会占用大量的内存，导致其无法应对大数据场景，因此在"时间换空间"like 的策略选择中，这里就需要考虑通过时间，或者准确率等其他的因素来换空间。 通常来说，针对大数据场景，会无限扩张的数据结构显然是不适用的，所以希望能用固定的空间来进行计数的管理，同时希望尽量不要影响到运行的时间，换言之，可以牺牲掉一定的准确性，来实现节省空间的效果。 基于上述需求，我们可以想到 Hash 算法：将无限大的空间映射到固定的 size 的输出上；而大数据场景下的 Hash 会遇到冲突会被无限放大的问题，如何解决冲突是最核心的问题 基于概率数据结构实现的 Blomm Filter 算法采取多 Hash 的方法来减少冲突 而其衍生出来的 CMS 算法以同样的思想，基于不同的设计，更为适应这种计数场景 下面介绍该方法的具体实现 CMS 的具体实现 首先第一点，通过 hash 来实现数值空间的转换，通过哈希函数 H 将输入元素 x 映射到一维数组上，通过该 index 的值来判断元素的 Count（是否存在） ...

@AikenHong 2021 @Code: Scipy（repo） @Reference: 匈牙利算法&KM算法 该篇笔记用来介绍匈牙利算法和KM算法(Kuhn-Munkres Algorithm)，这两个算法通常用来做目标之间的匹配问题。 常用于：多目标跟踪，和深度聚类中的标签匹配问题。 Method 这两种方法实际上解决的问题都是： 二分图的最大匹配问题； 首先需要对二分图有个基本的了解： 实际上就是将数据分为两组，各组的每一个点都去另一个组找对应的匹配，我们希望将两组中，相关的数据尽可能的准确的匹配起来。 可以想象成，是同一个数据在不同的映射下的不同表征需要做这样的匹配关系。 解决这种问题的方式就是使用匈牙利算法或者KM算法 匈牙利算法 匈牙利算法是一种在多项式时间内求解任务分配问题的组合优化算法 匈牙利算法可以将二分图中的连线，看成是我们认为可能是相同的目标（不带权值），实际上就是从上到下假想成立，然后进行唯一匹配的搜索，有点像BackTrack的过程。 整体算法的成功率或者准确率实际上十分依赖与连线的准确率，对算法输出预测的准确度要求更高。 KM KM解决的是带权的二分图的最优匹配的问题。 相当于我们给每条线都给出一个置信度预测值，基于这样的权值图去计算对应的匹配关系 Step1: 将左边节点标上与他所关联的最大权值的边的数值 Step2: 寻找匹配，原则如下 只有权重和左边分数相同的边才进行匹配； 如果找不到边，此条路径的所有左边顶点-d，右侧+d，这里我们将d取值为0.1 对于考虑换边的另一个节点，如果无法换边，也需要对应的进行-d 具体的例子可以这么看（最好还是看blog）： ...