神刀安全网

逆向工程师手中的利器-Sublime Text中的模糊匹配

逆向工程师手中的利器-Sublime Text中的模糊匹配

我曾经使用过很多不同类型的代码编辑器,但是 Sublime Text 是我在编程的过程中最喜欢使用的一款。

我之所以如此偏爱Sublime Text,是因为它有一个非常棒的功能-模糊搜索算法。利用这个功能,我可以快速地定位到具体的文件或者函数上。在此之前,已经有很多人在网上询问过这一功能的具体实现方法了。但是网上的答案没有一个是令人满意的。所以我决定亲自来给大家讲解这一功能的具体工作机制和使用方法。

如果你觉得这篇文章的内容过于繁琐,那么下面这一段文字也许可以满足你:

如果你不想阅读这些无聊的文字内容,你想直接看到最终的结果?没关系,我不会责怪你。

互动演示实例:点击 这里 获取

源代码: C++ JavaScript

进入正题

Sublime Text中的模糊匹配到底是什么呢?为什么我会觉得这个功能非常的棒呢?我很高兴大家有这样的疑问。

Sublime有两个功能非常强大的文件导航功能,而且程序员使用起来也非常的顺手。其中一个是专门用于搜索文件的,而另一个是专门用于搜索特殊字符以及标记的(例如函数和类名等等)。这两个功能的工作机制实际上是一样的。在这个功能的帮助下,我们不需要在搜索框中输入精确的文件名,我们只需要输入几个字符,Sublime就会帮助我们搜索出我们想要的文件或者函数。在输入了少量字符之后,Sublime会搜索目录下的文件,并对搜索结果进行智能排序。下图显示的就是我们的搜索结果。

逆向工程师手中的利器-Sublime Text中的模糊匹配

我们可以看到,上图显示的实际上是代码文件的搜索结果,我在搜索栏中输入的是“clu”。在经过系统的智能排序之后,显示在最上方的搜索结果为“client_uni.cpp”。在搜索结果中,具体匹配到的字符会进行加粗显示。

下图显示的是另一种形式的搜索结果。

逆向工程师手中的利器-Sublime Text中的模糊匹配

在搜索栏中输入了“agn”之后,Sublime显示了很多AnimGraphNode类型。我们只需要键入少量的关键字符,Sublime就可以为我们显示出大多数与输入字符相匹配的文件内容。

灵感来源

Sublime的模糊匹配功能真的非常的棒。简直是太棒了!我非常喜欢这个功能。不幸的是,很多其他类型的文本编辑器,IDE工具,以及网站的搜索栏都没有这个功能。这个功能如此的强大和实用,我认为所有的搜索功能都应该引入模糊匹配机制。

但是,我想要通过我的努力来改变这一现状。首先,我需要对模糊匹配功能进行深入地分析和研究,并发现其中的奥秘。其次,我还会给大家提供这一功能的源代码,其他现有的项目可以直接使用这些源代码来提升程序的搜索性能。

实际上,我已经在脑海中设想出了几个该功能的特殊使用场景了。我想要在编程的过程中也能够使用这个功能,包括搜索文件名,类名,以及函数名等等。但是,我所想要实现的肯定远远不止于此。

我是一名狂热的炉石玩家,在游戏的过程中寻找卡片是再常见不过的任务了。很多玩家也会在网上搜索这些内容,类似HearthArena的网站可以给广大玩家提供一定程度上的帮助。除此之外,我也是卡片数据库的狂热粉丝,例如Hearth.cards等网站。

大多数与炉石有关的网站只会给用户提供基本的子字符串匹配搜索。但是,如果卡片名称为“Ragnaros the Firelord”,那么这个卡片名称中包含有子字符串“rag”吗?很明显,卡片名称的确包含这个子字符串。但是如果卡片名称为“Inner Rage”,“ Faerie Dragon”, “Magma Rager”,或者其他类似这种形式的字符串呢?其中是否还包含子字符串“rag”呢?这一点值得思考,但是很明显,如果我们输入“rtf”或者“ragrs”来进行搜索的话,速度会更快,搜索结果也会更加准确。

我个人认为,在进行模糊匹配的过程中,搜索速度要保证快速,而且在对成千上万条记录进行搜索的过程中,还需要一定的交互功能。

功能讲解

如果大家对Sublime Text编辑器进行了深入地分析之后,有两个地方肯定会变得非常的明显。

1.    Sublime Text在进行模糊匹配的过程中,会尝试在搜索结果中与每一个字符进行匹配。

2.    其模糊匹配算法种还存在有一种隐藏的评分机制,并会根据具体的算法来决定哪一个搜索结果更加的重要,并按照评分顺序进行显示输出。

我们可以直接用代码来实现第一个功能,过程非常的简单,具体代码如下图所示:

逆向工程师手中的利器-Sublime Text中的模糊匹配

大家可以从上图中看到实现该功能的具体实现代码,而且我还在我的代码库中添加了该功能的C++版本和JavaScript版本。我这么做是有我自己的理由的,因为这段代码可以替换掉很多简单的子字符串匹配功能。

评分系统

最有趣的地方莫过于这个隐藏的评分机制了。系统会利用什么样的因素来对搜索结果进行评分呢?系统又是根据什么来决定搜索结果的排序呢?首先,我对下面这几个影响因素进行了分析:

-匹配的字符

-不匹配的字符

-连续匹配的字符

-起始字符的位置

-字符后面是否跟有分隔符(如空格和下划线)

-大写字母后面是否跟有小写字母(即驼峰命名法)

这部分内容其实很好理解。根据匹配的字符来对搜索结果排序,然后排除不匹配的字符。

但是关键的问题在于,系统如何评判哪一个搜索结果应该排在前面。我觉得就这一点而言,并没有唯一的正确答案。数据权重应该取决于数据集的具体情况。而且文件路径与文件名不同,文件的后缀名往往会被忽略掉。对于单词而言,系统往往关注的是连续的字符是否匹配,而不会考虑分隔符和驼峰命名法这两个因素。

如果大家想要了解其在对不同数据集进行搜索排序时所采用的技术细节,我强烈建议大家阅读 源代码

-初始评分为0

-检测到匹配字符:+0分

-检测到不匹配的字符:-1分

-检测到连续匹配的字符:+5分

-检测到分隔符:+10分

-检测到驼峰命名法:+10分

-检测到首字母不匹配:-3分(最多减9分)

总结

我非常喜欢Sublime Text和它的模糊匹配算法。我现在也在努力尝试去开发出一个类似的软件,并实现类似的功能。我觉得我马上就要完成了!

其次,我会将我所开发出的源代码提交至GitHub中,我希望所有人都能够从中获益。我不知道我的项目中是否存在漏洞或者设计缺陷,所以对此感兴趣的朋友可以在我的GitHub上留言。

互动演示:请点击 这里 获取

源代码: C++ JavaScript

GitHub: lib_fts

感谢大家的阅读!

本文由 360安全播报 翻译,转载请注明“转自360安全播报”,并附上链接。

原文链接:https://blog.forrestthewoods.com/reverse-engineering-sublime-text-s-fuzzy-match-4cffeed33fdb#.aqe8vjmt1

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 逆向工程师手中的利器-Sublime Text中的模糊匹配

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮