Macを持ってない人がMacを使ってみたいと思うキラーソフトがいくつかあります。プレゼンソフト「Keynote」やウィンドウ整列ソフト「Expose」が代表格でしょう。そして，アプリケーションやファイルを開くことからiTunesの操作，Twitter投稿までが数回のキータイプで行える「QuickSilver」もその一つでしょう。

この記事では，QuickSilverで実現している「タイプされた文字から適切なアプリケーションを特定する」操作に使われているアルゴリズム「AlcorのAbbreviation Scoring」について解説しています。「⁠Alcor」は，このアルゴリズムを実装した人の名前です。QuickSilverはGoogle Codeにてオープンソース化されており，このアルゴリズムはJavaScriptやPython，Emacs Lispなど，さまざまな言語にポーティングされています。

記事では元のObjective-CのコードをRubyに書き直して解説しています。全体のコード量は50行に満たない小さなものです。重要な部分は，ユーザが入力した文字列である比較文字列（abbreviation）を，「⁠何かの語のプレフィックス（接頭辞）のリスト」と解釈するところです。

たとえば「CUR」と入力した場合，次のような語のプレフィックスと解釈できます。

• CURry
• CUrry Restaurant
• Curry URbanization
• Curry Unification Registance

そしてこれらのパターンを順に試していきマッチすれば，そのスコアを返します。スコアは1文字ずつ計算され，最終的に0～1の間で表します。スコア計算もいくつか工夫がしてあり，マッチした対象文字列が空白で区切られた単語群であったりCamelCaseであったりする場合には特別な計算が行われます。

長い文字列が入力され，すべてのパターンについて調べていくとなると相当な時間がかかるのではと想像してしまいますが，実際は一致するものが見つかった時点で止めたり，1文字入力の時点で検索した結果だけを2文字目が与えられたときの検索対象にしたりなど，コストがかからない工夫を施してあります。

このアルゴリズムは，少ないタイプ数で目的の操作が行えるインタフェースに最適と言えます。iPhoneやAndroidなどの携帯端末でも大いに活躍しそうです。

似たようなインタフェースはほかのソフトでも実現されているので，実装の違いを調べてみるのもおもしろいでしょう。ちなみに，「⁠FirefoxのロケーションバーでのURL補完機能も似ていたな」と思って調べてみたら，単にSQLiteをLIKE検索していただけでした。

URL：http://steps.dodgson.org/?date=20090912