http://www.sqlite.org/withoutrowid.html WITHOUT ROWID 最適化について

SQLite は常に暗黙的な rowid カラムを持っていることになっている。これはカラムとして明示することもできるし、interger primary key として定義されたフィールドは暗黙的な rowid の代わりにすることができる。SQLite ではこの rowid が基本のプライマリキーになっている。

適当な数値をプライマリキーにしたい場合はこれで全く問題ないが、複合キーだったり文字列をプライマリキーにしたい場合、その表面上のプライマリキーとは別に rowid カラムができる。このケースでは表面上のプライマリキーを使って SELECT しようとすると、表面上のプライマリキーのインデックスを探したうえで、さらに rowid のインデックスを探すことになる。つまり、このケースのプライマリキーとは単に UNIQUE なインデックスでしかない。

そこそこ最近(3.8.2・2013年)からは WITHOUT ROWID をテーブル定義時に指定することで、暗黙的な rowid 生成を抑制して、プライマリキー指定した定義を「真のプライマリキー」とすることができる。

これによって

  • インデックスを辿る回数が減るのでパフォーマンスがあがる
  • 表面上のプライマリキー→rowid のインデックスがなくなるのでDBサイズが減る
  • インデックスが減るので挿入時の負荷が減る

と良いことがある。一方デメリットで気になるのは

  • 古い SQLite (3.8.2 より前) で該当DBを読もうとすると malformed database schema で怒られて読めない
  • sqlite3_last_insert_rowid() が使えない
  • インクリメンタルblob I/Oが使えない (大きなカラムを少しずつ読める低レベルな仕組み)
  1. トップ
  2. tech
  3. SQLite で「PRIMARY KEY」を《真のプライマリキー》とするには

TF-IDFによる類似エントリー機能の実装をしてみました。ほぼSQLiteですませるような構成です。

やっていることの概要

  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

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

  1. トップ
  2. tech
  3. TF-IDFとコサイン類似度による類似エントリー機能の実装

結構みてる気がする

  • ふらいんぐうぃっち
  • 田中くんはいつもけだるげ
  • くまみこ
  • 学戦都市アスタリスク 2nd SEASON
  • 甲鉄城のカバネリ
  • Re:ゼロから始める異世界生活
  • 坂本ですが?
  • ネトゲの嫁は女の子じゃないと思った?
  • あんハピ♪
  • クロムクロ
  • マクロスΔ
  • ジョジョの奇妙な冒険 ダイヤモンドは砕けない
  • ばくおん!!

Hello darkness, my dear friend -

4.0 / 5.0

久しぶりに CD を買った。原点回帰っぽい構成みたいだけど、どうなんだろうな〜

ところで久しぶりにリッピングしようと思ったら CD ドライブがついているPCが起動せず、面倒なのでドライブを買った……

ASUS バスパワー対応ポータブルDVDドライブ 【 Windows10対応 】スリムタイプ / Windows Mac 両対応 書き込みソフト付属 ブラック SDRW-08D2S-U LITE -

4.0 / 5.0

前までは EAC でリッピングしていた記憶があるけど、今回は iTunes でリッピングした。CDDB がまだ生きてて簡単だった。

【Quick Charge 2.0対応】 Anker PowerPort+ 6 (QC対応 60W 6ポート USB急速充電器) Galaxy S6 / Edge / Plus, Note 5 / 4, LG G4, HTC One M8 / M9, Nexus 6, iPhone, iPad 他対応 (ブラック) -

5.0 / 5.0

自宅にいくつか Anker の充電器はあるが、Quick Charge 付きのものはなかった。そして、充電器いくつかあるとはいえ、旅行にいこうとすると足りなくて不便だった。

ということで上記のものを買った。ポート数多くなって便利。

Zenfone2 は Quick Charge 2.0 対応なので (特にそうとは書いてないが 9V 充電可能)、繋ぐと以下のように「急速充電中」とともに、発熱に関しての警告がマーキーで表示される。

ただ、Quick Charge 対応ポートは1つだけなので、急速充電したいときは気をつける必要がある。USBケーブルをQuick Charge ポートだけ色が違うものにした。

SQLite にはかなり基本的な算術演算関数しかない。追加で何かしらやるためには拡張 (Run-Time Loadable Extension) を使う必要がある。

LOG や SQRT などはオフィシャルの Contributed Files のextension-functions.c をコンパイルして使う。 http://www.sqlite.org/contrib

Ubuntu でのコンパイル。当然ながら SQLite のヘッダファイルなどが必要なので入れておく。

sudo apt-get install libsqlite3-dev

そのうえで以下のようにコンパイルする。apt-get で入れてる場合 -I などは指定しなくてもデフォルトで良さそう。必要なら pkg-config sqlite3 とかして引数を得る。

gcc -fPIC -shared extension-functions.c -o libsqlitefunctions.so -lm

extension-functions.c の冒頭にもコンパイル方法が書いてある。ただし、今はそれだと上手くいかなくて、-lmは最後につけないとダメ。罠があって、リンクに失敗しても load_extension するまで気付かない。

使うときは以下のように load_extension() を使う

select load_extension("/path/to/libsqlitefunctions.so");

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 を見る。

  1. トップ
  2. tech
  3. SQLite で LOG や SQRT を使うには

食品安全委員会の QA によると、

大豆イソフラボンの安全な一日摂取目安量の上限値70〜75mg/日(大豆イソフラボンアグリコン換算値)

https://www.fsc.go.jp/sonota/daizu_isoflavone.html#19

と書いてある。150mg ぐらい摂取すると健康被害の影響があるかもしれないので、その半分を上限にしているらしい。ちょっと調べてみると、これが案外厳しい基準に思えたので記録しておく。

豆乳の大豆イソフラボン含有量

大豆イソフラボンアグリコン換算は以下のようになっている。食品表示にある「イソフラボン」はイソフラボン配糖体のことなので、換算して考える必要がある。

(例)大豆イソフラボン配糖体10mg×0.625 =大豆イソフラボンアグリコンとして 6.25mg

https://www.fsc.go.jp/sonota/daizu_isoflavone.html#8

ここで、一番メジャーな紀文の調整豆乳について見てみると、「イソフラボン 43mg/200ml」となっている。0.625 をかけて、26.875mg/200ml (大豆イソフラボンアグリコン換算値)

また、FAQ中の表に豆乳の含有量について記載がある。

(大豆イソフラボンアグリコンとしてmg/100g)
〜 省略 〜

食品名(検体数):豆乳(3検体)
含有量: 7.6〜59.4
平均含有量: 24.8

https://www.fsc.go.jp/sonota/daizu_isoflavone.html#6

紀文の調整豆乳はだいたい平均的な値の倍(訂正)


もし毎食コップ一杯の豆乳を飲むと、それだけで75mg/日を超える。もちろん他の大豆製品 (特に味噌や納豆) にも含まれるので豆乳単体でどうとはいえない。

なお、大豆イソフラボンアグリコンの一日摂取目安量の上限値、70~75 ㎎/日は、この量を毎日欠かさず長期間摂取する場合の平均値としての上限値であること、また、大豆食品からの摂取量がこの上限値を超えることにより、直ちに、健康被害に結びつくというものではないことを強調しておく。

https://www.fsc.go.jp/hyouka/hy/hy-singi-isoflavone_kihon.pdf

と書いてある通りなので、豆乳めっちゃ好きすぎる!!!とか、豆乳で必要タンパク質全部とるぞ!!みたいな意気込みがなければ、平均的には大丈夫なのかな。

主観による温度感

大人は毎日1日コップ一杯ぐらいは他に大豆食品をとっていても問題なさそう。妊婦や子供に対してはもっと気をつけるべきのようで、だぶん牛乳代わりに毎日飲む/飲ませるみたいな習慣はやめたほうが良さそう、というのが僕からみた温度感です。

キッコーマン飲料 調製豆乳 200ml×18本 -

5.0 / 5.0