使用 BFS 广度优先搜索算法求字符串相似度

广度优先搜索算法求字符串相似度"/>

使用 BFS 广度优先搜索算法求字符串相似度

现在有2个字符串，mother和monster，将 mother 变成 monster，每次操作只能是 修改一个字母，删除一个字母，添加一个字母，则将 monther 变成 Monster 的编辑路径有很多种，我们需要求出最短的编辑路径，因为这2个字符串的相似度是由最小的编辑距离决定的。

我们来演示一下搜索出的搜索过程：

m o t h e r :1. m o n h e r  ( t 修改为 n )1. m o n s e r ( h 修改为 s )1. m o n s t r ( e 修改为 t )1. m o n s t e ( r 修改为 e )1. m o n s t e r ( 添加 r,结束)2. m o n s t r ( 添加 r )1. m o n s t e ( r 修改为 e )1. m o n s t e r ( 添加 r,结束 )2. m o n s t r r( 添加 r )1. m o n s t e r ( r 修改为 e,结束 )2. m o n s e e ( r 修改为 e )1. m o n s t e ( e 修改为 t )1. m o n s t e r ( 添加 r,结束 )2. m o n s e e r ( 添加 r )1. todo2.3.3. m o n s e r r ( 添加 r )2. m o n h t r ( e 修改为 t )3. m o n h e r ( r 修改为 e )4. m o n h e r r ( 添加 r )2. m o t s e r  ( h 修改为 s )1. m o n s e r ( t 修改为 n )2. m o t s t r ( e 修改为 t )3. m o t s e e ( r 修改为 e )4. m o t s e r r ( 添加 r )3. m o t h t r  ( e 修改为 t )1. m o n h t r ( t 修改为 n )2. m o t s t r ( h 修改为 s )3. m o t h t e ( r 修改为 e )4. m o t h t r r ( 添加 r )4. m o t h e e  ( r 替换为 e )5. m o t h e r r ( 添加 r )

NodeVO.java：

import lombok.Getter;
import lombok.Setter;import java.io.PipedReader;
import java.io.Serializable;
import java.util.List;@Getter
@Setter
public class NodeVO implements Serializable {private String str;private NodeVO parent;private List<NodeVO> children;}

StringEditDistanceTest.java：

import com.alibaba.fastjson.JSONObject;import java.util.*;public class StringEditDistanceTest {/*
// 先将2个字母按照头部对齐，// 每次可以增( 人选一个位置增加缺少的字母 )、删( 人选一个位置删除多余的字母 )、改( 任选一个字母和目标字符串对应位置处的不同的进行替换 )m o t h e rm o n s t e rm o t h e r :1. m o n h e r  ( t 修改为 n )1. m o n s e r ( h 修改为 s )1. m o n s t r ( e 修改为 t )1. m o n s t e ( r 修改为 e )1. m o n s t e r ( 添加 r,结束)2. m o n s t r ( 添加 r )1. m o n s t e ( r 修改为 e )1. m o n s t e r ( 添加 r,结束 )2. m o n s t r r( 添加 r )1. m o n s t e r ( r 修改为 e,结束 )2. m o n s e e ( r 修改为 e )1. m o n s t e ( e 修改为 t )1. m o n s t e r ( 添加 r,结束 )2. m o n s e e r ( 添加 r )1. todo2.3.3. m o n s e r r ( 添加 r )2. m o n h t r ( e 修改为 t )3. m o n h e r ( r 修改为 e )4. m o n h e r r ( 添加 r )2. m o t s e r  ( h 修改为 s )1. m o n s e r ( t 修改为 n )2. m o t s t r ( e 修改为 t )3. m o t s e e ( r 修改为 e )4. m o t s e r r ( 添加 r )3. m o t h t r  ( e 修改为 t )1. m o n h t r ( t 修改为 n )2. m o t s t r ( h 修改为 s )3. m o t h t e ( r 修改为 e )4. m o t h t r r ( 添加 r )4. m o t h e e  ( r 替换为 e )5. m o t h e r r ( 添加 r )*/public static void main(String[] args) {String str_src = "hello";String str_target = "halllo";// searchShortestEditDistance( str_src,str_target );List<Character> letters = getLettersThatStr1Lack(str_src, str_target);System.out.println( JSONObject.toJSONString( letters ) );}private static List<Character> string2Letters( String str ){int length = str.length();List<Character> letters = new ArrayList<>();for(int i = 0;i < length;i++){letters.add( str.charAt(i) );}return letters;}/*** 返回 srcStr 缺少的字母集合* @param str1* @param str2* @return*/private static List<Character> getLettersThatStr1Lack( String str1,String str2 ){List<Character> letters1 = string2Letters(str1);List<Character> letters2 = string2Letters(str2);// hello   hallloooListIterator<Character> iterator = letters2.listIterator();while ( iterator.hasNext() ){Character letter = iterator.next();if( letters1.contains( letter ) ){letters1.remove( letter );iterator.remove();}}return letters2;}/*** @param beginString* @param endString*/private static void searchShortestEditDistance(String beginString, String endString) {List<NodeVO> nodes_currLevel = new ArrayList<>();NodeVO node_begin = new NodeVO();node_begin.setStr( beginString );nodes_currLevel.add( node_begin );List<NodeVO> nodes_nextLevel = new ArrayList<>();boolean finish = false;int treeDeep = 0;while( true ){if( nodes_currLevel.size() == 0 ){break;}// 先将2个字母按照头部对齐，// 每次可以增( 任选一个位置增加缺少的字母 )、删( 人选一个位置删除多余的字母 )、改( 任选一个字母和目标字符串对应位置处的不同的进行替换 )// m o t h e r// m o n s t e r// hello// halllotreeDeep++;for( NodeVO node:nodes_currLevel ){String currString = node.getStr();if( currString.equals( endString ) ){// 已经变换成目标字符串了finish = true;break;}List<Character> letters_lack = getLettersThatStr1Lack(currString, endString);if( letters_lack == null || letters_lack.size() == 0 ){// todo 表示 currString 不缺字母，因此 currString 比 endString 多了一些字母// 从 letters_redundant 中选一个多余的字母进行删除操作，比如多了字母a,则 currString 可能多个位置处都有a，则每个位置都进行// 删除操作，一个位置表示一个可达路径List<Character> letters_redundant = getLettersThatStr1Lack(endString, currString);}else {// 选一个缺少的字母在所有可能位置进行 add操作// todoCharacter letter_lack = letters_lack.get(0);}// todo}if( finish ){break;}nodes_currLevel = nodes_nextLevel;nodes_nextLevel = new ArrayList<>();}// todo}
}