転置インデクス(逆索引)の実装

以下のコードを使ったら、Jaccard/Simpson係数を簡単で計算できる。
キーワードX,キーワードYの一緒に出る文を定時間で計算できる。
メモリは生コーパスより小さいはずです。

#!/usr/bin/python
# -*- coding: utf8 -*-
"""
    Use Inverted Index.
    最初には、Mecabを用いて、コーパスを単語分割をする。
    また、このコーパスの単語をインデクスする。
    入力したキーワードのインデクス配列を用いて、一緒に出る文を抽出する。
    以下のコードには、自分自身がバイナリサーチンを用いて、検索する手法を実装する。
    一方、Pythonの集合(set)を使って、実装する。
    どちらの方が早いか?とわからない。
    自分自身の手法は、計算量がlog(n)である。(nはインデクスの文の数)
    setを使ったら、Pythonのメソードのスピードに依存する。

"""
import codecs
from bisect import bisect_left

def binarysearch(x, Z, left, right):
    """ある値xが集合Zの[left, right]の範囲の中に、どこにある。"""
    pos = bisect_left(Z, x, left, right)
    return (pos if (pos < right or (pos == right and Z[pos] >= x))
                else right + 1)

def common(Zx, Zy):
    """
    二分検索を用いて、共通部分集合を列挙する
 Zx, Zyは集合(リスト)である。
  Pythonのset型と比べると、どっちの方が早いか?わかない。
    ただ、計算量はlog(n)である。
    """
    x_left = 0
    x_right = len(Zx) - 1
    y_left = 0
    y_right = len(Zy) - 1
    ans = set([])
    while x_left <= x_right and y_left <= y_right :
        if x_left <= x_right : 
            pos = binarysearch(Zx[x_left], Zy, y_left, y_right)
            if (pos <= y_right and Zy[pos] == Zx[x_left]):
                ans.add(Zy[pos])
                pos += 1
            x_left += 1
            y_left = pos
        if y_left <= y_right :
            pos = binarysearch(Zy[y_left], Zx, x_left, x_right)
            if (pos <= x_right and Zx[pos] == Zy[y_left]):
                ans.add(Zx[pos])
                pos += 1
            y_left += 1
            x_left = pos
    return ans

class Index:
    """
    転置インデクス(逆索引)を管理するクラス。
    buildメソードは、パラメータのコーパスに対して転置インデクスを作成する。
    union : 和集合
    intersection : 共通集合
    difference : 差集合
    symmetric_difference : 対称的差集合
    prints(セット)
    """
    def __init__(self):
        self.index = {}
        self.index_number = 0
        self.corpus = []
        return
       
    def build(self, corpus_path):
        fi = codecs.open(corpus_path, "r", "utf8")
        for line in fi :
            self.index_number += 1
            self.corpus.append(line)
            bow = line.split()
            for word in bow :
                if self.index.has_key(word) :
                    self.index[word].add(self.index_number - 1)
                else :
                    self.index[word] = set([self.index_number - 1])
        return
              
    def union(self, X, Y):
        if not self.index.has_key(X) :
            print "No such keyword", X
            return []
        if not self.index.has_key(Y) :
            print "No such keyword", Y
            return []
        return (self.index[X] | self.index[Y])
   
    def intersection(self, X, Y):
        if not self.index.has_key(X) :
            print "No such keyword", X
            return []
        if not self.index.has_key(Y) :
            print "No such keyword", Y
            return []
        return (self.index[X] & self.index[Y])
   
    def difference(self, X, Y):
        if not self.index.has_key(X) :
            print "No such keyword", X
            return []
        if not self.index.has_key(Y) :
            print "No such keyword", Y
            return []
        return (self.index[X] - self.index[Y])

    def symmetric_difference(self, X, Y):
        if not self.index.has_key(X) :
            print "No such keyword", X
            return []
        if not self.index.has_key(Y) :
            print "No such keyword", Y
            return []
        return (self.index[X] ^ self.index[Y])
 
    def prints(self, ans):
        for i in ans :
            print i, self.corpus[i]
        return

    def length(self, X):
        if self.index.has_key(X) : return len(self.index[X])
        else : return 0

"""#使用例   
test = Index()
test.build("test.txt")
test.prints(test.intersection(u"thể", u"thao"))
"""


Comments