Rubyで作る実験的Quicksilverのようなもの

前回探った、略語(Abbreviation)と関連するテキストを点数付けするアルゴリズムは、Quicksilverの使い勝手を左右する重要な要素の一つだ。とすると、このアルゴリズムを取り込めば、なんちゃってQuicksilverもどきが出来るかもしれない...。と思って、まったく実用的ではないのだけど、実験的なソフトウェアとして試してみた。

作業環境

  • 以下、コード中に半角¥が見える場合は、すべて半角\に置き換える必要があり。

Ruby版 scoreForAbbreviation

  • Stringクラスを拡張して、to_scoreメソッドを追加した。
    • 正規表現を利用して実装した。
    • マッチした部分とその前後の文字列が簡単に取得できるので、Objective-Cよりシンプルに書ける。
    • コードの縦・横が圧縮されて、見通し*1がとても良くなった。
  • たった30行のコードが、略語のスコアリングをしてくれる。
  • ちなみに、_アンダースコアもスペースと同等に評価するようにアレンジした。
class String
  def to_score(abbrev)
    return 0.9 if abbrev.empty?
    return 0.0 if abbrev.size > self.size
    
    abbrev.size.downto(1) do |s|
      match_index = (/#{abbrev[0, s]}/i =~ self)
      next if !match_index
      next if abbrev.size - s > $'.size
      
      # マッチした部分より前pre, マッチした部分match, マッチした部分より後post
      pre, match, post = $`, $~[0], $'
      
      remaining_score = post.to_score(abbrev[s, abbrev.size - s])
      if remaining_score > 0 then
        score = match.size
        if match_index > 0 && /[\s\_]/ =~ self[match_index - 1, 1]
          score += 0.85 * pre.gsub(/[\s\_]/, "").size + 1
        elsif /[A-Z]/ =~ self[match_index, 1] 
          score += 0.85 * pre.gsub(/[A-Z]/, "").size
        end
        score += remaining_score * post.size
        score /= self.size
        return score
      end
    end
    0
  end
  
end
  • テストしてみる。
DATA = [["hello world", "he"], 
        ["hello world", "hw"], 
        ["HelloWorld", "hw"],
        ["helloWorld", "hw"],
        ["HelloWorld", "hlw"],
        ["Helloworld", "hlw"],
        ["Helloworld", "hw"],
        ["hello_world", "hw"],
        ["hell oworld", "hw"]]
DATA.each{|i| printf("%f '%s'.to_score('%s')\n", i[0].to_score(i[1]), i[0], i[1])}

# 以下結果...
0.918182 'hello world'.to_score('he')
0.909091 'hello world'.to_score('hw')
0.900000 'HelloWorld'.to_score('hw')
0.900000 'helloWorld'.to_score('hw')
0.830000 'HelloWorld'.to_score('hlw')
0.660000 'Helloworld'.to_score('hlw')
0.560000 'Helloworld'.to_score('hw')
0.909091 'hello_world'.to_score('hw')
0.509091 'hell oworld'.to_score('hw')
  • うまく動いている!

カタログの準備

  • 略語で検索する目的は、必要最小限の操作で、素早く、アプリケーションや書類を開くことにある。
  • 実装を単純にするために、とりあえずここでは、アプリケーションを素早く開くことを考えてみる。
  • 自分のMacBook環境では、主要なアプリケーションは/Applicationsあるいは/Developer以下に存在する。
  • それらのディレクトリの中から、.app拡張子の付いたアプリケーション名をあらかじめ抽出しておく。でも、ちょっと工夫が必要...。
  • アプリケーションは、Applications直下以外にも、さらにその下にフォルダ分けしてインストールされている可能性もあり、再帰的に検索する必要がある。
  • 但し、OSXのアプリケーションの実態はファイルではなく、パッケージ化されたディレクトリなので、闇雲に階層を深めて検索しても、無駄な時間を浪費してしまう。
  • ターミナルから以下のコマンドでは、結構な時間がかかってしまうのだ。
$ find /Applications/**/*.app
  • そこで、OSXのウリであるSpotlightのコマンド版mdfindを利用してみた。
$ mdfind -onlyin /Applications 'kMDItemFSName == "*.app"' 
  • これなら、許せるスピード感で検索結果が表示された。
  • 欲しいのはアプリケーション名のみ、.app拡張子も不要だ。xargsコマンドを経由して、basenameコマンドで必要なファイル名のみ抽出してみた。
  • OSXのアプリケーション名には、思い切り半角スペースが含まれ、引数区切りの半角スペースと混同してしまう...。
  • そこで、mdfindとxargsに-0(ゼロ)オプションを設定すると、NUL(\0)を区切り文字に利用するようになった。
$ mdfind -0 -onlyin /Applications 'kMDItemFSName == "*.app"' | xargs -0 basename -s .app
  • 上記で抽出したテキストは、ホームディレクトリ直下に~/.catalog.txtとして保存しておくことにした。
$ mdfind -0 -onlyin /Applications 'kMDItemFSName == "*.app"' | xargs -0 basename -s .app > ~/.catalog.txt
$ mdfind -0 -onlyin /Developer 'kMDItemFSName == "*.app"' | xargs -0 basename -s .app >> ~/.catalog.txt

点数計算

  • 上記カタログ~/.catalog.txtのすべての項目に対して、略語"ip"で点数付けしてみた。
  • 経験的に、少なくとも0.7以上でないと無意味な検索結果となりそうなので、0.7未満は削除。
  • 検索結果が多過ぎても迷うだけなので、点数が大きい順に上位20項目を表示するようにした。
WORDS = File.read("#{File.expand_path('~')}/.catalog.txt").split("\n")
scores = WORDS.map{|i| [i.to_score("ip"), i]}.reject{|i| i[0]<0.7}.sort
scores.reverse[0, 20].each {|i| printf("%f %s\n", i[0], i[1])}
  • 実行結果は以下のようになった。
0.933333 iPhoto
0.913333 iPhone Explorer
0.911111 iText Pro
0.905263 iSync Plug-in Maker
0.882558 AirPort Admin Utility for Graphite and Snow
0.854762 FirefoxProfileManager
0.850000 PicLens Publisher
0.850000 AirPort Utility
0.836667 Disk for iPhone
0.827273 Mitaka Plus
0.820000 NicePlayer
0.800000 iSpeech
0.787500 QuickTime Player
0.753226 Adobe AIR Application Installer
0.727273 iExtractMP3
0.722222 SimpleCap
0.700000 ClipMenu
  • 人として有意義なのは、上位4件くらいかもしれない。
  • それにしても、このように評価が見られると面白い!

Rubyで実装するとスピードが問題になるかと思ったが、意外にも、400件ほどのカタログの点数評価は10回繰り返しても、一瞬(1秒未満)で完了。十分実用に耐える。

  • ちなみに、カタログリストを作成する時間は20秒くらい。
  • でも、事前に1回作ってしまえば、毎回実行する必要はないので、耐えられる。

readlineで入力する

  • 現状、略語はコードの中で"ip"固定にしてしまっている。
  • 略語の変更で、その都度コードを修正するのではあまりにも不便だ。
  • readlineを利用すると、簡単に入力を取得できるらしい。
require 'readline'

WORDS = File.read("#{File.expand_path('~')}/.catalog.txt").split("\n")
while buf = Readline.readline("> ")
  scores = WORDS.map{|i| [i.to_score(buf), i]}.reject{|i| i[0]<0.7}.sort
  scores.reverse[0, 20].each {|i| printf("%f %s\n", i[0], i[1])}
end

参考ページ(たいへん参考になりました。感謝です!)

指定したアプリケーションを実行する

  • 点数評価を眺めているだけではやはり満足できなくて、そこから特定のアプリケーションを実行したい。
    • よって、完全一致したアプリケーション名については、実行するようにしてみた。
  • また、表示された点数評価を見て、アプリケーション名を再入力していては非効率だ。
    • readlineの履歴入力を利用して、そこに点数順のアプリケーション名を代入して、矢印キーで選択できるようにしてみた。
    • 履歴入力を利用するには、引数にtrueを追加するだけでOK。Readline.readline("> ", true)
    • Readline::HISTORY.push(*items)のように、展開した配列*itemsを引数に指定すれば、インデックス順のテキストが履歴に設定された。
while buf = Readline.readline("> ", true)
  scores = WORDS.map{|i| [i.to_score(buf), i]}.reject{|i| i[0]<0.7}.sort
  next if scores.empty?
  
  items = scores.map{|i| i[1]}
  Readline::HISTORY.push(*items)
  if scores.last[0] == 1
    puts "open -a '#{items.last}'"
    `open -a "#{items.last}"` 
  else
    scores.reverse[0, 20].each {|i| printf("%f %s\n", i[0], i[1])}
  end
end
  • ついでに、補完機能も簡単に利用できることがわかった。
  • 以下のように、Readline.completion_procに、補完する値の配列を返すprocを定義すればOK。
  • これで、入力途中にtabキー2度押しで、補完リストが表示される。
Readline.completion_proc = proc do |word|
  WORDS.grep(/\A#{Regexp.quote word}/i)
end
  • ここでもQuicksilverアルゴリズムを試してみた。しかし...
    • たとえ点数順に配列を返すようにしても、補完リストはABC順で表示されてしまった...。(配列順をキープする方法はあるのだろうか?)
    • それでは使い難いので、補完については単純に前方一致で表示するようにしておいた。
    • 単純な前方一致とQuicksilverアルゴリズムの違いを感じられて良いかもしれない。

トップスコアのアプリケーションをデフォルトの入力値として表示する

  • 最後の仕上げは、検索結果で最高得点のアプリケーションをデフォルトの入力値として表示しておけば、さらに楽が出来るかもしれない。
    • Quicksilverの経験上、トップスコア=目的のアプリケーションであることが多い。
    • その場合、続けてreturnキーを押すだけで、素早く目的のアプリケーションが起動できる。
    • 矢印キーを1回余分に押すかどうかの僅かな違いだが、何度も繰り返すことなので快適さが向上するかも。
  • 直前の履歴をデフォルトの入力値とする方法は、↑上矢印キーを押す方法しか思い付かなかった。
  • そこで、RubyからAppleScriptを実行して、↑上矢印キーを押すことにした。
module AppleScript
  def self.key_code(num)
    code = <<EOC
tell application "System Events"
tell process ""
key code #{num}
end tell
end tell
EOC
    `osascript -e '#{code}'  > /dev/null 2>&1 &`
  end
end

AppleScript.key_code(126) # ↑上矢印

コード全体

  • 以上のコードを一つにまとめると、以下のようになった。(ファイル名:to_score.rb)
  • カタログの自動生成機能を追加した。
require 'readline'

class String
  def to_score(abbrev)
    return 0.9 if abbrev.empty?
    return 0.0 if abbrev.size > self.size
    
    abbrev.size.downto(1) do |s|
      match_index = (/#{abbrev[0, s]}/i =~ self)
      next if !match_index
      next if abbrev.size - s > $'.size
      
      # マッチした部分より前pre, マッチした部分match, マッチした部分より後post
      pre, match, post = $`, $~[0], $'
      
      remaining_score = post.to_score(abbrev[s, abbrev.size - s])
      if remaining_score > 0 then
        score = match.size
        if match_index > 0 && /[\s\_]/ =~ self[match_index - 1, 1]
          score += 0.85 * pre.gsub(/[\s\_]/, "").size + 1
        elsif /[A-Z]/ =~ self[match_index, 1] 
          score += 0.85 * pre.gsub(/[A-Z]/, "").size
        end
        score += remaining_score * post.size
        score /= self.size
        return score
      end
    end
    0
  end
  
end

module AppleScript
  def self.key_code(num)
    code = <<EOC
tell application "System Events"
tell process ""
key code #{num}
end tell
end tell
EOC
    `osascript -e '#{code}'  > /dev/null 2>&1 &`
  end
end

CATALOG = "#{File.expand_path('~')}/.catalog.txt"
unless File.exist?(CATALOG)
  puts "カタログ作成中..."
  `mdfind -0 -onlyin /Applications -onlyin /Developer 'kMDItemFSName == "*.app"' | xargs -0 basename -s .app > ~/.catalog.txt`
  puts "カタログ作成完了"
end
WORDS = File.read(CATALOG).split("\n")

Readline.completion_proc = proc do |word|
  WORDS.grep(/\A#{Regexp.quote word}/i)
end

while buf = Readline.readline("> ", true)
  scores = WORDS.map{|i| [i.to_score(buf), i]}.reject{|i| i[0]<0.7}.sort
  next if scores.empty?
  
  items = scores.map{|i| i[1]}
  Readline::HISTORY.push(*items)
  if scores.last[0] == 1
    puts "open -a '#{items.last}'"
    `open -a "#{items.last}"` 
  else
    scores.reverse[0, 20].each {|i| printf("%f %s\n", i[0], i[1])}
    AppleScript.key_code(126) # ↑上矢印
  end
end
  • ターミナルから、Rubyで実行して利用する。
$ ruby ~/to_score.rb


快適なQuicksilverの検索アルゴリズムを身近に感じられるかも。

*1:Objective-Cのコードは、長いラベル名・長い変数名によって、メソッド呼び出しがとても長くなりがち。英語が苦手な自分にとって、コードの見通しがとても悪くなる。