我正在从事一个项目,该项目需要根据非常大的字符串列表检查字符串,搜索字符串是列表元素之一的子字符串的情况。
原来我有这个方法:
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)
