以下のコードを使ったら、Jaccard/Simpson係数を簡単で計算できる。 キーワードX,キーワードYの一緒に出る文を定時間で計算できる。 メモリは生コーパスより小さいはずです。 #!/usr/bin/python# -*- coding: utf8 -*-""" Use Inverted Index. 最初には、Mecabを用いて、コーパスを単語分割をする。 また、このコーパスの単語をインデクスする。 入力したキーワードのインデクス配列を用いて、一緒に出る文を抽出する。 以下のコードには、自分自身がバイナリサーチンを用いて、検索する手法を実装する。 一方、Pythonの集合（set)を使って、実装する。 どちらの方が早いか？とわからない。 自分自身の手法は、計算量がlog(n)である。（ｎはインデクスの文の数） setを使ったら、Pythonのメソードのスピードに依存する。"""import codecsfrom bisect import bisect_leftdef binarysearch(x, Z, left, right): """ある値ｘが集合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 ansclass 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"""#使用例 test = Index()test.build("test.txt")test.prints(test.intersection(u"thể", u"thao"))""" |
|
|