簡単で効率的♪ Pythonをつかって、Nグラム表をささっと作成する - Men talking over coffee with smoking Ark Royal.

前回に引き続き、Nグラムの話です。タイトルをクックパッドぽくしてみました。nグラム表を作って、そこからフレーズを取り出してみます。以下の文献を参考にしました。
長尾眞, 森信介, 1993, 「大規模日本語テキストのnグラム統計の作り方と語句の自動抽出」, 情報処理学会研究報告. 自然言語処理研究会報告 93(61), 1-8
1993年の文献だけあって、「処理能力が向上」、「64MBのメモリ」などなど懐かしさこみあげる文言が踊っています。それだけあって、いかに効率的にやるかという点に焦点があてられています。やはり、人の営為を研ぎ澄ませるのはいつでも制約条件ですね。
まずは下ごしらえです。L文字の文章資源を、i=1,2..文字目からL文字目までのL本の文字列にして、それを辞書順にソート、前後の文字列が何文字目まで同一かを調べます。

from collections import defaultdict

raw_string = お手元の文章資源（ここでは参院選期間中の候補者のツイートを使用）
# 改行コードと半角スペースをなきものにしちゃったけどいいのかな…。
raw_string = raw_string.replace(u"\n",u"").replace(u" ",u"")

# 下ごしらえ
# i文字目からlen(raw_string)文字目までのlen(raw_string)本の文字列をつくる
strings = []
for i in range(len(raw_string)):
	strings.append([raw_string[i:], i])

# 辞書順で並び替え（時間掛かる）
strings = sorted(strings, key=lambda x:x[0])

# i番目の文字列とi+1番目の文字列は、なん文字目まで一致するか？（最大MAX_N文字に設定）
MAX_N = 12
for i in range(len(strings)-1):
	count, _MAX_N = 0, MAX_N
	if len(strings[i][0]) < MAX_N or len(strings[i+1][0]) < MAX_N: # 文字列の長さがMAX_N未満の場合
		if len(strings[i][0]) < len(strings[i+1][0]):
			_MAX_N = len(strings[i][0])-2
		else:
			_MAX_N = len(strings[i+1][0])-2
	for j in range(_MAX_N):
		if strings[i][0][j] == strings[i+1][0][j]:
			count += 1
		else:
			break
	strings[i].append(count)
	#if len(strings[i]) < 3: strings[i].append(count)
	#else: strings[i][2] = count

nグラム表をつくる関数を定義して、試しに10グラム表を出力してみます。論文を読んでいて、ここが一番美しかった！

# nグラム表と、n文字列の左右の1文字辞書（あとで使う）の作成
l_str, r_str = defaultdict(list), defaultdict(list)
def make_ngram_table(raw, strs, n_gram, l_str=l_str, r_str=r_str):
	ngram_table = defaultdict(int)
	for i in range(len(strs)-1):
		if len(strs[i][0]) < n_gram: continue # 文字列の長さがn数未満の場合はスルー
		if strs[i][2] >= n_gram:
			ngram_table[strs[i][0][:n_gram]] += 1 # nグラム表（dict）を作成
			if strs[i][1] != 0: l_str[strs[i][0][:n_gram]].append(raw[strs[i][1]-1]) # 左の1文字辞書へ追記
			r_str[strs[i][0][:n_gram]].append(strs[i][0][n_gram]) # 右の1文字辞書へ追記
	return ngram_table

# 試しに10グラム表を作ってみる
ngram_table = make_ngram_table(raw_string, strings, 10)
# 頻度30回以上に絞り込んで、頻度が高い順にソート
ngram_table_30 = sorted([n for n in  ngram_table.items() if n[1] >= 30], key=lambda x:x[1], reverse=True) 
# 10文字列|頻度 となるように出力
for nstring in ngram_table_30:
	print u"%s|%s" % (nstring[0], nstring[1])
# tp://t.co/|252
# ttp://t.co|252
# http://t.c|252
# (BOT)#石田まさ|124
# OT)#石田まさひろ|124
# BOT)#石田まさひ|124
# す(BOT)#石田ま|85
# 。http://t.|79
# ます(BOT)#石田|66
# ブログを更新しました|45
# ログを更新しました。|45
# ...http://|42
# .http://t.|42
# ..http://t|42
# 』http://t.|40
# す。http://t|37
# グを更新しました。『|36
# ます。http://|31

続いて、n文字列の左右の1文字のレパートリが多い場合に、そのn文字列がひとつの塊である可能性が高いという仮説のもと、先ほど作ったl_str, r_strを利用して、塊の可能性が高いものを出力してみます。

# n文字列の左右の1文字のレパートリが多いとき、単語の可能性が高いと仮定し、それを出力する
def extract_words(ngram_table, freq_thres, lr_thres, l_str=l_str, r_str=r_str):
	for w in ngram_table.items():
		if w[1] >= freq_thres:
			lr_count = len(list(set(l_str[w[0]]))) + len(list(set(r_str[w[0]])))
			if lr_count >= lr_thres:
				print u"%s|%s|%s" % (w[0], w[1], lr_count)



# In [329]: extract_words(make_ngram_table(raw_string, strings, 10), 10, 10)
# Out [329]:
# 単語（候補）|頻度|左右の文字の種類数
# ありがとうございます|24|20
# (BOT)#石田まさ|124|10
# ブログを更新しました|45|30
# tp://t.co/|252|61
# ...http://|42|16
# 』http://t.|40|23
# OT)#石田まさひろ|124|50
# 次の@YouTube|12|12
# りがとうございます。|14|12
# 。http://t.|79|15
# 新しい写真をFace|17|13
# グを更新しました。『|36|15
# http://t.c|252|35
# せていただきました。|12|12

このあと論文は、塊をうまく取り出す方法を幾つか提案しているのですが、それはまた後日ということで今日はここまで。