trie树统计词频输出前n个
时间: 2023-12-14 21:39:27 浏览: 43
Trie树可以用于统计字符串出现的次数,可以先将所有字符串插入Trie树中,每个节点记录当前路径代表的字符串出现的次数。然后可以使用深度优先搜索遍历整棵树,找到出现最多的前n个字符串。
以下是Python代码示例:
```python
class TrieNode:
def __init__(self):
self.children = {}
self.freq = 0
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.freq += 1
def dfs(self, node, path, freqs):
if node.freq > 0:
freqs.append((path, node.freq))
children = node.children.items()
children = sorted(children, key=lambda x: x[1].freq, reverse=True)
for char, child in children:
self.dfs(child, path + char, freqs)
def top_n_freq(self, n):
freqs = []
self.dfs(self.root, '', freqs)
freqs = sorted(freqs, key=lambda x: x[1], reverse=True)
return freqs[:n]
# 示例用法
trie = Trie()
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'banana']
for word in words:
trie.insert(word)
top_freqs = trie.top_n_freq(2)
print(top_freqs) # output: [('banana', 3), ('apple', 2)]
```
在上面的示例中,我们首先将所有字符串插入Trie树中,然后使用深度优先搜索遍历整棵树,找到出现次数最多的前n个字符串。最后输出结果即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)