0
推荐
1944
阅读
【模式匹配】Aho-Corasick自动机
1. 多模匹配AC自动机（Aho-Corasick Automaton）是多模匹配算法的一种。所谓多模匹配，是指在字符串匹配中，模式串有多个。前面所介绍的KMP、BM为单模匹配，即模式串只有一个。假设主串T[1⋯m]，模式串有k个P={P1,⋯,Pk}，且模式串集合的总长度为n。如果采用KMP来匹配多模式串，则算法复杂度为：而KMP并没有利用到模式串之...
0
推荐
1597
阅读
【模式匹配】更快的Boyer-Moore算法
1. 引言前一篇中介绍了字符串KMP算法，其利用失配时已匹配的字符信息，以确定下一次匹配时模式串的起始位置。本文所要介绍的Boyer-Moore算法是一种比KMP更快的字符串匹配算法，它到底是怎么快的呢？且听下面分解。不同于KMP在匹配过程中从左至右与主串字符做比较，Boyer-Moore算法是从模式串的尾字符开始从右至左做比较...
0
推荐
1391
阅读
【模式匹配】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
推荐
1847
阅读
双数组Trie树 (Double-array Trie) 及其应用
双数组Trie树（Double-array Trie, DAT）是由三个日本人提出的一种Trie树的高效实现 [1]，兼顾了查询效率与空间存储。Ansj便是用DAT（虽然作者宣称是三数组Trie树，但本质上还是DAT）构造词典用作初次分词，极大地节省了内存占用。本文将简要地介绍DAT，并实现了基于DAT的前向最大匹配的中文分词算法。1. Trie树两种实现...
0
推荐
1284
阅读
Bloom Filter：海量数据的HashSet
Bloom Filter一般用于数据的去重计算，近似于HashSet的功能；但是不同于Bitmap（用于精确计算），其为一种估算的数据结构，存在误判（false positive）的情况。1. 基本原理Bloom Filter能高效地表征数据集合S={x1,x2,...,xn}，判断某个数据是否属于这个集合。其基本思想如下：用长度为m的位数组A来存储集合信息，同时是...
0
推荐
1689
阅读
多叉树实现类目体系
1. 引言电商类的网站（比如：京东）为了便于用户浏览商品，建立了一套类目体系，对商品进行各种粗细粒度的划分；如下图：类似地，用户画像的标签体系也划分多层级的结构。在做标签洞察时，需要将这种带有层级的体系序列化json，提供给前端。但是，标签体系是存储在MySQL数据库中，为平铺化的表结构，如何将其表达为具有...
0
推荐
1470
阅读
Trie树的应用：查询IP地址的ISP
1. 问题描述给定一个IP地址，如何查询其所属的ISP，如：中国移动（ChinaMobile），中国电信（ChinaTelecom），中国铁通（ChinaTietong)？现有ISP的IP地址区段可供下载，比如中国移动的IP地址段103.20.112.0/22103.21.176.0/22111.0.0.0/20112.0.0.0/10117.128.0.0/10120.192.0.0/10183.192.0.0/10211.103.0.0/17211.136....