我应该使用哪种数据结构来计算单词以及它们出现的文档？

我正在浏览文档列表，计算每个单词在全球出现的时间以及存储在哪些文档中。因此，我需要一个或多或少是一个字典的数据结构，其中关键是字和值是一个计数和文档ID列表。我应该使用哪种数据结构来计算单词以及它们出现的文档？

基本上就是这样，我猜？：

{ 
'word1': [num1, [id1, id2, id3]], 
'word2': [num2, [id2, id4, id5]], 
'word3': [num3, [id1, id4, id6, id]] 
}

有没有这样的事情？

我需要的是：

新行必须创建如果我推这个词已经不存在，
的num场必须易于增加，
的清单id s很容易用新文档更新id

我应该使用字典吗？或者是其他东西？我可以看到如何用list和['word', num, [id1, id2, id3]]来处理每个单词，但是我觉得代码对于那些容易的事情来说是相当复杂的，所以我想知道是否有其他的数据结构，我不知道它们是哪一个更适合我的用途？

来源

2017-02-25 François M.

什么是主要用例？例如你想知道有多少文件有特定的单词吗？或者给定文档中有多少个独特的单词？这会对你应该关键的东西以及你应该看重的东西产生影响。因此，首先考虑如何使用您的结构。你需要随机访问还是顺序访问？ – rism

我想显示30个最常用的单词，以便我可以了解最常提及的内容（文档实际上是推文）。一旦找到了，我就会摆脱其他所有的话。这些ID必须存储，因为我想要一个给定单词似乎很容易找到的推文。我最感兴趣的是确保它速度合理（它的脚本可以每分钟运行多次）。谢谢 –

我建议哈希与Chaining概念。请仔细阅读文档here 最坏情况的复杂度是O（n）。

来源

2017-02-26 17:19:23 Ram

from collection import defaultdict 
import re 

s = "the task is to find the frequency of words in multiple docs" 
ids = { 'the': [1,2,4], 'frequency' : [2,3] , 'of' : [1,2,3,4,5], 'words': [8] } 
d = defaultdict(int) 

#build the histogram of words: 
for w in re.findall('\w+',s): 
    d[w] += 1 

#new dictionary of frequency and ids: 
new_ids = defaultdict(list) 

for k in d: 
    new_ids[k].append(d[k]) 
for k in ids: 
    new_ids[k].append(ids[k])

输出：

>>>new_ids 
defaultdict(list, 
      {'docs': [1], 
      'find': [1], 
      'frequency': [1, [2, 3]], 
      'in': [1], 
      'is': [1], 
      'multiple': [1], 
      'of': [1, [1, 2, 3, 4, 5]], 
      'task': [1], 
      'the': [2, [1, 2, 4]], 
      'to': [1], 
      'words': [1, [8]]})

换句话说，一种方法是合并默认字典利用他们的特点优势，轻松地创建数和追加名单值。

来源

2017-02-26 19:16:09 gregory

我应该使用哪种数据结构来计算单词以及它们出现的文档？

回答

相关问题