Part of Nobumi Iyanaga's website. n-iyanag@nifty.com. 8/27/08.

logo picture

MacJPerl script for n-gram analysis...

n-gram とは……

　最近、近藤泰弘さんという方の「コンピュータによる文学語学研究にできること――古典語の「内省」を求めて」という文献を読んで見て、n-gram の概略や仕組み、おもしろさが少しだけ分かってきました。近藤さんの web site は
http://klab.ri.aoyama.ac.jp/
にあり、
http://klab.ri.aoyama.ac.jp/kondo.html の
http://klab.ri.aoyama.ac.jp/public/paper/20010602.pdf
から上の表題の研究発表要旨をダウンすることができます。

　n-gram については、google で検索すると「約 7,130 件」のヒットがあり、コンピュータの世界では非常に重要な話題なのだろうと思いますが、なにしろあまりに大量のリソースがあって、どこから見たらいいか分からない状態です。

　それで、ここでは近藤さんの論文にしたがって、ぼくが理解した範囲で書いてみます。近藤さんによると（肝心なところを少し長く引用させていただきます）：

N-gram とは、シャノン[7]によって始められた情報学の基礎理論
であり、例えば、特定の言語から、文字の並びを１ 文字（グラ
ム）、２グラム、３ グラムと取り出して、その種類や出現確率を
計算して、その言語の特質を記述するものである。例えば、日本
語ならば、「ことが」という３ 文字列は「ことがら（事柄）」「こ
とが（事が）」「みことが（尊が）」のようにいくらでも存在す
るが、「ぜへぐ」という３ 文字列はまず存在しない、というよう
なことである。日本語の用言述部がこの種の分析に適しているこ
とは、水谷[14]に指摘がある。〔参考文献については、もとの論文に当たってください−引用者〕
今回は、『古今集』と『源氏物語』とをN-gram モデルで比較する
ことにする。例えば、次の太線部分が共通する文字列なのである
が［ここでは  <b>xxx</b>  で表示］、このようなものを人間の認識
力だけで見つけることは実際には極めて困難である（実は、この文
字列一致は、古注・諸注釈に指摘がない）。

逢ふまでのかたみに契る中の緒のしらべはことに変わざらなむ「こ
の音たがはぬさきにかならずあひみむ」と頼めたまふめり
（源氏・明石・二・二六七）
今ははや恋ひ死なましをあひ見むと頼めしことぞ命なりける
（古今・恋二・六一三・清原深養父）

そこで、各文献の本文をすべて平仮名にして、そこから１ 文
字から20文字程度を、全体から順にすべて取り出して、文字列の
異なりリストを作成し、相互にそれをつきあわせる。
あ
あひ
あひみ
あひみむ
あひみむと
あひみむとた
あひみむとたの
あひみむとたのめ
あひみむとたのめた
あひみむとたのめたま
あひみむとたのめたまふ
あひみむとたのめたまふめ
あひみむとたのめたまふめり
あふ
あふま
あふまで
（源氏物語）
あ
あひ
あひみ
あひみむ
あひみむと
あひみむとた
あひみむとたの
あひみむとたのめ
あひみむとたのめし
あひみむとたのめしこ
あひみむとたのめしこと
あひみむとたのめしことぞ
あひみむとたのめしことぞい
あひみむとたのめしことぞいの
あひみむとたのめしことぞいのち
あひみむとたのめしことぞいのちな
（古今集）
......

というふうに書かれています。つまり、n- gram モデルの基本は、あるテクストがあって、それの、たとえば「5 gram」の文字列を抽出する、ということは、テクストのはじめから１文字ずつずらしていって、５文字ずつの文字列を抽出すること、と考えられます。
　「その種類や出現確率を計算する」ということは、種類については抽出された文字列をソートすることで最低限のことが分かりますし、出現確率は、同じ文字列が何回出現するか、ということを計算する必要があるわけでしょう。

　ここで、例として、いまの「「その種類や...」から「わけでしょう」までのテクストを対象に、3 gram の文字列を抽出するとすると（句読点はこの際、削除します）：


頻度    文字列  グラム数
＿＿＿＿＿＿＿＿＿＿＿＿＿
1   ートす  3
1   「その  3
1   」とい  3
1   あるわ  3
1   いては  3
1   かとい  3
1   かりま  3
1   がある  3
1   が何回  3
1   が分か  3
1   けでし  3
1   ことが  3
1   ことで  3
1   ことは  3
1   ことを  3
1   された  3
1   しょう  3
1   し出現  3
1   じ文字  3
1   すし出  3
1   する」  3
1   するか  3
1   するこ  3
1   する必  3
1   その種  3
1   た文字  3
1   ついて  3
1   ては抽  3
1   でしょ  3
1   で最低  3
1   とが分  3
1   とで最  3
1   とは種  3
1   とを計  3
1   につい  3
1   のこと  3
1   の種類  3
1   は種類  3
1   は抽出  3
1   は同じ  3
1   ますし  3
1   や出現  3
1   ります  3
1   る」と  3
1   るかと  3
1   ること  3
1   るわけ  3
1   る必要  3
1   れた文  3
1   わけで  3
1   をソー  3
1   ソート  3
1   トする  3
1   何回出  3
1   回出現  3
1   確率は  3
1   確率を  3
1   現する  3
1   限のこ  3
1   最低限  3
1   字列が  3
1   字列を  3
1   種類に  3
1   種類や  3
1   出され  3
1   出現す  3
1   抽出さ  3
1   低限の  3
1   同じ文  3
1   必要が  3
1   分かり  3
1   要があ  3
1   率は同  3
1   率を計  3
1   類につ  3
1   類や出  3
1   列が何  3
1   列をソ  3
2   いうこ  3
2   うこと  3
2   という  3
2   を計算  3
2   計算す  3
2   現確率  3
2   算する  3
2   出現確  3
2   文字列  3
という結果を得ることができます。

　普通は、n-gram 分析は統計を取ることを目的に使われるので、頻度が１のものは採取の対象にならないそうですが、それだとこの場合おもしろくないので、全部を取り上げることにしました。

なお、n-gram に関しては、「漢字文献情報処理研究」（Journal of Japan Association for East Asian Text Processing）第２号（２００１年１０月・好文出版）の「特集２：N-gram が開く世界」に最新の情報が載せられています（http://www.jaet.gr.jp/jj/2.html 参照）。この研究会については http://www.jaet.gr.jp/ も御参照ください。

n-gram のプログラム

　n-gram のプログラム（http://www.jaist.ac.jp/~shigeru/ngram-ja.html に置いてあります）は、Unix 用のもので、Windows では Cygwin などを使って疑似 Unix 環境を作りだし、その中で実行する、とのことです。これは、少ないメモリで無制限の大きなファイルを扱える、とのことで、非常にすぐれたもののようですが、日本語としては JIS と EUC しか扱えない、また、統計用なので、頻度２以上の文字列しか抽出しない、という制限がある、とのことです。

それ以外にも、「極悪トリッポン」さんの Perl のスクリプト（http://www1.u-netsurf.ne.jp/~dune//N_2Dgram.html?）、また、師茂樹さんの UTF-8 のファイルを対象にした Perl のスクリプトがあります（http://www.ya.sakura.ne.jp/~moro/resources/ngram/morogram.html）。これらは、大変すぐれたものですが、残念ながら、OS X 以前の Mac では直接は使えない（あるいは使いにくい）もののようです。

　そこで、OS X 以前のMac でも使える 簡易 n-gram のプログラムなら、いろいろ制限はあっても、いくらかは自作できるのではないか、という気がしてきました。いまのところ考えたのは、以下のようなものです。


#!perl
# obaka_ngram.pl by N. Iyanaga 2001/07/15
# corrected by gokuaku-san 2001/10/22
# Usage:
# Argument 1: Input file's full path
# Argument 2, 3...  Optional arguments: Full paths of files to 
#                   compare
# Argument before last argument (Argument 2 if there is no 
#          optional argument): Folder path of the output file
# Last argument (Argument 3 if there is no optional 
#      argument): number of gram(s)
# Character encoding: Shift-JIS
# Must be JPerl


#@ARGV = ("Macintosh HD:myFolder:0246.sjis", "Macintosh HD:myFolder:n-gram:", 3);


if ($#ARGV > 2) {
	$infile = shift;
	$ngram = pop;
	$outfolder = pop;
	foreach $file (@ARGV) {
		push (@comparefiles, $file);
	}
}
else {
	$infile = shift;
	$ngram = pop;
	$outfolder = pop;
}


my $dlm = $^O eq 'MacOS' ? ':'  :
	$^O =~ /Win32/ ? '\' :
	'/';


$infilefn = (split(/Q$dlm/, $infile))[-1];
$outfilepath = $outfolder . $infilefn . "." . $ngram . "-g.log";


undef $/;


open (IN, $infile) || die ("Couldn't open input file $infile: $!");


$originaltext = ;


close (IN);


$text = $originaltext;


$text =~ s/[tnrf -~]+|[。　，、‖：【】]+//g;
$originaltext2 = $text;


while ($text) {
	$keyword = substr ($text, 0, ($ngram * 2));
	last if length ($keyword) < ($ngram * 2);
	if ($seen{$keyword}++) {
		$text = substr ($text, 2);
		next;
	}
	$temp = $originaltext2;
	$ct = $temp =~ s/$keyword//g;
	$ct = &padwithzeros ($ct, 4);
	push (@res, "$ct\t$keyword\t$ngram\t($infilefn: $ct)");
	$text = substr ($text, 2);
}


$originaltext = "";
$text = "";
$originaltext2 = "";


if (@comparefiles != ()) {
	foreach $filetocompare (@comparefiles) {
		@res = &comparewith ($filetocompare);
	}
}


open (OUT, ">$outfilepath") || die ("Couldn't open output file $outfilepath: $!");
foreach $resLine (sort @res) {
#	print OUT "$resLine\n" unless $seen{$resLine}++ ;
	print OUT "$resLine\n";
}


close (OUT);


sub padwithzeros {
	my $num = shift;
	my $pad = shift;


	while (length ($num) < $pad) \{
		$num = "0" . $num;
	}
	return ($num);
}


sub comparewith {
	my $file = shift;
	my $dlm = $^O eq 'MacOS' ? ':'  :
		$^O =~ /Win32/ ? '\' :
		'/';


	my $fn = split(/Q$dlm/, $infile))[-1];
	open (IN, $file) || die ("Couldn't open input file $file: $!");
	my $originaltext = ;
	close (IN);


	$originaltext =~ s/[tnrf -~]+|[。　，、‖：【】]+//g;


	my ($resline, $ct, $keyword, $gram, $ct2, $thisct, $i);
	$i = 0;
	foreach $resline (@res) {
		($ct, $keyword, $gram, $ct2) = split (/t/, $resline);
		$ct2 = substr ($ct2, 0, -1); # remove closing parenthesis
		$temp = $originaltext;
		$thisct = $temp =~ s/$keyword//g;
		$thisct = &padwithzeros ($thisct, 4);
		$ct += $thisct;
		$ct = &padwithzeros ($ct, 4);
		$ct2 = $ct2 . ", " . $fn . ": " . $thisct . ")";
		$res[$i] = "$ct\t$keyword\t$gram\t$ct2";
		$i++;
	}


	return (@res);
}
__END__

　これは DOS/Windows の JPerl でも動くはずだと思います。入力・出力ファイルの文字コードは SJIS です。入力ファイルの中の 1 byte 文字や「。　，、‖：【】」はすべて削除されます（&Mxxxxxx; 形式の外字表記も削除されます）。

このページ、最初２００１年１０月２１日にアップしたのですが、翌日、早速、極悪さんがスクリプトを訂正してくださいました。ありがとうございました！

引数１に基礎となる主要インプットファイルのフルパス、引数２以下、オプショナルで、比較の対象となるインプットファイルのフルパス、終りから２番目の引数で出力ファイルが作られるフォルダのパス、最後の引数で gram 数（半角数字）を指定する仕様になっています。

引数２以下はオプショナルですから、

を入れれば、一つだけのファイルの結果が得られます。
出力は、たとえば引数１のインプットファイルの名が「0246.sjis」で gram 数が 3 の場合：
「0246.sjis.3-g.log」というファイルができて、 


頻度　　文字列　gram　ファイル名：ファイル内の頻度
0001    阿引哩  3   (0246.sjis: 0001)
0001    阿仁二  3   (0246.sjis: 0001)
0001    阿慕伽  3   (0246.sjis: 0001)
0001    阿哩夜  3   (0246.sjis: 0001)
0001    阿拏迦  3   (0246.sjis: 0001)
0001    哀纒欒  3   (0246.sjis: 0001)
.....
となります。

それに「0245.sjis」というファイルを比較した結果（

を入れた場合）は、 


0001    阿引哩野二合五三滿多    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等散曼陀羅花曼    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等成菩薩道恒河    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等得生天上無量    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等聞佛所説諸災    10  (0246.sjis: 0001, 0245.sjis: 0000)
......

というふうに表示されます。引数１に入れた入力ファイルが、つねに「基準ファイル」になります。
（これは 10 grams ですから「0246.sjis.10-g.log」というファイルに出力されます）

　Mac の場合は、MacJPerl を使い〔MacPerl は不可）、スクリプトの最初の方の


#@ARGV = ("Macintosh HD:myFolder:0246.sjis", "Macintosh HD:myFolder:n-gram:", 3);

と書いた行のコメント記号（#）を削除し、 


("Macintosh HD:myFolder:0246.sjis", "Macintosh HD:myFolder:n-gram:", 3)
の部分に該当する引数を書き入れて実行すれば、動くはずです。ただ、これは MacPerl の普通のインターフェースとあまりにかけ離れているので、もう少し普通の使い方でできるように工夫したものも作りました。

　残念ながら、スピードとメモリの点で、相当に問題があると思います。とくに、メモリに関しては、全文を一度に読み込み、全文字列をメモリ内で処理するので、ぼくのところでは、MacJPerl に 10 MB ほどのメモリを割り当てたうえで、60 KB 程度の文書で試した程度です。Windows の JPerl のメモリ処理はより優秀なので、たぶんそれほどは気にしなくてもいいかもしれませんが。

ダウンロードと使い方

　ダウンロードには、[Macro error: ]をクリックしてください（フォルダ名「ngram_pls」）。
　内容は です。

　上の２つは、JPerl を用います。２番目のものは MacJPerl が必要です（MacPerl は使えません）。それと、ng_grep.applescript は、Tex-Edit Plus と Nisus Writer （v. 5.x 以上）を使います。そのほかに、mgrep OSAX と Text X OSAX も必要です（Text X は "QuoEdit" (version 0.641 以降) というすぐれたエディタに付属しています。これは http://hyperarchive.lcs.mit.edu/HyperArchive/Abstracts/text/HyperArchive.html で "QuoEdit" を探せばダウンロードできます。また、OS 8.5 以前の OS を使っておられる場合は、Jon's Commands も必要になるかもしれません。これは http://www.seanet.com/~jonpugh/ からダウンロードできます）。

　最初の ngram_commandline.pl は一応、DOS/Windows の JPerl 用に書きました。内容は、上に挙げたスクリプトと同じで、

jperl ngram_commandline.pl inputfile outputfolder gram_number
または
jperl ngram_commandline.pl inputfile1 inputfile2... outputfolder gram_number
という形式で実行できるはずです（じつは、自分では試していません……）。

　これを Mac で使う場合は、まず、なんらかのエディタでこのファイルを開き、行頭の「lf」（ASCII 10）を全部削除してセーブしたうえで、MacJPerl で開き、冒頭の

@ARGV = ("xxxx", "yyyy", "zzzz");
に
inputfile, outputfolder, gram_number
または
inputfile1, inputfile2,... outputfolder, gram_number
を手動で書き入れて実行します。

　２番目の ngram_droplet.pl は MacJPerl のドロップレットで、MacJPerl 的なインターフェースを使っています。inputfile（または inputfile1, inputfile2...）には、このドロップレットの上にドラッグ＆ドロップしたファイルが自動的にセットされます。その後、gram_number を入力するダイアローグと、outputfolder を指定するファイルダイアローグがでます。なお、outputfolder は、すでに存在するフォルダーしか選べないので、その点に注意してください。また、メモリ不足で終了した場合は、MacJPerl のメモリを増やし、さらにこのドロップレットのメモリも増やしてみることをお勧めします。

　３番目の AppleScript のスクリプト ng_grep.applescript は「おまけ」です。たとえば 


0001    阿引哩野二合五三滿多    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等散曼陀羅花曼    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等成菩薩道恒河    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等得生天上無量    10  (0246.sjis: 0001, 0245.sjis: 0000)
0001    阿修羅等聞佛所説諸災    10  (0246.sjis: 0001, 0245.sjis: 0000)
......
というアウトプットがあったとき、もとのファイルのどういうコンテクストで「阿修羅等得生天上無量」という文字列が見つかるのかを調べたい、というような場合に、このスクリプトを使うことができます。なお、このスクリプトはCBETA のファイル（を Shift-JIS に変換したもの）にしか使えないので、その点を御了承ください。

　まず、必要なソフト（Tex-Edit Plus, Nisus Writer, mgrep OSAX, Text X OSAX および場合によっては Jon's Command）の中でもっていないものがあればダウンロードしてください。OSAX 類（mgrep OSAX, Text X OSAX, Jon's Command）は Scripting Additions フォルダに入れます。
　ng_grep.applescript は、Tex-Edit Plus の Scripts （日本語版ならば「スクリプト」）フォルダに入れます。

この状態で、

本来ならば、Nisus Writer だけで実現したい機能ですが、Nisus Writer の AppleScript のサポートが十分でないため、残念ながら、インターフェースとして Tex-Edit Plus を利用した次第です。

８年後になりましたが、OS X 用の n-gram のスクリプトをつけ足します（これ以前のスクリプトは、みな不完全で使い物になりません！）。たいへん原始的なものですが、まったくないよりはましでしょう。中身は、Perl のスクリプトを組み入れた AppleScript のドロップレットです。一字一字処理します（単語では処理しませんので注意してください）。

操作は簡単です。一つ、または複数の UTF-8 のテクストファイルをこのドロップレットの上に載せます（複数のファイルを処理する場合は、同じフォルダーのものしか載せられませんので注意してください。ファイル名は、".txt" で終わっている必要があります。基本となるファイルは、ファイル名のソート順で一番若いファイルです）。「何グラムで処理しますか」という意味のダイアローグがでるので、適当な数を入れます。デフォルトでは３になっています。処理が終わると、自動的に終了します。非常に時間がかかりますので、あらかじめ「心の準備」をしておいてください（300 KB 程度のファイルを 400 KB 程度のファイルと一緒に処理した場合、ぼくのマシンで３〜４分かかります。gram 数 5 で、約 2.4 MB のファイルができます）。同じフォルダー内に、基本となるファイルの(ファイル名 - extension) + "_" + gram 数 + "-g.txt" というファイルができます（同じ名前のファイルがある場合は上書きします）。UTF-8 のテクストファイルです。

１行目に
"ngram result: " + 基本となるファイルの(パス＋ファイル名 - extension) + "for " gram 数 + "gram(s)"
または（比較の対象となるファイルがある場合は）
"ngram result: " + 基本となるファイルの(パス＋ファイル名 - extension) + "compared with " + 比較の対象となるファイルの(ファイル名 - extension) + "for " gram 数 + "gram(s)"
という表示がおかれ、２行目以下に結果が表示されます。

ファイルの比較は、あくまでも基本となるファイルに対する比較である、という点に御留意ください。

ドロップレットは、次のリンク (85K to download)リンクからダウンロードできます。これと同じ ReadMe と、ドロップレットに組み入れてある perl のスクリプトを同梱してあります。

なにしろ非常に不完全なものです。できるなら morogram が OS X で動くようになればずっといいはずです。

　バグレポート、改良点のサジェスチョンなど、フィードバックをお待ちしています。

Go to Research tools Home Page
Go to NI Home Page

Mail to Nobumi Iyanaga

frontierlogo picture

This page was last built with Frontier on a Macintosh on Wed, Aug 27, 2008 at 11:06:03 AM. Thanks for checking it out! Nobumi Iyanaga