Levenshtein \u8ddd\u79bb\uff0c\u53c8\u79f0\u7f16\u8f91\u8ddd\u79bb\uff0c\u6307\u7684\u662f\u4e24\u4e2a\u5b57\u7b26\u4e32\u4e4b\u95f4\uff0c\u7531\u4e00\u4e2a\u8f6c\u6362\u6210\u53e6\u4e00\u4e2a\u6240\u9700\u7684\u6700\u5c11\u7f16\u8f91\u64cd\u4f5c\u6b21\u6570\u3002
\n\u8bb8\u53ef\u7684\u7f16\u8f91\u64cd\u4f5c\u5305\u62ec\u5c06\u4e00\u4e2a\u5b57\u7b26\u66ff\u6362\u6210\u53e6\u4e00\u4e2a\u5b57\u7b26\uff0c\u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\uff0c\u5220\u9664\u4e00\u4e2a\u5b57\u7b26\u3002
\n\u7f16\u8f91\u8ddd\u79bb\u7684\u7b97\u6cd5\u662f\u9996\u5148\u7531\u4fc4\u56fd\u79d1\u5b66\u5bb6Levenshtein\u63d0\u51fa\u7684\uff0c\u6545\u53c8\u53ebLevenshtein Distance\u3002<\/p>\n
\u76f8\u4f3c\u5ea6\u4ee3\u7801\u5982\u4e0b\uff0c\u4e00\u822c\u6765\u8bf4\u76f8\u4f3c\u5ea6\u5927\u4e8e0.7\u5c31\u7b97\u6bd4\u8f83\u9ad8\u4e86 <\/p>\n
\/**\n * @className:MyLevenshtein.java\n * @classDescription:Levenshtein Distance \u7b97\u6cd5\u5b9e\u73b0\n * \u53ef\u4ee5\u4f7f\u7528\u7684\u5730\u65b9\uff1aDNA\u5206\u6790 \u3000\u3000\u62fc\u5b57\u68c0\u67e5 \u3000\u3000\u8bed\u97f3\u8fa8\u8bc6 \u3000\u3000\u6284\u88ad\u4fa6\u6d4b\n *\/\n public class MyTest {\n\n public static void main(String[] args) {\n \/\/\u8981\u6bd4\u8f83\u7684\u4e24\u4e2a\u5b57\u7b26\u4e32\n String str1 = \"\u4eca\u5929\u661f\u671f\u56db\";\n String str2 = \"\u4eca\u5929\u662f\u661f\u671f\u4e94\";\n levenshtein(str1,str2);\n }\n\n \/**\n * \u3000\u3000DNA\u5206\u6790 \u3000\u3000\u62fc\u5b57\u68c0\u67e5 \u3000\u3000\u8bed\u97f3\u8fa8\u8bc6 \u3000\u3000\u6284\u88ad\u4fa6\u6d4b\n *\/\n public static void levenshtein(String str1,String str2) {\n \/\/\u8ba1\u7b97\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u957f\u5ea6\u3002\n int len1 = str1.length();\n int len2 = str2.length();\n \/\/\u5efa\u7acb\u4e0a\u9762\u8bf4\u7684\u6570\u7ec4\uff0c\u6bd4\u5b57\u7b26\u957f\u5ea6\u5927\u4e00\u4e2a\u7a7a\u95f4\n int[][] dif = new int[len1 + 1][len2 + 1];\n \/\/\u8d4b\u521d\u503c\uff0c\u6b65\u9aa4B\u3002\n for (int a = 0; a < = len1; a++) {\n dif[a][0] = a;\n }\n for (int a = 0; a <= len2; a++) {\n dif[0][a] = a;\n }\n \/\/\u8ba1\u7b97\u4e24\u4e2a\u5b57\u7b26\u662f\u5426\u4e00\u6837\uff0c\u8ba1\u7b97\u5de6\u4e0a\u7684\u503c\n int temp;\n for (int i = 1; i <= len1; i++) {\n for (int j = 1; j <= len2; j++) {\n if (str1.charAt(i - 1) == str2.charAt(j - 1)) {\n temp = 0;\n } else {\n temp = 1;\n }\n \/\/\u53d6\u4e09\u4e2a\u503c\u4e2d\u6700\u5c0f\u7684\n dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,\n dif[i - 1][j] + 1);\n }\n }\n System.out.println(\"\u5b57\u7b26\u4e32\\\"\"+str1+\"\\\"\u4e0e\\\"\"+str2+\"\\\"\u7684\u6bd4\u8f83\");\n \/\/\u53d6\u6570\u7ec4\u53f3\u4e0b\u89d2\u7684\u503c\uff0c\u540c\u6837\u4e0d\u540c\u4f4d\u7f6e\u4ee3\u8868\u4e0d\u540c\u5b57\u7b26\u4e32\u7684\u6bd4\u8f83\n System.out.println(\"\u5dee\u5f02\u6b65\u9aa4\uff1a\"+dif[len1][len2]);\n \/\/\u8ba1\u7b97\u76f8\u4f3c\u5ea6\n float similarity =1 - (float) dif[len1][len2] \/ Math.max(str1.length(), str2.length());\n System.out.println(\"\u76f8\u4f3c\u5ea6\uff1a\"+similarity);\n }\n\n \/\/\u5f97\u5230\u6700\u5c0f\u503c\n private static int min(int... is) {\n int min = Integer.MAX_VALUE;\n for (int i : is) {\n if (min > i) {\n min = i;\n }\n }\n return min;\n }\n }\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u8ba1\u7b97\u4e24\u5b57\u7b26\u4e32\u7684\u76f8\u4f3c\u7a0b\u5ea6 Levenshtein \u8ddd\u79bb\uff0c\u53c8\u79f0\u7f16\u8f91\u8ddd\u79bb\uff0c\u6307\u7684\u662f\u4e24\u4e2a\u5b57\u7b26\u4e32\u4e4b\u95f4\uff0c\u7531\u4e00\u4e2a\u8f6c\u6362\u6210\u53e6\u4e00\u4e2a\u6240\u9700\u7684\u6700\u5c11\u7f16\u8f91\u64cd\u4f5c\u6b21\u6570\u3002 \u8bb8\u53ef\u7684\u7f16\u8f91\u64cd\u4f5c\u5305\u62ec\u5c06\u4e00\u4e2a\u5b57\u7b26\u66ff\u6362\u6210\u53e6\u4e00\u4e2a\u5b57\u7b26\uff0c\u63d2\u5165\u4e00\u4e2a\u5b57\u7b26\uff0c\u5220\u9664\u4e00...<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"pgc_sgb_lightbox_settings":"","footnotes":""},"categories":[33],"tags":[],"class_list":["post-1220","post","type-post","status-publish","format-standard","hentry","category-coding"],"views":4623,"_links":{"self":[{"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=\/wp\/v2\/posts\/1220","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1220"}],"version-history":[{"count":3,"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=\/wp\/v2\/posts\/1220\/revisions"}],"predecessor-version":[{"id":1222,"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=\/wp\/v2\/posts\/1220\/revisions\/1222"}],"wp:attachment":[{"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.yeetrack.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}