Hàm so sánh chuỗi java

Cách phổ biến của tính toán độ tương tự giữa hai chuỗi theo kiểu 0% -100% , như được sử dụng trong nhiều thư viện, là để đo mức độ (trong %) bạn sẽ phải thay đổi chuỗi dài hơn để biến nó thành chuỗi ngắn hơn:

/** * Calculates the similarity (a number within 0 and 1) between two strings. */ public static double similarity(String s1, String s2) { String longer = s1, shorter = s2; if (s1.length() < s2.length()) { // longer should always have greater length longer = s2; shorter = s1; } int longerLength = longer.length(); if (longerLength == 0) { return 1.0; /* both strings are zero length */ } return (longerLength - editDistance(longer, shorter)) / (double) longerLength; } // you can use StringUtils.getLevenshteinDistance() as the editDistance() function // full copy-paste working code is below

Tính toán editDistance():

Hàm editDistance() ở trên dự kiến ​​sẽ tính khoảng cách chỉnh sửa giữa hai chuỗi. Có một số triển khai cho bước này, mỗi bước có thể phù hợp với một kịch bản cụ thể tốt hơn. Phổ biến nhất là Thuật toán khoảng cách Levenshtein và chúng tôi sẽ sử dụng trong ví dụ của chúng tôi dưới đây (đối với các chuỗi rất lớn, các thuật toán khác có khả năng hoạt động tốt hơn).

Đây là hai tùy chọn để tính khoảng cách chỉnh sửa:

• Bạn có thể sử dụng Văn bản Apache Commons của khoảng cách Levenshtein: apply(CharSequence left, CharSequence rightt)
• Thực hiện nó trong của riêng bạn. Dưới đây bạn sẽ tìm thấy một ví dụ thực hiện.

Ví dụ làm việc:

Xem bản demo trực tuyến tại đây.

public class StringSimilarity { /** * Calculates the similarity (a number within 0 and 1) between two strings. */ public static double similarity(String s1, String s2) { String longer = s1, shorter = s2; if (s1.length() < s2.length()) { // longer should always have greater length longer = s2; shorter = s1; } int longerLength = longer.length(); if (longerLength == 0) { return 1.0; /* both strings are zero length */ } /* // If you have Apache Commons Text, you can use it to calculate the edit distance: LevenshteinDistance levenshteinDistance = new LevenshteinDistance(); return (longerLength - levenshteinDistance.apply(longer, shorter)) / (double) longerLength; */ return (longerLength - editDistance(longer, shorter)) / (double) longerLength; } // Example implementation of the Levenshtein Edit Distance // See http://rosettacode.org/wiki/Levenshtein_distance#Java public static int editDistance(String s1, String s2) { s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); int[] costs = new int[s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { int lastValue = i; for (int j = 0; j <= s2.length(); j++) { if (i == 0) costs[j] = j; else { if (j > 0) { int newValue = costs[j - 1]; if (s1.charAt(i - 1) != s2.charAt(j - 1)) newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1; costs[j - 1] = lastValue; lastValue = newValue; } } } if (i > 0) costs[s2.length()] = lastValue; } return costs[s2.length()]; } public static void printSimilarity(String s, String t) { System.out.println(String.format( "%.3f is the similarity between \"%s\" and \"%s\"", similarity(s, t), s, t)); } public static void main(String[] args) { printSimilarity("", ""); printSimilarity("1234567890", "1"); printSimilarity("1234567890", "123"); printSimilarity("1234567890", "1234567"); printSimilarity("1234567890", "1234567890"); printSimilarity("1234567890", "1234567980"); printSimilarity("47/2010", "472010"); printSimilarity("47/2010", "472011"); printSimilarity("47/2010", "AB.CDEF"); printSimilarity("47/2010", "4B.CDEFG"); printSimilarity("47/2010", "AB.CDEFG"); printSimilarity("The quick fox jumped", "The fox jumped"); printSimilarity("The quick fox jumped", "The fox"); printSimilarity("kitten", "sitting"); } }

Đầu ra:

1.000 is the similarity between "" and "" 0.100 is the similarity between "1234567890" and "1" 0.300 is the similarity between "1234567890" and "123" 0.700 is the similarity between "1234567890" and "1234567" 1.000 is the similarity between "1234567890" and "1234567890" 0.800 is the similarity between "1234567890" and "1234567980" 0.857 is the similarity between "47/2010" and "472010" 0.714 is the similarity between "47/2010" and "472011" 0.000 is the similarity between "47/2010" and "AB.CDEF" 0.125 is the similarity between "47/2010" and "4B.CDEFG" 0.000 is the similarity between "47/2010" and "AB.CDEFG" 0.700 is the similarity between "The quick fox jumped" and "The fox jumped" 0.350 is the similarity between "The quick fox jumped" and "The fox" 0.571 is the similarity between "kitten" and "sitting"

Tôi đã dịch thuật toán khoảng cách Levenshtein sang JavaScript:

String.prototype.LevenshteinDistance = function (s2) { var array = new Array(this.length + 1); for (var i = 0; i < this.length + 1; i++) array[i] = new Array(s2.length + 1); for (var i = 0; i < this.length + 1; i++) array[i][0] = i; for (var j = 0; j < s2.length + 1; j++) array[0][j] = j; for (var i = 1; i < this.length + 1; i++) { for (var j = 1; j < s2.length + 1; j++) { if (this[i - 1] == s2[j - 1]) array[i][j] = array[i - 1][j - 1]; else { array[i][j] = Math.min(array[i][j - 1] + 1, array[i - 1][j] + 1); array[i][j] = Math.min(array[i][j], array[i - 1][j - 1] + 1); } } } return array[this.length][s2.length]; };

Cảm ơn người trả lời đầu tiên, tôi nghĩ có 2 phép tính computeEditDistance (s1, s2). Do chi tiêu thời gian cao của nó, đã quyết định cải thiện hiệu suất của mã. Vì thế:

public class LevenshteinDistance { public static int computeEditDistance(String s1, String s2) { s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); int[] costs = new int[s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { int lastValue = i; for (int j = 0; j <= s2.length(); j++) { if (i == 0) { costs[j] = j; } else { if (j > 0) { int newValue = costs[j - 1]; if (s1.charAt(i - 1) != s2.charAt(j - 1)) { newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1; } costs[j - 1] = lastValue; lastValue = newValue; } } } if (i > 0) { costs[s2.length()] = lastValue; } } return costs[s2.length()]; } public static void printDistance(String s1, String s2) { double similarityOfStrings = 0.0; int editDistance = 0; if (s1.length() < s2.length()) { // s1 should always be bigger String swap = s1; s1 = s2; s2 = swap; } int bigLen = s1.length(); editDistance = computeEditDistance(s1, s2); if (bigLen == 0) { similarityOfStrings = 1.0; /* both strings are zero length */ } else { similarityOfStrings = (bigLen - editDistance) / (double) bigLen; } ////////////////////////// //System.out.println(s1 + "-->" + s2 + ": " + // editDistance + " (" + similarityOfStrings + ")"); System.out.println(editDistance + " (" + similarityOfStrings + ")"); } public static void main(String[] args) { printDistance("", ""); printDistance("1234567890", "1"); printDistance("1234567890", "12"); printDistance("1234567890", "123"); printDistance("1234567890", "1234"); printDistance("1234567890", "12345"); printDistance("1234567890", "123456"); printDistance("1234567890", "1234567"); printDistance("1234567890", "12345678"); printDistance("1234567890", "123456789"); printDistance("1234567890", "1234567890"); printDistance("1234567890", "1234567980"); printDistance("47/2010", "472010"); printDistance("47/2010", "472011"); printDistance("47/2010", "AB.CDEF"); printDistance("47/2010", "4B.CDEFG"); printDistance("47/2010", "AB.CDEFG"); printDistance("The quick fox jumped", "The fox jumped"); printDistance("The quick fox jumped", "The fox"); printDistance("The quick fox jumped", "The quick fox jumped off the balcany"); printDistance("kitten", "sitting"); printDistance("rosettacode", "raisethysword"); printDistance(new StringBuilder("rosettacode").reverse().toString(), new StringBuilder("raisethysword").reverse().toString()); for (int i = 1; i < args.length; i += 2) { printDistance(args[i - 1], args[i]); } } }