检查一个字符串是否至少包含列表中的一个字符串

Question

我正在尝试使用Python进行匹配。

我有一个字符串列表（长度约为3000），和一个文件，我想检查文件中的每一行是否至少有一个字符串在列表中。

最直接的方法是逐个检查，但这需要时间（虽然不是很长）。

有没有一种更快的搜索方法？

例如：

lst = ["aq", "bs", "ce"]

if the line is "aqwerqwerqwer"  -> true (since has "aq" in it)
if the line is "qweqweqwe" -> false (has none of "aq", "bs" or "ce")

- TYZ

---

这回答解决了您的问题吗？检查多个字符串是否存在于另一个字符串中 - Tomerikoo

Answer 1

你可以使用任何和一个生成器表达式：

# Please do not name a list "list" -- it overrides the built-in
lst = ["a", "b", "c"]
if any(s in line for s in lst):
    # Do stuff

上述代码将测试lst中的任何项是否可以在line中找到。如果是这样，将运行# Do stuff。

以下是一个演示：

>>> lst = ["aq", "bs", "ce"]
>>> if any(s in "aqwerqwerqwer" for s in lst):
...     print(True)
...
True
>>> if any(s in "qweqweqwe" for s in lst):
...     print(True)
...
>>>

- user2555451

---

这仍然会对文件的每一行执行线性搜索。请改用set()。 - liori

@liori 将该行转换为集合本身需要线性时间。 - Ashwini Chaudhary

@Aशwiniचhaudhary 没问题，因为我会多次使用这个集合或列表，所以肯定比每次搜索列表要好。 - TYZ

关于 set 和 list，set 构建时间较长，但支持比 list 更快的查找。set 也是无序的，不能包含重复元素，但这并不重要。通常情况下，如果我需要进行超过10次的查找，我会使用 set，除非有其他限制（如顺序、重复元素等），但你的情况可能会有所不同。 - Adam Smith

不过，我认为有一种更快的方法。让我写下来… - liori

Answer 2

这实际上是使用自动生成的正则表达式和正则表达式引擎的一个很好的用例。

尝试一下：

def re_match(strings_to_match, my_file):
    # building regular expression to match
    expression = re.compile(
        '(' + 
        '|'.join(re.escape(item) for item in strings_to_match) +
        ')')

    # perform matching
    for line in my_file:
        if not expression.search(line):
            return False
    return True

正则表达式比简单的线性扫描每个字符串来匹配每一行更快。这是由于两个原因：正则表达式是用C实现的，并且正则表达式被编译成状态机，只检查每个输入字符一次，而不像朴素解决方案那样检查多次。

在IPython笔记本中查看比较: http://nbviewer.ipython.org/gist/liori/10170227。测试数据包括3000个要匹配的字符串和100万行列表。朴素方法在我的机器上花费了1分46秒，而这种解决方案只需要9.97秒。

- liori

Answer 3

你可以使用itertools.groupby：

from itertools import groupby
pats = ['pat', 'pat2', …]
matches = groupby(lines, keyfunc=lambda line:any(pat in line for pat in pats))

如果您的模式都是单个字符的字符串，您可以使用集合进一步优化它：

pats = set('abcd')
matches = groupby(lines, keyfunc=pats.intersection)

这将导致类似于可迭代的结果

[(matched patterns, lines matched),
 (empty list, lines not matched),
 (matched patterns, lines matched),
 …]

（除了它将是一个生成器，而不是一个列表。）这就是它的主要逻辑。接下来是一种迭代预处理生成器以产生输出的方法。

for linegrp in matches:
  for line in matched_pats, linegrp:
    if matched_pats:
      print('"{}" matched because of "{}"'.format(line, matched_pats))
    else:
      print('"{}" did not match')

- kojiro

Answer 4

更复杂但速度更快：将字符串列表预处理为前缀树。

然后，对于每个文件行，在每个字符位置开始，看看你能走多远进入前缀树。

如果你保持所有活动前缀树的队列，你只需要在扫描行时查看每个字符位置一次。你还可以在每个前缀树节点处包括一个“最小终端深度”计数器，以便在接近字符串结尾时尽早截断比较。

---

一个更简单的方法是将你的字符串大列表转换成一个字典，其中每个键都是你要查找的字符串的前三个字符，对应的值则是包含这些字符串的列表。

from itertools import count, tee, izip

def triwise(iterable):
    # base on pairwise, from the itertools documentation
    "s -> (s0,s1,s2), (s1,s2,s3), (s2,s3,s4), ..."
    a, b, c = tee(iterable, 3)
    next(b, None)
    next(c, None)
    next(c, None)
    return izip(a, b, c)

class Searcher:
    def __init__(self):
        self.index = {}

    def add_seek_strings(self, strings):
        for s in strings:
            pre = s[:3]
            if pre in self.index:
                self.index[pre].append(s)
            else:
                self.index[pre] = [s]

    def find_matches(self, target):
        offset = -1
        for a,b,c in triwise(target):
            offset += 1
            pre = a+b+c
            if pre in self.index:
                from_here = target[offset:]
                for seek in self.index[pre]:
                    if from_here.startswith(seek):
                        yield seek

    def is_match(self, target):
        for match in self.find_matches(target):
            return True
        return False

def main():
    srch = Searcher()
    srch.add_seek_strings(["the", "words", "you", "want"])

    with open("myfile.txt") as inf:
        matched_lines = [line for line in inf if srch.is_match(line)]

if __name__=="__main__":
    main()

- Hugh Bothwell