依靠动态规划编写单词提示功能

单词提示功能

单词提示在ide中特别常见，eclipse，ideal等等，包括atom等等文本编辑器中也有这样的功能，基本就是你写个单词字母，他来提供你可能想输入的单词，例如写个Str,就会提示String,StringBuilder等等。而且在你写错的时候，你要点击提示，才会告诉你是不是改成其他单词相似的，提示的时候并不做这个功能。例如ssb,你可能是想写StringBuilder的。一般是这种是不给提示的。本文就来做一个在你有手误的情况下还能正常给提示的功能。还有就是不需要首字母提示，例如写个Builder,也可以去匹配到StringBuilder的。

实现的关键点

根据上面的描述，其实可以发现这就是一个字符串匹配问题。每一个字符串都要和字典里的做匹配，那执行效率是个问题。所以我们把重点放在一个单词如何匹配以及并发操作上。

字符匹配方式

字符串匹配方式有很多，我们的前提是考虑允许出错的，那么精准匹配的方式就不那么适合了。正则表达式起码可以排除了。暴力枚举的方式是可以的，只是想想就算了，都是n次方级别的，枚举下来时间太多了，我们可以把这个问题转化为一个公共子序列问题，最后看看子序列长度占匹配字符的长度，来算容错率。不是很明白的匹配方式的请查看下面的文章。
动态规划查找子序列问题

并发匹配

这个就需要借助线程池来做了，并且可以获取返回值。内容简单可以直接上代码。

        StringBuilder sb = new StringBuilder();
        List<Future<String>> result = new ArrayList<Future<String>>(dic.size());
        for (String dicString : dic) {
            result.add(pool.submit(new CharMatching(input, dicString)));
        }

        for (Future<String> future : result) {
            String data = future.get();
            if (data != null) {
                sb.append(data);
                sb.append(" ");
            }
        }

        return sb.toString();

匹配方式的优缺点

动态规划找公共子序列速度不慢的，但是ide里并不是靠他来做的，主要是lucene,ide的字典量特别大，都收入内存就不合适了。还主要是靠文件来做存储。那么动态规划带来了什么好处呢，首先算法并不慢，m*n。在量大的情况下，比暴力破解好太多了。内存中都能获取到值，那么就可以考虑做到容错了处理了。带来了一定的灵活性。
代码地址如下，有兴趣的可以继续改良。https://github.com/xpbob/Automatic-prompt

原创首发于慕课网