3
推荐
1749
阅读
【数据压缩】LZ77算法原理及实现
1. 引言【数据压缩】LZ77算法原理及实现【数据压缩】LZ78算法原理及实现LZ77算法是采用字典做数据压缩的算法，由以色列的两位大神Jacob Ziv与Abraham Lempel在1977年发表的论文《A Universal Algorithm for Sequential Data Compression》中提出。基于统计的数据压缩编码，比如Huffman编码，需要得到先验知识——信源的字...
0
推荐
1491
阅读
【数据压缩】Huffman编码
1. 压缩编码概述数据压缩在日常生活极为常见，平常所用到jpg、mp3均采用数据压缩(采用Huffman编码)以减少占用空间。编码CC是指从字符空间AA到码字表XX的映射。数据压缩编码指编码后信息的长度较于原始信息要短。本文试图探讨Huffman编码是如何保证唯一可译性、如何压缩、以及压缩效率如何？前缀码前缀码的任意一码字均不...
0
推荐
1221
阅读
Top K问题的两种解决思路
Top K问题在数据分析中非常普遍的一个问题（在面试中也经常被问到），比如：从20亿个数字的文本中，找出最大的前100个。解决Top K问题有两种思路，最直观：小顶堆（大顶堆 -> 最小100个数）；较高效：Quick Select算法。LeetCode上有一个问题215. Kth Largest Element in an Array，类似于Top K问题。1. 堆小顶堆（mi...
2
推荐
1274
阅读
最长回文子串
1. 问题描述回文串（palindromic string）是指这个字符串无论从左读还是从右读，所读的顺序是一样的；简而言之，回文串是左右对称的。所谓最长回文子串问题，是指对于一个给定的母串abcdedcb从所有的为回文串的子串a, ded, cdedc, bcdecdb中；找出最长的那一个bcdecdb。但是该如何判断子串是否回文然后找出最长者呢？正...
2
推荐
1532
阅读
连续子数组最大和
1. 问题描述输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x应该返回 x[2..6]的和187.2. 问题解决我们很自然地能想到穷举的办法，穷举所有的子数组的之和，找出最大值。穷举法i, j的for循环表示x[i..j]，k的for循环用来计算x[i..j]之和。maxsofar = 0
for i = [0, n)
for j = [i, n)
sum = ...
3
推荐
1945
阅读
【动态规划】最长公共子序列与最长公共子串
1. 问题描述子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串cnblogsbelong比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致，我们将其称为公共子序列。最长公共子序列（Longest Common Subsequence, LCS），顾名思义，是指在所有的子序列中最长的那一个。子串是要求...
3
推荐
1638
阅读
【图论】有向无环图的拓扑排序
1. 引言有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。拓扑排序是对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。亦可理解为对某点v而言，只有当v的所有源点均出现了，v才能...
0
推荐
1401
阅读
【图论】求无向连通图的割点
1. 割点与连通度在无向连通图中，删除一个顶点v及其相连的边后，原图从一个连通分量变成了两个或多个连通分量，则称顶点v为割点，同时也称关节点(Articulation Point)。一个没有关节点的连通图称为重连通图(biconnected graph)。若在连通图上至少删去k 个顶点才能破坏图的连通性，则称此图的连通度为k。关节点和重连通图...
1
推荐
1464
阅读
【图论】深入理解Dijsktra算法
1. 介绍Dijsktra算法是大牛Dijsktra于1956年提出，用来解决有向图单源最短路径问题；但是不能解决负权的有向图，若要解决负权图则需要用到Bellman-Ford算法。Dijsktra算法思想：在DFS遍历图的过程中，每一次取出离源点的最近距离的点，将该点标记为已访问，松弛与该点相邻的结点。有向图记为G=(n,m)，其中，n为顶点数，m...
0
推荐
1923
阅读
【模式匹配】Aho-Corasick自动机
1. 多模匹配AC自动机（Aho-Corasick Automaton）是多模匹配算法的一种。所谓多模匹配，是指在字符串匹配中，模式串有多个。前面所介绍的KMP、BM为单模匹配，即模式串只有一个。假设主串T[1⋯m]，模式串有k个P={P1,⋯,Pk}，且模式串集合的总长度为n。如果采用KMP来匹配多模式串，则算法复杂度为：而KMP并没有利用到模式串之...
0
推荐
1586
阅读
【模式匹配】更快的Boyer-Moore算法
1. 引言前一篇中介绍了字符串KMP算法，其利用失配时已匹配的字符信息，以确定下一次匹配时模式串的起始位置。本文所要介绍的Boyer-Moore算法是一种比KMP更快的字符串匹配算法，它到底是怎么快的呢？且听下面分解。不同于KMP在匹配过程中从左至右与主串字符做比较，Boyer-Moore算法是从模式串的尾字符开始从右至左做比较...
0
推荐
1378
阅读
【模式匹配】KMP算法的来龙去脉
1. 引言字符串匹配是极为常见的一种模式匹配。简单地说，就是判断主串TT中是否出现该模式串PP，即PP为TT的子串。特别地，定义主串为T[0…n−1]T[0…n−1]，模式串为P[0…p−1]P[0…p−1]，则主串与模式串的长度各为nn与pp。暴力匹配暴力匹配方法的思想非常朴素：依次从主串的首字符开始，与模式串逐一进行匹配；遇到失配时，则移...
0
推荐
1834
阅读
双数组Trie树 (Double-array Trie) 及其应用
双数组Trie树（Double-array Trie, DAT）是由三个日本人提出的一种Trie树的高效实现 [1]，兼顾了查询效率与空间存储。Ansj便是用DAT（虽然作者宣称是三数组Trie树，但本质上还是DAT）构造词典用作初次分词，极大地节省了内存占用。本文将简要地介绍DAT，并实现了基于DAT的前向最大匹配的中文分词算法。1. Trie树两种实现...
0
推荐
1273
阅读
Bloom Filter：海量数据的HashSet
Bloom Filter一般用于数据的去重计算，近似于HashSet的功能；但是不同于Bitmap（用于精确计算），其为一种估算的数据结构，存在误判（false positive）的情况。1. 基本原理Bloom Filter能高效地表征数据集合S={x1,x2,...,xn}，判断某个数据是否属于这个集合。其基本思想如下：用长度为m的位数组A来存储集合信息，同时是...
0
推荐
1677
阅读
多叉树实现类目体系
1. 引言电商类的网站（比如：京东）为了便于用户浏览商品，建立了一套类目体系，对商品进行各种粗细粒度的划分；如下图：类似地，用户画像的标签体系也划分多层级的结构。在做标签洞察时，需要将这种带有层级的体系序列化json，提供给前端。但是，标签体系是存储在MySQL数据库中，为平铺化的表结构，如何将其表达为具有...