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

问题描述 投票:-1回答:2

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

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

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

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

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

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

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

欢迎所有建议。谢谢。

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

python algorithm data-structures prefix trie
2个回答
0
投票
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]只是颠倒顺序


0
投票

如果我们知道前缀的长度(例如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)
© www.soinside.com 2019 - 2024. All rights reserved.