Quicksilverは如何にして鋭い検索を行っているのか？

Quicksilverの検索性能が、感性をくすぐってきた。

「apple」→「AppleScript Editor」
「ase」→「AppleScript Editor」
「prol」→「Property List Editor」
「im」と入力して、「Image Capture」を起動したいが、「iMove」がトップヒットになってしまう...。
- そんな状況でも、候補リストから2回連続で「Image Capture」を選択すれば、3回目以降は「Image Capture」がトップヒットになる。
- 直近のユーザーの好みを学習してくれるのだ。
- もちろん、「ima」まで入力すれば「Image Capture」がトップヒットになる。

「ase」「prol」のような、単純な前方一致でも、部分一致でもない検索には恐れ入る。しかも、シンプルだけど学習もしてくれる。使うほどに手に馴染んでくる仕組みは、この辺にあるのかもしれない。
それにしても気になるのは、なぜ「ase」で「AppleScript Editor」がトップヒットになるのか？その仕組みが、とっても気になる。
Quicksilverの候補リストには「ase」のあらゆるパターンを含むファイルが300項目もヒットしている。（以下は例）

「Folder Action Setup」
「Audio MIDI Setup」
「PasteboardPeeker」

その中からどのようにして「AppleScript Editor」をトップヒットにしているのか？人間の感覚なら、「単語の切れ目の頭文字を取った意味のある3文字だから」と言ってしまえば、話しは簡単だ。でも、この人間臭い判定をQuicksilverというアプリケーションがコードを実行してやっている、しかも一瞬でとなると、そこに崇高なアルゴリズムを感じる。調べてみた。

ソースコードの在処

現在、Quicksilverはオープンソースとして開発されていた。そのプロジェクトはGoogle Codeで管理されている。
- http://code.google.com/p/blacktree-alchemy/

数あるプロジェクトファイルの中で、目指すソースコード（Objectiv-C）は、以下の位置だと見当をつけた。
- http://code.google.com/p/blacktree-alchemy/source/browse/trunk/Crucible/Code/NSString_BLTRExtensions.m

しかし、自分の技能では、いきなりこのコードを読んで理解するのはかなり厳しい。
毎度のことだが、きっと世界のどこかに先達となる開拓者が居るはず。探してみる。

仕組み

詳細に解説されたページも見つかる。まさに知りたかったことが解説されていた。（感謝です！）

Quicksilverは「el」と入力した瞬間、検索対象のファイル名と「el」の一致度合いの点数付けをしているらしい。
その点数は0から1までの小数で表現される。
- 0は不一致
- 1は完全一致
- 最も1に近い点数を得たテキストが、トップヒットとして表示される。

例：

"hello"を"el"で点数付け

文字列 h e l l o 計 ÷5文字

スコア 0 1 1 0.9 0.9 3.8 0.76

"hello"を"eo"で点数付け

文字列 h e l l o 計 ÷5文字

スコア 0 1 0 0 1 2 0.4

"HelloWorld"を"hw"で点数付け

文字列 H e l l o W o r l d 計 ÷10文字

スコア 1 0.85 0.85 0.85 0.85 1 0.9 0.9 0.9 0.9 9 0.9

文字列	h	e	l	l	o		計	÷5文字
スコア	0	1	1	0.9	0.9		3.8	0.76

文字列	h	e	l	l	o		計	÷5文字
スコア	0	1	0	0	1		2	0.4

文字列	H	e	l	l	o	W	o	r	l	d		計	÷10文字
スコア	1	0.85	0.85	0.85	0.85	1	0.9	0.9	0.9	0.9		9	0.9

なるほど。解説ページから読み取って、以下のように理解した。

原則

検索キーを1文字単位まで分解して、すべての組み合わせで検索する。
但し、相対的な位置関係（語順）は考慮する。
- "hello"に対する"eo"は0.76点だが、
- "hello"に対する"oe"は0点。（左から"e"、"o"の順には並んでいないので）

一致した文字は1点
一致しない文字は0点

条件1

但し、"hello"に対する"el"などを略語と考えれば、後の文字は省略されていると考えて良いはず。
よって、最後に一致した文字以降の残りの部分"lo"は、0点でなく0.9点とする。
- 1点未満にするのは、完全一致との点差を出すためと思われる。
- この条件によって、同じ文字数の一致でも、より先頭に近い文字が、より多く一致した方が高得点になる。
- また、一致した文字数と位置が同じなら、より短い単語の方が高得点になる。（例："Hello"と"Hello World"に対して"h"で点数付けすると、"Hello"の方が高得点）

条件2

さらに、"hello world"に対する"hw"はスペースで区切られた単語の頭文字を取った有意義な略語である。（"ho"よりも"hw"で検索した方が高得点であるべき）
同様に、"HelloWorld"に対する"hw"も大文字で区切られた単語の頭文字を取った有意義な略語である。
そこで、頭文字に挟まれる部分"ello"は、0点とせず0.85点とする。
- 0.9点未満にするのは、"he"で検索した時との点差を出すためと思われる。

実験

英語のページも見つかった。見当をつけたソースコードはどうやら正解だったようだ。

Quicksilverの検索機能を探る目的においては、読み解くべきはNSString_BLTRExtensions.mの以下の3つのメソッドだと理解できた。
NSStringに、scoreForAbbreviationというメソッドを追加することで、文字列と略語の一致度合いの点数付けを実現しているようだ。

主要な処理は、3番目のscoreForAbbreviation:inRange:fromRange:hitMask:メソッドで実行されている。
1番目、2番目のメソッドは、3番目のメソッドを簡単に呼び出すためのラッパー*1である。

- (float) scoreForAbbreviation:(NSString *)abbreviation
- (float) scoreForAbbreviation:(NSString *)abbreviation hitMask:(NSMutableIndexSet *)mask
- (float) scoreForAbbreviation:(NSString *)abbreviation inRange:(NSRange)searchRange fromRange:(NSRange)abbreviationRange hitMask:(NSMutableIndexSet *)mask

こうゆうことは、目と頭で追うだけよりも、実際にコードを動かして検証しながら探る方が分かり易い。

早速、Xcodeを起動して、新規プロジェクト...からCocoa Applicationを作成してみた。（プロジェクト名：abbreviation）
新規ファイル...からObjective-C classを追加した。（ファイル名：NSString_BLTRExtensions.m、同時に"ヘッダーファイル.h"も作成）
QuicksilverのソースコードNSString_BLTRExtensions.hとNSString_BLTRExtensions.mのコードをそのままコピーした。
NSString_BLTRExtensions.m の10行目「import "NSArray_BLTRExtensions.h"」だけは、今回の検証には不要なのでコメントアウトした。
abbreviationAppDelegate.mの18行目「// Insert code here to initialize your application」以下に2行追記してみた。

//
//  abbreviationAppDelegate.m
//  abbreviation
//
//  Created by zari on 10/02/28.
//  Copyright 2010 __MyCompanyName__. All rights reserved.
//

#import "abbreviationAppDelegate.h"
#import "NSString_BLTRExtensions.h"

@implementation abbreviationAppDelegate

@synthesize window;

- (void)applicationDidFinishLaunching:(NSNotification *)aNotification {
    // Insert code here to initialize your application 
    NSLog(@"%f", [@"hello" scoreForAbbreviation:@"el"]);
    [NSApp terminate:self];
}

@end

一旦、保存してから、実行してみる。

...（中略）...
プログラムをデバッガに読み込み中...
プログラムは読み込まれました。
run
[Switching to process 23495]
実行中...
2010-02-28 09:51:24.397 abbreviation[23495:a0f] 0.760000

Debugger stopped.
Program exited with status value:0.

"hello"に対する"el"の一致度合いの点数は、予定どおり0.76と表示された！うまく動いている感じ！

このようにして、一致度合いの点数をいろいろ調べてみた。

[@"hello world" scoreForAbbreviation:@"he"];// => 0.918182//ここは"he"
[@"hello world" scoreForAbbreviation:@"hw"];// => 0.909091
[@"HelloWorld" scoreForAbbreviation:@"hw"];// => 0.900000
[@"helloWorld" scoreForAbbreviation:@"hw"];// => 0.900000
[@"HelloWorld" scoreForAbbreviation:@"hlw"];// => 0.830000//ここは"hlw"
[@"Helloworld" scoreForAbbreviation:@"hlw"];// => 0.660000//ここは"hlw"
[@"Helloworld" scoreForAbbreviation:@"hw"];// => 0.560000
[@"hello_world" scoreForAbbreviation:@"hw"];// => 0.509091
[@"hell oworld" scoreForAbbreviation:@"hw"];// => 0.509091

[@"iMove" scoreForAbbreviation:@"im"];// => 0.940000
[@"Image Capture" scoreForAbbreviation:@"im"];// => 0.915385

[@"for your information" scoreForAbbreviation:@"fyi"];// => 0.912500

様々な"hello world"の一致度合いを比べてみると、Quicksilverのポリシーが見えてくる。
概ね、自分が感じる一致度合いと整合性がある。

コードを追いかける

仕組みは分かったのだけど、果たして、どうやってこれをコードの流れとして実現しているのか？それが一番知りたいところなのだ。

まずはソースコード。読み易いように不要なコメントは削除して、若干、改行などを入れて整形した。

- (float) scoreForAbbreviation:(NSString *)abbreviation 
{
    return [self scoreForAbbreviation:abbreviation 
                              hitMask:nil];
}

- (float) scoreForAbbreviation:(NSString *)abbreviation 
                       hitMask:(NSMutableIndexSet *)mask 
{
    
    //return QSScoreForAbbreviation((CFStringRef) self, (CFStringRef)abbreviation, mask);
    
    return [self scoreForAbbreviation:abbreviation 
                              inRange:NSMakeRange(0, [self length]) 
                            fromRange:NSMakeRange(0, [abbreviation length]) 
                              hitMask:mask];
}

- (float) scoreForAbbreviation:(NSString *)abbreviation
                       inRange:(NSRange)searchRange
                     fromRange:(NSRange)abbreviationRange
                       hitMask:(NSMutableIndexSet *)mask
{
    float   score, remainingScore;
    int     i, j;
    NSRange matchedRange, remainingSearchRange;
    
    if (!abbreviationRange.length) return 0.9; //deduct some points for all remaining letters（残りの文字列から特定の点数を控除する）
    if (abbreviationRange.length > searchRange.length) return 0.0; //検索対象の文字列より、略語（検索キー）の方が長ければ、0を返す

    for (i=abbreviationRange.length; i>0; i--) { //Search for steadily smaller portions of the abbreviation（略語（検索キー）をどんどん小さな固まりにして検索する）
        // 検索対象文字列に、略語（検索キー）が含まれる範囲を検索して、返す
        matchedRange = [self rangeOfString:[abbreviation substringWithRange:NSMakeRange(abbreviationRange.location, i)]
                                   options:NSCaseInsensitiveSearch //大文字小文字関係なく検索する
                                     range:searchRange];
        
        if (matchedRange.location == NSNotFound) continue;
        if (matchedRange.location + abbreviationRange.length > NSMaxRange(searchRange)) continue;
        
        if (mask) [mask addIndexesInRange:matchedRange];
        
        remainingSearchRange.location = NSMaxRange(matchedRange);                               
        remainingSearchRange.length   = NSMaxRange(searchRange) - remainingSearchRange.location;
        
        // Search what is left of the string with the rest of the abbreviation（残りの文字列を、残りの略語で、検索する）
        remainingScore = [self scoreForAbbreviation:abbreviation
                                            inRange:remainingSearchRange
                                          fromRange:NSMakeRange(abbreviationRange.location+i, abbreviationRange.length-i)
                                            hitMask:mask];
        if (remainingScore) {
            score = remainingSearchRange.location - searchRange.location;
            // ignore skipped characters if is first letter of a word（単語の頭文字なら、文字をスキップしない(0点としない)）
            if (matchedRange.location > searchRange.location) {//if some letters were skipped
                j = 0;
                if ([[NSCharacterSet whitespaceCharacterSet] characterIsMember:[self characterAtIndex:matchedRange.location-1]]) {
                    for (j = matchedRange.location-2; j >= (int) searchRange.location; j--) {
                        if ([[NSCharacterSet whitespaceCharacterSet] characterIsMember:[self characterAtIndex:j]]) score--;
                        else score -= 0.15;
                    }
                } else if ([[NSCharacterSet uppercaseLetterCharacterSet] characterIsMember:[self characterAtIndex:matchedRange.location]]) {
                    for (j = matchedRange.location-1; j >= (int) searchRange.location; j--) {
                        if ([[NSCharacterSet uppercaseLetterCharacterSet] characterIsMember:[self characterAtIndex:j]]) score--;
                        else score -= 0.15;
                    }
                } else {
                    score -= matchedRange.location - searchRange.location;
                }
            }
            score += remainingScore * remainingSearchRange.length;
            score /= searchRange.length;
            return score;
        }
    }
    return 0;
}

初めの一歩

まず最初はシンプルに、[@"hello" scoreForAbbreviation:@"el"]が呼び出された場合を考えてみた。
二つのラッパーメソッドを通して、最終的には以下のメソッド呼び出しとして処理が始まる。

[@"hello" scoreForAbbreviation:@"el"];

// 以下のメソッド呼び出しに整形され、点数付けの処理が開始される

[@"hello" scoreForAbbreviation:@"el" 
                       inRange:NSMakeRange(0, 5) // @"hello"の範囲、先頭から5文字分
                     fromRange:NSMakeRange(0, 2) // @"el"の範囲、先頭から2文字分
                       hitMask:nil];

登場する変数

self（検索対象文字列、例：@"hello"）、abbreviation（略語、例：@"el"）、
searchRange（検索対象文字列の範囲、例：{0,5}）、abbreviationRange（略語の範囲、例：{0,2}）、mask（マスク？）
matchedRange（検索で一致した範囲、例：{1,2}）、remainingSearchRange（残りの検索対象文字列の範囲、例：{3,2}）
score（点数、例:0.76）、remainingScore（残りの点数、例：0.9）
i（略語を小さな固まりにする際のカウンター）、j（略語が頭文字の場合に、点数を控除する際のカウンター）

予備知識

NSRangeは、位置と長さを持つ構造体{location,length}。文字列の範囲を指定することに利用している。
NSMakeRange(位置,長さ)は、指定された位置と長さのNSRangeを返す。
NSMaxRange(範囲)は、範囲の最大値、つまり渡された範囲の最後の位置を返してくれる。
- 例：NSMaxRange(NSMakeRange(2,3)) => 5
[[NSCharacterSet whitespaceCharacterSet] characterIsMember:(unichar)文字];は、文字がスペースかタブであればYESを返す。
[[NSCharacterSet uppercaseLetterCharacterSet] characterIsMember:(unichar)文字];は、文字が大文字であればYESを返す。

追跡

ステップ1 - 終了条件

    if (!abbreviationRange.length) return 0.9; //deduct some points for all remaining letters（残りの文字列から特定の点数を控除する）
    if (abbreviationRange.length > searchRange.length) return 0.0; //検索対象の文字列より、略語（検索キー）の方が長ければ、0を返す

コードを読み進むと分かるが、scoreForAbbreviationメソッドは、forループの中で自分自身を呼び出す。
自分自身を呼び出す時は、何らかの終了条件が必要で、それが無いとメモリが許す限り永遠に繰り返してしまうことになる。
この二つのif文は、その終了条件となっている。
- abbreviationRange.length（略語の範囲の長さ）が0の時、0.9を返す。
- abbreviationRange.length（略語の範囲の長さ）がsearchRange.length（検索対象文字列の長さ）より大きい時、0.0を返す。
最初の段階では、@"el"の文字数2、@"hello"の文字数5なので、この条件は成立しない。

ステップ2 - forループと略語検索

    for (i=abbreviationRange.length; i>0; i--) { //Search for steadily smaller portions of the abbreviation（略語（検索キー）をどんどん小さな固まりにして検索する）
        // 検索対象文字列に、略語（検索キー）が含まれる範囲を検索して、返す
        matchedRange = [self rangeOfString:[abbreviation substringWithRange:NSMakeRange(abbreviationRange.location, i)]
                                   options:NSCaseInsensitiveSearch //大文字小文字関係なく検索する
                                     range:searchRange];
        
        if (matchedRange.location == NSNotFound) continue;
        if (matchedRange.location + abbreviationRange.length > NSMaxRange(searchRange)) continue;
        
        if (mask) [mask addIndexesInRange:matchedRange];

for文にabbreviationRange.lengthの値を代入してみる。（最初の段階）
- for (i=2; i>0; i--)
つまり、変数iは、2、1と変化する。

matchedRange = [self rangeOfString:[abbreviation substringWithRange:NSMakeRange(abbreviationRange.location, i) ...];にも値を代入してみる。
- matchedRange = [@"hello" rangeOfString:@"el" ...];
matchedRangeには、文字列"hello"に対して略語"el"を検索して、位置と範囲が代入されるのだ。

見つからなければ、forループの次のステップに進む。（略語を1文字短くして検索してみる）
あるいは、見つかったとしても、残りの略語が見つかる可能性が無い場合も、forループの次のステップに進む。（"hello"に対して"oz"で検索した場合、この条件が成立する）
つまり、略語が"abcd"であれば、"abcd"→"abc"→"ab"→"a"のように、どんどん短い語句で検索を試みることになるのだ。
そして、一致する略語が見つかると、次のステップ3の処理が始まる。

if (mask) [mask addIndexesInRange:matchedRange];では、一致した文字の記録がmaskにどんどん追加されていく。
- でも、自分が試す場合、いつもnilを指定するので、ここの処理はスキップされるのだ。

ステップ3 - 再帰呼び出し

        remainingSearchRange.location = NSMaxRange(matchedRange);                               
        remainingSearchRange.length   = NSMaxRange(searchRange) - remainingSearchRange.location;
        
        // Search what is left of the string with the rest of the abbreviation（残りの文字列を、残りの略語で、検索する）
        remainingScore = [self scoreForAbbreviation:abbreviation
                                            inRange:remainingSearchRange
                                          fromRange:NSMakeRange(abbreviationRange.location+i, abbreviationRange.length-i)
                                            hitMask:mask];

一致する略語が見つかると、残りの検索対象文字列の範囲remainingSearchRangeと、残りの略語の範囲を設定して、scoreForAbbreviationメソッド自身を再度、呼び出す。

例：[@"hello" scoreForAbbreviation:@"el"]であれば、
- 1回目で"el"が一致して、ここでの呼び出しは[@"lo" @""]と同等になる。
- 2回目で終了条件によって、0.9が返ってくる。

例：[@"hello world" scoreForAbbreviation:@"hw"]であれば、
- 1回目で"h"が一致して、ここでの呼び出しは[@"ello world" @"w"]と同等になる。
- 2回目で"w"が一致して、ここでの呼び出しは[@"orld" @""]と同等になる。
- 3回目で終了条件によって、0.9が返ってくる。

このように、終了条件で何らかの値（0.9か0.0のどちらか）が返ってくるまで、ここまでの処理が繰り返し行われることになる。

ステップ4 - 点数付け

        if (remainingScore) {
            score = remainingSearchRange.location - searchRange.location;
            // ignore skipped characters if is first letter of a word（単語の頭文字なら、文字をスキップしない(0点としない)）
            if (matchedRange.location > searchRange.location) {//if some letters were skipped
                j = 0;
                if ([[NSCharacterSet whitespaceCharacterSet] characterIsMember:[self characterAtIndex:matchedRange.location-1]]) {
                    for (j = matchedRange.location-2; j >= (int) searchRange.location; j--) {
                        if ([[NSCharacterSet whitespaceCharacterSet] characterIsMember:[self characterAtIndex:j]]) score--;
                        else score -= 0.15;
                    }
                } else if ([[NSCharacterSet uppercaseLetterCharacterSet] characterIsMember:[self characterAtIndex:matchedRange.location]]) {
                    for (j = matchedRange.location-1; j >= (int) searchRange.location; j--) {
                        if ([[NSCharacterSet uppercaseLetterCharacterSet] characterIsMember:[self characterAtIndex:j]]) score--;
                        else score -= 0.15;
                    }
                } else {
                    score -= matchedRange.location - searchRange.location;
                }
            }
            score += remainingScore * remainingSearchRange.length;
            score /= searchRange.length;
            return score;
        }

終了条件で0.9が返ってくると、再帰呼び出しで保留されていた点数付けの処理が次々に実行される。
逆に、終了条件で0.9が返らない時は、この点数付けの処理は一切行われない。つまり、0点と評価され、略語は含まれないことになる。
ifとforが絡んで長めの処理になっているが、単語の頭文字に対して特別な点数付けをするため。
もし、原則どおりの点数付け（一致すれば1点・一致しなければ0点）しか行わなければ、以下のようにシンプルで理解し易くなる。

例：[@"hello" scoreForAbbreviation:@"el"]であれば、
- "el"が一致した時の計算

        if (remainingScore) {
            score = remainingSearchRange.location - searchRange.location; //score = 3 - 0 = 3
                score -= matchedRange.location - searchRange.location; //score -= 1 - 0 = 1
            score += remainingScore * remainingSearchRange.length; //score += 0.9 * 2 = 1.8
            score /= searchRange.length; //score = 3.8 / 5
            return score; //return 0.76
        }

例：[@"helloworld" scoreForAbbreviation:@"hw"]であれば、
- "w"が一致した時の計算

        if (remainingScore) {
            score = remainingSearchRange.location - searchRange.location; //score = 6 - 1 = 5
                score -= matchedRange.location - searchRange.location; //score -= 5 - 1 = 4
            score += remainingScore * remainingSearchRange.length; //score += 0.9 * 4 = 3.6
            score /= searchRange.length; //score = 4.6 / 9
            return score; //return 0.5111111111...
        }

- "h"が一致した時の計算

        if (remainingScore) {
            score = remainingSearchRange.location - searchRange.location; //score = 1 - 0 = 1
                score -= matchedRange.location - searchRange.location; //score -= 0 - 0 = 0
            score += remainingScore * remainingSearchRange.length; //score += 0.5111111111... * 9 = 4.6
            score /= searchRange.length; //score = 5.6 / 10
            return score; //return 0.56
        }

実際には、単語の頭文字として一致した場合、直前に一致した文字までの間の点数が0.85となるように処理している。
その処理が以下の二つのif分に分けられて、forループを組み合わせて行われていた。
- if ( [ [NSCharacterSet whitespaceCharacterSet] characterIsMember:[self characterAtIndex:matchedRange.location-1] ] )
- 一致した文字の直前が、スペースかタブの場合

- } else if ( [ [NSCharacterSet uppercaseLetterCharacterSet] characterIsMember:[self characterAtIndex:matchedRange.location] ] )
- 一致した文字が、大文字の場合

ここまで読んでみて、やっと、コードの動きを自分の感覚として理解できた。

所感

文字列オブジェクトNSStringを無駄に生成せず、範囲を表す構造体NSRangeを利用して、効率良く計算している。
略語を出来る限り分割して検索する方法は、つまり、正規表現でマッチさせる方法と似ている。（点数計算せず）
- [@"hello world" scoreForAbbreviation:@"hw"];
- /.*h.*w.*/ =~ "hello world"
今まで、正規表現はどんな仕組みでマッチさせているのか謎だったが、このアルゴリズムなら効率良く検索できそう。
点数付けの方法は、ステップ4を修正することでカスタマイズできる。
- 例えば、現状アンダースコアは単語区切りと見なされないが、スペースと同等の意味を持たせることも簡単にできそう。

*1:必要最小限の引数でメソッド呼び出しするために、省略された引数について、nilやデフォルト値を事前設定する目的のメソッド。メソッド本来の処理は、詳細な引数を持つメソッドを呼び出して実行される。