2015年 1月 の投稿一覧

blessed-contribというCUIベースのダッシュボードを作れるnpmパッケージを触ってみた。以前紹介したdashingはブラウザで閲覧できましたが、これはターミナル上で確認できます。素敵。

百聞は一見にしかずということで下のGIFアニメ参照。

tmuxで区切った画面の右側にblassed-contribで作ったダッシュボードを表示させています。

ダッシュボードの中身は

• 左側に利用しているMacのCPU温度の折れ線グラフ(2秒毎に更新)
• 右下にCPU温度の値(1秒毎に更新)
• 右上にredisのログ(ログ更新毎)

が表示されています。redis-cliからflushdbするとダッシュボードの右上にredisのログが流れていくのや、左上でredisへ書き込みを行うプログラムを走らせるとCPU温度のグラフが右肩上がりしていきます。

具体的にダッシュボードを作るには以下の様なスクリプトで実現をすることができます。

CUIベースでも十分表現力あるので、ターミナル上でいろいろ眺めるダッシュボードを作ってみたい方はお試しを。

GitHub

 

106 Users

1030 Pockets

yaronn/blessed-contrib

https://github.com/yaronn/blessed-contrib

Build terminal dashboards using ascii/ansi art and javascript - yaronn/blessed-contrib

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

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

いままで作成した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ページ上で実際にコマンドを入力して挙動を試せたりできるので便利。

バージョンナンバーを表示するバッジを作るサイトを少し調べたのでメモ。Version Badge for npm, RubyGems, PyPI, Bower and other packagesというサイトで作れたので作ってみた。

evacなら、こんな感じ。

相変わらずあまり本が読めない一ヶ月...。2015年はもう少し本を読みたい。

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏は、検索という処理に関してひと通り一冊で把握できるし、具体的な実装についてコードで示されていてとても読みやすかった。また更に細かく知りたい人向けにエイリアスも本中に多く設けられていてとても良書。

この本を読んで実際に手を動かしてみて、

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

といった簡単な実装をnode.jsでやってみたり。

また、全然ジャンルは変わりますが、日本のごちそう すき焼き も、読んでとても興味深く、そして何よりお腹が空いてしまう本だった。すき焼きの発祥から調理法、牛肉そのものの扱いについてまで書かれていて、すき焼き好きの人には是非一読していただきたい。

たくさんお店も紹介されているのだけど、なかなか自分が行くには敷居が高そうだがいつか行ってみたい。

UNIXという考え方―その設計思想と哲学
Mike Gancarz
読了日：12月21日

新幹線の車窓から 東海道新幹線編
栗原景
読了日：12月21日

検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏
山田浩之
読了日：12月21日

日本のごちそう すき焼き
向笠千恵子
読了日：12月30日

沈みゆく帝国 スティーブ・ジョブズ亡きあと、アップルは偉大な企業でいられるのか
ケイン岩谷ゆかり
読了日：12月30日