2009-09-12
Alcor の Abbreviation Scoring
同僚の生産性ツール愛好家が熱に浮かされて言った. "QuickSilver の検索がすごいんだよ!" どう凄いのかというと, たとえば "Skype を検索するのに <sp> でいい!" らしい. それは凄いのかも.
私もいちおう QuickSilver を使っているけれど, 素敵機能の類はまったく活用していない. だいたい私の使うアプリケーションはどれも一文字で特定できる. Firefox, Emacs, iTerm, Activity Monitor... そういえば iTunes は iTerm と被ってる. ためしに <iu> と打ってみたら iTunes にマッチする. なんとなく凄い気がしてきた.
同僚はこのアルゴリズムが気になるらしい. 編集距離の仲間かとも思ったけれど, 違う気がする.
とりあえずぐぐってみたところ, QuickSilver は 2007 年に オープンソース 化していた. これなら話が早い. 中身を見てみよう. 幸いこのアルゴリズムを JS に移植した先人 LiquidMetal のページからオリジナルコードへのリンクがあった. (NSString_BLTRExtensions.m) これを読めばいいらしい.
ruby で AbbreviationScorer
関数は NSString の category として実装されている. self がマッチ対象の文字列 (例:"iTunes") で, 比較用のパターン (例:"iu") を引数にとる. そして文字列ととパターンの一致度をあらわした実数のスコアを返す. 関数名は NSString#scoreForAbbreviation(), 実装したのは Alcor さん. このアルゴリズムは Alcor の Abbreviation Scoring と呼ぶことにしよう.
元のコードは Objective-C で若干しんどい. アルゴリズムはそのままで ruby に直してみた.
class AbbreviationScorer def initialize(toscore) @toscore = toscore @td = toscore.downcase end def compute(abbreviation) return 0.9 if abbreviation.empty? return 0.0 if @toscore.size < abbreviation.size ad = abbreviation.downcase (0 ... ad.size).inject(nil) do |a, i| a or score_for(ad, ad.size - i) end or 0.0 end private def score_for(abbreviation, pivot) ahead = abbreviation[0, pivot] atail = (abbreviation[pivot .. -1] or "") found = @td.index(ahead) return nil unless found tail = (@toscore[found + pivot .. -1] or "") tail_score = AbbreviationScorer.new(tail).compute(atail) return nil unless 0 < tail_score point = (found + pivot) - penalty(found) return (point + tail_score*tail.size)/@toscore.size end def penalty(found) return 0 if 0 == found skipped = @toscore[0, found] if /\s$/ =~ skipped nws = skipped.scan(/\s/).size return (nws + (skipped.size - nws)*0.15) elsif /^[[:upper:]]/ =~ @toscore[found .. -1] nuc = skipped.scan(/[[:upper:]]/).size return (nuc + (skipped.size - nuc)*0.15) else return skipped.size end end end
動かしてみる:
def print_score(str, pat) width = str.size < 8 ? 5 : 12 printf("%-#{width}s <- %-5s = %f\n", str, pat, AbbreviationScorer.new(str).compute(pat)) end print_score("hello", "h") print_score("hello", "he") print_score("hello", "hel") print_score("hello", "helo") print_score("hello", "hello") print_score("hello", "llo") print_score("hello", "lo") print_score("hello", "ho") print_score("hello", "hx")
結果:
capricious:ascore omo$ ruby ascore.rb capricious:ascore omo$ ruby ascore.rb hello <- h = 0.920000 hello <- he = 0.940000 hello <- hel = 0.960000 hello <- helo = 0.800000 hello <- hello = 1.000000 hello <- llo = 0.600000 hello <- lo = 0.400000 hello <- ho = 0.400000 hello <- hx = 0.000000
それっぽいかんじ. なお, 私の手抜きと可読性の都合で性能はよくない. オリジナルは NSRange で部分文字列を表現し, 文字列のインスタンス化を避けている. けれど↑ではじゃんじゃかやっている. ちゃんと作るときは元のからぱくることをお勧めします.
アルゴリズム
基本的なアイデアは, 比較文字列 (abbreviation) を語のプレフィクスのリストだと解釈しなおす こと. たとえば "CUR" という abbreviation があったとして, これは "CUR" というプレフィクス一つかもしれないし (CURry), "CU と R" という二つのプレフィクスかもしれないし (CUrry Restrant) , "C と UR" かもしれないし (Curry URbanization), "C と U と R" かもしれない (Curry Unification Registance). abbreviation=略語は何かの語のプレフィクスのリストを連結したものだというわけ.
こうしたプレフィクス化のパターンを列挙して順に試していき, 対象の文字列とマッチすれば=(対処の文字列の略語と見なせるパターンがあれば) その一致具合(=スコア)を返す. スコアは, 対象の文字列が略語としてそれっぽいほど高くなる. どの略語にも含まれない文字が比較対象の文字列に含まれると減点され, 略語に含まれている文字が比較対象の文字列に含まれていないと失格する.
常に全てのパターンを試すわけではなく, 一致するものが見つかったらその場で試行を打ち切るのは面白い. 性能の都合なのか, 先頭に近い側を優先するのが使いやすいのか.
スコア計算の小細工
スコアの計算は, 対象文字列を一文字ごとに評価して, 合計を正規化するかんじ. プレフィクスに一致した文字のスコアが 1 点(満点), 略されたらしい部分が 0.9 点, 略語として解釈できずスキップした文字 (対象が "hello", abbreviationが "l" のときの "he" の部分) は 0 点と数える.
0 点になるはずのスキップ文字を底上げするロジックが面白い. まず, プレフィクスにマッチした直前に空白文字があったとき, 対象文字列は文章だとみなされるらしい. このモードでは, 単語の区切りにある空白だけが 0 点になる. 空白以外の文字は 0.85 点扱い. 同様に, マッチの先頭が大文字だった場合, それは CamelCase と見なされるらしい. そして大文字だけが 0 点で, 小文字は 0.85 点と数えられる.
print_score("how_are_you", "ay") print_score("how are you", "ay") print_score("howareyou", "ay") print_score("HowAreYou", "ay")
結果:
how_are_you <- ay = 0.345455 how are you <- ay = 0.731818 howareyou <- ay = 0.422222 HowAreYou <- ay = 0.800000
複数語からなる長いファイル名を減点しすぎない仕組みなんだろうね.
絞りこみ
このアルゴリズムは, abbreviation が長くなると遅くなるのが目に見えている. 文字列長が N のとき, プレフィクスのリストとして解釈できるパターン数は 2^{N-1}. (...だとおもう. たぶん.) 個々のプレフィクス長は N より小さいから指数的というと誹謗中傷の恐れがあるけれど, それなりに重いのは確かだろう.
幸い実際の N はそれほど大きくない. (私の場合は大半が 1 で, 多くても 3.) また QuickSilver の実装はインクリメンタルサーチをうまく使い, 一文字入力の時点で検索した結果だけが二文字目が与えられた時の検索対象になる. 3 文字目以降も同じ. スコアが 0 点の文字列 (略語に一致しない文字を含む文字列) は どんどん検索対象から外れるので, 個々のスコア計算が重くなってもなんとかなるということなのだろう. GUI とアルゴリズムに一体感があってかっこいい.
まとめ
QuickSilver が実装している Alcor の Abbreviation Scoring は 略語のメタファをコードで実現する素敵アルゴリズムでした. あらあらかしこ.