熟练使用 Python 字典处理索引统计

索引引擎

的基本工作原理便是倒排索引, 即将一个文档所包含的文字反过来映射至文档; 这方面算法并没有太多花样可言, 为了增加效率, 索引数据尽可往内存里面搬。

举个基本思路的简单例子，现在有如下文档（分词已经完成）和其中包含的关键词：

doc_a: [word_w, word_x, word_y]
doc_b: [word_x, word_z]
doc_c: [word_y]

将其变换为

word_w -> [doc_a]
word_x -> [doc_a, doc_b]
word_y -> [doc_a, doc_c]
word_z -> [doc_b]

写成 Python 代码, 便是

doc_a = {'id': 'a', 'words': ['word_w', 'word_x', 'word_y']} 
doc_b = {'id': 'b', 'words': ['word_x', 'word_z']} 
doc_c = {'id': 'c', 'words': ['word_y']} 
  
docs = [doc_a, doc_b, doc_c] 
indices = dict() 
  
for doc in docs: 
  for word in doc['words']: 
    if word not in indices: 
      indices[word] = [] 
    indices[word].append(doc['id']) 
  
print indices

但是这里有个小技巧，就是判断当前单词是否已经在索引字典的分支中

if word not in indices: 
  indices[word] = []

可以用dict的setdefault(key, default=None)接口代替。这个接口的作用是，如果key在字典里，可以说取出对应的值；否则，创建一个新键并将默认对应值设置为 default 。但是从设计的角度来看，我不明白为什么 default 的默认值为 None。这似乎没有多大意义。如果真的要使用这个接口，一般会带上自己的默认值，如下

for doc in docs: 
  for word in doc['words']: 
    indices. setdefault(word, []) .append(doc['id'])

这样就省掉分支了, 代码看起来少很多.

但是也有一些setdefault不好用的情况：默认值构造复杂的时候，或者默认值有副作用的时候，后面会讲到的情况；前两种情况一言以蔽之，即 setdefault 不适合 default 需要惰性求值的场景。换句话说，为了适应这个要求， setdefault 可以设计为

def setdefault(self, key, default_factory): 
  if key not in self: 
    self[key] = default_factory() 
  return self[key]

倘若真如此, 那么上面的代码应改成

for doc in docs: 
  for word in doc['words']: 
    indices.setdefault(word, list ).append(doc['id'])

不过实际上有其它替代方案, 这个最后会提到.

如果上面只是一个可以预见但实际上可能根本不会遇到的 API 缺陷，那么下面这个就有点打脸了。

考虑现在需要词频统计，即一个词在文章中出现的次数。如果直接用dict写的话，大致就是

def word_count(words): 
  count = dict() 
  for word in words: 
    count.setdefault(word, 0) += 1
  return count 
  
print word_count(['hiiragi', 'kagami', 'hiiragi', 'tukasa', 'yosimizu', 'kagami'])

当你兴致勃勃地运行上面的代码时，代码会以闪电般的速度在你的鼻尖抛出异常——因为在 Python 中 += 运算符左侧出现的 count.setdefault(word, 0) 不是左值.好吧，让我们现在开始讨论 C 狗屎类型系统。

因为 Python 将默认文字常量 {} 等同于 dict()，所以 dict 是灵丹妙药的想法是不可取的； Python 有很多数据结构，要解决统计问题，理想的解决方案是类 collections.defaultdict。下面的代码一定一看就懂

from collections import defaultdict 
  
doc_a = {'id': 'a', 'words': ['word_w', 'word_x', 'word_y']} 
doc_b = {'id': 'b', 'words': ['word_x', 'word_z']} 
doc_c = {'id': 'c', 'words': ['word_y']} 
  
docs = [doc_a, doc_b, doc_c] 
indices = defaultdict(list) 
  
for doc in docs: 
  for word in doc['words']: 
    indices[word].append(doc['id']) 
  
print indices 
  
def word_count(words): 
  count = defaultdict(int) 
  for word in words: 
    count[word] += 1
  return count 
  
print word_count(['hiiragi', 'kagami', 'hiiragi', 'tukasa', 'yosimizu', 'kagami'])

完满解决了之前遇到的那些破事.

此外 collections 里还有个 Counter , 可以粗略认为它是 defaultdict(int) 的扩展.