首页 > 代码库, 技术随笔 > Visual Assist代码提示使用的字符串模糊匹配算法

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点击订阅我的文章

  1. vanxining
    | #1

    兄弟寻根究底的劲头不错

    • Kevin Yang
      | #2

      从小就钻牛角尖钻惯了,呵呵

  2. guoguo
    | #3

    不错,这样钻下去能有大修为

  1. 暂时没有trackbacks.