タグ付けアプリについて - moririn2528’s blog

タグ付けする Web サイト(ブックマーク機能)を製作している。そのサイトのバックエンドを担当した。

何かしらの Web サイトを作りたいと思い、友人にどのようなサイトが欲しいか聞いたところ、タグ付けサイトが上がったため製作することとなった。このサイトのフロントエンドは別の友人が製作している。

基本的な機能は、ユーザー登録、ログインして、文献、URL にタグをつける、そして、タグを与えると、そのタグが付いた文献を表示する、というものである。

以下話すことがある部分について書く。

タグの検索機能を付けた。

最初は prefix が一致するものをすべて返す、という実装。

これだと 1 文字間違えると候補として出ない。また、真ん中の単語だけを覚えていたとしても検索できない。

これらの対処法として、2 グラムを用いた。また、検索単語、タグ名の 2 グラムで一致するものの数を類似度とし、類似度が大きいものから順に出力することにした。

文字の並びの情報をある程度保持している
検索単語とタグ名が同じの時、類似度は文字列の長さを n とすると n-1 になる。そして、類似度 n-1 のタグは、文字列が小さいとき文字列内で同じ文字が使われることは少ないので、多くの場合で検索単語と同じといえる。
編集距離 1 (1 文字削除、追加、置換) による類似度の減少は高々 2 であるので、類似度が高いものは検索単語に近いと示される
タグ名、検索文字列は数文字から十数文字と考えられる。よって、3 グラム以上にすると検索効率が落ちると思われる (例えば、検索単語 5 文字で真ん中の単語が違うとき検索結果は意味がなくなるため)

今回、データベースから検索するユーザーが登録したタグすべてを取ってきて、それぞれのタグに対し類似度を調べ、ソートしている。計算量は検索単語文字列長 m、タグ名の平均文字列長 n、タグ数 t とすると O(nmt)

タグ名をランダムなアルファベット 20 文字とし、10 万個のタグを登録した上で検索する。

3 文字以上の連続部分文字列であれば、上位 3 つのうちに正しいタグが出る。また、5 文字の連続部分文字列の 3 文字目を置換して検索しても上位 3 つのうちに正しいタグが出る。

これらから、検索機能はうまくいっているといえる。

検索文字列が 5 文字のとき、データベースからタグ名取得、上記アルゴリズム、それ以外の処理、それぞれの時間を計測し平均すると、0 ms, 365 ms, 1 ms になった。

高速化を行う。

検索文字列の 2 グラムを map に保存する、これで計算量は O(nt) となる。実際、時間を計測すると 110 ms になった。

タグ名の 2 グラムをテーブルに保存すると、アルゴリズムの計算時間はさらに小さくなるが、データの大きさが増える上、取ってくるときの時間がさらにかかる。データベースの無料枠が小さいのも相まって、この方法は取らないことにした。

ログイン機能を付けた。ID、パスワード、メールアドレスを登録すると、そのメールアドレスに認証メールが届く。その後、認証メールに記載されたリンクに行くと認証されて、ログインすることが可能となる。

ログインすると、一時的な ID を発行、その ID で他の関数を使うことが可能となる。

こういう機能を付けるのが初めてだったので、どういう構造にするべきかかなり悩んだ。JWT 認証とかも考えたが、結局使わなかった。

まとめ

これらによって、Go 言語、MySQL に慣れ、バックエンドに触れることができた。しかし、このアプリはまだ多くのユーザーに使われていない、同期処理などもしておらず、実際にたくさんの人に使われたらどうなるのかわからないという問題点がある。