プログラム

evacでは、アグリゲータとしての挙動をJSONファイルで定義する様にしていて、その内容の解釈にnconfを利用しているのだけど、YAMLもフォーマットとしてサポートさせたいので試してみたのでその際のメモ。

nconf自体はパーサーを外部に指定できる仕組みがあるので以下の様に組み合わせるとYAMLをJSONを扱うのと同様に解釈できた。

YAMLのパーサーには以下を利用した。

GitHub

 

11 Users

87 Pockets

nodeca/js-yaml

https://github.com/nodeca/js-yaml

JavaScript YAML parser and dumper. Very fast. Contribute to nodeca/js-yaml development by creating an account on GitHub.

YAMLファイルを適当に準備。

in:
staticWord:
text: "test word."
filter:
through:
out:
stdout:

これをnconfと組み合わせてYAMLを設定ファイルとして解釈させるには以下の様にすればよい。

var config = require('nconf');
var yaml = require('js-yaml');
config.use('file',{
file:'/home/hideack/foo.yaml',
format:{
parse: yaml.safeLoad,
stringify: yaml.safeDump
}
});
config.load(function (err, conf) {
console.log(conf);  //{ in: {staticWord: {text:'test word.'}},filter: {through: null},out: {stdout: null}}
});

JSONで設定ファイルだとちょっと...といったケースでYAMLを使いたいときに試してみると良さそう。

Google analyticsのレポートの値を取得する方法をあれこれ調べていたのでひと通りまとめてみました。

npmのパッケージとしては、sfarthin/ga-analytics · GitHubというのがあるので、これを利用するとあっさりレポートの値は取れるのですが、Google analyticsのAPIを利用するため、以下の手順が必要です。

1. Google Developer Consoleでサービスアカウントを準備する
2. Google analyticsにユーザを追加する
3. Developer consoleで取得した.p12証明書をpem形式に変換する

上の手続きをひと通り行うとGoogle analyticsのレポートの値を取得できる様になります。

Google Developer Consoleでサービスアカウントを準備する

Google Developer Console にログインしてまずは新規プロジェクトを作成します。

次にGoogle analyticsのAPIを選びます。APIの利用ON/OFFをONに切り替えます。

次に左側のメニューにある「APIと認証」の「認証情報」を選択して、新しいクライアントIDの作成を行います。

上記の手続きが完了すると以下の画面が表示されるので

• ①クライアントID
• ②メールアドレス
• ③自動的にダウンロードされる.p12(PKCS12)形式の証明書
• ④パスワード*1

を控えます。

Google analyticsにユーザを追加する

Google developer console 上からAPIを利用できる状態にしても、Google analyticsにユーザを追加しないと実際にGoogle analyticsのパラメータを取得することはできないので、Google analytics上からユーザを追加します。

Google analyticsの「アナリティクス設定」を開いて

上記の箇所に先のDeveloper consoleで追加されたメールアドレス(〜@developer.gserviceaccount.com) を入力してユーザとして追加します。

続けて実際に取得したいGoogle analyticsのレポートを識別するためにビューIDという値があるので

を開くと、以下の箇所にビューIDがあるのでこれを控えます。

• ⑤取得したいレポートのビューID

Developer consoleで取得した.p12証明書をpem形式に変換する

OpenSSLのコマンドを利用して証明書の形式を変換します。パスワードの部分には④で表示されていたものを入力します。

openssl pkcs12 -in key.p12 -nocerts -passin pass:***** -nodes -out key.pem

ここで出力された証明書ファイルのパスを控えておきます。

• ⑥PEM形式に変換された証明書ファイル

ga-analyticsを利用してGoogle analyticsの値を取得

ここまでで準備は完了したので実際にsfarthin/ga-analytics · GitHubを利用してレポートの値を取得してみます。

試しに恥ずかしながらこのブログのページビューを...。

$ npm install ga-analytics --save

として ga-analytics のインストールを行った上で

var gaAnalytics = require("ga-analytics");
var CLIENT_ID = '****.apps.googleusercontent.com';   // ①
var SERVICE_ACCOUNT_EMAIL = '****@developer.gserviceaccount.com';   // ②
var SERVICE_ACCOUNT_KEY_FILE = '/home/hideack/key.pem';   // ⑥
gaAnalytics({
metrics: "ga:pageviews",
clientId: CLIENT_ID,
serviceEmail: SERVICE_ACCOUNT_EMAIL,
key: SERVICE_ACCOUNT_KEY_FILE,
ids: "ga:*****"   // ⑤
}, function(err, res) {
if(err) throw err;
console.log(res.totalsForAllResults);
});

これで出力してみると。

{ 'ga:pageviews': '1973' }

といった形。実際にAnalyticsでレポートの値を確認すると同じ値が取れることがわかります。

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏を読んでみたところから続く検索してみるシリーズ。

前回作成した検索の処理をもって転置インデックスを作成するところから、それを利用した検索までの一連の流れができたので次は実際にいくらか大きめのデータを入れて比較してみることにします。

いままで作成したnode.js + redisベースの実装はremieraという名前を付けてgithubに置いています。一応、コマンドライン引数でインデックス対象のファイルを指定したり検索ができる様にしています。

インデックス対象の文章はテキストファイルで与えられるものとして、1行が1文章として扱われる様になっています。

今回は大きめのデータのサンプルということで本に倣ってWikipediaのタイトル2,654,075件の文字列をサンプルとして投入します。

$ wc -l ~/tmp/wikipedia/jawiki-latest-all-titles
2654075
$ time remiera -i ~/tmp/wikipedia/jawiki-latest-all-titles
remiera -i ~/tmp/wikipedia/jawiki-latest-all-titles  1011.13s user 229.40s system 99% cpu 20:44.89 total

redis自体もコード自体も何もチューニングをしていない状態で20分程度要しました。

では、まずは比較として先ほどインデックス対象としたファイルを素朴にgrepで検索してみます。

$ time grep -n コロスケ ~/tmp/wikipedia/jawiki-latest-all-titles
969851:奈良崎コロスケ
2180964:コロスケ
2180965:コロスケ123123
2180966:コロスケ准将
2180967:コロスケ＠1億円
grep -n コロスケ ~/tmp/wikipedia/jawiki-latest-all-titles  1.46s user 0.01s system 99% cpu 1.479 total

grepでは1.4秒強程度要しています。

次は転置インデックスを使って検索を行ってみます。

$ time remiera -s コロスケ
[ { no: '969850', pos: 3 },
{ no: '2180964', pos: 0 },
{ no: '2180965', pos: 0 },
{ no: '2180963', pos: 0 },
{ no: '2180966', pos: 0 } ]
remiera -s コロスケ  0.09s user 0.03s system 74% cpu 0.156 total

現状の実装では文書番号と出現位置で返るだけですが、0.09秒程度*1で結果が得られています。

インデックスする際に文書番号は0から始めているため 行番号 = 文書番号-1 となっています。これが先ほどのgrepした結果と検索結果とが一致していることもこの結果から確認できます。

一旦まとめ

ここまでやったこととして、検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏を読みながら以下のことを試してみました。

• JavaScriptで文字列を与えられた場合にn-gramすること
• ひとまずは永続化することを考えずに配列として転置インデックスを作ってみること
• 転置インデックスを利用して検索を行ってみること
• 転置インデックスをredisに保管して永続化させ、更にそれを利用して検索をした上でgrepと結果を比較

ここまでで、本でまとめられている第4章までの内容をnode.js + redisで実装をしながら進めることができました。

更に次のステップとして更に大きな文書を投入しての計測や5章以降で触れられているパラメータの調整等々も試していきたいと思いますがこれはまた次に...。

あわせて読みたい

• JavaScriptでn-gram
• JavaScriptで転置インデックスを作る
• 転置インデックスを利用して検索してみる
• 転置インデックスをredisで永続化する
• redisで作成した転置インデックスで検索してみる

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏を読んでみたところから続く検索してみるシリーズ。

前回のエントリで転置インデックスをredisに作ってみるところまではできたので、次は実際にこれを利用して検索を行ってみます。

前回はbi-gramで文章を分割し、分割語を転置インデックスとして以下の形で格納しています。それぞれ、

• (A)分割語が属す文書番号を管理するセット型の集合
• (B)特定の文書に特定の分割語の出現位置を管理する文字列型の集合

これを利用して検索を行うために以下の手順で処理を進めます

(1) 与えられた分割語をbi-gramで分割する

ここでは検索語として「コロスケ」を考えます。bi-gramなので、コロ, ロス, スケ に分割。

(2) 分割語が全て含まれる文書を特定する

(A)のセット型の集合に対してSINTERコマンドを発行して各分割語が全て含まれる文書番号を抽出します。

127.0.0.1:6379> SINTER コロ ロス スケ
1) "9"
...

(3) (2)で得られた文書中の分割語の出現位置を確認

(2)で得られた分割語が全て含まれる文書、それぞれに対して分割語毎にその出現位置を確認し、その語が連続しているかを確認します。
例えば、コロ, ロス, スケの分割語が文書番号9で含まれていることが(2)でわかっていれば、その出現位置が連続で出現するかを確認します。

127.0.0.1:6379> GET コロ-9
"3"
127.0.0.1:6379> GET ロス-9
"4"
127.0.0.1:6379> GET スケ-9
"5"

この場合は文書番号9の3文字目から分割語が連続で出現していることから、「コロスケ」という単語が文書番号9の3文字目に含まれていることがわかります。

上記までの内容をまとめると以下の様な概要図になります。

実際にnode.jsで書いてみた例は以下の形になりました。

'use strict';
var ngram = require('../util/ngram'),
  _ = require('underscore'),
  redis = require("redis"),
  client = redis.createClient();
var search = {};
search.basic = function (query, n, callback) {
  var grams = ngram(query, n),
    results = [];
  client.sinter(grams, function (err, documentNumbers) {
    if (documentNumbers.length == 0) {
      client.end();
      callback(null, results);
    }
    documentNumbers.forEach(function (docNo) {
      var positions = grams.map(function (gram) {
        return gram + "-" + docNo
      });
      client.mget(positions, function (err, res) {
        var charPositions = res.map(function (pos) {
          return pos.split(",").filter(function (e) {
            return e !== ""
          }).map(function (e) {
            return parseInt(e)
          });
        });
        for (var i = 1; i < charPositions.length; i++) {
          charPositions[i] = charPositions[i].map(function (v) {
            return v - i
          });
        }
        charPositions.reduce(function (a, b) {
          return _.intersection(a, b)
        }).forEach(function (position) {
          results.push({
            no: docNo,
            pos: position
          });
        });
        if (docNo == documentNumbers[documentNumbers.length - 1]) {
          client.end();
          callback(null, results);
        }
      });
    });
  });
}
module.exports = search;

これで先日作ったredisの転置インデックスを利用して検索が行えます。

現状だと作ってみただけになるので実際に少し大きめの文書例を入れてみて測定してみるのはまた次に。

あわせて読みたい

• JavaScriptでn-gram
• JavaScriptで転置インデックスを作る
• 転置インデックスを利用して検索してみる
• 転置インデックスをredisで永続化する

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏を読んでみたところから続く検索してみるシリーズ。

過去に転置インデックスを利用して検索してみるといったエントリを書いてJavaScriptのハッシュで構成された転置インデックスを利用して検索を試みていたが、このままだと永続化できないのでredisを用いて永続化してみた。

node.jsでredisを扱う場合はnode_redisを利用するのがよさそうなのでnpm経由でインストール。

$ npm install redis --save

使い方はそのままの形なので先のgithubのREADME.mdを参照すれば特に支障なく利用できるかと思う。
基本的にはredisのコマンドがそのままメソッドとして実装されているので、見た感じそのままである。

今回は転置インデックスをredisに格納するにあたって、以下の方法で実装してみた。ここはひとまずとりあえず。

• 該当の単語が出現する文書番号を格納
  • redisのセット型
  • keyを単語とし、その集合として文書番号を格納
• 該当の単語が特定の文書中に出現する位置を格納
  • redisの文字列型
  • keyで単語と文書番号を表現し、その値に出現位置をカンマ区切りで格納

としてみた。

こうすることで、検索語が与えられた場合、その検索後を転置インデックスに対応する形で単語分割し、その単語が全て含められる文書を絞り込んだ上で、更に転置インデックスを参照して該当する単語が含まれる位置を探すことで検索が実現できそう。

'use strict';
var ngram = require('../util/ngram'),
  redis = require("redis"),
  client = redis.createClient(),
  fs = require('fs'),
  byline = require('byline');
var index = {};
var indexing = function (no, str) {
  ngram(str, 2).forEach(function (gram, pos, array) {
    client.sadd(gram, no);
    client.append(gram + "-" + no, pos + ",");
  });
}
index.redis = function (path) {
  client.flushdb(function (err, didSucceed) {
    var stream = byline(fs.createReadStream(path, {
      encoding: 'utf8'
    }));
    var i = 0;
    stream.on('data', function (line) {
      indexing(i, line);
      i++;
    });
    stream.on('finish', function () {
      client.end();
    });
  });
}
module.exports = index;

こうすることでredisに転置インデックスを格納することができた。

では、ここまでで転置インデックスの永続化はできたので、実際にこれを利用して検索するのはまた次に。

併せて読みたい

• JavaScriptでn-gram
• JavaScriptで転置インデックスを作る
• 転置インデックスを利用して検索してみる

Command reference – Redis というredisのコマンドがまとめられたページがあるのだけど、各コマンドの詳細が書かれているページにEXAMPLESという項目があって、コマンド例がまとめられているのだけど、この欄実際に自分で試しにコマンドを入力できることに今日気づいた。

Webページ上で実際にコマンドを入力して挙動を試せたりできるので便利。

肝心なところ知らないこと多い...。

console.time と console.timeEnd で挟んだ部分の時間を計測できる。引数にはラベル名を指定できてそのラベルで対応した範囲の時間が計測される。

// Indexing
console.time("indexing");
var stream = byline(fs.createReadStream('/tmp/foo.txt', { encoding: 'utf8' }));
var i=0;
stream.on('data', function(line) {
indexing(i, line);
i++;
});
stream.on('finish', function(){
console.timeEnd("indexing");
// Search
console.time("search");
var res = search("コロスケ", 2);
console.timeEnd("search");
// Results
var resultOut = _.template("文書番号=<%=no %> : 文字位置=<%=pos %>")
_.each(res, function(v){
console.log(resultOut(v));
});
});

こうすると、以下の様な形で処理時間を計測できる。

$ node test.js
indexing: 5ms
search: 1ms
文書番号=0 : 文字位置=15
文書番号=2 : 文字位置=8
文書番号=2 : 文字位置=35

素朴に便利だったのでメモエントリ。

$ npm install byline --save

npmからインストールして以下の様な形で使える。

var byline = require('byline');
var fs = require('fs');
var stream = byline(fs.createReadStream('/tmp/foo.txt', { encoding: 'utf8' }));
stream.on('data', function(line) {
console.log(line);
});
stream.on('finish', function(){
console.log("ファイル読み終わり");
});

redisの型の認識が何気だったので改めて整理してみた。自分の頭の整理用に図も描いたりしたのでせっかくなので掲載。

文字列型

一番シンプルな形。

127.0.0.1:6379> SET key1 value1
OK
127.0.0.1:6379> SET key2 value2
OK
127.0.0.1:6379> GET key1
"value1"
127.0.0.1:6379> GET key2
"value2"
127.0.0.1:6379> MGET key1 key2
1) "value1"
2) "value2"

expireを設定することもできるのでキャッシュとして用いる場合はこれを利用する。

127.0.0.1:6379> SETEX cache1 5 cache-val1
OK
127.0.0.1:6379> GET cache1
"cache-val1"
(5秒経過後)
127.0.0.1:6379> GET cache1
(nil)

リスト型

双方向な線形リストで構成。要素の追加の方向は基本先頭か末尾。

これを利用することでスタックやキューを構成することができる。

スタック(LIFO)

LPUSH , LPOP を利用するとスタックを構成できる。LPOPで取り出されている要素を確認すると一番最後に格納した要素から取り出せている。

127.0.0.1:6379> LPUSH list1 1
(integer) 1
127.0.0.1:6379> LPUSH list1 2
(integer) 2
127.0.0.1:6379> LPUSH list1 3
(integer) 3
127.0.0.1:6379> LPOP list1
"3"
127.0.0.1:6379> LPOP list1
"2"
127.0.0.1:6379> LPOP list1
"1"
127.0.0.1:6379> LPOP list1
(nil)

キュー(FIFO)

RPUSH, LPOPを利用するとキューを構成できる。LPOPから取り出されている要素を確認すると最初に格納した要素が取り出せている。

127.0.0.1:6379> RPUSH list1 1
(integer) 1
127.0.0.1:6379> RPUSH list1 2
(integer) 2
127.0.0.1:6379> RPUSH list1 3
(integer) 3
127.0.0.1:6379> LPOP list1
"1"
127.0.0.1:6379> LPOP list1
"2"
127.0.0.1:6379> LPOP list1
"3"
127.0.0.1:6379> LPOP list1
(nil)

リスト操作

リストに対して部分操作ができる。例えば先頭から2要素を抽出するときは LRANGE コマンドを使う。

127.0.0.1:6379> RPUSH list1 1
(integer) 1
127.0.0.1:6379> RPUSH list1 2
(integer) 2
127.0.0.1:6379> RPUSH list1 3
(integer) 3
127.0.0.1:6379> RPUSH list1 4
(integer) 4
127.0.0.1:6379> LRANGE list1 0 1
1) "1"
2) "2"

セット型

値の重複を許さない文字列型の集合で且つ集合同士の操作ができる。例えば SINTER コマンドを使うと積集合を得ることができる。

下の例だと集合 set1 と set2 に対して SINTER コマンドを発行すると両方の集合に対して属している 3 が取り出せている。

127.0.0.1:6379> SADD set1 1
(integer) 1
127.0.0.1:6379> SADD set1 2
(integer) 1
127.0.0.1:6379> SADD set1 3
(integer) 1
127.0.0.1:6379> SADD set2 3
(integer) 1
127.0.0.1:6379> SADD set2 4
(integer) 1
127.0.0.1:6379> SADD set2 5
(integer) 1
127.0.0.1:6379> SINTER set1 set2
1) "3"

ソート済みセット型

セット型で更にそれぞれの要素はスコアを持ち、そのスコアにもとづいてソートされた形で格納される。

127.0.0.1:6379> ZADD sortset 5 A
(integer) 1
127.0.0.1:6379> ZADD sortset 10 B
(integer) 1
127.0.0.1:6379> ZADD sortset 8 C
(integer) 1
127.0.0.1:6379> zrangebyscore sortset -inf +inf
1) "A"
2) "C"
3) "B"

ハッシュ型

こちらはそのまま。集合内の要素は全てキーと値で一意となるハッシュとして管理される。

127.0.0.1:6379> HSET hash1 foo 10
(integer) 1
127.0.0.1:6379> HSET hash1 bar 20
(integer) 1
127.0.0.1:6379> HSET hash1 hoge 30
(integer) 1
127.0.0.1:6379> HGET hash1 foo
"10"
127.0.0.1:6379> HGET hash1 bar
"20"
127.0.0.1:6379> HGET hash1 hoge
"30"
127.0.0.1:6379> HGET hash1 hoge2
(nil)

n-gram及び、転置インデックス を作ってみたので実際に検索してみます。

var _ = require('underscore');
// (snip)
var search = function (query, n) {
  var grams = ngram(query, n),
    firstPostingList = invertedIndex[grams[0]],
    results = [];
  var searchProcess = function (positions, key) {
    positions.forEach(function (pos) {
      if (query.length <= n) {
        results.push({
          no: key,
          pos: pos
        });
      } else {
        for (var i = 1; i < grams.length; i++) {
          postingList = invertedIndex[grams[i]];
          if (postingList[key]) {
            var targetList = postingList[key];
            if (_.contains(targetList, pos + i)) {
              if (i == grams.length - 1) {
                results.push({
                  no: key,
                  pos: pos
                });
              }
            } else {
              continue;
            }
          }
        }
      }
    });
  };
  _.each(firstPostingList, searchProcess);
  return results;
}
// Indexing
var text = ["本日は晴天なり。いい天気なり。コロスケなり。", "コロばない様にスケートボートに乗ります", "今日は黒豆を煮てコロスケとコロコロコミックとコロッケを買いに行きます。コロスケ〜。"];
for (var i = 0; i < text.length; i++) {
  indexing(i, text[i]);
}
// Search
var res = search("コロスケ", 2);
// Results
var resultOut = _.template("文書番号=<%=no %> : 文字位置=<%=pos %>")
_.each(res, function (v) {
  console.log(resultOut(v));
});

これを実行してみると、「コロスケ」で検索した結果が出力されます。

文書番号=0 : 文字位置=15
文書番号=2 : 文字位置=8
文書番号=2 : 文字位置=35

インデックスに投入した文書とくらべて、検索した単語が含まれる文書が抽出できていて且つ、出現位置も正しく特定できています。

やっていることとしては、

• 検索語をn-Gramで分割する (上の例なら "コロスケ" → "コロ", "ロス", "スケ")
• 分割された最初の分割語を持つ文書とその出現位置を転置インデックスから得る
• 得られた一つ目の文書について
  • 2番目の分割語がその文書に含まれているか確認する
  • 含まれていればその語の出現位置が1番目の検索語の次にあるかを確認する
  • 以下、検索語を分割した数だけ繰り返す
• 以下、分割された最初の分割語が含まれる文書数繰り返す

といった手順。

ひとまず素朴な検索ができたけれど、このままだと転置インデックスが永続化されないですね。

では、次に何かしらのストレージを利用して永続化させることをやってみます。

一連のn-gram, 転置インデックス, 検索の話は以下の本を読んでいたら実際に手を動かして確認したくなったので試してみたのでした。

具体例も多く、読んでいても面白いですが実際に手を動かすともっと面白いのでお勧め。

今回の話は第4章「検索しよう」の内容を読みながら進めてみました。

d.hatena.ne.jp

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏 | 山田 浩之, 末永 匡...

http://d.hatena.ne.jp/asin/4774167533/hatena-blog-22

Amazonで山田 浩之, 末永 匡の検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏。アマゾンならポイント還元本が多数。山田 浩之, 末永 匡作品ほか、お急ぎ便対象商品は当日お届けも可能。また検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏もアマゾン配送商品なら通常配送無料。

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏 著者 : 山田浩之 技術評論社 発売日 : 2014-09-25 ブクログでレビューを見る»