基于KMP与Levenshtein模糊匹配算法的银行联行号查询

浏览数：20 / 时间：2015年06月08日

在人民银行那里，每个银行的每一个营业网点都有自己唯一的银行联行号,根据这个号码能快速定位一间银行具体的分支行，就像根据一个身份证号码能快速确定一个人一样。例如汇款时，汇款单上要求填写收款人开户行，然后银行会把收款人开户行的联行号连其他信息发到人民银行进行清算，这样能保证以最快的速度汇到收款人的手上。如果联行号不准确，那么在汇款的时候会发生分行落地，支行间调拨等操作，影响导致时间，尤其是跨行汇款的时候。一般银行的代收付接口，都会要求提供此参数。

银行联行号一般是根据输入的分支行信息模糊查询出来的，有的银行接口也会提供类似的根据传入的信息返回联行号的接口，其实现的技术也是根据模糊匹配思路，只是不同的银行实现的水准高低不同，如输入"工行海淀支行"有的返回的是中国工商银行北京市分行海淀镇支行营业室102100000458,有的返回的是中国工商银行北京市海淀支行四季青分理处102100024537。

本文主要是基于前两年在支付行业的代码实战，通过联行号模糊查询示例讲解KMP与Levenshtein模糊匹配算法，有关此两种算法的介绍可以参考Levenshtein字符串距离算法介绍与KMP字符串匹配算法，本文只是整个查询功能的代码示例，为了专注算法重点，略去了银行同义词之间的匹配与模糊地市查询能力。（银行同义词如工行、工商银行、中国工商银行股份有限公司，模糊地市如江西省南昌市、江西南昌）

先看整体效果

技术分享

主要代码说明：

swing初始化及数据加载

 1 try {
 2             JFrame frame = new JFrame("银行模糊匹配---edited by Dimmacro");
 3             textLabel = new JLabel("请输入待匹配的字符串:");
 4             textLabel.setFont(new Font("Default", Font.PLAIN, 18));
 5             textField = new JTextField(30);
 6             textField.setFont(new Font("Default", Font.PLAIN, 18));
 7             resultArea = new JTextArea();
 8             resultArea.setFont(new Font("Default", Font.BOLD, 15));
 9             resultArea.setEditable(false);
10             // 设置窗口初始化大小为屏幕大小的1/4，位置在最中间
11             JPanel panel = new JPanel();
12             panel.add(textLabel);
13             panel.add(textField);
14             frame.getContentPane().add(panel, BorderLayout.NORTH);
15             frame.getContentPane().add(new JScrollPane(resultArea), BorderLayout.CENTER);
16 
17             frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
18             Dimension d = Toolkit.getDefaultToolkit().getScreenSize();
19             frame.setSize(d.width / 2, d.height / 2);
20             frame.setLocation((d.width - frame.getSize().width) / 2, (d.height - frame.getSize().height) / 2);
21             frame.setVisible(true);
22             textField.addKeyListener(new KeyAdapter() {
23                 public void keyReleased(KeyEvent e) {
24                     startTime = System.nanoTime();
25                     readyCheck = true;
26                 }
27                 
28                 public void keyPressed(KeyEvent e) {
29                     startTime = System.nanoTime();
30                     readyCheck = false;
31                 }
32                 
33             });
34         } catch (Exception e) {
35             e.printStackTrace();
36             resultArea.setText("执行出错!");
37         }

联行号数据加载：需要把联行号数据库先加载到内存中，其单行格式为：102100000030,中国工商银行北京市分行营业部

 1 private static long initSourceData() {
 2         long counts = 0;
 3         try {
 4             InputStream bankCodeInputStream = BankMatch.class.getClassLoader().getResourceAsStream(bankCodeFile);
 5             BufferedReader bReader = new BufferedReader(new InputStreamReader(bankCodeInputStream, "GBK"),20480);
 6             String lineString;
 7             bankMap = new HashMap<String, String>();
 8             String code, name;
 9             while ((lineString = bReader.readLine()) != null) {
10                 int firstCommaIndex = lineString.indexOf(",");
11                 code = lineString.substring(0, firstCommaIndex);
12                 name = lineString.substring(firstCommaIndex + 1);
13                // System.out.println("code=" + code + " and name=" + name+"=========="+counts);
14                 bankMap.put(code, name);
15                 counts++;
16             }
17         } catch (Exception e) {
18             e.printStackTrace();
19         }
20         return counts;
21     }

根据传入的参数模糊查询，返回符合条件的列表，并按最佳匹配程度进行排序

 1     public List<String> handleMatch() {
 2         List<String> resultList = new ArrayList<String>();
 3         String code, name;
 4         String[] nameArray;
 5         String findResult;
 6         for (Map.Entry<String, String> entry : bankMap.entrySet()) {
 7             code = entry.getKey();
 8             name = entry.getValue();
 9             nameArray = name.split(",");
10             findResult = code + "," + nameArray[0];
11             List<String> arrangeList = new ArrayList<String>();
12             resultStr = new String[nameArray.length];
13             arrageArray(arrangeList, nameArray); // 如果有省份城市,重排其顺序以保证匹配的准确性
14             for (String oneArrangeStr : arrangeList) {
15                 name = oneArrangeStr.replaceAll(",", "");
16                 // 处理BMP全字匹配的情况
17                 if ((KMPMatchString.kmpMatch(name, matchStr) || KMPMatchString.kmpMatch(matchStr, name)) && !resultList.contains(findResult)) {
18                     resultList.add(findResult);
19                     match.printOut(findResult);
20                     match.getShowArea().selectAll();
21                 }
22             }
23         }
24         // Levenshtein 模糊算法
25         if (resultList.size() > 0) {
26             // 根据Levenshtein 模糊算法排序
27             Collections.sort(resultList, new Comparator<String>() {
28                 public int compare(String s1, String s2) {
29                     return LevenshteinMacthString.levenshteinMacth(s1.split(",")[1], matchStr)
30                     - LevenshteinMacthString.levenshteinMacth(s2.split(",")[1], matchStr);
31                 }
32             });
33         }
34         return resultList;
35     }

KMP算法

 1 public static boolean kmpMatch(String source, String target)
 2     {
 3         if(null == source || null == target || "".equals(source.trim()) || "".equals(target.trim()))
 4         {
 5             return false;
 6         }
 7         
 8         int bl = source.length();
 9         int al = target.length();
10         
11         for(int bi = 0,ai = 0;bi < al;ai++)
12         {
13             if(bi == al || ai == bl)
14             {
15                 return false;
16             }
17             else if(source.charAt(ai) == target.charAt(bi))
18             {
19                 bi++;
20             }
21         }
22         return true;
23     }

Levenshtein算法

 1 public static int levenshteinMacth(String source,String target) {
 2         int n = target.length();
 3         int m = source.length();
 4         int[][] d = new int[n + 1][m + 1];
 5 
 6         // Step 1
 7         if (n == 0) {
 8             return m;
 9         }
10 
11         if (m == 0) {
12             return n;
13         }
14 
15         // Step 2
16         for (int i = 0; i <= n; d[i][0] = i++) {
17         }
18 
19         for (int j = 0; j <= m; d[0][j] = j++) {
20         }
21 
22         // Step 3
23         for (int i = 1; i <= n; i++) {
24             // Step 4
25             for (int j = 1; j <= m; j++) {
26                 // Step 5
27                // System.out.println(t.charAt(j - 1));
28               //  System.out.println(s.charAt(i - 1));
29                // int cost = (t.charAt(j - 1) == s.charAt(i - 1)) ? 0 : 1;
30                 int cost = (source.substring(j - 1, j) == target.substring(i - 1, i) ? 0 : 1);
31 
32                 // Step 6
33                 d[i][j] = Math.min(Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1), d[i - 1][j - 1] + cost);
34             }
35         }
36         // Step 7
37         return d[n][m];
38     }

附件下载：Eclipse工程，直接导入运行BankMatch类即可看到效果。下载
遗留代码问题：如整体效果看到的那样，每次从输入框输入完释放最后一次按键时，如果1秒内没有接着按下一个键，才会开始查询，这样既可以做到根据输入的效果实时查询，又不至于要每次输入一个字符就开始查。对于这个实现采用的是wihe（true)的方式，但是发现如果不加线程sleep的话会出现不响应查询的情况，请万能的博客园高手看看。