y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

『言語処理 100 本ノック』に PHP で挑む (問題 05)

『言語処理 100 本ノック』に PHP で挑戦しています。今回は問題 05 を解きます。
www.cl.ecei.tohoku.ac.jp

05. n-gram

与えられたシーケンス(文字列やリストなど)からn-gramを作る関数を作成せよ.この関数を用い,"I am an NLPer"という文から単語bi-gram,文字bi-gramを得よ.

N-gram とは、シーケンスの中で連続して出現する n 個の要素のことです。n = 1, 2, 3 の場合をそれぞれユニグラム (unigram), バイグラム (bigram), トライグラム (trigram) と言います。N-gram については『言語処理のための機械学習入門』の 2.2 節に説明があります。
言語処理のための機械学習入門 (自然言語処理シリーズ) : 高村 大也, 奥村 学 : 本 : Amazon

問題文に対する単語 n-gram は、それぞれ次のようになります*1。専門用語の意味を理解してしまえば、プログラミングとしては特に難しい処理ではなさそうです。

N-gram 要素
ユニグラム [ "I", "am", "an", "NLPer" ]
バイグラム [ "I am", "am an", "an NLPer" ]
トライグラム [ "I am an", "am an NLPer" ]

N-gram の利用例としては Google Ngram Viewer が分かりやすいです。単語列を入力すると、Google Books における出現頻度の推移をグラフに表示してくれます。たとえば "natural language processing" と入力すると、1960 年代から 1990 年頃にかけて出現頻度が急増していく様子が分かります。
Google Ngram Viewer

文字 n-gram は、単語ではなく文字単位で n-gram を構成したものです。こちらは、全文検索用のインデックスなどに使われます。文字 N-gram をキーとして、その n-gram の出現位置の集合を値とする連想配列を作っておけば、入力された検索文字列がドキュメントのどこに出現しているかを高速に列挙できるというわけです。こちらは『高速文字列解析の世界』の第 7 章で、n-gram 以外の手法も合わせて詳しく説明されています。
高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学) : 岡野原 大輔 : 本 : Amazon

さて、前置きが長くなりましたが、n-gram を作成するプログラムを書いていきます。PHP では文字列と配列を共通に扱うことはできないので、まずは配列から n-gram を作成する関数を以下のように実装しました。

<?php
function ngram($sequence, $n)
{
    $ngram = [];
    $iend = count($sequence) - $n + 1;
    for ($i = 0; $i < $iend; ++$i) {
        $ngram[] = array_slice($sequence, $i, $n);
    }
    return $ngram;
}

以下のようなテストプログラムで動作を確認します。1 から 5 の整数を要素とする配列から bigram を作成できます。

<?php
require_once __DIR__ . '/ngram.php';

$input = range(1, 5);
$ngram = ngram($input, 2);
echo json_encode($ngram), "\n"; // 実行結果: [[1,2],[2,3],[3,4],[4,5]]

次に、単語 n-gram を作る関数を実装します。上で作成した ngram 関数を利用する形にしました。入力文を explode 関数で分割して単語の配列に変換した後、ngram 関数を呼び出します。ngram 関数の戻り値の型は「文字列の配列の配列」になっています。今回は、各要素を改めて連結して、文字列の配列として戻すようにしました。どのようなデータ構造とするかは、本来は n-gram の用途に合わせて判断する必要があります*2

<?php
require_once __DIR__ . '/ngram.php';

function word_ngram($sentence, $n)
{
    $sequence = explode(' ', $sentence);
    $ngram = ngram($sequence, $n);

    $result = [];
    foreach ($ngram as $words) {
        $result[] = implode(' ', $words);
    }
    return $result;
}

以下のように、問題の入力文に対して結果を確認します。

<?php
require_once __DIR__ . '/word_ngram.php';

$sentence = 'I am an NLPer';
$wordBigram = word_ngram($sentence, 2);
echo json_encode($wordBigram), "\n"; // 実行結果: ["I am","am an","an NLPer"]

文字 n-gram を作る関数も同様に実装します。explode ではなく str_split を使って文字ごとに配列に分割します*3

<?php
require_once __DIR__ . '/ngram.php';

function character_ngram($sentence, $n)
{
    $sequence = str_split($sentence);
    $ngram = ngram($sequence, $n);

    $result = array_map('implode', $ngram);
    return $result;
}

こちらも以下のようにして結果を確認します。

<?php
require_once __DIR__ . '/character_ngram.php';

$sentence = 'I am an NLPer';
$characterBigram = character_ngram($sentence, 2);
echo json_encode($characterBigram), "\n"; // 実行結果: ["I "," a","am","m "," a","an","n "," N","NL","LP","Pe","er"]

ところで、今回はせっかく ngram 関数を作ったので、これを利用して単語 n-gram や文字 n-gram を作成する処理を実装しましたが、実際のところ各々 substr 関数で文字列処理として実装する方が無駄のない処理になりそうです。単語 n-gram について比較してみます。次の実装では、まず入力文字列から空白文字の位置を $pos に列挙し、それから、その情報を利用して substr 関数で n-gram を作成していきます。

<?php
function word_ngram_fast($sentence, $n)
{
    $pos = [-1];
    $curr = 0;
    while (($curr = strpos($sentence, ' ', $curr)) !== false) {
        $pos[] = $curr++;
    }
    $pos[] = strlen($sentence);

    $ngram = [];
    for ($i = 0; $i < count($pos) - $n; ++$i) {
        $start = $pos[$i] + 1;
        $end = $pos[$i + $n] - 1;
        $ngram[] = substr($sentence, $start, $end - $start + 1);
    }

    return $ngram;
}

二つの実装の処理時間を比較してみます。巨大な文字列で試さないと違いがわからないので、『言語処理 100 本ノック』の第 8 章で利用するデータから、次のようにしてテストデータを作成しました。おおよそ 20 万単語、1 MB 規模のデータになります。

$ wget http://www.cs.cornell.edu/people/pabo/movie-review-data/rt-polaritydata.tar.gz
$ tar zxf rt-polaritydata.tar.gz
$ cat rt-polaritydata/rt-polarity.* | cut -f2- -d' ' | tr -d '\n' >largedata.txt
$ wc largedata.txt
      0  213304 1171716 largedata.txt

テストプログラムは以下のとおりです。標準入力から文字列を読み込み、それぞれの実装の処理時間を計測します。

<?php
require_once __DIR__ . '/word_ngram.php';
require_once __DIR__ . '/word_ngram_fast.php';

$sentence = file_get_contents('php://stdin');

$slow_begin = microtime(true);
$slow_bigram = word_ngram($sentence, 2);
$slow_end = microtime(true);
echo ($slow_end - $slow_begin), "\n";

$fast_begin = microtime(true);
$fast_bigram = word_ngram_fast($sentence, 2);
$fast_end = microtime(true);
echo ($fast_end - $fast_begin), "\n";

実行時間は次のとおりでした。配列に変換して処理する方式では 48 秒もかかっているのに対して、文字列操作として実装した方では 0.1 秒未満で処理できています。このように、実装方法によって実行時間に大きな差があることを確認できました。

$ cat largedata.txt | php word_ngram_fast_test.php
48.17666888237
0.079248905181885

*1:教科書にも記載があるように、文頭や文末を表す記号を追加して考えることもありますが、今回はそうしていません。

*2:N-gram を作成して結果を確認するというのが今回の用途なので、表示したときに見やすいデータ構造を選択したという言い方もできます。

*3:str_split 関数は、何文字ずつ分割するかを第二引数で指定できます。この引数を省略すると一文字ずつになります。