反向索引Inverted Index – Map Reduce Program

Inverted Index （反向索引）是搜索引擎需要做的一件经常性工作。在Google提出Map Reduce分布式编程框架中，这是一件很容易完成的事情。下面就是一个python写的示例。

Map:

#!/usr/bin/python
#
#  InvertedIndex mapper in Python
#  Author: Zeng, Xi
#  SID:    1010105140
#  Email:  zengxi@cuhk.edu.hk

import sys

def main(argv):
  line = sys.stdin.readline().lower()
  words = line.split()
  try:
    while line:
      for word in words[1:]:
        print line.split()[0] + "\t" + word
      line = sys.stdin.readline().lower()
      words = line.split()
  except "end of file":
    return None
if __name__ == "__main__":
  main(sys.argv)

Reduce:

#!/usr/bin/python
#
#  InvertedIndex reducer in Python
#  Author: Zeng, Xi
#  SID:    1010105140
#  Email:  zengxi@cuhk.edu.hk

import sys
index_list = {}

## collect (key,val) pairs from sort phase
for line in sys.stdin:
    try:
        word, index = line.strip().split("\t", 2)

        if index not in index_list:
            index_list[index] = word
        else:
            if word not in index_list[index]:
                index_list[index] = index_list[index] + " " + word

    except ValueError, err:
        sys.stderr.write("Value ERROR: %(err)s\n%(data)s\n" % {"err": str(err), "data": line})

## emit results
for word, index in index_list.items():
    print " ".join([word, index])