signed

QiShunwang

“诚信为本、客户至上”

算法问题:为啥idea的全局搜索这么快?idea的冗余代码检测怎么实现?

2021/6/3 14:18:31   来源:

idea是程序员常用的开发工具,今早有同事突然问起来,idea能不能搜索windows其他文件内容,因为idea的文本搜索能力确实很强,基本上做到了整个项目里面的文本内容秒级搜索。
然后我思考了下这两个问题:

1.为啥idea的全局搜索这么快?
idea的常用操作:全局搜索 Ctrl + Shift + F,可以对整个项目的任意文本做秒级搜索,定位到关键字所在的文件list、所在文件位置(代码行数);
2.idea的冗余代码检测怎么实现的?
方法的重用,一直是高质量代码里面的一条标准,如果代码出现大量重复代码,可能就需要做优化,程序员使用idea做开发,代码出现冗余时候就会有个代码冗余提示。

网上也搜索了下,好像也没找到具体的详细解析。故根据个人的算法经验,编写了此文章,以下实现思路均为本人的个人想法,若和idea的具体实现有出入,或有更好实现方案,可多多交流

IDEA全局搜索界面:

一、idea的全局搜索实现

几种常见搜索查询算法对比:
Hash:时间复杂度O(1),适合确定key的单值搜索,如Java里面的HashMap结构;
红黑树:时间复杂度Olog(n),适合数字或短小字符串的搜索,如Java里面的HashMap结构;
B+树:时间复杂度取决于树高和分页大小(一般16k),适合数字或短小字符串的单值和范围查询,如mysql的聚簇索引结构;
KMP算法:字符串的快速搜索算法,适合文本内容的模糊搜索;
字典树(Trie):空间换时间的算法,将整个文本或单词加载到trie树中并做维护,可快速模糊查询子串的个数和子串的各种信息;

我想到的最佳的实现方案是利用字典树(Trie),空间换时间的算法,而且可以快速定位关键字内容、关键字所属文件、包含关键字的所有文件和具体位置;
Trie结构的节点Node:
    value属性:存储当前Unicode字符,使用Unicode字符因为这里可以搜索中文和英文;;
    path属性:存储当前Unicode字符所在的文件路径和文件名的引用list(多个文件),这里可将所有在Trie树中的文件路径和文件名放到一个list里面,path引用到list里;
    line属性:存储当前Unicode字符所在文件的位置(代码行数);
    next属性:使用HashMap结构,key存储单个Unicode字符,value存储下一个Node;使用HashMap结构是因为Unicode字符集很多,可以快速定位下一个Node;

实现步骤:
1. idea打开项目,将整个项目的文本文件加载到Trie树中;

比如文件a.file,内容为"abcdefghijklmn",将文本的后缀字符串数组分别加入Trie树中;
abcdefghijklmn
bcdefghijklmn
cdefghijklmn
defghijklmn
efghijklmn
fghijklmn
ghijklmn
hijklmn
ijklmn
jklmn
klmn
lmn
mn
n

后缀字符串数组的特点:
任意字符都可以在trie中搜索出结果,包括空格、换行、制表符;

2. 编辑和删除文本或文件,相对应的维护Trie树结构;
3. 输入任意关键字,Trie树查询算法,查询出关键字所在的文件list、所在文件位置(代码行数);
4. 可以将此Trie树结构压缩持久化到磁盘,下次启动idea加载该项目时候,检查文本是否有改动,没有改动则可直接从磁盘上将Trie树加载出来;

注:字典树(Trie)具体的数据结构和算法实现,可以参看我之前的《字典树(Trie)》文章;

二、idea的冗余代码检测实现

其实该实现用算法来说,就是查找文本的“最长公共子字符串”问题,在《算法4》中有一种巧妙的算法来解决:后缀排序!
实现步骤:
1.subing()方法创建一个由字符串s的所有后缀字符串(由字符串的所有位置开始得到的后缀字符串)组成的数组;
2.对第1步的字符串数组排序;
3.最长重复子字符串会出现在数组的相邻位置,只需遍历一遍即可在相邻元素中找到最长公共前缀。

 《算法4》中的“最长公共子字符串”问题解决步骤:

IDEA代码冗余提示:

IDEA代码冗余提示配置界面: