メタキャラクタとORの扱い
import sys, re, csv
path_dict, path_data = sys.argv[1], sys.argv[2]
encoding = 'cp932'
col_keyword, col_data = 1, 3
reader = csv.reader(file(path_dict, "rb"))
keyword = [unicode(row[col_keyword], encoding) for row in reader]
pattern = re.compile(u"(" + u"|".join(keyword) + u")")
for row in csv.reader(file(path_data, "rb")):
print pattern.sub(r"(\1)", unicode(row[col_data], encoding)).encode(encoding)sys.argv の長さをチェックしていないとか、csv モジュールは ascii の範囲外での動作が保証されていないとか、encoding は locale.getpreferredencoding() でとったほうがいいんじゃないかとか、いろいろ細かいことはあるんだけど、正規表現の生成がまずすぎる。10人以上もブックマークしておいて、だれも気づかんかなぁ。どっちかというと誰もツッコミを入れない点にびっくりだ。
さて、一応問題の解説。
pattern = re.compile(u"(" + u"|".join(keyword) + "u"))ってやっているけど、これじゃ keyword*1 に "." とか "?" とかのメタキャラクタを含む文字がきたらひどいことになる。単純文字列マッチングなら
pattern = re.compile(u"(" + u"|".join(re.escape(k) for k in keyword) + u")")とするべき*2。
あと、
試しに1500語の辞書を使って2000行くらいのcsvファイルのキーワードを強調してみたところ、あっというまでしたですよ。正規表現なんだからそりゃそうだよな。。。
とのことだが、OR でつないだ正規表現は多分 NFA*3 になって、単純に各パターンを順番に見ていく羽目になる。つまりマッチング毎にキーワード数に比例した計算コストがかかっているのであって、あっという間というのは単に計算量が非常に小さいだけのことだ。
まぁ、こんなことをここで言うまでも無く、そういう話はGoogleの工藤さんがだいぶ前に言及しているので、そっちを参照。(ってもうほとんど書いてしまっているけど)
で、実際どのくらいスケールしないかは良くわからないので、先日抽出したはてなキーワードを使って試してみた。(ちなみに、UnicodeError を無視しているのは Unicode に変換できない文字を含むキーワードがあるから。EUC-JPとしてもおかしいのもある)。
#!/usr/bin/env python
import sys, re, codecs, locale
DOC_ENCODING = locale.getpreferredencoding()
KEYWORD_ENCODING = "euc-jp"
if len(sys.argv) != 4:
print >>sys.stderr, "usage: %s keywordlist.extracted n doc" % sys.argv[0]
sys.exit(0)
keyword_path = sys.argv[1]
n = int(sys.argv[2])
doc_path = sys.argv[3]
keywords = []
decoder = codecs.getdecoder(KEYWORD_ENCODING)
for line in open(keyword_path, 'r'):
try:
keywords.append(decoder(line)[0].rstrip())
except UnicodeError:
pass
keywords = keywords[:n]
pat = re.compile(u'(' + '|'.join(re.escape(k) for k in keywords) + u')')
for line in (x.rstrip() for x in codecs.open(doc_path, 'r', DOC_ENCODING)):
print pat.sub(r'(\1)', line)どうなるかといえば入力テキストにもよるのだが、大体 n = 10000 も入れれば
RuntimeError: internal error in regular expression engine
とか言われる。
