如何查找和排序字符串列表中的所有前缀？

Question

我有一个字符串列表，我想找到流行的前缀。前缀是特殊的，因为它们在输入列表中以字符串形式出现。

我在这里找到了类似的问题，但答案旨在找到the one最常见的前缀：Find *most* common prefix of strings - a better way?

虽然我的问题很相似，但不同之处在于我需要找到所有流行的前缀。或者也许要简单地说一下，将前缀从最常见到最不重要。

作为示例，请考虑以下字符串列表：在，印度，印度，印度国旗，公牛，恶霸，废话

前缀排名：在-4次印度-3次公牛-3次...等等。请注意-输入列表中有in，bull和india。

以下无效前缀：印bu布尔...因为它们不在输入列表中。

为建模解决方案，我应该查看哪种数据结构？我倾向于在每个节点上使用带有计数器的“ trie”，该计数器跟踪在创建trie期间该节点被触摸了多少次。

欢迎所有建议。谢谢。

ps.s。 -我喜欢python，也希望有人能发布一个简短的摘要来帮助我入门。

Answer 1

words = [ "in", "india", "indian", "indian", "flag", "bull", "bully", "bullshit"]

Result = sorted([ (sum([ w.startswith(prefix) for w in words ]) , prefix )  for prefix in words])[::-1]

它以每个词作为前缀，并检查有多少其他词以它开头，然后对结果进行排序。 [[::-1]只是颠倒顺序

Answer 2

如果我们知道前缀的长度（例如3）

from nltk import FreqDist
suffixDist=FreqDist()
for word in vocabulary:
    suffixDist[word[-3:]] +=1
commonSuffix=[suffix for (suffix,count) in suffixDist.most_common(150) ]
print(commonSuffix)