正则表达式时间复杂度(正则匹配复杂度)
使用正则表达式匹配时间格式字符串的小心得
"/Date(1546012800000+0800)/"，而我需要把它转化成这种格式:2019-05-23 12:34:22(北京时间)，并作为入参传给另一个 MAPI 接口。
第一时间想到的解决办法就是看看框架中是否带有这种时间戳处理的功能，发 现大多是直接处理时间戳的，像这种:1554362965，所以需要把得到的时间格 式进行处理一下:
首先括号及括号两边的字符是不需要的，另外，+0800 是时区差，表示北京时 间，所以+0800 也可以不需要。要取出 1546012800000 至少有两种方式，第一 种就是正则表达式，第二种就是字符串截取函数 slice()、substring()、substr()。
解释一下这个正则表达式:
第一个字符“/”是正则表达式的开始，第二个字符“\”是转义符，因为字符串中带 有“/”，属于元字符，所以我们需要用转义符转义一下，/Date 是字符串中的内 容，因为格式不变，这个地方可以直接匹配。然后又出现了“\”，因为后面的
“ (”也是属于元字符，因此我们还是需要“\”转义符，之后的( ) 就是分组，\d 表 示数字，*表示数字在文本中出现零次或连续多次，+号表示以+号结尾，最后 以“/”结束整个正则表达式。
这个方法很大程度上有赖于你所写 的正则表达式是否包含 g，如果没有 g，那么 match() 方法就只能在 str 中执行 一次匹配。如果没有找到任何匹配的文本，match() 将返回 null。否则，它将 返回一个数组，其中存放了与它找到的匹配文本有关的信息。该数组的第 0 个 元素存放的是匹配文本，而其余的元素存放的是与正则表达式的子表达式匹配 的文本。除了这些常规的数组元素之外，返回的数组还含有两个对象属性。 index 属性声明的是匹配文本的起始字符在 str 中的位置，input 属性存放的是 你要匹配的文本。如果有 g，则 match() 方法会全局检索，找到 str 中所有匹配 的子字符串，全局匹配到子串时返回的数组中没有 index 属性或 input 属性。 上面的正则表达式还可以这样写，结果也是一样的。
直接从 Date 开始匹配，正则表达式就更简短了。
对于上面这个正则，其他的不用多解释，\w 和+号可以说一说。
\w 用来匹配字母、数字和下划线，而后面的+号表示在文本中连续出现一次或 多次。这个正则中的第三个+号是文本中的+号，由于+号是元字符，所以我们 需要用“\”进行转义一下。 另外再说一个分组的问题，如果上面的字符串我们要把+0800 也匹配进来，可 以在正则表达式中多加一对括号，像下面这样:
第一个正则表达式我们只匹配到了 1546012800000，因为它只能识别 /Date(xxx，上面这个正则表达式还可以识别/Dyzc(，例如：
元字符:有特殊含义，以至于不能表示原本意义的字符。 除了正则表达式，HTML、XML、URL，到处都有元字符，并且他们的元字符 还不一定一样。
HTML:
空格( )不表示空格， 只能用 ? 来表示空格。
大于号()不能表示大于号，只能用 来表示大于号
URL 中，例如:
这个 URL 中的%20 其实是个空格。 因为 URL 规定里面只能包含很少的几十种 字符，其中空格就是被禁用的，不能包含空格，那不能包含空格而用户的确需 要表示空格，怎么办呢?
用另外的东西代表空格，在 URL 中，就是%20
因此
等于
y
但是下面这个 url 是不合法，所以要被「转义」为上面这个。
url 或者 cookie 中一般一大堆%数字 1、%数字 2 的，全是%开头的，这都是套 路。
正则表达式中可以用/来把元字符转义成他本来的意思，
/ = / ( = ( + = +
HTML 中是以为开头，;结尾的。
URL 中是以%开头。
正则表达式是以/开头，/结尾的。
终于说完了正则表达式，下面来说说第二种获取"/Date(1546012800000+0800)/" 中 1546012800000 的方法，个人觉得用字符串截取函数来获取也同样是要抓住
不变点和变点，只有抓住这两个，就很好解决这个问题了。因为返回的时间格 式是固定的，所以我们可以从/开始数，第 6 个(index=6)开始，然后以+号结 束，拿到的刚好是 1546012800000，下面我借助一下 indexOf 来获取到+号的位置:
indexOf() 方法可返回某个指定的字符串值在字符串中首次出现的位置。第一个 参数是必须的，就是要检索的字符串值，它还可以传入第二个参数，必须是个 整数，从 0 开始，表示从字符串中开始检索的位置，比如说你想从第 6 个字符 开始检索，就可以传 5，最大的取值就是 str.length-1。如果省略就是从首字符开 始检索。
再说一下 substr()函数: substr()方法返回从指定位置开始的字符串中指定字符数的字符，第一个参数是 指定开始的位置，第二个参数是截取的长度。 这里的第二个参数长度就是用+号的位置减去前面不需要的 6 个字符，得到的就 是我们真正要的时间戳。
而 slice()、substring()就更更简单了了。
slice()和 substring()方法都是返回一个索引和另一个索引之间的字符串。所以这 里只需要传+号的位置就行，而且这两个文法第二个参数都不包含该索引位置的
字符。具体可以参考下面这篇文章。
拿到时间戳之后就可以直接用框架中的工具，把 1558281600000 转换成 2019-5- 20 0:0:0。
C语言怎么用正则表达式
由于它可以极大地简化处理字符串时的复杂度，因此现在已经在许多 L i n u x 实用工具中得到了应用。千万不要以为正则表达式只是 P e r l 、 P y t h o n 、 B a s h 等脚本语言的专利，作为 C 语言程序员，用户同样可以在自己的程序中运用正则表达式。标准的 C 和 C + + 都不支持正则表达式，但有一些函数库可以辅助 C / C + + 程序员完成这一功能，其中最著名的当数 P h i l i p H a z e l 的 P e r l - C o m p a t i b l e R e g u l a r E x p r e s s i o n 库，许多 L i n u x 发行版本都带有这个函数库。编译正则表达式为了提高效率，在将一个字符串与正则表达式进行比较之前，首先要用 r e g c o m p ( ) 函数对它进行编译，将其转化为 r e g e x _ t 结构： i n t r e g c o m p ( r e g e x _ t * p r e g , c o n s t c h a r * r e g e x , i n t c f l a g s ) ; 参数 r e g e x 是一个字符串，它代表将要被编译的正则表达式；参数 p r e g 指向一个声明为 r e g e x _ t 的数据结构，用来保存编译结果；参数 c f l a g s 决定了正则表达式该如何被处理的细节。如果函数 r e g c o m p ( ) 执行成功，并且编译结果被正确填充到 p r e g 中后，函数将返回 0 ，任何其它的返回结果都代表有某种错误产生。匹配正则表达式一旦用 r e g c o m p ( ) 函数成功地编译了正则表达式，接下来就可以调用 r e g e x e c ( ) 函数完成模式匹配： i n t r e g e x e c ( c o n s t r e g e x _ t * p r e g , c o n s t c h a r * s t r i n g , s i z e _ t n m a t c h , r e g m a t c h _ t p m a t c h [ ] , i n t e f l a g s ) ; t y p e d e f s t r u c t { r e g o f f _ t r m _ s o ; r e g o f f _ t r m _ e o ; } r e g m a t c h _ t ; 参数 p r e g 指向编译后的正则表达式，参数 s t r i n g 是将要进行匹配的字符串，而参数 n m a t c h 和 p m a t c h 则用于把匹配结果返回给调用程序，最后一个参数 e f l a g s 决定了匹配的细节。在调用函数 r e g e x e c ( ) 进行模式匹配的过程中，可能在字符串 s t r i n g 中会有多处与给定的正则表达式相匹配，参数 p m a t c h 就是用来保存这些匹配位置的，而参数 n m a t c h 则告诉函数 r e g e x e c ( ) 最多可以把多少个匹配结果填充到 p m a t c h 数组中。当 r e g e x e c ( ) 函数成功返回时，从 s t r i n g + p m a t c h [ 0 ] . r m _ s o 到 s t r i n g + p m a t c h [ 0 ] . r m _ e o 是第一个匹配的字符串，而从 s t r i n g + p m a t c h [ 1 ] . r m _ s o 到 s t r i n g + p m a t c h [ 1 ] . r m _ e o ，则是第二个匹配的字符串，依此类推。释放正则表达式无论什么时候，当不再需要已经编译过的正则表达式时，都应该调用函数 r e g f r e e ( ) 将其释放，以免产生内存泄漏。 v o i d r e g f r e e ( r e g e x _ t * p r e g ) ; 函数 r e g f r e e ( ) 不会返回任何结果，它仅接收一个指向 r e g e x _ t 数据类型的指针，这是之前调用 r e g c o m p ( ) 函数所得到的编译结果。如果在程序中针对同一个 r e g e x _ t 结构调用了多次 r e g c o m p ( ) 函数， P O S I X 标准并没有规定是否每次都必须调用 r e g f r e e ( ) 函数进行释放，但建议每次调用 r e g c o m p ( ) 函数对正则表达式进行编译后都调用一次 r e g f r e e ( ) 函数，以尽早释放占用的存储空间。报告错误信息如果调用函数 r e g c o m p ( ) 或 r e g e x e c ( ) 得到的是一个非 0 的返回值，则表明在对正则表达式的处理过程中出现了某种错误，此时可以通过调用函数 r e g e r r o r ( ) 得到详细的错误信息。 s i z e _ t r e g e r r o r ( i n t e r r c o d e , c o n s t r e g e x _ t * p r e g , c h a r * e r r b u f , s i z e _ t e r r b u f _ s i z e ) ; 参数 e r r c o d e 是来自函数 r e g c o m p ( ) 或 r e g e x e c ( ) 的错误代码，而参数 p r e g 则是由函数 r e g c o m p ( ) 得到的编译结果，其目的是把格式化消息所必须的上下文提供给 r e g e r r o r ( ) 函数。在执行函数 r e g e r r o r ( ) 时，将按照参数 e r r b u f _ s i z e 指明的最大字节数，在 e r r b u f 缓冲区中填入格式化后的错误信息，同时返回错误信息的长度。应用正则表达式最后给出一个具体的实例，介绍如何在 C 语言程序中处理正则表达式。 # i n c l u d e s t d i o . h ; # i n c l u d e s y s / t y p e s . h ; # i n c l u d e r e g e x . h ; / * 取子串的函数 * / s t a t i c c h a r * s u b s t r ( c o n s t c h a r * s t r , u n s i g n e d s t a r t , u n s i g n e d e n d ) { u n s i g n e d n = e n d - s t a r t ; s t a t i c c h a r s t b u f [ 2 5 6 ] ; s t r n c p y ( s t b u f , s t r + s t a r t , n ) ; s t b u f [ n ] = 0 ; r e t u r n s t b u f ; } / * 主程序 * / i n t m a i n ( i n t a r g c , c h a r * * a r g v ) { c h a r * p a t t e r n ; i n t x , z , l n o = 0 , c f l a g s = 0 ; c h a r e b u f [ 1 2 8 ] , l b u f [ 2 5 6 ] ; r e g e x _ t r e g ; r e g m a t c h _ t p m [ 1 0 ] ; c o n s t s i z e _ t n m a t c h = 1 0 ; / * 编译正则表达式 * / p a t t e r n = a r g v [ 1 ] ; z = r e g c o m p ( r e g , p a t t e r n , c f l a g s ) ; i f ( z ! = 0 ) { r e g e r r o r ( z , r e g , e b u f , s i z e o f ( e b u f ) ) ; f p r i n t f ( s t d e r r , " % s : p a t t e r n ' % s ' \ n " , e b u f , p a t t e r n ) ; r e t u r n 1 ; } / * 逐行处理输入的数据 * / w h i l e ( f g e t s ( l b u f , s i z e o f ( l b u f ) , s t d i n ) ) { + + l n o ; i f ( ( z = s t r l e n ( l b u f ) ) ; 0 l b u f [ z - 1 ] = = ' \ n ' ) l b u f [ z - 1 ] = 0 ; / * 对每一行应用正则表达式进行匹配 * / z = r e g e x e c ( r e g , l b u f , n m a t c h , p m , 0 ) ; i f ( z = = R E G _ N O M A T C H ) c o n t i n u e ; e l s e i f ( z ! = 0 ) { r e g e r r o r ( z , r e g , e b u f , s i z e o f ( e b u f ) ) ; f p r i n t f ( s t d e r r , " % s : r e g c o m ( ' % s ' ) \ n " , e b u f , l b u f ) ; r e t u r n 2 ; } / * 输出处理结果 * / f o r ( x = 0 ; x n m a t c h p m [ x ] . r m _ s o ! = - 1 ; + + x ) { i f ( ! x ) p r i n t f ( " % 0 4 d : % s \ n " , l n o , l b u f ) ; p r i n t f ( " $ % d = ' % s ' \ n " , x , s u b s t r ( l b u f , p m [ x ] . r m _ s o , p m [ x ] . r m _ e o ) ) ; } } / * 释放正则表达式 * / r e g f r e e ( r e g ) ; r e t u r n 0 ; } 上述程序负责从命令行获取正则表达式，然后将其运用于从标准输入得到的每行数据，并打印出匹配结果。执行下面的命令可以编译并执行该程序： # g c c r e g e x p . c - o r e g e x p # . / r e g e x p ' r e g e x [ a - z ] * ' r e g e x p . c 0 0 0 3 : # i n c l u d e r e g e x . h ; $ 0 = ' r e g e x ' 0 0 2 7 : r e g e x _ t r e g ; $ 0 = ' r e g e x ' 0 0 5 4 : z = r e g e x e c ( r e g , l b u f , n m a t c h , p m , 0 ) ; $ 0 = ' r e g e x e c ' 小结对那些需要进行复杂数据处理的程序来说，正则表达式无疑是一个非常有用的工具。本文重点在于阐述如何在 C 语言中利用正则表达式来简化字符串处理，以便在数据处理方面能够获得与 P e r l 语言类似的灵活性。
算法设计-帮帮忙
这个估计要用文件输入
否则太累了
--我们必须尽量优化程序才能达到题目的要求。显然n实在是太大了，所以我们不但不可能忍受O(n2)的复杂度，甚至连n前面的系数过大都会造成超时。为了尽量减小时间复杂度，我们只能依靠自动机的理论。
自动机理论
一个DFA（确定性有限自动机）是一个五元组∑, U, s, T, φ，其中∑是字符集U 是一个有限的状态集合, s 是 U 的一个元素表示初始状态, T 是 U的一个子集，表示终止状态and φ : U × ∑ → U 是转移函数。
开始时自动机在初始状态s，每步它读入一个字符c，然后根据state=φ(state,c)进行状态的转移。如果当字符串结束时它达到了终止状态，那么就说它接受了字符串。
NFA（非确定性自动机）与DFA的主要区别就是，NFA从一个状态按照一个字符转移到的状态可能有多个。因此NFA需要使用一个状态集合来表示当前可能处在的状态。
把自动机用图来表示的话，一般用结点表示状态，而结点之间有标有某个字符的有向边，表示可以从边的起点通过这个字符转移到边的终点。
此外NFA还可以包含标有ε的边，这种边表示不需要任何字符就可以直接进行状态的转移。
容易想到，如果我们建立了一个只接受符合正则表达式的自动机，就可以通过它来较快的判断哪些位置是可匹配的。
具体应用
比较常见的字符串匹配自动机大多都是DFA。但是由于有+，*，把正则表达式直接转变成DFA是非常困难的。因此我们只能先把它转化成NFA。
先看一下一般的转换规则：
如果正则表达式是一个字符，那么对应的NFA是：
p0-a-p1
如果正则表达式是A+B的形式，那么只要把它们的起始状态和终止状态合并就可以：
p0-a-p1
p0-b-p1
如果正则表达式是AB的形式，那么只要把A和B对应的自动机首尾相接：
p0-a-p1-b-p2
如果正则表达式是A*的形式，那么就需要按下面的图来进行处理：
p0-a-p0
p0-p1
通过上面的步骤可以得出：NFA的状态数不会超过正则表达式长度。
NFA中的状态转移
在NFA中进行状态转移比DFA要困难一些。我们可以定义两个函数，一个叫做epsilon-closure，用来计算一组NFA状态通过epsilon边能够到达的NFA状态集合。另外一个move用来在NFA上进行状态的转移。
设当前的状态集合是now，那么状态转移的过程就是：
new = {}
for every state s in now do
new = new ∪ {t | (s,t) = c}
new = epsilon_closure(new)
其中的(s,t)=c表示从s状态经过一个字符c可以转化到t状态。因为这个语句需要的集合总数也不会太多，所以可以通过预先计算出它们来加快速度。预处理后这个过程的复杂度是O(m2)，而系数是比较小的。
但是由于在NFA中，我们必须把状态的集合作为一个真正的状态，每次状态转移都是对这个集合的处理。这样转移一次的复杂度是O(m2)，这是不可忍受的（最大的数据需要大约2分钟才能出解）。
既然NFA速度过慢，我们自然想要把它转化为DFA。因为DFA中的状态转移是O(1)的。可是并没有一个多项式复杂度的方法可以把NFA转换成DFA。一般介绍的NFA转换到DFA的方法都是通过类似BFS的方法来把NFA中所有可能出现的状态集合对应成DFA的一个状态。
这种转换在本题中显然是不可行的，因为NFA的结点数最多是500，而转化成的DFA则可能有多达2500个状态，即使实际有许多状态不能达到，也是无论如何不可以忍受的。
看来把NFA转换成DFA是行不通的。但是我们还是从NFA转DFA的过程中受到了一些启发：NFA之所以速度慢，是因为我们在进行状态转移的时候可能进行许多重复操作：比如从{1,2}沿一个字符1转移后是{2,3}，以后我们还可能遇到相同的情况，而这时我们还会用O(m2)的时间去进行状态转移。这是一种很严重的浪费。因此我们每进行一次状态转移，就把这个状态转移的情况放到hash表中，以后使用的时候就可以查找了。这相当于只把我们需要的一部分子集转移成DFA，虽然一般情况下并不能降低时间复杂度，但是在实际应用中确实很有效。（特别是对于没有*和括号的自动机，这样做可以保证线形的时间复杂度）
算法回顾和细节
我们重新来看一下算法的框架：
根据正则表达式建立NFA
now = start
while not eof do begin
read(c);
if 曾经进行过now,c的转移 then 利用以前的结果
else 进行状态转移并记录结果
if 终止状态 in now then 输出当前位置
end
建立NFA有各种方法，由于NFA并不会很大，所以我们可以使用递归的方法来实现。为了尽量减小系数，我们使用位压缩的方式来实现集合，并采用较为简化的hash函数（比如把一个集合位压缩后的一系列整数加起来取对220的余数），并在输入和输出的时候通过缓冲区来加快速度。这样就基本可以达到题目的时间要求。
但是注意到字符串可能有10M，而产生的NFA的状态集合最多也可能有10M个，而每个集合都需要100到200字节的存储空间，大大超出了允许的空间范围。因此我们需要对hash表的规模加以严格限制。如果规模过大就不得不放弃存储状态的想法，牺牲一定的时间来换取空间。
正则表达式，我写的判断月份日期的 MMDD这种格式的
这个东东没有什么好优化的，看来你对非捕获组挺有了解。
但是这个表达式有一个严重的错误就是不能匹配：0229这个形式，这个涉及到瑞年（100的倍数被400整除否则被4整除）的判断，如果要加上去复杂度会提高很多很多。
已经很不容易了，加油！
告别正则表达式，这个Python库可以快M倍
FlashText 算法是由 Vikash Singh 于2017年发表的大规模关键词替换算法，这个算法的时间复杂度仅由文本长度（N）决定，算法时间复杂度为O（N）。
而对于正则表达式的替换，算法时间复杂度还需要考虑被替换的关键词数量（M），因此时间复杂度为O（MxN）。
简而言之， 基于FlashText算法的字符串替换比正则表达式替换快M倍以上，这个M是需要替换的关键词数量，关键词越多，FlashText算法的优势就越明显 。
下面就给大家介绍如何在 Python 中基于 flashtext 模块使用 FlashText 算法进行字符串查找和替换，如果觉得对你的项目团队很有帮助，请记得帮作者转发一下哦。
1.准备
开始之前，你要确保Python和pip已经成功安装在电脑上，如果没有，可以访问这篇文章：超详细Python安装指南 进行安装。
(可选1) 如果你用Python的目的是数据分析，可以直接安装Anaconda：Python数据分析与挖掘好帮手—Anaconda，它内置了Python和pip.
(可选2) 此外，推荐大家用VSCode编辑器，它有许多的优点：Python 编程的最好搭档—VSCode 详细指南。
请选择以下任一种方式输入命令安装依赖 ：
1. Windows 环境 打开 Cmd (开始-运行-CMD)。
2. MacOS 环境 打开 Terminal (command+空格输入Terminal)。
3. 如果你用的是 VSCode编辑器 或 Pycharm，可以直接使用界面下方的Terminal.
pip install flashtext
2.基本使用
提取关键词
一个最基本的提取关键词的例子如下：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. 添加关键词
keyword_processor.add_keyword( 'Big Apple' , 'New York' )
keyword_processor.add_keyword( 'Bay Area' )
# 3. 处理目标句子并提取相应关键词
keywords_found = keyword_processor.extract_keywords( 'I love Big Apple and Bay Area.' )
# 4. 结果
print(keywords_found)
# ['New York', 'Bay Area']
其中 add_keyword 的第一个参数代表需要被查找的关键词，第二个参数是给这个关键词一个别名，如果找到了则以别名显示。
替换关键词
如果你想要替换关键词，只需要调用处理器的 replace_keywords 函数：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. 添加关键词
keyword_processor.add_keyword( 'New Delhi' , 'NCR region' )
# 3. 替换关键词
new_sentence = keyword_processor.replace_keywords( 'I love Big Apple and new delhi.' )
# 4. 结果
print(new_sentence)
# 'I love New York and NCR region.'
关键词大小写敏感
如果你需要精确提取，识别大小写字母，那么你可以在处理器初始化的时候设定 sensitive 参数:
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器, 注意设置大小写敏感(case_sensitive)为TRUE
keyword_processor = KeywordProcessor(case_sensitive= True )
# 2. 添加关键词
keyword_processor.add_keyword( 'Big Apple' , 'New York' )
keyword_processor.add_keyword( 'Bay Area' )
# 3. 处理目标句子并提取相应关键词
keywords_found = keyword_processor.extract_keywords( 'I love big Apple and Bay Area.' )
# 4. 结果
print(keywords_found)
# ['Bay Area']
标记关键词位置
如果你需要获取关键词在句子中的位置，在 extract_keywords 的时候添加 span_info=True 参数即可：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. 添加关键词
keyword_processor.add_keyword( 'Big Apple' , 'New York' )
keyword_processor.add_keyword( 'Bay Area' )
# 3. 处理目标句子并提取相应关键词, 并标记关键词的起始、终止位置
keywords_found = keyword_processor.extract_keywords( 'I love big Apple and Bay Area.' , span_info= True )
# 4. 结果
print(keywords_found)
# [('New York', 7, 16), ('Bay Area', 21, 29)]
获取目前所有的关键词
如果你需要获取当前已经添加的所有关键词，只需要调用处理器的 get_all_keywords 函数：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. 添加关键词
keyword_processor.add_keyword( 'j2ee' , 'Java' )
keyword_processor.add_keyword( 'colour' , 'color' )
# 3. 获取所有关键词
keyword_processor.get_all_keywords()
# output: {'colour': 'color', 'j2ee': 'Java'}
批量添加关键词
批量添加关键词有两种方法，一种是通过词典，一种是通过数组：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. （第一种）通过字典批量添加关键词
keyword_dict = {
"java" : [ "java_2e" , "java programing" ],
"product management" : [ "PM" , "product manager" ]
}
keyword_processor.add_keywords_from_dict(keyword_dict)
# 2. （第二种）通过数组批量添加关键词
keyword_processor.add_keywords_from_list([ "java" , "python" ])
# 3. 第一种的提取效果如下
keyword_processor.extract_keywords( 'I am a product manager for a java_2e platform' )
# output ['product management', 'java']
单一或批量删除关键词
删除关键词也非常简单，和添加类似：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. 通过字典批量添加关键词
keyword_dict = {
"java" : [ "java_2e" , "java programing" ],
"product management" : [ "PM" , "product manager" ]
}
keyword_processor.add_keywords_from_dict(keyword_dict)
# 3. 提取效果如下
print(keyword_processor.extract_keywords( 'I am a product manager for a java_2e platform' ))
# ['product management', 'java']
# 4. 单个删除关键词
keyword_processor.remove_keyword( 'java_2e' )
# 5. 批量删除关键词，也是可以通过词典或者数组的形式
keyword_processor.remove_keywords_from_dict({ "product management" : [ "PM" ]})
keyword_processor.remove_keywords_from_list([ "java programing" ])
# 6. 删除了java programing关键词后的效果如下
keyword_processor.extract_keywords( 'I am a product manager for a java_2e platform' )
# ['product management']
3.高级使用
支持额外信息
前面提到在添加关键词的时候第二个参数为其别名，其实你不仅可以指示别名，还可以将额外信息放到第二个参数中：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
kp = KeywordProcessor()
# 2. 添加关键词并附带额外信息
kp.add_keyword( 'Taj Mahal' , ( 'Monument' , 'Taj Mahal' ))
kp.add_keyword( 'Delhi' , ( 'Location' , 'Delhi' ))
# 3. 效果如下
kp.extract_keywords( 'Taj Mahal is in Delhi.' )
# [('Monument', 'Taj Mahal'), ('Location', 'Delhi')]
这样，在提取关键词的时候，你还能拿到其他一些你想要在得到此关键词时输出的信息。
支持特殊单词边界
Flashtext 检测的单词边界一般局限于 w [A-Za-z0-9_] 外的任意字符，但是如果你想添加某些特殊字符作为单词的一部分也是可以实现的：
from flashtext import KeywordProcessor
# 1. 初始化关键字处理器
keyword_processor = KeywordProcessor()
# 2. 添加关键词
keyword_processor.add_keyword( 'Big Apple' )
# 3. 正常效果
print(keyword_processor.extract_keywords( 'I love Big Apple/Bay Area.' ))
# ['Big Apple']
# 4. 将 '/' 作为单词一部分
keyword_processor.add_non_word_boundary( '/' )
# 5. 优化后的效果
print(keyword_processor.extract_keywords( 'I love Big Apple/Bay Area.' ))
# []
4.结尾
个人认为这个模块已经满足我们的基本使用了，如果你有一些该模块提供的功能之外的使用需求，可以给 flashtext 贡献代码：
附 FlashText 与正则相比 查询关键词 所花费的时间之比：
附 FlashText 与正则相比 替换关键词 所花费的时间之比：
这篇文章如果对你有帮助的话，记得转发一下哦。
一道很难的算法题
只想到一种暴力方法,就是找到一个最短的+串进行枚举所有的匹配可能,由于长度最多是8,2^8不是很大还可以接受.然后对所有的+串进行一次改进,每当发现一个匹配串不符合某个+串,则进行添加,若无论如何都无法匹配,则否决.然后再对所有的-串进行一次检查,若匹配则否决,最后剩下的匹配串里面输出最短那个.
时间复杂度在O(2^m*n*m)级别,还算在接受范围之内.
不过的确不优美,最好是能找到更优的做法.