mysqlで疑似的にtrieを実現する方法

mysqlで疑似的にtrieを実現する方法のメモ。

ウェブサービスで、処理対象とする URL が何らかの除外したい URL に前方一致でマッチするかを判定したい場合、
除外URLの数が多い場合、効率よく判定を行う必要があります。

例えば、test.com/abcdef/ghi が mysql に登録されたURLにマッチするかを調べる場合、
以下のような select 文で前方一致の検索を行うことができます。

select * from {table名} where 'test.com/abcdef/ghi' like concat({URLのカラム名}, '%');

しかし、上記の select 文では、mysql に登録されている各レコードの URL カラムに対して
前方一致で文字列マッチの判定が行われ、レコード数分の検索が行われることになります。
そのため、レコード数に応じて処理速度が低下します。


以下は、mysql で trie 相当の機能を実現する方法案です。
ある URL が、除外したい URL にマッチするかどうかの判定を行う例で考えます。

まず、除外URL に URL に使用されない文字を追加して固定文字列長の URL を生成します。
例えば、除外URL の文字列長が15文字で、除外 URL が test.com/abc の場合、
URLに使用されない文字として '@' を追加して以下のような文字列を生成し、DBに登録します。

test.com/abc@@@

判定対象の URL (= 'test.com/abcdefg') が除外対象の URL かを判定するために、
以下の検索式でテーブルを検索します。

select * from {テーブル名} where {URLのカラム名} regexp '^t[e@][s@][t@][\.@][c@][o@][m@][/@][a@][b@][c@][d@][e@][@f][@g]';

正規表現の ^ で URL の文字列の先頭にマッチさせ、次の t は URL の先頭文字列です。
前方一致でのマッチを行うため、一文字目は判定対象の URL の先頭文字の t が
必ず入っていることを想定しています。

次の [e@] は "test.com の e または 使用されない文字 @" にマッチする場合で、
前方一致の URL として te または t@ が登録されている場合にマッチします。
t@ にマッチするのは前方一致の URL が t のみの場合で、DBに登録された値が "t"+"@"x15 の場合に相当します。
[s@] 以降も同様です。


以下、検証です。

URLのテーブルとして、以下を定義して適当にテスト用のURLを登録します。

create table url_trie_test (
       url   varchar(512) not null,
       index(url)
);

そして、以下の explain を実行します。

explain select * from url_trie_test where url regexp '^t[e@][s@][t@][\.@][c@][o@][m@][/@][a@][b@][c@][d@][e@][f@][g@][h@][i@][j@][/@][k@][l@][m@]'\G

すると、explain の結果は以下のようになり、インデックスが使われた検索になっているようです。

  select_type: SIMPLE
        table: url_trie_test
         type: index
possible_keys: NULL
          key: url
      key_len: 514
          ref: NULL
         rows: 2691
        Extra: Using where; Using index

前方一致の url として約2700件が登録されている状態で、上記の select 文を実行すると、以下のようになりました。

mysql> select * from url_trie_test where url regexp '^t[e@][s@][t@][\.@][c@][o@][m@][/@][a@][b@][c@][d@][e@][f@][g@][h@][i@][j@][/@][k@][l@][m@]'\G
*************************** 1. row ***************************
url: test.com/abc@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1 row in set (0.08 sec)

mysqlのインデックスを使って、疑似的に trie の検索ができているようです。

pip でバージョンを指定してパッケージをインストールする方法

pip でバージョンを指定してパッケージをインストールする方法のメモ。

pip install パッケージ名==バージョン

例えば、以下のように使います。

$ pip install nmslib==1.6.3
Collecting nmslib==1.6.3
  Downloading https://files.pythonhosted.org/packages/56/02/83e77d9cbe5a8e3593c06974331b548e61f161b8af7f91b21399161e5366/nmslib-1.6.3.tar.gz (366kB)
...

JavaScriptでURLを変更する方法

JavaScriptで現在表示中のページのURLを変更する方法のメモ。

以下、chrome の console での実行例。

> location.href
"https://blog.goo.ne.jp/dak-ikd/e/6c246c6c31d0f460e73ed0f98ff097a4"  <-- 現在のURL

> history.replaceState(null, null, "https://blog.goo.ne.jp/dak-ikd/e/a2f41210278a671fc272fa97b405d6e2?fm=entry_awc")
undefined

>location.href
"https://blog.goo.ne.jp/dak-ikd/e/a2f41210278a671fc272fa97b405d6e2?fm=entry_awc" <-- 変更後のURL