搜索字符串中的不同子字符串

我有一个字符串。我需要知道以下任何子字符串是否出现在字符串中。搜索字符串中的不同子字符串

所以，如果我有：

thing_name = "VISA ASSESSMENTS"

我一直在做我的搜索与：

any((_ in thing_name for _ in ['ASSESSMENTS','KILOBYTE','INTERNATIONAL']))

我经历thing_name项目的一个长长的清单，我不需要过滤，确切地说，只需检查任何数量的子字符串。

这是最好的方法吗？感觉不对，但我想不出一个更有效的方法来解决这个问题。

来源

2013-08-19 Josh English

您是否在搜索'VISA'和'ASSESSMENTS'或任何子字符串？ –

如果你可能的子串的列表是一个集合，你或许可以加快一点，但除此之外，我认为这种方法没有任何问题。这是好的和可读的。下一步将是严肃的算法设计。 – kojiro

@AshwiniChaudhary，我正在寻找'ASSESSMENTS'，'KILOBYTES'或其他几个项目之一。 –

你可以试试re.search看看是否更快。一些东西沿线

import re 
pattern = re.compile('|'.join(['ASSESSMENTS','KILOBYTE','INTERNATIONAL'])) 
isMatch = (pattern.search(thing_name) != None)

来源

2013-08-19 19:29:16

感谢大家的建议。因此，我做了一些时间安排，发现重新解决方案在我的情况下是最快的。我想出了八种不同的方式来做这件事，并从我的情况中获取数据，考虑到字段的长度和数量，RE是最快的。预编译正则表达式是最好的，其次是在我的列表中每次运行期间编译正则表达式。设置交集是第三快，但是当检查集合的长度并且比较0比单纯地将交集转换为布尔值时更快。 –

我建议在子字符串中使用're.escape'，然后将它们传递给're.compile'（例如're.compile（'|'.join（re.escape（sub）for sub in [... ]））'），否则包含非字母数字字符的子字符串可能会产生问题（甚至可能导致're.compile'失败）。 – Bakuriu

@Bakuriu，用于告诉're.escape' +1。 –

如果你的子串列表很小并且输入很小，那么使用for循环做比较就没有问题。

否则，我知道搜索一个（大）的子串列表的字符串最快的方法是构造一个单词列表的DAWG，然后遍历输入字符串，保持DAWG遍历列表并注册子串每次成功遍历。

另一种方法是将所有子字符串添加到散列表中，然后在遍历输入字符串时对每个可能的子字符串（最长子字符串的长度）进行散列。

因为我在Python中工作已经有一段时间了，我记得它的实现速度很慢。要使用DAWG路由，我可能会将其实现为本地模块，然后使用它从python （如果可能的话）。否则，我会做一些速度检查来验证第一，但可能去散列表路由，因为在Python中已经有高性能的哈希表。

来源

2013-08-19 19:01:42

指向非循环字图上的文档的链接可能会按顺序排列。 http://en.wikipedia.org/wiki/Directed_acyclic_word_graph – kojiro

搜索字符串中的不同子字符串

回答

相关问题