Python-从列表中删除包含其他单词的所有单词

Question

我有一个单词列表，里面的单词来自字典。我想找到一种方法，只考虑形成目标单词开头的词根单词，将所有单词都删除。

例如，单词“rodeo”将从列表中删除，因为它包含英文有效单词“rode”。 “Typewriter”也会被删除，因为它包含英文有效单词“type”。但是，“snicker”这个单词仍然有效，即使它包含“nick”这个词，因为“nick”在单词中间而不是在开头。

我考虑了以下代码：

 for line in wordlist:
        if line.find(...) --

但是我希望那个“if”语句可以遍历列表中的每一个单词，检查是否找到它，并且如果找到了，则从列表中删除它，以便只剩下根词。我需要创建一个wordlist的副本来遍历吗？

- Parseltongue

---

有两个列表吗？一个来自字典，另一个包含您的“根”单词？ - aqua

你建议使用双重嵌套循环，一个用于考虑每个目标单词，另一个用于对有效列表中的每个单词调用.startswith()方法。这将非常慢。Python for循环不是最快的，而且在任何情况下，Python提供了一些有用的数据结构，具有快速查找功能。在这种问题中，你应该考虑“Python中哪些数据结构会有所帮助？”字典是可能的，但集合在这里是理想的。只需尝试目标单词的各种子字符串进行快速集合查找，就像我建议的那样，这将更容易和更快。 - steveha

Answer 1

所以您有两个列表: 您想要检查和可能删除的单词列表和一个有效单词列表。如果您愿意，您可以将相同的列表用于这两个目的，但我假设您有两个列表。

为了提高速度，您应该将有效单词列表转换为集合。然后，您可以非常快地检查特定单词是否在该集合中。然后，取出每个单词，并检查它的所有前缀是否存在于有效单词列表中。由于“a”和“I”是英语中的有效单词，您会删除以“a”开头的所有有效单词，还是会设置一个前缀的最小长度规则？

我使用的是我的Ubuntu安装中的文件/usr/share/dict/words。该文件包含各种奇怪的东西;例如，似乎包含每个字母本身作为一个单词。因此，“k”在其中，“q”，“z”等。据我所知，这些都不是单词，但它们可能因某种技术原因而在其中。无论如何，我决定简单地从我的有效单词列表中排除任何少于三个字母的内容。

这就是我想出来的：

# build valid list from /usr/dict/share/words
wfile = "/usr/dict/share/words"
valid = set(line.strip() for line in open(wfile) if len(line) >= 3)

lst = ["ark", "booze", "kite", "live", "rodeo"]

def subwords(word):
    for i in range(len(word) - 1, 0, -1):
        w = word[:i]
        yield w

newlst = []
for word in lst:
    # uncomment these for debugging to make sure it works
    # print "subwords", [w for w in subwords(word)]
    # print "valid subwords", [w for w in subwords(word) if w in valid]
    if not any(w in valid for w in subwords(word)):
        newlst.append(word)

print(newlst)

如果你喜欢使用一行代码，可以使用列表推导式来代替for循环：

newlst = [word for word in lst if not any(w in valid for w in subwords(word))]

我认为这段话比应该更加简洁，但是我喜欢能够添加打印语句进行调试。

嗯，仔细想想，如果您只是添加另一个函数，它就不会太简洁了：

def keep(word):
    return not any(w in valid for w in subwords(word))

newlst = [word for word in lst if keep(word)]

如果您像这样编写函数并为它们取好名称，Python 可以很容易阅读和理解。

- steveha

---

这个方法的效率远不如它应该的高。如果我没理解错的话，它的时间复杂度是O(n²)而不是O(n)。 - BudgieInWA

即使它效率低下，它很容易理解。非常感谢。 - Parseltongue

我理解这个问题是“从列表中删除（包含其他单词的所有单词）”，而不是“删除所有包含（同一列表中的其他单词）的单词”。如果我们只关心列表内的其他单词，那么这个解决方案就有些过度了。如果你能提供一个O(n)算法来解决我正在解决的同样的问题，我预测它将涉及到树结构，比如trie。我认为我们应该说这是一个O(m*n)的解决方案，其中m是每个单词的平均字母数，n是单词数。它绝对不是O(n²)，其中n是列表中单词的数量。 - steveha

我同意你正在解决一个稍微不同的问题。我想问一下，w in valid需要O(n)的时间（valid被遍历了）吗？这是否使得时间复杂度为O(n*m)，其中n是lst的长度，m是valid的长度？ - BudgieInWA

如果valid是一个list，那么w in valid将花费O(n)的时间。但是valid是一个set，所以w in valid只需要O(1)的时间。实际上，为了获得最快的速度，它应该是一个frozenset；我们不需要修改这个集合，而且我相信frozenset比set稍微快一些，而代价是不能被修改。dict也是O(1)查找。（所有这些都使用哈希，我猜哈希运行时间可能会因哈希桶的填充程度而异...）http://pyref.infogami.com/frozenset - steveha

谢谢Steveha，当我上床睡觉时，我也有类似的想法。 - BudgieInWA

Answer 2

我假设您只有一个列表，想要从该列表中删除任何具有相同前缀的元素。

#Important assumption here... wordlist is sorted

base=wordlist[0]                      #consider the first word in the list
for word in wordlist:                 #loop through the entire list checking if
    if not word.startswith(base):     # the word we're considering starts with the base
        print base                    #If not... we have a new base, print the current
        base=word                     #  one and move to this new one
    #else word starts with base
        #don't output word, and go on to the next item in the list
print base                            #finish by printing the last base

编辑：添加了一些注释以使逻辑更明显

- jkerian

---

你需要将“print base”移动到第一行之后。现在，这会将最后一个单词打印两次，而第一个单词则根本不打印。此外，用yield替换print可以为最终列表生成器。 - user97370

你能解释一下这个是如何工作的吗？我真的不明白这个怎么能从单词列表中删除包含其他单词的单词。 - Parseltongue

@Paul Hankin：使用yield替换print确实可以使列表生成器，但是您错误地移动了print语句。请尝试一个简单的测试用例。 - jkerian

Answer 3

我认为jkerian的答案是最好的（假设只有一个列表），我想解释一下原因。

这是我的代码版本（作为一个函数）：

wordlist = ["a","arc","arcane","apple","car","carpenter","cat","zebra"];

def root_words(wordlist):
    result = []
    base = wordlist[0]
    for word in wordlist:
        if not word.startswith(base):
            result.append(base)
            base=word
    result.append(base)
    return result;

print root_words(wordlist);

只要单词列表已排序（如果需要，可以在函数中完成此操作），则这将在一次解析中获取结果。这是因为当您对列表进行排序时，由另一个列表中的单词组成的所有单词都将直接放在该根单词之后。例如，在您特定的列表中介于“arc”和“arcane”之间的任何东西，也将因为根单词“arc”的存在而被消除。

- BudgieInWA

---

如果有效单词列表很大，这个算法将非常慢。如果您真的想做这样的事情，应该构建某种树形结构来保存有效单词列表；“trie”是理想的选择。然后对于您想要查找的每个单词，您将遍历trie而不是迭代可能非常长的单词列表。在我的Ubuntu计算机上，/usr/share/dict/words超过98,000行，对于“cat”，您只关心以'c'开头的行。您会浪费时间处理'a'和'b'单词以及任何'd'或之后的单词；这就是为什么树更好的原因。 - steveha

@steveha：在某些方面，trie是解决这个问题的一个巧妙方法，因为你可以在加载它时对其进行修剪，并且你永远不会有一个单词以非叶子结尾。如果你需要在加载和设置完列表后重复访问它，那么这可能是最好的方法。另一方面，对于一个简单的任务来说，这是一种荒谬的代码开销，上面的版本在我的古老笔记本电脑上对那个单词文件只需不到十分之一秒。 - jkerian

我正在解决一个与Parseltongue实际想要解决的问题略有不同的问题。这个答案与被接受的答案非常相似，所以在我看来，你更好地理解了实际需求。我同意，对于仅从同一列表中查找以其他单词为前缀的单词，这比我的解决方案更好。 - steveha

@steveha 我对trie的了解不多，但考虑到你从一个单词列表开始，我想这个函数的运行效率已经无法更高了。 - BudgieInWA

我撤回我对这个程序会很慢的抱怨。当我写那篇评论时，我没有理解你的代码。非常抱歉。是的，我同意用Python构建trie树会比这个慢；只有在你想处理一个真正大的单独的有效单词列表时，才会尝试使用trie树。只要你只从同一列表中查找有效单词，这个方法就更好。顺便说一下，虽然我没有尝试过，但我认为你可以使用嵌套在其他字典中的字典，在Python中实现一个漂亮的trie树。 - steveha

Answer 4

你应该使用内置的lambda函数来完成这个任务。我认为它将使你的生活更加轻松。

words = ['rode', 'nick'] # this is the list of all the words that you have.
                         # I'm using 'rode' and 'nick' as they're in your example
listOfWordsToTry = ['rodeo', 'snicker']
def validate(w):
    for word in words:
        if w.startswith(word):
            return False
    return True

wordsThatDontStartWithValidEnglishWords = \
    filter(lambda x : validate(x), listOfWordsToTry)

这应该可以满足您的需求，除非我误解了您的问题。

希望这可以帮到您。

- inspectorG4dget

---

这个程序的运行时间复杂度为O(N^2)，在完整的字典上试一下，你就会发现它需要很长时间。此外，lambda表达式是多余的：'lambda x: validate(x)' 等同于 'validate'。 - user97370

@PaulHankin：你能否发布一份更好的代码版本？我很想看看我的代码如何可以变得更好。顺便说一句，我并不是在挑战你或者什么的，我真诚地想知道你的想法。 - inspectorG4dget

请查看jkerian提供的答案，它比这个答案快得多。 - user97370

批准的答案仅适用于一个列表。要查看与两个列表一起工作的更快替代方案，请参阅我的答案。在您的代码中，validate()使用for循环检查单词列表中的每个单词; 这真的很慢。在我的代码中，有效单词列表被转换为set以便检查可以是O(1)，然后检查目标单词的各种前缀。由于5个字母的单词有4个前缀要尝试，所以这应该比尝试使用.startswith()检查words列表中的每个单词要快得多。 - steveha

Answer 5

我写了一个答案，假设有两个列表，一个是需要修剪的列表，另一个是有效单词列表。在讨论中，我评论说也许 trie 解决方案会很好。

到底怎么回事，我就去写了它。

你可以在这里阅读有关 trie 的信息：

http://en.wikipedia.org/wiki/Trie

对于我的Python解决方案，我基本上使用了字典。一个键是一系列符号，每个符号都进入一个字典，其中包含另一个Trie实例作为数据。第二个字典存储“终端”符号，这些符号标记Trie中“单词”的结尾。在这个例子中，“单词”实际上是单词，但原则上单词可以是任何可哈希的Python对象序列。

维基百科的例子展示了一个键为字母的Trie，但可以不止一个字母；它们可以是多个字母的序列。为简单起见，我的代码仅使用一个符号作为键。

如果将单词“cat”和单词“catch”都添加到Trie中，则会有节点'c'、'a'和't'（以及“catch”中的第二个'c'）。在'a'的节点级别上，“终端”字典将包含't'（从而完成“cat”的编码），同样，在第二个'c'的更深层节点级别上，“终端”字典将包含'h'（完成“catch”）。因此，在“cat”之后添加“catch”只意味着一个额外的节点和一个终端字典中的一个条目。Trie结构使得存储和索引大量单词的效率非常高。

def _pad(n):
    return " " * n

class Trie(object):
    def __init__(self):
        self.t = {}  # dict mapping symbols to sub-tries
        self.w = {}  # dict listing terminal symbols at this level

    def add(self, word):
        if 0 == len(word):
            return
        cur = self
        for ch in word[:-1]: # add all symbols but terminal
            if ch not in cur.t:
                cur.t[ch] = Trie()
            cur = cur.t[ch]
        ch = word[-1]
        cur.w[ch] = True  # add terminal

    def prefix_match(self, word):
        if 0 == len(word):
            return False
        cur = self
        for ch in word[:-1]: # check all symbols but last one
            # If you check the last one, you are not checking a prefix,
            # you are checking whether the whole word is in the trie.
            if ch in cur.w:
                return True
            if ch not in cur.t:
                return False
            cur = cur.t[ch]  # walk down the trie to next level
        return False

    def debug_str(self, nest, s=None):
        "print trie in a convenient nested format"
        lst = []
        s_term = "".join(ch for ch in self.w)
        if 0 == nest:
            lst.append(object.__str__(self))
            lst.append("--top--: " + s_term)
        else:
            tup = (_pad(nest), s, s_term)
            lst.append("%s%s: %s" % tup)
        for ch, d in self.t.items():
            lst.append(d.debug_str(nest+1, ch))
        return "\n".join(lst)

    def __str__(self):
        return self.debug_str(0)



t = Trie()


# Build valid list from /usr/dict/share/words, which has every letter of
# the alphabet as words!  Only take 2-letter words and longer.

wfile = "/usr/share/dict/words"
for line in open(wfile):
    word = line.strip()
    if len(word) >= 2:
        t.add(word)

# add valid 1-letter English words
t.add("a")
t.add("I")



lst = ["ark", "booze", "kite", "live", "rodeo"]
# "ark" starts with "a"
# "booze" starts with "boo"
# "kite" starts with "kit"
# "live" is good: "l", "li", "liv" are not words
# "rodeo" starts with "rode"

newlst = [w for w in lst if not t.prefix_match(w)]

print(newlst)  # prints: ['live']

- steveha

Answer 6

我不想提供一个确切的解决方案，但我认为 Python 中有两个关键函数将在这里对你有很大帮助。

第一个是 jkerian 提到的：string.startswith() http://docs.python.org/library/stdtypes.html#str.startswith

第二个是：filter() http://docs.python.org/library/functions.html#filter

使用 filter，你可以编写一个条件函数来检查一个单词是否是另一个单词的基础，并在是的情况下返回 true。

对于列表中的每个单词，你需要遍历所有其他单词并使用 filter 评估条件，这可以返回正确的子集根词。

- dicato

---

我尝试在这个上面玩过滤器，你需要使用一个存储一些外部状态（即上面我的例子中的“base”）的过滤函数，结果看起来相当奇怪。 - jkerian

我承认我没有尝试编写代码。我认为可以使用列表中的另一个单词作为比较基础。不过，我认为Steveha说得很对。 - dicato

Answer 7

我只有一个列表 - 我想从中删除任何是另一个单词的前缀的单词。

这里有一个解决方案，应该在O（n log N）时间和O（M）空间内运行，其中M是返回列表的大小。运行时间由排序支配。

l = sorted(your_list)
removed_prefixes = [l[g] for g in range(0, len(l)-1) if not l[g+1].startswith(l[g])] + l[-1:]

• 如果列表已排序，则索引N处的项是前缀，如果它开始于索引N + 1处的项。

• 最后，它附加了原始排序列表的最后一项，因为根据定义它不是前缀。最后处理还允许我们在任意数量的索引上迭代而不会超出范围。

如果您在另一个列表中硬编码了禁止列表：

 banned = tuple(banned_prefixes]
 removed_prefixes = [ i for i in your_list if not i.startswith(banned)]

这取决于startswith接受元组的事实。它可能在接近N * M的情况下运行，其中N是列表中的元素数量，M是banned中的元素数量。Python可能会做一些聪明的事情来使它更快一些。如果您像OP一样想忽略大小写，则需要在某些地方使用.lower()调用。

- mateor