java正则效率_正则表达式太慢？这⾥有⼀个提速100倍的⽅案
（附代码）
作者：Vikash Singh
编译：肖依⽉、吴双、钱天培
“当遇到⼀个⽂本处理问题时，如果你在第⼀时间想到了正则表达式，那么恭喜你，你的问题从⼀个变成
时间正则表达式java
了俩！“
如果你曾参与过⽂本数据分析，正则表达式(Regex)对你来说⼀定不陌⽣。词库索引、关键词替换……正则表达式的强⼤功能使其成为了⽂本处理的必备⼯具。然⽽， 在处理⼤⽂本的情境下，正则表达式的低效率却常常让⼈抓⽿挠腮。今天，⽂摘菌将为你介绍⼀款⽐正则表达式快数百倍的Python库——FlashText。
让⼈抓狂的数据清洗⼯作
即便是最简单的⽂本分析，我们在进⼊正式分析之前也需要对⽂本作出数据清洗。清洗的⼯作往往涉及到搜索和替换关键词。例如，查询⽂本中是否出现““Python”这⼀关键词，或是将所有“python“都替换成”“Python”。如果仅有数百个被搜索和被替换的关键词，正则表达式处理起来会很快。但在⾃然语⾔处理任务中，有数万关键词的语料库和数百万的⽂档早已是家常便饭。这种情况下，运⾏正则表达式的时间就往往要以“天“来作计数单位了。
吓哭了的⽂摘菌
当然了，你会觉得并⾏运算能够解决这⼀问题，但实际上这⼀⽅案却收效甚微。有没有其他办法呢？
FlashText的创造者当年也⾯临了同样的问题，在经过了⼀番搜寻⽽⽆所获后，他决定⾃⼰来编写⼀个新算法。
在了解FlashText的实现原理之前，让我们先来看看FlashText和正则表达式在搜索任务中的性能对⽐图。
我们可以看到，当关键词数量上升时，Regex所花费的时间⼏乎呈线性增长，然⽽FlashText却⼏乎没受什么影响。
开⼼的⽂摘菌
再来看⼀张执⾏词语替换任务的对⽐图
同样的，在词语数量增加时，FlashText的运⾏时间却⼏乎不受影响。
所以，什么是FlashText呢？
FlashText是GitHub上的⼀个开源Python库，正如之前所提到的，它在提取关键字和替换关键字任务上有着极⾼的性能。
在使⽤FlashText时，你⾸先要给它⼀个关键词列表。这份列表将⽤于在内部建⽴⼀个单词查树的字典(Trie dictionary)。然后你将⼀个字符串传递给它，并告诉它是要执⾏替换还是搜索。
对于替换，它将⽤替换关键字创建⼀个新字符串。对于搜索，它将返回字符串中到的关键字列表。这些任务都只需要遍历字符串⼀遍。
FlashText为什么这么快？
举个例⼦吧。我们有⼀个句⼦，它由三个单词组成——I like Python，并且假设我们有⼀个四个单词组成的语料库{Python, Java, J2ee, Ruby}。
如果我们从语料库中拿出每个单词，并且检查它是否出现在句⼦中，这需要我们遍历字符串四次。
如果语料库⾥有n个词，它将需要n个循环。并且每个搜索步骤(is in sentence?)将花费⾃⼰的时间，这就是正则匹配(Regex match)的机制。
还有与第⼀种⽅法相反的另⼀种⽅法L对于句⼦中的每个单词，检查它是否存在于语料库中。
如果这个句⼦有m个词，它就有m个循环。在这种情况下，所花费的时间只取决于句⼦中的单词数。这个步骤( is in corpus? )可以使⽤字典查快速创建。
FlashText算法是基于第⼆种⽅法的，该灵感来⾃于Aho-Corasick算法和单词查树数据结构(Trie data structure)。
它的⼯作⽅式是：
⾸先根据语料库创建⼀个单词查树字典(Trie data structure)。如下图：
start和EOT(End Of Term)表⽰单词边界，可以是空格，句号或换⾏符。关键字只有在它的两边有单词边界时才能被匹配。这样可以防⽌apple和pineapple的匹配。
接下来，我们将输⼊⼀个字符串I like Python，并且⼀个字符⼀个字符搜索他、它。
因为该算法是⼀个字符接⼀个字符匹配，在搜索I时，我们可以很容易地跳过like在，因为I没有接在后⾯。这⼀机制让我们可以很快跳过词库中不存在的词。
FlashText算法只检查输⼊字符串“I like Python”中的每个字符。即便我们的字典有⼀百万个关键字，这对它的运⾏⼏乎没有影响。这正是FlashText算法的能⼒所在。
所以你什么时候应⽤FlashText？
简要回答：当关键词数量>500时
对于搜索⽽⾔，⼤约超过500个关键词后FlashText开始优于正则表达式。
补充：正则表达式可以搜索基于特殊字符为关键字，如^,$,*,\d,.但FlashText是不⽀持的。
所以如果你想匹配部分的单词(如“word\dvec”)是不⾏的，但它能很好地提取完整的单词(如“word2vec”)。
最后，奉上FlashText的基本功能调⽤代码！试⼀试，是不是⽐正则表达式快了很多呢？
代码：⽤FlashText查关键字
代码：⽤FlashText替换关键字

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。