Skip to main content
 首页 » 编程设计

python之在 python 中搜索给定字符串的超字符串列表的最快方法

2025年04月02日40虾米哥

我正在从事一个项目,该项目需要根据非常大的字符串列表检查字符串,搜索字符串是列表元素之一的子字符串的情况。

原来我有这个方法:

def isSubstring(subWord, words): 
    for superWord in words: 
            if superWord.find(subWord) != -1 and len(subWord) != len(superWord): 
                return True 
 
    return False 
 
def checkForSubstrings(words): 
    words.sort(key=len, reverse=False) 
 
    while len(words) > 1: 
        currentWord = words.pop(0) 
 
        if isSubstring(currentWord, words): 
            print("%s is a substring of some other string" % currentWord) 

按长度对所有字符串进行排序,对于每个单词,仅将其与较长的单词进行比较。

但这种方法有一个缺陷,就是在列表排序时,单词仍然与任意放在它后面的相同长度的单词进行比较。

所以我更改了 checkForSubstring 方法:

def checkForSubstring(words): 
    sameLengthWordsLists = [[w for w in words if len(w) == num] for num in set(len(i) for i in words)] 
 
    for wordList in sameLengthWordsLists: 
        words = words[len(wordList):] 
 
        if len(words) == 0: 
             break 
 
        for currentWord in wordList: 
            if isSubsumed(currentWord, words): 
                print("%s is a substring of some other string" % currentWord) 

此版本不是按长度排序,而是按长度将字符串列表拆分为多个列表,然后根据每个较大单词列表检查这些列表中的每一个。这解决了之前的问题。

但速度并没有明显加快,有人可以建议一种更快的方法吗?目前,这是一个瓶颈。

请您参考如下方法:

按照我的评论,是这样的:

def checkForSubstrings(words): 
  # e.g: fo: [foo, foobar] 
  super_strings = defaultdict(list) 
  # e.g: foo: [fo, oo] 
  substrings = defaultdict(list) 
  words.sort(key=len, reverse=True) 
  while words: 
    # Nota: pop(0) is highly inefficient, as it moves all the list 
    word = words.pop() 
    subwords = substrings[word] 
    # finding the smallest list of words that contain a substring of `word` 
    current_words = min(super_strings[w] for w in subwords, key=len) 
    if not current_words: 
      current_words = words 
    super_words = [w for w in current_words if len(w) > len(word) and w.find(word) > -1] 
    for s in super_words: 
      substrings[s].append(word) 
    super_strings[word] = super_words 
  # the result is in super_strings 

如果没有 2 个词是子串,或者如果所有都是,这不会改变任何东西。但是,如果只有一些,它应该加快一些事情。那并使用 pop() 而不是 pop(0)