需求:比较两个地址相似程度
1, 排除数字, 排除字母(大小写), 特殊符号
如以下三个地址都可以认为是实际相同,只是表述不同:
湖北省-武汉市-东西湖区 湖北省武汉市东西湖区革新大道四明路物流园c5
湖北省-武汉市-东西湖区 革新大道四明路物流园c5门
湖北省-武汉市-东西湖区 革新大道四明路南特1号
实际上,这些地址,前两个是相同的, 第三个是不同的
思路:
1, 格式化地址, 重复的去掉
2, 去掉数字, 排除字母(大小写), 特殊符号
3, 选取算法
目前能处理的字符串相同的算法很多,常见的:
1)SimHash:算法的主要思想是降维,将高维的特征向量映射成一个f-bit的指纹(fingerprint),通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。由于每篇文章我们都可以事先计算好Hamming Distance来保存,到时候直接通过Hamming Distance来计算,所以速度非常快适合大数据计算,google用的就是这个。但是SimHash对于短文本误判率比较高,因此建议大于500字以上的使用此算法。
2)汉明距离: 以理查德·卫斯里·汉明的名字命名的。在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
"toned" 与 "roses" 之间的汉明距离是 3。
3)Levenshtein 距离: 又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。
许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
java中也有实现的工具类:org.apache.commons.lang.StringUtils.getLevenshteinDistance(str1, str2);
可用于:DNA分析,拼字检查,语音辨识,抄袭侦测
4)余弦定理:通过对两个文本分词,TF-IDF算法向量化,对比两者的余弦夹角,夹角越小相似度越高,但由于有可能一个文章的特征向量词特别多导致整个向量维度很高,使得计算的代价太大不适合大数据量的计算。
经过一番测试后, 选择余弦定理
具体实例入下:
未采用分词
import java.io.UnsupportedEncodingException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class CosineSimilarAlgorithm {
public static double getSimilarity(String content1, String content2) {
Map<Integer, int[]> wordMap = new HashMap<Integer, int[]>();
// 将两个字符串中的中文字符以及出现的总数封装到,AlgorithmMap中
char[] char1 = content1.toCharArray();
for (int i = 0; i < char1.length; i++) {
if(isHanZi(char1[i])){
int charIndex = getGB2312Id(char1[i]);
if(charIndex != -1){
int[] fq = wordMap.get(charIndex);
if(fq != null && fq.length == 2){
fq[0]++;
}else {
fq = new int[2];
fq[0] = 1;
fq[1] = 0;
wordMap.put(charIndex, fq);
}
}
}
}
char[] char2 = content2.toCharArray();
for (int i = 0; i < char2.length; i++) {
if(isHanZi(char2[i])){
int charIndex = getGB2312Id(char2[i]);
if(charIndex != -1){
int[] fq = wordMap.get(charIndex);
if(fq != null && fq.length == 2){
fq[1]++;
}else {
fq = new int[2];
fq[0] = 0;
fq[1] = 1;
wordMap.put(charIndex, fq);
}
}
}
}
Iterator<Integer> iterator = wordMap.keySet().iterator();
double sqdoc1 = 0;
double sqdoc2 = 0;
double denominator = 0;
while(iterator.hasNext()){
int[] c = wordMap.get(iterator.next());
denominator += c[0]*c[1];
sqdoc1 += c[0]*c[0];
sqdoc2 += c[1]*c[1];
}
return denominator / Math.sqrt(sqdoc1*sqdoc2);
}
public static boolean isHanZi(char ch) {
// 判断是否汉字
return (ch >= 0x4E00 && ch <= 0x9FA5);
}
/**
* 根据输入的Unicode字符,获取它的GB2312编码或者ascii编码,
*
* @param ch 输入的GB2312中文字符或者ASCII字符(128个)
* @return ch在GB2312中的位置,-1表示该字符不认识
*/
public static short getGB2312Id(char ch) {
try {
byte[] buffer = Character.toString(ch).getBytes("GB2312");
if (buffer.length != 2) {
// 正常情况下buffer应该是两个字节,否则说明ch不属于GB2312编码,故返回'?',此时说明不认识该字符
return -1;
}
int b0 = (int) (buffer[0] & 0x0FF) - 161; // 编码从A1开始,因此减去0xA1=161
int b1 = (int) (buffer[1] & 0x0FF) - 161; // 第一个字符和最后一个字符没有汉字,因此每个区只收16*6-2=94个汉字
return (short) (b0 * 94 + b1);
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
}
return -1;
}
public static void main(String[] args) {
String address1 = "湖北省-武汉市-东西湖区 革新大道四明路物流园c5门";
String address2 = "湖北省-武汉市-东西湖区 革新大道四明路南特1号";
System.out.println(getSimilarity(address1, address2));
}
}
方案一:
1, 规整地址后(去掉重复省市, 特殊符号,数字,字母)
2, 结合上面的代码
方案二:
1, 规整地址后(去掉重复省市, 特殊符号,数字,字母)
2, 结合上面的代码(加入分词概念), 地址词库的完整直接关系到判断的准确性.
对比方案一和方案二选取最优的一个.
看官若有好的建议,欢迎拍砖
分享到:
相关推荐
使用 OpenCV 和 Python 检测两个图像的相似程度 基于SIFT算法,包括代码和数据
实施八个评估指标来访问两个图像之间的相似性。这八个指标如下:RMSE、PSNR、SSIM、ISSM、FSIM、SRE、SAM 和 UIQ。 图像相似度测量 实施八个评估指标来访问两个图像之间的相似性。八项指标如下: 均方根误差 (RMSE...
MATLAB编写的计算一幅图像投影熵,用来计较两幅图像的相似程度
最近有个需求,是做两个数组重复程度计算,麻烦就麻烦在单个数组的元素有可能重复,处理思路如下: 1. 找到重复元素 2. 元素个数统计,利用np.bincount转换,即元素个数统计到元素转化的索引 3. 统计相同元素匹配个...
类基因由4种核苷酸 分别用字母ACTG表示 要求编写一个程序 按以下规划比较两个基因序列并确定它们的相似程度 即两 给出两个基因序列AGTGATG和GTTAG 它们有多相似呢 测量两个基因的相似度一种方法称为对齐 使用对齐...
1.对于任意两个图形的相似程度必须得出一个量化的结果,在此称为图形相似度。 2.对图形形状的检测必须忽略 大小、旋转、轴对称、连线顺序的影响。 3.对于相同的图形,形状相似度必须为1;对于不相同的图形,形状...
要求编写一个程序,按以下规划比较两个基因序列并确定它们的相似程度。即两给出两个基因序列AGTGATG和GTTAG,它们有多相似呢?测量两个基因的相似度一种方法称为对齐。使用对齐方法可以在基因的适当位置加入空格,让...
C#比较照片的相似度,之前找的一个不好用,现在这个测试了一下还是不错的,有需要可以下载看一下
针对目前的软件盗版现象,在没有软件源代码的情形下提出一种程序相似性的比较方法。...最后的试验数据表明,该方法能够有效地检测出相似程度不一的各组程序之间的相似度,具有一定的可信度和适用性。
Win32 API to compare two images(.gif,.jpg,.bmp)
两个序列,例如S1 = {a, b, c, d}、 S2 = {a, c, b, d},如何度量它们的相似程度,有很重要的应用背景,在投票决策、表达式搜索、top-k比较、乃至搜索引擎优化等问题上有广泛的应用ref1,ref2。Kendall's tau则是其中...
为了更加准确地度量两个模型之间的形状差异,提出了一种基于粒子群的模型相似性计算方法。利用面的组成边数来构造面相似度矩阵,通过粒子群算法对该矩阵...实验结果表明,该方法能够准确地度量两个模型之间的相似程度。
图像比较 比较两个图像并查看它们使用 CCV 的相似程度。 在 C# 中实现。
对于两个C++程序,设计并实现两种不同的基于Hash表的检测算法(开地址法和链地址法),计算两个程序的相似度,并分析比较两种算法的效率。 分别读取两个C++程序文件(p1.cpp, p2.cpp),自行设计哈希函数,分别利用...
灰色关联度程序详细代码,对于两个系统之间的因素,其随时间或不同对象而变化的关联性大小的量度,称为关联度。在系统发展过程中,若两个因素变化的趋势具有一致性,即同步变化程度较高,即可谓二者关联程度较高;...
此代码通过生成高斯系数的灵敏度矩阵来比较两个地磁场模型的相似程度。 因此,此功能可用于将您制作的地磁模型与标准参考场模型进行比较。 对于地球,标准参考模型包括: > 世界磁模型 ( ...
图片相似图识别 主要功能: 支持识别,经过角度旋转,经过干扰,经过扭曲,完全不相同但近似的图。 论坛的很多图片相似度识别源码,大体都只能对比图片高度一致的图片才有效,对于经过了旋转角度,颜色干扰,或者...
设计18个(9对)从临床靶区中抽象出的轮廓,计算并比较这两类相似性系数。结果:根据比较结果,总结出3种不同类型情况:(1)图像符合度 好;(2)图像整体符合度好,但存在一小部分符合度差;(3)图像轮廓符合度差...
基于文本的数学算法,通过比较两个文本的一致内容,确定文本相似程度