- 浏览: 134820 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
zheng_zhimeng:
这个版本在linux的版本下有问题,亲们用的没有问题么
文档展示:IcePDF 将PDF转换为图片 -
yuming.xiao:
转换的某些图片,有些模糊。不知道楼主遇到这个问题没有
文档展示:IcePDF 将PDF转换为图片 -
zenghongqing:
您好,请教您一个问题://cell内容字符串总宽度 doub ...
Java POI Excel 行高自适应 -
xiang37:
http://xiva.iteye.com/blog/2066 ...
视频分割项目预研 -
I白I:
怎么还配置数据库了?
视频分割项目预研
前一篇博文:
http://zhuyufufu.iteye.com/blog/1989482
实现了我的一个相似度简单算法,但是其缺陷十分明显。这两天查找了一些资料,找到了应用编辑距离计算字符串相似度的算法。
俄罗斯科学家Vladimir Levenshtein在1965年提出这个编辑距离概念。
现在我就用这个算法实现变位词的相似度计算。也算是站在巨人的肩膀上了吧!
参考资料:
levenshtein距离
http://baike.baidu.com/view/4123766.htm
编辑距离
http://baike.baidu.com/view/2020247.htm
字符串相似度算法
http://wdhdmx.iteye.com/blog/1343856#bc2305994
对于字符串相似度算法:第二个和第三个链接的内容解释的非常清楚,我就不做赘述了。
变位词的相似度计算算法简要设计:
1.对两个单词按字母排序
2.计算排序后的编辑距离
3计算得到相似度
重构了第三篇博文中的字符串相似度算法程序
按照设计的算法计算变位词相似度
修改后的算法仍然没有解决原来的问题:
算法的缺陷:举例说明 abc 与 cbc 在本算法中相似度为 1/3;正常人看应该为 2/3。
看来有必要重新想一个算法了。
希望本博客的朋友们能提供一些想法。
非常感谢!
http://zhuyufufu.iteye.com/blog/1989482
实现了我的一个相似度简单算法,但是其缺陷十分明显。这两天查找了一些资料,找到了应用编辑距离计算字符串相似度的算法。
俄罗斯科学家Vladimir Levenshtein在1965年提出这个编辑距离概念。
现在我就用这个算法实现变位词的相似度计算。也算是站在巨人的肩膀上了吧!
参考资料:
levenshtein距离
http://baike.baidu.com/view/4123766.htm
编辑距离
http://baike.baidu.com/view/2020247.htm
字符串相似度算法
http://wdhdmx.iteye.com/blog/1343856#bc2305994
对于字符串相似度算法:第二个和第三个链接的内容解释的非常清楚,我就不做赘述了。
变位词的相似度计算算法简要设计:
1.对两个单词按字母排序
2.计算排序后的编辑距离
3计算得到相似度
重构了第三篇博文中的字符串相似度算法程序
package com.zas.anagram; /** * @className:Levenshtein.java * @classDescription:Levenshtein Distance 算法实现 * 可以使用的地方:DNA分析 拼字检查 语音辨识 抄袭侦测 * @author:donghai.wan * @createTime:2012-1-12 */ public class Levenshtein { public static void main(String[] args) { //要比较的两个字符串 String str1 = "今天星期四"; String str2 = "今天是星期五"; System.out.println("相似度为: " + getSimilarity(str1, str2)); } /** * 求字符串相似度 * @param str1 * @param str2 * @return */ public static Float getSimilarity(String str1,String str2) { int levenshteinLength = levenshtein(str1,str2); //计算相似度 float similarity =1 - (float) levenshteinLength / Math.max(str1.length(), str2.length()); return similarity; } /** * 获取编辑距离 * @param str1 * @param str2 * @return */ public static int levenshtein(String str1, String str2) { // 计算两个字符串的长度。 int len1 = str1.length(); int len2 = str2.length(); // 建立上面说的数组,比字符长度大一个空间 int[][] dif = new int[len1 + 1][len2 + 1]; // 赋初值,步骤B。 for (int a = 0; a <= len1; a++) { dif[a][0] = a; } for (int a = 0; a <= len2; a++) { dif[0][a] = a; } // 计算两个字符是否一样,计算左上的值 int temp; for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (str1.charAt(i - 1) == str2.charAt(j - 1)) { temp = 0; } else { temp = 1; } // 取三个值中最小的 dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, dif[i - 1][j] + 1); } } // 取数组右下角的值,同样不同位置代表不同字符串的比较 return dif[len1][len2]; } /** * 得到最小值 * @param is * @return */ private static int min(int... is) { int min = Integer.MAX_VALUE; for (int i : is) { if (min > i) { min = i; } } return min; } }
按照设计的算法计算变位词相似度
package com.zas.anagram; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileReader; import java.io.FileWriter; import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set; /** * 变位词算法设计 * @author zas * */ public class Anagram { /** * @param args */ public static void main(String[] args) { System.out.println(Anagram.getSimilarity(null, null)); System.out.println(Anagram.getSimilarity("", "")); System.out.println(Anagram.getSimilarity("", null)); System.out.println(Anagram.getSimilarity(null, "")); System.out.println(Anagram.getSimilarity(null, "cba")); System.out.println(Anagram.getSimilarity("cba", null)); System.out.println(Anagram.getSimilarity("abc", "cba")); System.out.println(Anagram.getSimilarity("abc", "cbaa")); System.out.println(Anagram.getSimilarity("abc", "cbc")); System.out.println(Anagram.getSimilarity("", "cbc")); System.out.println(Anagram.getSimilarity("abc", "")); System.out.println(Anagram.getSimilarity("abc", "acff")); } /** * 给出一个两个字符串互为变位词的相似度算法。 * 当他们为变位词的时候输出1.0; * 当他们长度不同且没有相同字母时输出0; * 其他情况给出一个规则输出一个0到1之间的浮点数。 * @param wordA * @param wordB * @return */ public static Float getSimilarity(String wordA, String wordB) { /** * 算法设计说明: * 一.是变位词与彻底不是变位词都有明确的定义 * 二.其余情况处理如下: * 1. 取排序后的单词 * 2. 计算其字符串相似度 */ //是变位词,返回1 if(isAnagram(wordA, wordB)){ return 1f; } if(isNotAnagram(wordA, wordB)){ return 0f; } //return getSimilarityByMap(wordA,wordB); return getSimilarityByLevenshtein(wordA,wordB); } private static Float getSimilarityByLevenshtein(String wordA, String wordB) { //获取两个单词的小写复本 wordA = wordA.toLowerCase(); wordB = wordB.toLowerCase(); //对两个单词按字母大小顺序排序 wordA = sort(wordA); wordB = sort(wordB); return Levenshtein.getSimilarity(wordA, wordB); } /** * 给出一个两个字符串互为变位词的相似度算法。 * @param wordA * @param wordB * @return */ private static Float getSimilarityByMap(String wordA, String wordB) { /** * 算法设计说明: * 一.是变位词与彻底不是变位词都有明确的定义 * 二.其余情况处理如下: * 1. 取两个单词长度较大的作为基准单词,如:abc与acff 则取acff作为基准单词。 * 2. 计算要增删多少个单词才能使长度小的单词达到长度大的那样,以 abc、acff为例:abc要删除b增加ff,则需要操作3个字母 * 3. 相似度公式 1 - 操作的字母数/基准单词长度 ,上例则为:1 - 3/4 = 0.25 */ //基准单词 String word = wordA; String otherWord = wordB; if(wordA.length() < wordB.length()){ word = wordB; otherWord = wordA; } Map<Character, Integer> mapWord = getWordMap(word); Map<Character, Integer> mapForOtherWord = getWordMap(otherWord); int count = getOperateCount(mapWord, mapForOtherWord); float result = 1f - (float)count/word.length(); return result; } /** * @param mapWord 基准单词 长单词 * @param mapForOtherWord 短单词 * @return */ private static int getOperateCount(Map<Character, Integer> mapWord, Map<Character, Integer> mapForOtherWord) { // 字母操作计数器 int count = 0; Set<Character> key = mapWord.keySet(); for (Iterator<Character> it = key.iterator(); it.hasNext();) { Character c = (Character) it.next(); Integer charCount = mapWord.get(c); Integer charCountOther = mapForOtherWord.get(c); // 短单词中没有字母时字母操作数加上字母数 if (null == charCountOther) { count = count + charCount; } else { // 否则加上字母个数差值的绝对值 count = count + Math.abs(charCount - charCountOther); } } Set<Character> keyOther = mapForOtherWord.keySet(); for (Iterator<Character> it = keyOther.iterator(); it.hasNext();) { Character c = (Character) it.next(); Integer charCount = mapWord.get(c); Integer charCountOther = mapForOtherWord.get(c); // 短单词中没有字母时字母操作数加上字母数 if (null == charCount) { count = count + charCountOther; } } return count; } /** * 判断是否不为变位词 * @param wordA * @param wordB * @return */ private static boolean isNotAnagram(String wordA, String wordB) { //当为变位词时,返回false if(isAnagram(wordA, wordB)){ return false; } //处理null if(null == wordA && null != wordB){ return true; } if(null != wordA && null == wordB){ return true; } //当他们长度不同且没有相同字母时不是变位词 if(wordA.length() != wordB.length()){ for (int i = 0; i < wordA.length(); i++) { if(wordB.contains(String.valueOf(wordA.charAt(i)))){ return false; } } return true; } return false; } /** * 判断两个单词是否互为变位词 * @param string * @param string2 * @return true/false */ public static boolean isAnagram(String wordA, String wordB) { //异常情况处理 if(null == wordA && null == wordB){ return true; } if(false == handleNull(wordA, wordB)){ return false; } return isAnagramBySort(wordA, wordB); //return isAnagramByMap(wordA, wordB); } /** * 处理异常情况 返回 true表示要继续处理 false表示不为变位词 * @param wordA * @param wordB * @return true/false */ private static boolean handleNull(String wordA, String wordB) { //一个为空,另一个不为空不是变位词 if(null == wordA && null != wordB){ return false; } if(null == wordB && null != wordA){ return false; } //长度不同不为变位词 if(wordA.length() != wordB.length()){ return false; } return true; } /** * 通过排序后比较其是否相同判断是否为变位词 * @param wordA * @param wordB * @return true/false */ private static boolean isAnagramBySort(String wordA, String wordB) { //获取两个单词的小写复本 wordA = wordA.toLowerCase(); wordB = wordB.toLowerCase(); //对两个单词按字母大小顺序排序 wordA = sort(wordA); wordB = sort(wordB); if(wordA.equals(wordB)){ return true; } return false; } /** * 按字母顺序排序字符串 * @param wordA * @return */ private static String sort(String word) { char[] charArray = word.toCharArray(); //排序基本为小数据量的,因此采用冒泡、选择、插入中的一种,这里选择选择排序 for (int i = 0; i < charArray.length; i++) { //内层循环找到未排序的最小字母 int selectedIndex = i; for (int j = 0; j < charArray.length; j++) { if(charArray[selectedIndex] > charArray[j]){ selectedIndex = j; } } if(selectedIndex != i){ char tempForSwap = charArray[selectedIndex]; charArray[selectedIndex] = charArray[i]; charArray[i] = tempForSwap; } } return String.valueOf(charArray); } /** * 通过 字母-字母个数 键值对来判断变位词 * @param wordA * @param wordB * @return true false; */ private static boolean isAnagramByMap(String wordA, String wordB) { Map<Character, Integer> mapForWordA = getWordMap(wordA); Map<Character, Integer> mapForWordB = getWordMap(wordB); //字母的个数不同肯定不是变位词 if(mapForWordA.size() != mapForWordB.size()){ return false; } //迭代mapForWordA的字母 并在mapForWordB中获得对应的字母个数 若不同则不是变位词 Set<Character> key = mapForWordA.keySet(); for (Iterator<Character> it = key.iterator(); it.hasNext();) { Character c = (Character) it.next(); Integer charCountA = mapForWordA.get(c); Integer charCountB = mapForWordB.get(c); if(charCountA != charCountB){ return false; } } return true; } /** * 获得一个字符串的字母-字母个数键值对 * @param wordA * @return */ private static Map<Character, Integer> getWordMap(String word) { Map<Character, Integer> map = new HashMap<Character, Integer>(); char[] charArray = word.toCharArray(); for (int i = 0; i < charArray.length; i++) { Character c = charArray[i]; Integer charCount = map.get(c); if(null == charCount){ charCount = 1; }else{ charCount = charCount + 1; } map.put(c, charCount); } return map; } /** * 从文件中获取词典列表 * @param path * @return List<String> */ private static List<String> getWordsListFromFile(String path) { List<String> wordList = new ArrayList<String>(); File file = new File(path); FileReader fr = null; BufferedReader br = null; try{ fr = new FileReader(file); br = new BufferedReader(fr); String s; while((s = br.readLine()) != null){ //去首尾空白 s = s.trim(); wordList.add(s); } }catch(FileNotFoundException e){ e.printStackTrace(); }catch (Exception e) { e.printStackTrace(); }finally{ if(br != null){ try { br.close(); } catch (IOException e) { e.printStackTrace(); } } if(fr != null){ try { fr.close(); } catch (IOException e) { e.printStackTrace(); } } } return wordList; } /** * 获取所有变位词集合列表 * @param wordList * @return */ private static Map<String, List<String>> getAnagramCollectionMap(List<String> wordList) { Map<String, List<String>> anagramCollectionMap = new HashMap<String, List<String>>(); while(wordList.size() > 0){ String word = wordList.remove(0); //将单词存入变位词集合map中 //这里有两种算法,一种是把单词排序之后放入map这样就不需要遍历map //另一种是遍历map的key判断它是否和该单词互为变位词 //这里采用第一种 String sortedWord = sort(new String(word).toLowerCase()); List<String> list = anagramCollectionMap.get(sortedWord); if(list == null){ list = new ArrayList<String>(); } list.add(word); anagramCollectionMap.put(sortedWord, list); } return anagramCollectionMap; } /** * 根据某种条件从map集中获取符合条件的列表 可以考虑实现一个说明模式 * 为了演示简便,给出获取特定大小变位词集合的实现 * @param anagramCollectionMap * @return */ private static Map<String, List<String>> getAnagramCollectionMapByCondition(Map<String, List<String>> anagramCollectionMap, int size) { Map<String, List<String>> resultMap = new HashMap<String, List<String>>(); Set<String> key = anagramCollectionMap.keySet(); for (Iterator<String> it = key.iterator(); it.hasNext();) { String str = (String) it.next(); List<String> list= anagramCollectionMap.get(str); if(list.size() == size){ resultMap.put(str, list); } } return resultMap; } /** * 向文件中输出变位词集合列表 * @param path * @return */ private static void writeWordsListToFile(String path, Map<String, List<String>> anagramCollectionMap) { File file = new File(path); FileWriter fw = null; BufferedWriter bw = null; try{ fw = new FileWriter(file); bw = new BufferedWriter(fw); Set<String> key = anagramCollectionMap.keySet(); for (Iterator<String> it = key.iterator(); it.hasNext();) { String str = (String) it.next(); List<String> list= anagramCollectionMap.get(str); bw.write(str + list.toString()); bw.newLine(); } }catch(FileNotFoundException e){ e.printStackTrace(); }catch (Exception e) { e.printStackTrace(); }finally{ if(bw != null){ try { bw.close(); } catch (IOException e) { e.printStackTrace(); } } if(fw != null){ try { fw.close(); } catch (IOException e) { e.printStackTrace(); } } } } }
修改后的算法仍然没有解决原来的问题:
算法的缺陷:举例说明 abc 与 cbc 在本算法中相似度为 1/3;正常人看应该为 2/3。
看来有必要重新想一个算法了。
希望本博客的朋友们能提供一些想法。
非常感谢!
发表评论
-
oracle按照某一字段里的数字排序
2014-10-21 19:59 1024select * from LSK_SBCAJ t ord ... -
JS onkeydown onenter
2014-10-20 16:53 957html中 onenter不是一个标准的事件。 js 中仿o ... -
Java数组删除指定元素
2014-09-18 11:30 2205package com.zas.util; impo ... -
sql 去重
2014-09-18 10:43 575delete from table t1 where t1.i ... -
linux 干掉所有java进程
2014-08-07 12:31 992ps -ef|grep java|grep -v grep|c ... -
Oracle自带连接池使用(转载收录)
2014-07-31 10:01 1359最近在搞数据迁移:从sql server 迁数据到oracle ... -
html dom jsoup httpclient
2014-07-10 21:45 1050xml dom 对大多数java程序员来说并不陌生,但是htm ... -
Oracle 清库脚本
2014-07-08 22:40 1254清库脚本一份 表dossier_group 的字段Dossi ... -
Java 对象存储到oracle Blob字段
2014-07-08 14:52 1056Java 数据对象在没有持久存储到业务表时,可能需要临时存 ... -
Java 科学计数法数字转字符串
2014-07-08 14:30 1425科学计数法数字转字符串,记录代码,留后使用 double ... -
突破tomcat jsp编译65535行的限制
2014-07-04 17:16 4669使用tomcat时有可能会遇到其对jsp编译行数的限制, ... -
oracle 函数中游标及递归的应用
2014-06-19 17:13 1367在代码中使用递归可能大部分程序员都不陌生,但是在存储过程或 ... -
视频操作类
2014-06-19 17:04 1082接 视频分割项目预研 http://zhuyufufu.i ... -
视频分割项目预研
2014-06-11 16:12 2157由于工作需要,研究下视频切割。 现在的情况:视频切割是重中之 ... -
Java POI Excel 行高自适应
2014-03-28 14:08 15581在Excel处理的过程中,可能有需要用到行高自适应的时候。 ... -
Java POI Excel sheet 合并遇到的问题解决2
2014-03-25 18:03 3168上接 Java POI Excel sheet 合并 http ... -
文档展示:使用iText转换各种图片为PDF
2014-03-23 12:38 2844如题: 下面这段代码可以处理各种格式的图片,代码的出处忘记了 ... -
Java 进程执行外部程序,造成外部程序阻塞的一种原因
2014-03-23 12:06 1423前一阵子在研究文档展示时使用了java进程直接调用外部程序 ... -
Java POI Excel sheet 合并遇到的问题解决
2014-03-23 11:30 5012上接 Java POI Excel sheet http:// ... -
Java POI Excel sheet合并
2014-03-19 10:59 6559由于工作上的需要,特地研究了下Excel合并的问题,现贴出来, ...
相关推荐
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
Java 实现推荐系统 两个字符串 余弦相似度 算法。
两个字符串,计算出两个字符串的相似度,用于模糊匹配,很简单的小例子
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
Levenshtein算法python也是用的这个对比字符串相似度的,还不错
主要介绍了java字符串相似度算法,是Java实现比较典型的算法,具有一定参考借鉴价值,需要的朋友可以参考下
java 计算字符串相似度
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
Delphi计算或比较两组字符串的相似程度 对字符串进行挨个读取并进行比对,取得相似度
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
NULL 博文链接:https://biansutao.iteye.com/blog/326008
一个实现不同字符串相似度和距离度量的库。目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟、Jaro-Winkler、最长公共子序列、余弦相似度等)。查看下面的汇总表以获取完整列表... python字符串相似度 下载 ...
针对传统字符串相似度算法复杂的局限,在向量空间模型(VSM)的基础上,提出一种同时考虑字符相邻位置关系和词序的字符串相似度计算模型。通过计算VSM中向量的汉明距离来描述字符串相邻程度,并以向量的曼哈顿距离...
Levenshtein:快速计算编辑距离以及字符串的相似度
编辑距离算法,比较字符串相似度 pb11.5版本
Java字符串相似度 一个实现不同字符串相似度和距离度量的库。 当前实现了十二种算法(包括Levenshtein编辑距离和同级,Jaro-Winkler,最长公共子序列,余弦相似性等)。 查看下面的摘要表以获取完整列表... 下载 ...
这个demo运行起来要注意,字符串数量不能太大,不然会发生内存泄漏
两个字符串的相似度算法实现——编辑距离之Levenshtein距离
一个完整可直接用的LD算法计算两个字符串之间的相似度。