关于编辑距离的应用方案--

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

//构建前缀树

package com.pcauto.utils.bkutils;

import java.util.*;

public class BKTreeAlgo<T> {
    private final int radius;

    private Node root;
    private Metric<T> metric;

    public BKTreeAlgo(int radius, Metric<T> metric) {
        this.radius = radius;
        this.metric = metric;
    }

    public void add(T value) {
        if (root == null)
            root = new Node(value);
        else {
            root.add(value);
        }
    }

    public void addAll(Collection<? extends T> collection) {
        for (T val : collection) {
            add(val);
        }
    }

    public Set<T> search(T value) {
        Set<T> result = new HashSet<>();
        if (root != null)
            root.search(value, result);
        return result;
    }

    class Node {
        private T value;
        private Map<Integer, Node> childs;

        Node(T v) {
            this.value = v;
            this.childs = new HashMap<Integer, Node>();
        }

        void add(T value) {
            int distance = metric.getMetric(this.value, value);
            if (this.childs.containsKey(distance)) {
                this.childs.get(distance).add(value);
            } else {
                this.childs.put(distance, new Node(value));
            }
        }

        void search(T value, Set<T> resultSet) {
            int distance = BKTreeAlgo.this.metric.getMetric(this.value, value);

            if (distance <= radius) {
                resultSet.add(this.value);
            }

            for (int i = Math.max(distance - radius, 1); i <= distance + radius; i++) {
                Node ch = this.childs.get(i);
                if (ch != null)
                    ch.search(value, resultSet);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

package com.pcauto.utils.bkutils;

public interface Metric<T> {
    int getMetric(T t1, T t2);
}



package com.pcauto.utils.bkutils;


public class StringEditMetric implements Metric<String> {
    @Override
    public int getMetric(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= s2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                dp[i][j] = Math.min(
                        dp[i - 1][j - 1] + (s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1),
                        Math.min(dp[i][j - 1], dp[i - 1][j]) + 1
                );
            }
        }

        return dp[s1.length()][s2.length()];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//构建树的词典读取
package com.pcauto.utils.bkutils;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

public class DataHandler {

    public static Set<String> getDictionary() throws IOException{
        Set<String> dictionary = new HashSet<>();
        BufferedReader bufferedReader = new BufferedReader(new FileReader(new File("/Users/glin/IdeaProjects/Basic_Learn/nlp/zh_correct_pinyin-master/src/main/java/com/pcauto/utils/bkutils/data/PROJECTS.csv")));
        String temp;
        while ((temp = bufferedReader.readLine()) != null){
            dictionary.add(temp);
        }
        bufferedReader.close();
        return dictionary;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//代码测试
package com.pcauto.utils.bkutils;


import java.io.IOException;
import java.util.Scanner;

public class SearchTest {

    public static void main(String[] args) {

        //数据初始化
        BKTreeAlgo<String> bkTree = new BKTreeAlgo<String>(1, new StringEditMetric());
        try {
            bkTree.addAll(DataHandler.getDictionary());
        } catch (IOException e) {
            e.printStackTrace();
        }

        //数据搜索
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String word = scanner.next().trim();
            System.out.printf("匹配列表: %s\n", bkTree.search(word));
        }

    }
}