Visual Assist代码提示使用的字符串模糊匹配算法

Visual Assist是Visual Studio上一个很强大的插件。特别是在代码提示方面，相比Visual Studio自带的要强很多。

Visual Studio自带的代码提示（智能感知）功能会根据我们敲入的字符串，找到相似的类或者方法等。但是它的匹配规则非常简单，就是前向匹配。例如当我们输入了String字符串，那么Visual Studio会列出String,StringBuilder,StringComparer等以“String”打头的字符串。这样的设计其实是非常不够用的。稍微敲快一些漏掉一两个字母是很正常的事情，但是在VS中就无法享受代码提示带来的便捷了。好在Visual Assist改进了这一点。

VA采用字符串模糊匹配的算法，即使你漏过了其中几个字母，或者当你想要搜索含有某个字符串的类、方法等的时候，VA都可以很好的列出你想找的东西。

例如，我想使用SqlConnectionStringBuilder这个类，但是这个类名太长了。那么我们只需要输入“sqlconbui”字符串即可。又或者，我们想看看类库中有什么和String相关的，我们只需要输入String即可。

一直很好奇它这个匹配算法是怎么实现的，在论坛问了别人都没什么人感兴趣。自己研究了一下，我觉得算法要求可以这样来描述：

源字符串在经过若干次插入操作之后，能够变换成目标字符串。那么就说源字符串成功匹配到了目标字符串。否则不匹配。

插入操作，指的是在源字符串的任意位置上插入任意长度的字符串。

自己写了个大概的算法实现（C#版）：

/// <summary>
/// 字符串模糊匹配。
/// </summary>
/// <param name="source"></param>
/// <param name="search"></param>
/// <returns></returns>
public static bool FuzzySearch(String source, String search)
{
    if (String.IsNullOrEmpty(source))
    {
        throw new ArgumentNullException("source");
    }
    if (String.IsNullOrEmpty(search))
    {
        return true;
    }
    // 不区分大小写
    source = source.ToLowerInvariant();
    search = search.ToLowerInvariant();
    int index = source.IndexOf(search[0]);
    for (short i = 1; i < search.Length; i++)
    {
        char ch = search[i];
        index = source.IndexOf(ch, index + 1);
        if (index < 0)
        {
            return false;
        }
    }
    return true;
}

测试了一下，“sqlconbui”能够成功匹配到SqlConnectionStringBuilder。不过验证了其他几个字符串，发现和VA的算法还是有点差别的，感觉我这个匹配相比它的更宽松的样子。

——Kevin Yang

本博客遵循CC协议2.5，即署名-非商业性使用-相同方式共享
写作很辛苦，转载请注明作者以及原文链接~
如果你喜欢我的文章，你可以订阅我的博客:-D点击订阅我的文章