Parse Tree Dynamic Visualization

多忙だったこともあり、久しぶりのエントリとなってしまいました。

さて、Gmailのメッセージ検索にはダッシュ(-)、OR演算子および括弧が用意されています。これらの演算子は大変便利で、強い依存性があるように思います。それぞれの演算子の用法は大変簡潔ですが、実によく練られており、使いやすく、何より直感的なのです。

同様の構文を様々な場面で用いることが出来たらよいなと思い、解析木を構築するプロトタイプを実装してみました。構築した解析木を視覚的に確認するため、JavaScript + Prototype.js + Canvasの組み合わせを用いました。

Filterフィールドに検索語句群を入力するにつれ、構築した解析木をCanvasに動的に描画します。検索語句間にはスペースを入力します。OR演算子はGmailに習い、大文字で入力することにしました。また、構築された解析木を元にカリー化した関数オブジェクトを生成し、Contentフィールドに入力されている文字列とマッチするか否かを表示します。

また、Show Preorder Indexesオプションを有効とした際、解析木の行きがけ順の順序を描画するようにしています。

元来論理積演算子であるANDは存在しませんが、視覚化された解析木の説得力が増すため木の一部となるようにしています。

解析木のレイアウトには、アルゴリズムC 第3巻の第44章、総当たり検索の章に掲載されている木の配置に用いられている(であろう)アルゴリズムを用いています。

以前、アルゴリズムCにおける二分木の配置アルゴリズムを解説しましたが、節点が節点を二つ以上持つ木での配置はこれよりも多少複雑です。具体的には、節点数を変数の数とする連立一次方程式を立て、それを解くことで導きます。つまり、この問題は線形計画問題の一種と言えます。線形計画問題と言っても一次方程式群に不等式が含まれないため、連立一次方程式を解くこと自体はそんなに難しいことではありません。

線形計画問題を解く過程では行列を利用することが多いです。行列の要素数は木の節点数のほぼ二乗に比例するため、複雑な木を扱った場合、なかなか巨大な行列となります。しかし、この問題の場合、巨大な行列といってもほとんどの要素が0である疎な行列となるため、連立一次方程式を解くのにはさほど時間はかかりません。そのため、即時にCanvasへの描画を開始することを可能としています。

元々、論理積演算子を明記しないことに由来すると思われますが、この構文で特筆すべきは、OR演算子による論理和演算の優先順位が論理積演算の優先順位よりも高いことが挙げられるかと思います。そのため、論理積演算を優先する場合、以下の図に示すように明示的に括弧を追加する必要があります。