VPS 環境を Mondo Rescue でバックアップ

wget ftp://ftp.mondorescue.org/ubuntu/12.04/mondorescue.sources.list
sudo mv mondorescue.sources.list /etc/apt/sources.list.d/
sudo apt-get update
sudo apt-get install mindi mindi-busybox mondo

バックアップの実行

バックアップしたのち、ローカルに転送して捨てるので、/tmp/backup へバックアップファイルを保存することとします

mkdir /tmp/backup
sudo mondoarchive -O -i -N -d /tmp/backup -s 30g

-O バックアップを作成
-i ISOイメージとする
-N 全てのネットワークファイルシステムを無視する
-d バックアップの保存先を /tmp/backup に
-s 30g バックアップファイルの分割単位を30GBに(実質分割しない)

/tmp 以下はデフォルトで非バックアップ対象なので、-E オプションはつけていません。なお -d の指定ディレクトリは前もって作っておく必要があります。

手元の環境だと約1時間かかりました。(バックアップ対象約8GB メモリ1GB HDD 出力 mondorescue-1.iso 3.3G)

このファイルを scp で手元に転送しておきます。

Virtual Box に環境を復元してみる

先にいくつかハマったポイントを列挙しておきます

• パーティション番号の最大が4までなので5を使っているとエラる
• F12 を押すと終了するので注意
• mkinitrd コマンドが存在しなくて再生成できなかった。が起動した。
  • Ubuntu は mkinitramfs らしい
  • mkinitramfs というか update-initramfs -u が一番簡単っぽい
• インストール直後にネットワークインターフェイスの設定をやること
  • /etc/network/interfaces を編集
• /etc/hosts に hostname に関するエントリを追加しておくこと (後述)

Waiting for network configuration…
Waiting up to 60more seconds for network configuration…

Team ID を取得する

Apple Developer Center にいくと、Membership Details に Team ID という項目がある。

あるいはコードサイン用に Key Chain に自分用の証明書を入れていると思うが、その証明書名の括弧の中の文字列がチームIDとなっている。

追加の Info.plist を作る

<plist version="1.0">
<dict>
	<key>ElectronTeamID</key>
	<string>$TEAM_ID$</string>
</dict>
</plist>

こんな感じで Info.plist を作っておく、不完全なファイルに見えるが、残りは electron-packager が埋めるのでこれで良い。

こうした上で electron-packager に --extend-info=dev/Info.plist をつけて実行する。

entitlements ファイルの更新

parent.plist を以下のようにする。com.apple.security.network.client は今回の件とは関係なく、Chemr に必要なのでつけているだけで、必須ではない。

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
  <dict>
    <key>com.apple.security.app-sandbox</key>
    <true/>
    <key>com.apple.security.network.client</key>
    <true/>
    <key>com.apple.security.application-groups</key>
    <string>$TEAM_ID$.net.lowreal.Chemr</string>
  </dict>
</plist>

child.plist は以下のようにする

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
  <dict>
    <key>com.apple.security.app-sandbox</key>
    <true/>
    <key>com.apple.security.inherit</key>
    <true/>
  </dict>
</plist>

codesign

electron-packager にも codesign のオプションはあるが、使ってない。electron-osx-sign を直接呼びだしている。

./node_modules/.bin/electron-osx-sign --no-pre-auto-entitlements --version=1.2.0 "$APP_PATH" --entitlements=dev/parent.plist --entitlements-inherit=dev/child.plist --identity="$APP_KEY"

こんな感じで、上記 entitlements ファイルを指定して codesign させる。

なお electron-osx-sign の 0.4.0-beta4 以上だとこの entitlements の処理を自動でやってくれるみたいだが、なんとなく自動的にやるのが信用ならないのでこれはつかってない。

備考

使ったツールのバージョン

• "electron-osx-sign": "^0.4.0-beta4"
• "electron-prebuilt": "1.2.1"
• "electron-packager": "^7.0.3"
• electron-packager に渡す --version の値: 1.2.1 (新しいものじゃないと ElectronTeamID に対応してないので注意)

証明書なしでサンドボックスアプリとして実行したい

デバッグのため、とりあえず証明書なしでサンドボックスを有効にしたい場合、ad-hoc signing でも動かすことができた。これは identity に - を指定することでできる。

すなわち

./node_modules/.bin/electron-osx-sign --no-pre-auto-entitlements --platform=mas --version=1.2.0 "$APP_PATH" --entitlements=dev/parent.plist --entitlements-inherit=dev/child.plist --identity="-"

のようにする。おそらく Team ID は一致さえしていればなんでもいい(と思うが試してはいない)

備考 electron-osx-sign を verbose にする

環境変数 DEBUG を設定すると詳細なログがでるようになる。DEBUG='electron-osx-sign' これは debug という npm パッケージを使っているため。

感想

「Chrome が新圧縮アルゴリズム対応!」みたいなニュースが流れてからだいぶ経っています。しばらくは Firefox だけ有効な状態だったので「まだかまだか」とちょくちょくチェックしていたのですが、ついにデフォルト有効になりました。これによって劇的にパフォーマンスが改善するわけではないと思いますが、accept-encoding に新しいのが加わるとわくわくします。

なおこのサイトは全体的に brotli 対応にしてあるので、開発者ツールとかで眺めてニヤニヤしています。

やっていることの概要

1. エントリーのHTMLを適当なワード単位に分割
   • タグ削除とか記号削除とかしつつ、簡単な形態素解析で分割
2. エントリごとのワード出現回数をSQLiteに全て入れる (テーブル構造的には転置インデックスとして機能)
3. エントリ・ワードごとにTF-IDF の計算
4. エントリごとにTF-IDFのベクトルとして正規化
5. エントリごとに共通語が一定数を超えるエントリ複数に対しコサイン類似度でスコアを計算

ワード分割

MeCab を使った形態素解析などでもいいのですが、お手軽にやりたかったので以下のようにしています。

my $text = ...;
$text =~ s{<style[^<]*?</style>}{}g;
$text =~ s{<script[^<]*?</script>}{}g;
$text =~ s{<[^>]+?>}{}g;
$text =~ s{[^\w]+}{ }g;
my $words = reduce {
	$a->{$b}++;
	$a;
} +{},
	map {
		s/^\s|\s$//g;
		$_;
	}
	map {
		if (/[^a-z0-9]/i) {
			Text::TinySegmenter->segment($_);
		} else {
			$_;
		}
	} split /\s/, $text; 

不必要なHTML要素及びタグを削除し、記号類を全てスペースに置換したうえでスペースで分割し、日本語が含まれていそうな部分だけ TinySegmenter による簡易形態素解析をしています。

自分しか書かない日記の類似をとるので、表記揺れが殆どないことを前提に、アルファベットだけで構成される部分に関してはそのまま特徴語としたいためです。また、プログラムについて書くことが多いので日本語部分は比較的重要度が低いという見立てがあります。

転置インデックス

転置インデックスはあるワードがどのエントリに含まれるかを記録したデータ構造です。エントリー中の文章を適切な粒度で分割して、ワードからエントリーをひけるインデックスをつくります。

転置インデックスだけでも、あるワードが含まれるエントリーのリストを得るのは簡単になるので、例えば「共通ワードが多いエントリ同士は類似している」というスコアリングを採用するなら、転置インデックスのみで実現できます。

DBとしてSQLiteを使っているので、簡単な定義の単一テーブルだけを作ってなんとかしています。

CREATE TABLE tfidf (
	`id` INTEGER PRIMARY KEY,
	`term` TEXT NOT NULL,
	`entry_id` INTEGER NOT NULL,
	`term_count` INTEGER NOT NULL DEFAULT 0, -- エントリ内でのターム出現回数
	`tfidf` FLOAT NOT NULL DEFAULT 0, -- 正規化前の TF-IDF
	`tfidf_n` FLOAT NOT NULL DEFAULT 0 -- ベクトル正規化した TF-IDF 
);
CREATE UNIQUE INDEX index_tf_term ON tfidf (`term`, `entry_id`);
CREATE INDEX index_tf_entry_id ON tfidf (`entry_id`);

見ての通りですがターム(ワード)とエントリIDでユニークなテーブルです。

エントリ内のHTMLを適当な粒度で分割したのち、このテーブルに入れています。この段階では term, entry_id, term_count だけ埋めます。

INSERT INTO tfidf (`term`, `entry_id`, `term_count`) VALUES (?, ?, ?);

TF-IDF

TF-IDFは特徴語抽出のアルゴリズムです。文書中のワード出現頻度 (Term Frequency) と、全文書中のワード出現頻度の逆数( Inverse Document Frequency) から、ある文書のあるワードがどれぐらいその文書を特徴付けているかをスコアリングできます。

転置インデックスから「共通ワードが多いエントリ同士は類似している」というスコアリングを使ってエントリを抽出すると、ワード数の多いエントリ同士は類似していなくても類似しているとスコアリングされてしまいます。

TF-IDF を使って各ワードに重み付けをすれば「特徴語の傾向が似ている文書は類似してる」というスコアリングにすることができます。

まずは後述する正規化を考えずにテーブルの tfidf カラムを埋めます。

-- SQRT や LOG を使いたいので
SELECT load_extension('/path/to/libsqlitefunctions.so');

-- エントリ数をカウントしておきます
-- SQLite には変数がないので一時テーブルにいれます
CREATE TEMPORARY TABLE entry_total AS
    SELECT CAST(COUNT(DISTINCT entry_id) AS REAL) AS value FROM tfidf;

-- ワード(ターム)が出てくるエントリ数を数えておきます
-- term と entry_id でユニークなテーブルなのでこれでエントリ数になります
CREATE TEMPORARY TABLE term_counts AS
    SELECT term, CAST(COUNT(*) AS REAL) AS cnt FROM tfidf GROUP BY term;
CREATE INDEX temp.term_counts_term ON term_counts (term);

-- エントリごとの合計ワード数を数えておきます
CREATE TEMPORARY TABLE entry_term_counts AS
    SELECT entry_id, LOG(CAST(SUM(term_count) AS REAL)) AS cnt FROM tfidf GROUP BY entry_id;
CREATE INDEX temp.entry_term_counts_entry_id ON entry_term_counts (entry_id);

-- TF-IDF を計算して埋めます
-- ここまでで作った一時テーブルからひいて計算しています。
UPDATE tfidf SET tfidf = IFNULL(
	-- tf (normalized with Harman method)
	(
		LOG(CAST(term_count AS REAL) + 1) -- term_count in an entry
		/
		(SELECT cnt FROM entry_term_counts WHERE entry_term_counts.entry_id = tfidf.entry_id) -- total term count in an entry
	)
	*
	-- idf (normalized with Sparck Jones method)
	(1 + LOG(
		(SELECT value FROM entry_total) -- total
		/
		(SELECT cnt FROM term_counts WHERE term_counts.term = tfidf.term) -- term entry count
	))
, 0.0)

一時テーブルを使いまくっています。何度も同じ TF-IDF 計算をするなら効率化のため保存しておけそうなテーブルもありますが、更新処理が複雑になるためTF-IDF更新時に作っては消しています。修正が頻発するような開発初期段階では特に一時テーブルは設計変更などに強くて便利です。

TF-IDF のベクトル正規化

TF-IDF を計算して、エントリごとにエントリ中の単語数次数を持つ特徴ベクトルを作ったことになります。このあとコサイン類似度をとるわけですが、その際にはベクトルの大きさが不要なのでこれを正規化します。

ベクトル正規化はあるベクトルを方向（角度）をそのままに長さを1にするとこを言っています。コサイン類似ではエントリごとの角度だけを比較したいので、あらかじめ文書ごとのベクトルを正規化することで計算を簡単にできます。

-- エントリごとのTF-IDFのベクトルの大きさを求めておきます
CREATE TEMPORARY TABLE tfidf_size AS
	SELECT entry_id, SQRT(SUM(tfidf * tfidf)) AS size FROM tfidf
	GROUP BY entry_id;
CREATE INDEX temp.tfidf_size_entry_id ON tfidf_size (entry_id);

-- 計算済みの TF-IDF をベクトルの大きさで割って正規化します
UPDATE tfidf SET tfidf_n = IFNULL(tfidf / (SELECT size FROM tfidf_size WHERE entry_id = tfidf.entry_id), 0.0)

コサイン類似

コサイン類似はベクトル長さを無視しての角度の差を求めるためのアルゴリズムです。2つのベクトルの角度の差のコサインを求めます。例えば、2つのベクトルの角度差が0(一致している)場合、 = 1、90度(直交・相関関係なし) なら 、180度(負の相関)なら と、なります。

前もってベクトル正規化をしているのでかけ算と足し算だけで計算できます。

ただ計算が簡単とはいえ、候補エントリ数*関係するワード(ターム)の数だけレコードをひいてくる必要があるので結構大変になってしまいます。

ここの効率化方法があまり思いつかず以下にようにしています

• エントリの特徴語を50語取得する(TF-IDF順にソートして大きいほうから50件)
• 特徴語を含むエントリを共通語が多い順に100エントリ取得する (コサイン類似前に足切り)
• それぞれのエントリ同士でコサイン類似度を計算してスコアを算定してソートする

特徴語の共通語が多い順で足切りをしているので、長いエントリほどここでは有利となってしまいます。また、極端に短いエントリに関しては100エントリ以上が同一数の共通語を持つ状態になる場合があり、このケースではスコアをつける前に「類似」と判定すべきエントリが確率的に足切りされてしまうので正確ではありません。

TF-IDF の大きい順に50件だけを採用しているので、正確なコサイン類似度ではありません (ベクトル正規化のときに使った次数と違う) が、無視しています。

うまくいった場合はスコアリングで上位に類似エントリが集まるようになります。

-- 類似していそうなエントリを共通語ベースでまず100エントリほど出します
CREATE TEMPORARY TABLE similar_candidate AS
	SELECT entry_id, COUNT(*) as cnt FROM tfidf
	WHERE
		entry_id > ? AND
		term IN (
			SELECT term FROM tfidf WHERE entry_id = ?
			ORDER BY tfidf DESC
			LIMIT 50
		)
	GROUP BY entry_id
	HAVING cnt > 3
	ORDER BY cnt DESC
	LIMIT 100

-- 該当する100件に対してスコアを計算してソートします
SELECT
	entry_id AS eid,
	SUM(a.tfidf_n * b.tfidf_n) AS score
FROM (
	(SELECT term, tfidf_n FROM tfidf WHERE entry_id = ? ORDER BY tfidf DESC LIMIT 50) as a
	INNER JOIN
	(SELECT entry_id, term, tfidf_n FROM tfidf WHERE entry_id IN (SELECT entry_id FROM similar_candidate)) as b
	ON
	a.term = b.term
)
WHERE eid != ?
GROUP BY entry_id
ORDER BY score DESC
LIMIT 10

これによって求められた類似エントリは別途テーブルに保存しておいて、表示時にはこのテーブルのみをひいてくる構成にしました。

Perl の DBD::SQLite で使うには

Perl から DBD::SQLite 経由で使う場合、

$dbh->do('SELECT load_extension("/path/to/libsqlitefunctions.so")');   

とする。が、実はこれだけだと動かず、以下のように謎のエラーが出る。

DBD::SQLite::db do failed: SQL logic error or missing database
not authorized 

ドキュメントにも書いてあるが、sqlite_enable_load_extension を前もって呼ぶ必要がある。

$dbh->sqlite_enable_load_extension(1);
# または
$dbh->func(1, "enable_load_extension"); 

備考

拡張の開発方法については Run-Time Loadable Extensions を見る。