算法问题: 为啥idea的全局搜索这么快？idea的冗余代码检测怎么实现的？_ide工具实现快速全局搜索的原理

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的冗余代码检测实现

两种方法解决：
方法一、基于上面的字典树(Trie)结构，轻松得到项目中的重复字符串，这个贼快！

方法二、“最长公共子字符串”问题解决：

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

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

IDEA代码冗余提示：

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