- TF-IDFでデータベース内の類似テキストを検索する Part 1 （基本機能編）
http://pgsqldeepdive.blogspot.jp/2016/07/tf-idf-part-1.html
■検索対象とするドキュメント
今回題材として使うドキュメント（コーパス）はPostgreSQLの日本語マニュアルです。
- PostgreSQL 9.5.3文書
https://www.postgresql.jp/document/9.5/html/index.html
そういう文書を読むときに、「関連するページ」を自動的にピックアップすることができれば、より深い理解や周辺の理解につながるのではないか、というのがもともとのモチベーションです。
■PostgreSQL内にコーパスを作成する
まず、PostgreSQLのマニュアルを保存するテーブルを作成します。スキーマは以下の通りです。
CREATE TABLE pgsql_doc ( docid SERIAL PRIMARY KEY, filename TEXT NOT NULL, html TEXT NOT NULL, plain TEXT, tf JSONB, tfidf JSONB );ファイル名、HTMLとしてのドキュメント、プレーンテキストに直したドキュメントを保存するカラムを準備します（TF-IDFの計算はプレーンテキストに変換してから行います）。また、TF および TF-IDF を保存するカラムも作成します。
次に、使用するPostgreSQLマニュアルをHTMLファイルで取得します。今回は wget を使ってクローリングします。
[snaga@localhost pgsql-doc]$ wget -r -np http://www.postgresql.jp/document/9.5/html/index.html
--2016-07-12 11:24:10-- http://www.postgresql.jp/document/9.5/html/index.html
www.postgresql.jp をDNSに問いあわせています... 157.7.153.71
www.postgresql.jp|157.7.153.71|:80 に接続しています... 接続しました。
HTTP による接続要求を送信しました、応答を待っています... 200 OK
長さ: 特定できません [text/html]
`www.postgresql.jp/document/9.5/html/index.html' に保存中
[ <=> ] 15,839 --.-K/s 時間 0.01s
2016-07-12 11:24:11 (1.50 MB/s) - `www.postgresql.jp/document/9.5/html/index.html' へ保存終了 [15839]
(...略...)
`www.postgresql.jp/document/9.5/html/pgstandby.html' に保存中
[ <=> ] 31,352 --.-K/s 時間 0.01s
2016-07-12 11:30:46 (2.15 MB/s) - `www.postgresql.jp/document/9.5/html/pgstandby.html' へ保存終了 [31352]
終了しました --2016-07-12 11:30:46--
ダウンロード完了: 1306 ファイル、28M バイトを 1m 22s で取得 (349 KB/s)
[snaga@localhost pgsql-doc]$ ls -l
合計 4
drwxrwxr-x. 3 snaga snaga 4096 7月 12 11:24 2016 www.postgresql.jp
[snaga@localhost pgsql-doc]$
取得したファイルは www.postgresql.jp というディレクトリに保存されますので、取得したファイルの中から、HTML ファイルだけを抜き出してリストを作成します。
[snaga@localhost pgsql-doc]$ find www.postgresql.jp -type f -name '*.html' > file.txt [snaga@localhost pgsql-doc]$ head file.txt www.postgresql.jp/document/9.5/html/typeconv-union-case.html www.postgresql.jp/document/9.5/html/release-9-1-20.html www.postgresql.jp/document/9.5/html/recovery-config.html www.postgresql.jp/document/9.5/html/tutorial-agg.html www.postgresql.jp/document/9.5/html/ecpg-sql-deallocate-descriptor.html www.postgresql.jp/document/9.5/html/postgres-fdw.html www.postgresql.jp/document/9.5/html/tutorial.html www.postgresql.jp/document/9.5/html/runtime-config-error-handling.html www.postgresql.jp/document/9.5/html/release-9-3-5.html www.postgresql.jp/document/9.5/html/release-9-1-16.html [snaga@localhost pgsql-doc]$ wc file.txt 1304 1304 74949 file.txt [snaga@localhost pgsql-doc]$リストができたら、以下のスクリプトを使って、先ほど定義したテーブルの filename カラムにファイル名を、html カラムにHTMLテキストを INSERT する SQL ファイルを生成します。
#!/usr/bin/env python2.7
print "BEGIN;"
for f in open("file.txt"):
f = f.rstrip()
print "-- " + f
html = ""
for h in open(f):
html = html + h
filename = f.replace('www.postgresql.jp/document/9.5/html/', '')
html = html.replace("'", "''")
print("INSERT INTO pgsql_doc (filename, html) VALUES ('{filename}', '{html}');".format(filename=filename, html=html))
print "COMMIT;"
以下のように、load.sql ファイルを作成します。
[snaga@localhost pgsql-doc]$ ./load_html.py > load.sql
[snaga@localhost pgsql-doc]$ head load.sql
BEGIN;
-- www.postgresql.jp/document/9.5/html/typeconv-union-case.html
INSERT INTO pgsql_doc (filename, html) VALUES ('typeconv-union-case.html', '<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>10.5. UNION、CASEおよび関連する構文</title><link rel="stylesheet" type="text/css" href="stylesheet.css" /><link rev="made" href="pgsql-docs@postgresql.org" /><meta name="generator" content="DocBook XSL Stylesheets V1.78.1" /><link rel="home" href="index.html" title="PostgreSQL 9.5.3文書" /><link rel="up" href="typeconv.html" title="第10章 型変換" /><link rel="prev" href="typeconv-query.html" title="10.4. 値の格納" /><link rel="next" href="indexes.html" title="第11章 インデックス" /><link rel="copyright" href="legalnotice.html" title="法的告知" /><meta name="viewport" content="width=device-width,initial-scale=1.0,minimum-scale=1.0" /><style type="text/css"><!--
body{margin:0;}
#lay_body{margin:8px;}
#lay_header{margin:0 0 4px 0 !important;border:0;width:100%;padding:0;}
#lay_header .b1{border-bottom:#cef solid 1px;}
#lay_header .b2{border-bottom:#8cf solid 1px;}
[snaga@localhost pgsql-doc]$
ここまでできたら、先ほどのCREATE TABLE文と、このload.sqlをPostgreSQLデータベースに対して実行して、コーパスを作成します。
[snaga@localhost pgsql-doc]$ psql testdb
psql (9.5.2)
"help" でヘルプを表示します.
testdb=> CREATE TABLE pgsql_doc (
testdb(> docid SERIAL PRIMARY KEY,
testdb(> filename TEXT NOT NULL,
testdb(> html TEXT NOT NULL,
testdb(> plain TEXT,
testdb(> tf JSONB,
testdb(> tfidf JSONB
testdb(> );
CREATE TABLE
testdb=> \i load.sql
BEGIN
INSERT 0 1
INSERT 0 1
INSERT 0 1
(...略...)
INSERT 0 1
INSERT 0 1
COMMIT
testdb=> \d+
リレーションの一覧
スキーマ | 名前 | 型 | 所有者 | サイズ | 説明
----------+---------------------+------------+--------+------------+------
public | pgsql_doc | テーブル | snaga | 13 MB |
public | pgsql_doc_docid_seq | シーケンス | snaga | 8192 bytes |
(2 行)
testdb=> select count(*) from pgsql_doc;
count
-------
1304
(1 行)
testdb=>
全部で 1304 のHTMLページが読み込まれていることが分かります。最後に、テーブルの html カラムに取り込んだ HTML テキストを、プレーンテキストに変換して plain カラムに格納します。
HTML をプレーンテキストに変換するには、Python の html2text モジュールを呼び出す UDF を使います。
CREATE OR REPLACE FUNCTION html2text(html text)
RETURNS text
AS $$
import html2text
h = html2text.HTML2Text()
h.ignore_links = True
return h.handle(html.decode('utf-8')).encode('utf-8')
$$
LANGUAGE 'plpython2u';
UPDATE 文を発行して、plain カラムにプレーンテキストを保存します。
testdb=> UPDATE pgsql_doc SET plain = html2text(html);
UPDATE 1304
testdb=> \d+
リレーションの一覧
スキーマ | 名前 | 型 | 所有者 | サイズ | 説明
----------+---------------------+------------+--------+------------+------
public | pgsql_doc | テーブル | snaga | 18 MB |
public | pgsql_doc_docid_seq | シーケンス | snaga | 8192 bytes |
(2 行)
testdb=>
以上でコーパスの準備は完了です。
■TF-IDFを計算する
まず、各ドキュメントの TF を計算して tf カラムに保存します。
なお、今回は前回と異なり、分かち書きの際に2文字以上のトークンのみを拾うように mecab_tokenize 関数を修正しています。
*** pg_tfidf.sql.orig 2016-07-12 16:11:36.122012659 +0900
--- pg_tfidf.sql 2016-07-12 16:10:32.886012704 +0900
***************
*** 45,51 ****
t = n['feature'][6]
if t == '*':
t = n['surface']
! if len(t) > 0:
tokens.append(t)
node = node.next
return json.dumps(tokens)
--- 45,51 ----
t = n['feature'][6]
if t == '*':
t = n['surface']
! if len(t) > 1:
tokens.append(t)
node = node.next
return json.dumps(tokens)
それでは TF を計算します。
testdb=> SELECT COUNT(tf) FROM pgsql_doc;
count
-------
0
(1 row)
testdb=> UPDATE pgsql_doc SET tf = tf(mecab_tokenize(plain));
UPDATE 1304
testdb=> SELECT COUNT(tf) FROM pgsql_doc;
count
-------
1304
(1 row)
testdb=>
上記の例では、最初 NULL だった tf カラムに値が設定されていることが分かります。次に、今作成した TF を使って TF-IDF を計算して tfidf カラムに保存します。
testdb=> SELECT COUNT(tfidf) FROM pgsql_doc;
count
-------
0
(1 row)
testdb=> UPDATE pgsql_doc SET tfidf = tf_idf(tf, (SELECT idf(tf) FROM pgsql_doc));
UPDATE 1304
testdb=> SELECT COUNT(tfidf) FROM pgsql_doc;
count
-------
1304
(1 row)
testdb=>
tfidf カラムについても、最初すべて NULL だったカラムが、すべて TF-IDF の値で埋まっていることが分かります。
■TF-IDFを基準に類似度の高いテキストを取得する
それでは、実際に特定のページに対して、内容が近いページを検索してみます。
ここでは wal.html というページを取り出し、それに（ユークリッド距離が）近い順番に他のページを並べてみています。
testdb=> SELECT
testdb-> filename,
testdb-> euclidean_distance(tfidf, (SELECT tfidf FROM pgsql_doc WHERE filename = 'wal.html') )
testdb-> FROM
testdb-> pgsql_doc
testdb-> ORDER BY
testdb-> 2;
filename | euclidean_distance
---------------------------------------------------+----------------------
wal.html | 1.49011611938477e-08
wal-intro.html | 0.670408645135645
wal-internals.html | 0.696786282911372
wal-reliability.html | 0.721978311656912
admin.html | 0.723694675276873
wal-async-commit.html | 0.725251929411429
runtime-config-wal.html | 0.72553385845936
wal-configuration.html | 0.729987981895102
release-7-4-29.html | 0.732088992934256
disk-full.html | 0.733543368352212
(...略...)
brin.html | 1.39337005247978
nls.html | 1.41008067598852
gin.html | 1.51901488292384
event-trigger-matrix.html | 1.91842947389792
sql-keywords-appendix.html | 2.23230386856231
(1304 rows)
testdb=>
距離の近いドキュメントを見てみると、いずれも WAL やディスク関連の内容が記述されたページが出てきました。TF-IDF による類似度検索が機能していることが分かります。もう一つの例として、gin.html に近いページを類似度検索してみます。
testdb=> SELECT
testdb-> filename,
testdb-> euclidean_distance(tfidf, (SELECT tfidf FROM pgsql_doc WHERE filename = 'gin.html') )
testdb-> FROM
testdb-> pgsql_doc
testdb-> ORDER BY
testdb-> 2;
filename | euclidean_distance
---------------------------------------------------+---------------------
gin.html | 2.1073424255447e-08
gin-limit.html | 1.1318263488524
gin-examples.html | 1.19411267385758
gin-intro.html | 1.26178461661249
gin-implementation.html | 1.28122198499309
gin-tips.html | 1.28399693208161
spgist-examples.html | 1.30248544760188
gin-extensibility.html | 1.32677302605941
indexes-types.html | 1.32835949747107
release-9-1-7.html | 1.34013416302523
sql-createindex.html | 1.3407384158454
textsearch-indexes.html | 1.34299614984885
xindex.html | 1.34457129207184
(...略...)
gist.html | 1.68315092630428
brin-builtin-opclasses.html | 1.68897216768224
nls.html | 1.79686563589178
event-trigger-matrix.html | 2.22159433303442
sql-keywords-appendix.html | 2.49797882729631
(1304 rows)
testdb=>
こちらも、GINや関連するインデックスに関するページが上位に出てきました。TF-IDF の類似度検索が機能していると考えて良さそうです。
■パフォーマンスを再考する
さて、実際に実行してみると分かりますが、この検索クエリはかなり時間がかかります。
私の手元の環境（Think Pad X1 Carbon 上の Vagrant）で100秒近くかかっています。
testdb=> EXPLAIN ANALYZE VERBOSE SELECT
testdb-> filename,
testdb-> euclidean_distance(tfidf, (SELECT tfidf FROM pgsql_doc WHERE filename = 'wal.html') )
testdb-> FROM
testdb-> pgsql_doc
testdb-> ORDER BY
testdb-> 2;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
Sort (cost=988.81..992.07 rows=1304 width=39) (actual time=98609.860..98611.538 rows=1304 loops=1)
Output: pgsql_doc.filename, (euclidean_distance(pgsql_doc.tfidf, $0))
Sort Key: (euclidean_distance(pgsql_doc.tfidf, $0))
Sort Method: quicksort Memory: 151kB
InitPlan 1 (returns $0)
-> Seq Scan on public.pgsql_doc pgsql_doc_1 (cost=0.00..299.30 rows=1 width=18) (actual time=0.111..0.287 rows=1 loops=1)
Output: pgsql_doc_1.tfidf
Filter: (pgsql_doc_1.filename = 'wal.html'::text)
Rows Removed by Filter: 1303
-> Seq Scan on public.pgsql_doc (cost=0.00..622.04 rows=1304 width=39) (actual time=73.871..98546.860 rows=1304 loops=1)
Output: pgsql_doc.filename, euclidean_distance(pgsql_doc.tfidf, $0)
Planning time: 0.062 ms
Execution time: 98613.087 ms
(13 rows)
Time: 98613.888 ms
testdb=>
euclidean_distance 関数を呼びながらのシーケンシャルスキャンで 98秒（actual time 98546.860）もかかっていますが、シーケンシャルスキャンだけでこんなにかかるわけはないので、当然ながらボトルネックは euclidean_distance 関数の内部にあるのでしょう。類似度検索はいくら便利だとは言え、もう少しパフォーマンスをどうにかしたいところです。
というわけで、次回はこの euclidean_distance 関数のボトルネックを調査し、パフォーマンス改善をしてみます。
■まとめ
今回は、PostgreSQLに実装した TF-IDF の関数を使って、実際の PostgreSQL のマニュアルの類似度検索を行い、現実の問題に対して TF-IDF の類似度検索が一通り動作することを確認しました。
一方で、現在の実装では検索にかなりの時間を要していることも分かりました。
最終回である次回は、何がボトルネックになっているのか、そしてパフォーマンスを改善するために PostgreSQL 内部で何ができるのかを考えてみます。
では。
0 件のコメント:
コメントを投稿