Alcor の Abbreviation Scoring

2009-09-12

同僚の生産性ツール愛好家が熱に浮かされて言った. "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 は略語のメタファをコードで実現する素敵アルゴリズムでした. あらあらかしこ.