「git でコミット時のスクリプト実行」を Qiita に投稿しました。
n-gram を使って文字列の類似度を計算する方法のメモ。
n-gram を使って 0（類似していない） ～ 1（類似している） の類似度を計算します。
n-gram
n-gram は n 文字の連続する文字列で、abcd という文字列の場合には以下のようになります。
- 1-gram (unigram): a, b, c, d
- 2-gram (bigram): ab, bc, cd
- 3-gram (trigram): abc, bcd
- ...
n-gram を使った文字列の類似度
ここでは n-gram の頻度を使って、２つの文字列の類似度を以下のように計算します。
類似度 ＝ sum({文字列1の n-gram の出現頻度} × {文字列2の n-gram の出現頻度})
÷ (sqrt(sum({文字列1 の n-gram の出現頻度}^2)) × sqrt(sum({文字列2 の n-gram の出現頻度}^2))以降で、以下の文字列1、文字列2、文字列3 について類似度を計算してみます。
- 文字列1: abcd
- 文字列2: bcde
- 文字列3: dcba
unigramでの類似度計算例
文字列1-3 の unigram はそれぞれ以下のようになります。
- 文字列1: a, b, c, d
- 文字列2: b, c, d, e
- 文字列3: d, c, b, a
文字列1 と文字列2 の unigram での類似度は以下のようになります。
類似度 ＝ (a:1×0 + b:1×1 + c:1×1 + d:1×1 + e:0×1) ÷ (sqrt(a:1^2 + b:1^2 + c:1^2 + d:1^2) × sqrt(b:1^2 + c:1^2 + d:1^2 + e:1^2)) ＝ 3 ÷ (sqrt(4) × sqrt(4)) ＝ 3/4
一方、文字列1 と文字列3 の unigram での類似度は以下のようになります。
類似度 ＝ (a:1×1 + b:1×1 + c:1×1 + d:1×1) ÷ (sqrt(a:1^2 + b:1^2 + c:1^2 + d:1^2) × sqrt(a:1^2 + b:1^2 + c:1^2 + d:1^2)) ＝ 4 ÷ (sqrt(4) × sqrt(4)) ＝ 4/4 ＝ 1
unigram の場合は、文字列の並び順が類似度に反映されないため、文字列1と文字列3の類似度が1になります。
bigram での類似度計算例
次に bigram での類似度を計算してみます。
文字列1-3 の bigram はそれぞれ以下のようになります。
- 文字列1: ab, bc, cd
- 文字列2: bc, cd, de
- 文字列3: dc, cb, ba
文字列1 と文字列2 の bigram での類似度は以下のようになります。
類似度 ＝ (ab:1×0 + bc:1×1 + cd:1×1 + de:0×1) ÷ (sqrt(ab:1^2 + bc:1^2 + cd:1^2) × sqrt(bc:1^2 + cd:1^2 + de:1^2)) ＝ 2 ÷ (sqrt(3) × sqrt(3)) ＝ 2/3
一方、文字列1 と文字列2 の bigram での類似度は以下のようになります。
類似度 ＝ (ab:1×0 + bc:1×0 + cd:1×0 + dc:0×1 + cb:0×1 + ba:0×1) ÷ (sqrt(ab:1^2 + bc:1^2 + cd:1^2) × sqrt(dc:1^2 + cb:1^2 + ba:1^2)) ＝ 0 ÷ (sqrt(3) × sqrt(3)) ＝ 0/3 ＝ 0
bigram だと文字の並び順が類似度に反映されるため、並び順がずれていると類似度が低くなります。
n-gram での文字列の類似度計算プログラムの例
このプログラムでは文字列の先頭、末尾を考慮するため、文字列の先頭、末尾に n-1 文字の \t を追加して類似度計算を行います。
#
# NgramMatcher
#
import math
class NgramMatcher:
BOS = '\t'
EOS = '\t'
@classmethod
def ngrams(cls, n, str):
ngrams = {}
str = (cls.BOS * (n-1)) + str + (cls.EOS * (n-1))
for i in range(0, len(str)-(n-1)):
ng = str[i:i+n]
cnt = ngrams.get(ng, 0)
ngrams[ng] = cnt + 1
return ngrams
@classmethod
def length(cls, ngrams):
len2 = 0
for ng in ngrams.keys():
cnt = ngrams[ng]
len2 += cnt * cnt
len1 = math.sqrt(len2)
return len1
@classmethod
def similarity(cls, n, str1, str2):
ngs1 = cls.ngrams(n, str1)
ngs2 = cls.ngrams(n, str2)
print(ngs1)
print(ngs2)
sum = 0
for ng1 in ngs1.keys():
cnt1 = ngs1[ng1]
cnt2 = ngs2.get(ng1, 0)
sum += cnt1 * cnt2
len1 = cls.length(ngs1)
len2 = cls.length(ngs2)
sim = sum / (len1 * len2)
return sim上記のプログラムを使って類似度を計算してみます。
$ python
>>> from ngram_matcher import NgramMatcher
>>> NgramMatcher.similarity(1, 'abcd', 'bcde')
{'a': 1, 'b': 1, 'c': 1, 'd': 1}
{'b': 1, 'c': 1, 'd': 1, 'e': 1}
0.75
>>> NgramMatcher.similarity(1, 'abcd', 'dcba')
{'a': 1, 'b': 1, 'c': 1, 'd': 1}
{'c': 1, 'd': 1, 'b': 1, 'a': 1}
1.0
>>> NgramMatcher.similarity(1, 'abab', 'baba')
{'a': 2, 'b': 2}
{'b': 2, 'a': 2}
0.9999999999999998
>>> NgramMatcher.similarity(2, 'abcd', 'bcda')
{'\ta': 1, 'ab': 1, 'bc': 1, 'cd': 1, 'd\t': 1}
{'\tb': 1, 'bc': 1, 'cd': 1, 'da': 1, 'a\t': 1}
0.3999999999999999
>>> NgramMatcher.similarity(2, 'abcd', 'dcba')
{'\ta': 1, 'ab': 1, 'bc': 1, 'cd': 1, 'd\t': 1}
{'\td': 1, 'dc': 1, 'cb': 1, 'ba': 1, 'a\t': 1}
0.0
>>> NgramMatcher.similarity(2, 'abab', 'baba')
{'\ta': 1, 'ab': 2, 'ba': 1, 'b\t': 1}
{'\tb': 1, 'ba': 2, 'ab': 1, 'a\t': 1}
0.5714285714285714
>>> NgramMatcher.similarity(2, 'abab', 'babab')
{'\ta': 1, 'ab': 2, 'ba': 1, 'b\t': 1}
{'\tb': 1, 'ba': 2, 'ab': 2, 'b\t': 1}
0.8366600265340756
PostgreSQL でテーブル情報などを確認する方法のメモ。
データベース一覧
# \list
List of databases
Name | Owner | Encoding | Locale Provider | Collate | Ctype | Locale | ICU Rules | Access privileges
------------------+----------+----------+-----------------+---------+---------+--------+-----------+-----------------------
postgres | postgres | UTF8 | libc | C.UTF-8 | C.UTF-8 | | |
template0 | postgres | UTF8 | libc | C.UTF-8 | C.UTF-8 | | | =c/postgres +
| | | | | | | | postgres=CTc/postgres
template1 | postgres | UTF8 | libc | C.UTF-8 | C.UTF-8 | | | =c/postgres +
| | | | | | | | postgres=CTc/postgres
test1 | postgres | UTF8 | libc | C.UTF-8 | C.UTF-8 | | |
test2 | postgres | UTF8 | libc | C.UTF-8 | C.UTF-8 | | |データベースに接続
# \connect test1
テーブル定義
# \d test1
Table "public.test1"
Column | Type | Collation | Nullable | Default
--------+-----------------------+-----------+----------+---------
id | character varying(32) | | not null |
name | character varying(32) | | not null |
Indexes:
"test1_pkey" PRIMARY KEY, btree (id)select
# select * from test1; id | name --------+---------- id_001 | name_001 id_002 | name_002 id_003 | name_003 id_004 | name_004 id_005 | name_005
検索結果を縦方向に表示
# \x Expanded display is on. # select * from test1; -[ RECORD 1 ]-- id | id_001 name | name_001 -[ RECORD 2 ]-- id | id_002 name | name_002 -[ RECORD 3 ]-- id | id_003 name | name_003 -[ RECORD 4 ]-- id | id_004 name | name_004 -[ RECORD 5 ]-- id | id_005 name | name_005
PostgreSQL で実行中のクエリを確認する方法のメモ。
pg_stat_activity テーブルで実行中のクエリを参照することができます。
# select * from pg_stat_activity;
datid | datname | pid | leader_pid | usesysid | usename | application_name | client_addr | client_hostname | client_port | backend_start | xact_start | query_start | state_change | wait_event_type | wait_event | state | backend_xid | backend_xmin | query_id | query | backend_type
-------+----------+------+------------+----------+----------+------------------+-------------+-----------------+-------------+-------------------------------+-------------------------------+-------------------------------+-------------------------------+-----------------+---------------------+--------+-------------+--------------+----------+---------------------------------+------------------------------
5 | postgres | 3983 | | 10 | postgres | psql | 127.0.0.1 | | 58884 | 2025-02-18 23:24:17.79372+09 | 2025-02-18 23:26:01.543685+09 | 2025-02-18 23:26:01.543685+09 | 2025-02-18 23:26:01.543687+09 | | | active | | 246389 | | select * from pg_stat_activity; | client backend
5 | postgres | 4527 | | 10 | postgres | psql | 127.0.0.1 | | 40056 | 2025-02-18 23:25:47.587781+09 | 2025-02-18 23:25:58.352106+09 | 2025-02-18 23:25:58.352106+09 | 2025-02-18 23:25:58.352109+09 | Timeout | PgSleep | active | | 246389 | | select pg_sleep(1000); | client backend
| | 1145 | | | | | | | | 2025-02-18 23:08:03.235239+09 | | | | Activity | AutovacuumMain | | | | | | autovacuum launcher
| | 1146 | | 10 | postgres | | | | | 2025-02-18 23:08:03.235243+09 | | | | Activity | LogicalLauncherMain | | | | | | logical replication launcher
| | 1121 | | | | | | | | 2025-02-18 23:08:03.193927+09 | | | | Activity | CheckpointerMain | | | | | | checkpointer
| | 1122 | | | | | | | | 2025-02-18 23:08:03.194386+09 | | | | Activity | BgwriterHibernate | | | | | | background writer
| | 1143 | | | | | | | | 2025-02-18 23:08:03.234863+09 | | | | Activity | WalWriterMain | | | | | | walwriter
PostgreSQL で extension のバージョンを確認する方法のメモ。
pg_available_extensions テーブルでバージョンを確認することができます。
# select * from pg_available_extensions;
name | default_version | installed_version | comment
--------------------+-----------------+-------------------+----------------------------------------------------------------
pageinspect | 1.12 | | inspect the contents of database pages at a low level
plpgsql | 1.0 | 1.0 | PL/pgSQL procedural language
...
xml2 | 1.1 | | XPath querying and XSLT
vector | 0.8.0 | | vector data type and ivfflat and hnsw access methods
hstore_plpython3u | 1.0 | | transform between hstore and plpython3u
jsonb_plpython3u | 1.0 | | transform between jsonb and plpython3u
plpython3u | 1.0 | | PL/Python3U untrusted procedural language
textsearch_ja | 42 | 42 | Integrated Full-Text-Search for Japanese using morphological an
ltree_plpython3u | 1.0 | | transform between ltree and plpython3u
PostgreSQL で textsearch_ja を使って日本語のテキストを全文検索する方法のメモ。
mecab のインストール
Groonga リポジトリを追加
sudo yum install https://packages.groonga.org/almalinux/9/groonga-release-latest.noarch.rpm
rpm パッケージをインストール
sudo yum install mecab mecab-devel mecab-ipadic
textsearch_ja のインストール
textsearch_ja をダウンロード
$ git clone https://github.com/oknj/textsearch_ja.git
インストール
$ make
$ export PATH="${PATH}:/usr/pgsql-17/bin"
$ sudo --preserve-env=PATH make install
$ psql -f textsearch_ja--42.sql # 必要に応じて -h、-U オプションを指定postgres にログインして textsearch_ja を有効化
$ psql -h 127.0.0.1 -U postgres # create extension textsearch_ja;
動作確認
# select ja_wakachi('日本語のテキストを単語に分割します。');
ja_wakachi
-----------------------------------------------
日本語 の テキスト を 単語 に 分割 し ます 。テーブル作成、データ登録
$ psql -h 127.0.0.1 -U postgres
# create database test_textsearch1;
# create table textsearch1 (
id integer not null,
body text,
primary key (id)
);
# create index on textsearch1 using gin (to_tsvector('japanese', body));
# insert into textsearch1 (id, body) values (0, '日本語のテキストです。');
# insert into textsearch1 (id, body) values (1, '英語のテキストではありません。');
# insert into textsearch1 (id, body) values (2, 'フランス語のテキストではありません。');
# insert into textsearch1 (id, body) values (3, '日本語の文章です。');
# insert into textsearch1 (id, body) values (4, '英語の文章ではありません。');テーブル検索
単純な検索の場合
# select * from textsearch1 where to_tsvector('japanese', body) @@ to_tsquery('japanese', ' 日本語');
id | body
----+------------------------
0 | 日本語のテキストです。
3 | 日本語の文章です。複数ワードでのAND検索の場合
# select * from textsearch1 where (to_tsvector('japanese', body) @@ to_tsquery('japanese', '日本語')) and (to_tsvector('japanese', body) @@ to_tsquery('japanese', 'テキスト'));
id | body
----+------------------------
0 | 日本語のテキストです。
PostgreSQL でテーブル定義を確認する方法のメモ。
vector2 テーブルのテーブル定義は \d vector2 で確認できます。
# \d vector2
Table "public.vector2"
Column | Type | Collation | Nullable | Default
--------+------------------------+-----------+----------+---------
id | integer | | not null |
name | character varying(256) | | not null |
vec | vector(1000) | | |
Indexes:
"vector2_pkey" PRIMARY KEY, btree (id)
"vector2_vec_idx" hnsw (vec vector_l2_ops)
Check constraints:
"vector2_vec_check" CHECK (vector_dims(vec::vector) = 1000)
PostgreSQL のベクトル検索のインデックス作成方法のメモ。
ベクトルカラムにインデックスを張ることで、高速にベクトル検索を行うことができます。
1000次元のベクトルのテーブルに10万レコードを登録して検索性能を比較
インデックスを張らない場合の検索実行時間
# select now();
# select id, name, vec <-> '[...]' from vector2 order by vec <-> '[...]' limit 3;
# select now();
now
-------------------------------
2025-02-10 22:41:46.857061+09
(1 row)
id | name | ?column?
-------+-----------------+--------------------
98408 | name_0000098408 | 11.862095295923496
59794 | name_0000059794 | 11.920021563004825
96991 | name_0000096991 | 11.927945292725399
(3 rows)
now
-------------------------------
2025-02-10 22:41:47.403764+09
(1 row)約0.6秒かかっています。
インデックスを張った場合の検索実行時間
# create index on vector2 using hnsw(vec vector_l2_ops);
# select now();
# select id, name, vec <-> '[...]' from vector2 order by vec <-> '[...]' limit 3;
# select now();
now
-------------------------------
2025-02-10 23:00:28.030441+09
(1 row)
id | name | ?column?
-------+-----------------+--------------------
43107 | name_0000043107 | 11.891565593957367
93189 | name_0000093189 | 11.940329011764277
29278 | name_0000029278 | 11.961626368144666
(3 rows)
now
-------------------------------
2025-02-10 23:00:28.111582+09
(1 row)約0.1秒で検索結果を取得できるようになりました。
インデックス作成方法
/* コサイン */
create index on {table名} using hnsw ({column名} vector_cosine_ops);
/* L2 距離 */
create index on {table名} using hnsw ({column名} vector_l2_ops);
/* 内積 */
create index on {table名} using hnsw ({column名} vector_ip_ops);
