何とは言わない天然水飲みたさ

探すな、絞り込め / 或いは階層化されたタグの話

カテゴリとタグ

不便なカテゴリ機能とタグ機能

大抵のブログサービスには「タグ」や「カテゴリ」といった機能がある。 (場合によっては「ラベル」とかの名前になっているかもしれない。) タグは階層化不可能で複数指定可能、カテゴリは階層化可能で複数指定不可能な場合がほとんどだ。

しかし、この仕様はまともだろうか?

たとえばC++に関する記事に「C++」と「プログラミング」のタグが両方付いていたら、どう考えても冗長だ。 C++というタグから、それがプログラミングにも関係あるということは自動的に察せられるべきである。 かといって、これをカテゴリ化すると、今度は他のカテゴリ(たとえば「サークル活動/ゲーム開発/完成物紹介」とか?)を使うことができなくなってしまう。

この状況を解消する方法は存在する。 カテゴリを複数指定できるように、或いはタグを階層化できるようにしてしまえば良い。 どちらにしろ本質的には同じことだ。

機能 複数指定 階層化
カテゴリ ×
タグ ×
そもそも別の機能として存在する必要があるのか?

パス中のカテゴリ

パス(URLのホスト部以降)にカテゴリを使っているケースはよく見掛けるが、カテゴリを1つに限定するのはそのせいもあるだろう。 ひとつの記事に複数のURLを割り当てると、(場合によるが)扱いが面倒だし、なによりユーザが記事の同一性を判定できなくなってしまう。

しかし、URLを記事ごとに一意に決めるのであれば、そもそも複数の選択肢のある情報を使うべきでない。 そういった理由もあり、このブログではURLにカテゴリやタグなどは一切使わず、日付と記事の名称のみで決定している。 そして、その仕様ゆえに、このブログではタグを階層化し複数指定可能にすることで、検索性を向上させた。

カテゴリとタグが本来表現したかったもの

では、カテゴリとタグは本来何を表現するのに適しているのか。

そもそもカテゴリにおける階層構造は、包含関係を表現している(そうなるように使うべきである)。 「A/B/C」というカテゴリがあればA⊃B⊃Cであると、多くの人は暗黙に了解しているはずだ。 (これはカテゴリがURLに使われる場合があることからも読み取れる。) ということは、単一のカテゴリ指定では、そのトップレベルノードの表現するものの外にあるものを指定できないということである。

逆に、階層化されていないタグは、理想的には独立であるべきだろう。 ここでいう独立というのは、共通部分が存在しないということでなく、互いの関係が希薄か皆無ということである。 (共通部分が存在しないのであれば、それは同じ分野内での排他的な分類である可能性が高い。) 或いは、直交と言ってもいいかもしれない。 タグはそれぞれ直交しており、それらが張る空間が、絞り込みに利用されるメタ情報の全体である。

このように考えると、カテゴリは特定の空間の中を、そのカテゴリに関連するテーマで絞り込むもので、タグは異なる空間同士の共通部分を、一方の分類とは関係ない基準で絞り込んで選択するものである、と捉えられる。

階層化されたタグの用法

わざわざ書くようなことではないが、タグを記事の集合として扱えばいい。 ……そんなのは誰だって思い付くことで、本当の問題は集合を指定しておきながら検索として集合演算を実装していないということだ。

具体例で説明しよう。 C++についての記事を調べたいが、Windows環境での話を除外したいとしよう。 集合で考えるなら、これは単純な差集合である。 しかし、単一のタグによる記事の一覧であったり、複数タグによるANDのような、シンプルな検索しか実装されていない場合、このような差集合の演算は通常の手段では不可能である。

一方、既存の(Googleのような)キーワードによる検索でも、このような検索は難しい。 「c++ -windows」のようなキーワードで調べれば、Windowsが本題ではないが本文で言及されている場合さえも排除してしまうからだ。 本文からの検索では、文字列の出現に関しては細かく指定できても、内容そのものについて精度良く検索することは難しい場合がある。

すなわち、タグ機能を有効に活用するためには、集合演算(最低でもunion, intersection, difference)によるタグ指定の実装は必須なのである。 これらの機能を欠いたタグ機能など、片手落ちだ。

このブログでのタグ機能

偉そうに語ったところで、このブログでのタグの実装(2016/04/30時点)がどのようなものか説明する。 詳しくはこのブログでのタグ検索ページを見るのが早いだろう。

子孫タグ

カテゴリや階層化されたタグの親子関係が集合の包含関係にあたることは前述の通りだが、逆に言えば、 特定のタグを持つ記事を抽出しようとしたとき、そのタグ(が表現する記事の集合)が包含するタグについても同時に抽出できるのが望ましいということになる。

このブログでは、その機能をexact, descrendant, exact_or_descendantクエリによって指定させることにした。 順に「深さに過不足なく、与えられたタグ自体が指定された記事」、「与えられたタグの子孫タグが指定された場合」、「与えられたタグ自体か、その子孫タグが指定された場合」を抽出する。

名前が長いので縮めた方が良さそうだとは思っているが、良い略が思い浮かばず放置されている。

タグに対する集合演算

このブログでのタグ検索では、もちろん差集合を含めて集合演算を実装した。 or, and, xor, differenceの4つだ。 これらの機能があれば、それなりに精度の良い検索ができるだろうと考えている。

xorはor, and, differenceの3つで表現可能だったが、どうせならネイティブで動かした方が早いしそんなに実装コストも大きくなかったため、とりあえず実装した。 使い道があるのかには疑問が残るが。

これらも割と頻繁に使われそうな気がしないでもないので、略として記号(|とか&とか)を使えるようにするべきかもしれない。

JSONによる検索クエリ

本当はツリービューのUIとかD&Dとかを用意して、マウスでポチポチ指定できるようにするべきだったのだろうが、検索コードを書いたら力尽きた。 べつに私はLISPerというわけではないが、どうせ頭の中で木構造を思い浮かべるのなら、最初から木構造を直接書けるようにしておくのが合理的だろう、と思ったのも特別なUIを用意しなかった理由でもある。

補集合は全体集合にのみ許される

この仕様の決定には少々悩んだ。 検索クエリをそのまま論理式として読み取れば、NOT演算に相当するものがあってもおかしくないからだ。

検索の実装の候補には2種類あって、ひとつはクエリを単一の論理式として組み立て、最後に全記事に対してその論理式でフィルタをかける方法。 もうひとつは、クエリそれぞれが集合か集合演算を表現するものとし、そのままjavascriptでも集合演算を行う方法だ。

前者の方法では、検索にかかる時間は、ほとんど記事数に比例すると考えられる。 ブログ全体での記事が増えると、たとえ単純なクエリであっても複雑なクエリであっても、該当記事数に関係なく時間がかかることになる。

対して、後者の方法では、該当記事の少ないタグやクエリを使えば、その分だけ演算量は少なくなる。 該当記事が少ないということは、それだけ限定された詳しい要求があると考えて良いだろうから、そのような目的のはっきりした検索には、大雑把なクエリより速く本命の情報に辿り着いてもらった方が良い。 (要するに、強い要求には良いパフォーマンスで応えた方が、全体的な満足度も高くなるだろうと考えたのである。)

しかし、後者の集合演算でも、補集合(NOT演算)を導入してしまうと、扱う記事数が簡単に膨れ上がってしまいかねず、集合演算による実装の良さを殺してしまうことになりかねない。 よって、概念上は補集合を使いつつ、実装では演算に用いる集合の要素数のみにパフォーマンスを影響される、差集合を導入したというわけだ。 無論、クエリ全体の否定は差集合だけではできない(全体集合が必要である)が、勿論同様の理由で全体集合も通常のクエリとして用意したくなかったので、 最後の最後で一度だけ補集合の計算を許すことで、検索クエリの表現力を全く落とさず、計算量を抑え気味の検索ができるようにした。

EcmaScript6のSetクラス

好都合にも、EcmaScript6からはSetクラスMapクラスが実装されているため、記事の集合の表現にはこれを用いた。 しかし奇妙なことに、集合に対する演算は(unionやintersectionでさえも!)実装されていなかったため、配列を経由してfilterしたり結合して、再びその結果の配列をSetにする、といったよくわからない回り道をすることになった。 そのうち標準で実装される日が来るのだろうか……期待したい。