地址相似度算法
给到两个中文的地址，如何尽可能准确的获取这两个地址的相似度以判断这两个地址是否接近或一致？
一般思路会有两种。
一种是直接计算两个字符串的相似度，这种情况可能会因为模糊内容越多导致相似度计算不准确的情况，比如两个地区的同一个名字的街道，实际上在地理层面却相聚甚远。
一种就是直接通过该地址的GPS数据进行距离计算，如果经纬度相近，则可以认为这两个地址是相近，但无法确认它们是同一个地址，除非经纬度基本一致。
为了合理的判断两个地址的相似度以及地理上的相近情况。可以结合上面两种算法，共同计算相似度结果。
对于字符串相似度算法有很多，比如余弦相似度、矩阵相似度、字符串编辑距离等等算法。本文会采用编辑距离算法中的Jaro-Winkler算法。
1.编辑距离算法
public class JaroWinklerDistance {
private static final float threshold = 0.8f;
public static float getDegree(String s1, String s2) {
int[] mtp = matches(s1, s2);
// 返回匹配数目（m）
float m = (float) mtp[0];
if (m == 0) {
return 0f;
}
// Jaro Distance
float j = ((m / s1.length() + m / s2.length() + (m - mtp[1]) / m)) / 3;
// 计算Jaro-Winkler Distance， 这里调整分数的因数=Math.min(0.1f, 1f / mtp[3])
float jw = j < threshold ? j : j + Math.min(0.1f, 1f / mtp[3]) * mtp[2] * (1 - j);
return jw;
}
private static int[] matches(String s1, String s2) {
String max, min;
if (s1.length() > s2.length()) {
max = s1;
min = s2;
} else {
max = s2;
min = s1;
}
// 两个分别来自s1和s2的字符如果相距不超过 floor(max(|s1|,|s2|) / 2) -1, 我们就认为这两个字符串是匹配的,
// 因此，查找时，
// 超过此距离则停止
int range = Math.max(max.length() / 2 - 1, 0);
// 短的字符串, 与长字符串匹配的索引位
int[] matchIndexes = new int[min.length()];
Arrays.fill(matchIndexes, -1);
// 长字符串匹配的标记
boolean[] matchFlags = new boolean[max.length()];
// 匹配的数目
int matches = 0;
// 外层循环，字符串最短的开始
for (int mi = 0; mi < min.length(); mi++) {
char c1 = min.charAt(mi);
// 可能匹配的距离，包括从给定位置从前查找和从后查找
for (int xi = Math.max(mi - range, 0), xn = Math.min(mi + range + 1, max.length()); xi < xn; xi++) {
// 排除被匹配过的字符，若找到匹配的字符，则停止
if (!matchFlags[xi] && c1 == max.charAt(xi)) {
matchIndexes[mi] = xi;
matchFlags[xi] = true;
matches++;
break;
}
}
}
// 记录min字符串里匹配的字符串，保持顺序
char[] ms1 = new char[matches];
// 记录max字符串里匹配的字符串，保持顺序
char[] ms2 = new char[matches];
for (int i = 0, si = 0; i < min.length(); i++) {
if (matchIndexes[i] != -1) {
ms1[si] = min.charAt(i);
si++;
}
}
for (int i = 0, si = 0; i < max.length(); i++) {
if (matchFlags[i]) {
ms2[si] = max.charAt(i);
si++;
}
}
// 查找换位的数目
int transpositions = 0;
for (int mi = 0; mi < ms1.length; mi++) {
if (ms1[mi] != ms2[mi]) {
transpositions++;
}
}
// 查找相同前缀的数目
int prefix = 0;
for (int mi = 0; mi < min.length(); mi++) {
if (s1.charAt(mi) == s2.charAt(mi)) {
prefix++;
} else {
break;
}
}
// 返回匹配数目（m），换位的数目（t），相同的前缀的数目，字符串最长
return new int[] { matches, transpositions / 2, prefix, max.length() };
}
}2.GPS距离计算
根据中文地址获取GPS数据，可以通过地址库或者其他厂商的API获得，需要地址的具体的经度和纬度数据，再根据经纬度计算出两地相距的距离。根据距离给定一个相似度。
public class GpsUtils {
/**
* 地球半径
*/
private static final double EARTH_RADIUS = 6378137;
private static double rad(String d) {
return Double.valueOf(d) * Math.PI / 180.0;
}
public static double distance(Location location1, Location location2) {
if (location1 != null && location2 != null) {
return distance(location1.getLng(), location1.getLat(), location2.getLng(), location2.getLat());
}
return Integer.MAX_VALUE;
}
/**
* 根据两点间经纬度坐标（double值），计算两点间距离，单位为米
*
* @param lng1
* @param lat1
* @param lng2
* @param lat2
* @return
*/
public static double distance(String lng1, String lat1, String lng2, String lat2) {
double radLat1 = rad(lat1);
double radLat2 = rad(lat2);
double a = radLat1 - radLat2;
double b = rad(lng1) - rad(lng2);
double s = 2 * Math.asin(Math.sqrt(
Math.pow(Math.sin(a / 2), 2) + Math.cos(radLat1) * Math.cos(radLat2) * Math.pow(Math.sin(b / 2), 2)));
s = s * EARTH_RADIUS;
s = Math.round(s * 10000) / 10000;
return s;
}
/**
* 根据距离计算匹配度（参考）
*
* @param distance
* @return
*/
public static float getDegreeByDistance(double distance) {
float matchedDegree = 0f;
if (distance > 10000) {
matchedDegree = 0.0f; //( >10000) 0
} else if (distance > 5000) {
matchedDegree = 0.1f; //(5000~10000] 0.1
} else if (distance > 2000) {
matchedDegree = 0.2f; //(2000~5000] 0.2
} else if (distance > 1000) {
matchedDegree = 0.3f; //(1000~2000] 0.3
} else if (distance > 500) {
matchedDegree = 0.4f; //(500~1000] 0.4
} else if (distance > 200) {
matchedDegree = 0.5f; //(200~500] 0.5
} else if (distance > 100) {
matchedDegree = 0.6f; //(100~200] 0.6
} else if (distance > 50) {
matchedDegree = 0.7f; //(50~100] 0.7
} else if (distance > 20) {
matchedDegree = 0.8f;//(20~50] 0.8
} else if (distance > 10) {
matchedDegree = 0.9f; //(10~20] 0.9
} else {
matchedDegree = 0.95f;//[0~10] 0.9
}
return matchedDegree;
}
}public class Location {
private static final long serialVersionUID = 1L;
/**经度*/
private String lng;
/**纬度*/
private String lat;
public Location(){
}
public Location(String lng, String lat) {
super();
this.lng = lng;
this.lat = lat;
}
public String getLng() {
return lng;
}
public void setLng(String lng) {
this.lng = lng;
}
public String getLat() {
return lat;
}
public void setLat(String lat) {
this.lat = lat;
}
@Override
public String toString() {
return "Location [lng=" + lng + ", lat=" + lat + "]";
}
}
3.最终计算（参考）
//根据gps距离计算得到的匹配度
double distance = GpsUtils.distance(location1, location2);
float gpsMatchedDegree = GpsUtils.getDegreeByDistance(distance);
if (gpsMatchedDegree == 0.0f) {
System.out.println("GPS距离过大");
return;
}
System.out.println("GPS匹配度:" + gpsMatchedDegree);
//字符串相似度匹配
float stringDegree = JaroWinklerDistance.getDegree(address1, address2);
System.out.println("字符串相似匹配度: " + stringDegree);
float result = 0.0f;
//根据两个匹配度确认最终相似度
if (stringDegree >= 0.5f && gpsMatchedDegree >= 0.5f) {
result = Math.min(stringDegree, gpsMatchedDegree);
} else if (stringDegree < 0.5f && gpsMatchedDegree < 0.5f) {
result = Math.max(stringDegree, gpsMatchedDegree);
} else {
result = (stringDegree + gpsMatchedDegree) / 2;
}
System.out.println("最终匹配度: " + result);