C# で Alcor の Abbreviation Scoring

ネタ元→steps to phantasien(2009-09-12)

QuickSilver の検索で使われている、検索対象のファイル名と略語の一致度合を点数付けするアルゴリズムを、C# の拡張メソッドで実装してみた。もしかしたら、検索機能を持つアプリを作るとき、このアルゴリズムを使うかもしれない。

using System;
using System.Text.RegularExpressions;

namespace AbbreviationScoringSample
{
    public static class AbbreviationScorer
    {
        /// <summary>
        /// 略語をスコアリングします。
        /// </summary>
        /// <param name="self">検索対象の文字列</param>
        /// <param name="abbrevation">略語</param>
        /// <returns>略語がどれくらいマッチしているかを表すスコア</returns>
        public static double ToScore(this string self, string abbrevation)
        {
            // パターンを照合し終えて残った部分のスコアは 0.9
            if (string.IsNullOrEmpty(abbrevation))
            {
                return 0.9;
            }

            // 残りの文字列とパターンが一致しない場合のスコアは 0
            if (self.Length < abbrevation.Length)
            {
                return 0;
            }

            // 略語にマッチするかチェック
            // マッチすれば点数を付ける
            // マッチしなければ略語を短くして再びチェック
            for (int i = abbrevation.Length; 1 <= i; i--)
            {
                var match = Regex.Match(self, abbrevation.Substring(0, i), RegexOptions.IgnoreCase);
                if (!match.Success)
                {
                    continue;
                }

                // マッチした部分より前
                var pre = self.Substring(0, match.Index);

                // マッチした部分より後
                var next = self.Substring(match.Index + match.Length);

                if (next.Length < (abbrevation.Length - i))
                {
                    continue;
                }

                // 残りの文字列をチェックする
                var remainingScore = next.ToScore(abbrevation.Substring(i, abbrevation.Length - i));

                if (0 < remainingScore)
                {
                    // パターンにマッチした部分のスコアは 1
                    var score = (double)match.Length;

                    // 意図的に省略された部分のスコアは 0.85
                    if ((0 < match.Index) && Regex.IsMatch(self.Substring(match.Index - 1, 1), @"[\s]"))
                    {
                        score += 0.85 * Regex.Replace(pre, @"[\s]", "").Length + 1;
                    }
                    else if (Regex.IsMatch(self.Substring(match.Index, 1), "[A-Z]"))
                    {
                        // CamelCase を考慮                        
                        score += 0.85 * Regex.Replace(pre, "[A-Z]", "").Length;
                    }
                    score += remainingScore * (double)next.Length;

                    // スコアは文字単位で正規化する
                    score /= self.Length;

                    return score;
                }
            }

            return 0;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("HelloWorld".ToScore("he"));  //=> 0.92
            Console.WriteLine("HelloWorld".ToScore("hw"));  //=> 0.9
            Console.WriteLine("HelloWorld".ToScore("hlw")); //=> 0.83
            Console.WriteLine("HelloWorld".ToScore("low")); //=> 0.66
            Console.WriteLine("HelloWorld".ToScore("wh"));  //=> 0
            Console.ReadLine();
        }
    }
}