单词分析器
单词数据
想要构建一个单词分析器，首先数据是必不可少的，这部分单词就靠大家自己去爬取了?
主要思路
利用单词作为主键创建数据库，优先利用前缀表达式获取单词，当发现前缀表达式匹配不到单词时，就断定该单词为错误单词，然后开始单词相似度分析，根据相似度分析寻找相似度最高的单词（指定size个）
单词相似度分析
相似度分析采用的是一类经典dp算法的解决“编辑距离”。详细可见 -> LeetCode73 编辑距离
算法思路
对任意两个单词，一定存在 n 次操作能让单词 A 变为单词 B 。
操作：
- A 增加一个单词
- A 减少一个单词
- A 替换一个单词
很明显，如果单词 A 变为单词 B 需要的操作次数越少，说明两个单词的相似度越高，而我们需要的就是提供相似度最高的前 size 个单词供用户选择
之前我也很纠结单词出错时候的匹配是遍历查找好还是怎么样，有想过构建另一个表来存储出现错误的单词，然后根据出错单词匹配
纠结于时间直接全部匹配时间复杂度会不会太高，但事实就是，即使是全盘便利，也就差不多600ms完成业务，这是在能接受的范围的（测试中单词数量爬取为2W单词）
public static List<Node> similarWords(String target) throws SQLException {
String sql = "SELECT * FROM words";
ResultSet resultSet = connection.prepareStatement(sql).executeQuery();
while(!distanceQueue.isEmpty()) distanceQueue.poll();
while(resultSet.next()){
Node node = new Node();
node.word = resultSet.getString("word");
node.pronounce = resultSet.getString("pronounce");
node.comment = resultSet.getString("comment");
node.distance = getSimilar(target,node.word);
distanceQueue.add(node);
if(currentSize >= size){
distanceQueue.poll();
}
else
currentSize ++;
}
ArrayList<Node> result = new ArrayList<>();
while (!distanceQueue.isEmpty()) result.add(distanceQueue.poll());
return result;
}
public static int getSimilar(String word1,String word2){
if(word1.length() == 0){
return word2.length();
}
if(word2.length() == 0){
return word1.length();
}
int[][] dp = new int[word1.length()][word2.length()];
if(word1.charAt(0) == word2.charAt(0)){
dp[0][0] = 0;
}
else
dp[0][0] = 1;
// 先添加 j == 0 时的情况
for(int i = 1; i < word1.length(); i++){
if(word1.charAt(i) == word2.charAt(0))
dp[i][0] = i ;
if(word1.charAt(i) != word2.charAt(0))
dp[i][0] = dp[i-1][0] + 1 ;
}
for(int j = 1; j < word2.length(); j++){
if(word1.charAt(0) == word2.charAt(j))
dp[0][j] = j;
if(word1.charAt(0) != word2.charAt(j))
dp[0][j] = dp[0][j-1] + 1;
}
for(int i = 1; i < word1.length(); i++){
for(int j = 1; j < word2.length(); j++){
if(word1.charAt(i) == word2.charAt(j)){
dp[i][j] = dp[i-1][j-1];
}
else{
int temp = Math.min(dp[i][j-1] + 1,dp[i-1][j] + 1);
dp[i][j] = Math.min(temp,dp[i-1][j-1] + 1);
}
}
}
return dp[word1.length()-1][word2.length()-1];
}
整体：
public static List<Node> predictWord(String prefix) throws SQLException {
String sql = "SELECT * FROM words WHERE word like ? LIMIT ?";
PreparedStatement preparedStatement = connection.prepareStatement(sql);
preparedStatement.setString(1,prefix + "%");
preparedStatement.setInt(2,size);
ResultSet resultSet = preparedStatement.executeQuery();
List<Node> list = new ArrayList<>();
while (resultSet.next()){
Node node = new Node();
node.word = resultSet.getString("word");
node.pronounce = resultSet.getString("pronounce");
node.comment = resultSet.getString("comment");
list.add(node);
}
if(list.size() == 0){ // 如果前缀表达式已经无法寻找到对应的单词，就进行相似度分析寻找相似度最高的 8 个单词返回
// System.out.println("未发现前缀匹配单词，开始寻找相似单词");
list = similarWords(prefix);
}
return list;
}