- 浏览: 139582 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
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 1095select * from LSK_SBCAJ t ord ... -
JS onkeydown onenter
2014-10-20 16:53 1011html中 onenter不是一个标准的事件。 js 中仿o ... -
Java数组删除指定元素
2014-09-18 11:30 2265package com.zas.util; impo ... -
sql 去重
2014-09-18 10:43 661delete from table t1 where t1.i ... -
linux 干掉所有java进程
2014-08-07 12:31 1037ps -ef|grep java|grep -v grep|c ... -
Oracle自带连接池使用(转载收录)
2014-07-31 10:01 1417最近在搞数据迁移:从sql server 迁数据到oracle ... -
html dom jsoup httpclient
2014-07-10 21:45 1131xml dom 对大多数java程序员来说并不陌生,但是htm ... -
Oracle 清库脚本
2014-07-08 22:40 1322清库脚本一份 表dossier_group 的字段Dossi ... -
Java 对象存储到oracle Blob字段
2014-07-08 14:52 1108Java 数据对象在没有持久存储到业务表时,可能需要临时存 ... -
Java 科学计数法数字转字符串
2014-07-08 14:30 1521科学计数法数字转字符串,记录代码,留后使用 double ... -
突破tomcat jsp编译65535行的限制
2014-07-04 17:16 4806使用tomcat时有可能会遇到其对jsp编译行数的限制, ... -
oracle 函数中游标及递归的应用
2014-06-19 17:13 1432在代码中使用递归可能大部分程序员都不陌生,但是在存储过程或 ... -
视频操作类
2014-06-19 17:04 1151接 视频分割项目预研 http://zhuyufufu.i ... -
视频分割项目预研
2014-06-11 16:12 2289由于工作需要,研究下视频切割。 现在的情况:视频切割是重中之 ... -
Java POI Excel 行高自适应
2014-03-28 14:08 15937在Excel处理的过程中,可能有需要用到行高自适应的时候。 ... -
Java POI Excel sheet 合并遇到的问题解决2
2014-03-25 18:03 3272上接 Java POI Excel sheet 合并 http ... -
文档展示:使用iText转换各种图片为PDF
2014-03-23 12:38 2928如题: 下面这段代码可以处理各种格式的图片,代码的出处忘记了 ... -
Java 进程执行外部程序,造成外部程序阻塞的一种原因
2014-03-23 12:06 1471前一阵子在研究文档展示时使用了java进程直接调用外部程序 ... -
Java POI Excel sheet 合并遇到的问题解决
2014-03-23 11:30 5136上接 Java POI Excel sheet http:// ... -
Java POI Excel sheet合并
2014-03-19 10:59 6643由于工作上的需要,特地研究了下Excel合并的问题,现贴出来, ...
相关推荐
字符串相似度算法 字符串相似度算法是一种衡量两个字符串之间相似度的方法,广泛应用于自然语言处理、数据挖掘、机器学习等领域。在本文中,我们将讨论一种常用的字符串相似度算法:Levenshtein Distance。 什么是...
在计算机科学领域,字符串相似度比较算法是一种用于评估两个字符串之间相似程度的技术。这些算法广泛应用于文本处理、信息检索、生物信息学等多个领域。当我们要判断两个字符串是否含有相同或相近的信息时,这类算法...
在IT领域,字符串相似度算法是一种非常重要的工具,特别是在数据挖掘、信息检索、文本分类以及自然语言处理等应用中。这个小例子旨在介绍如何通过计算字符串间的相似度来进行模糊匹配。我们将探讨几种常见的字符串...
《使用Delphi实现Levenshtein算法:计算字符串相似度》 在信息技术领域,字符串处理是常见的任务之一,其中计算两个字符串的相似度是尤为重要的一个环节。Levenshtein算法,也称为编辑距离算法,就是用于衡量两个...
根据给定的文件信息,本文将详细介绍如何使用Java实现基于字符串的余弦相似度算法,并应用于推荐系统中。 ### 一、引言 在推荐系统领域,为了衡量两个字符串之间的相似性,通常会采用多种算法,其中余弦相似度算法...
Levenshtein算法,也称为编辑距离算法,是由俄国数学家Vladimir Levenshtein在1965年提出的一种衡量两个字符串相似度的方法。这个算法基于动态规划原理,可以计算出将一个字符串转换成另一个字符串所需要的最少单...
本篇文章将深入探讨如何使用DELPHI编程语言实现LCS(最长公共子序列)算法来衡量两个字符串的相似度。LCS算法是一种找出两个序列中最长的相同子序列的算法,它不考虑子序列的顺序,对于字符串而言,就是找到最长的...
**字符串相似度算法——Levenshtein Distance(编辑距离)** 在信息技术和计算机科学领域,字符串相似度计算是一个重要的概念,特别是在文本处理、搜索引擎优化、数据校验和生物信息学等多个场景中。Levenshtein ...
Java字符串相似度算法是用于衡量两个字符串之间相似程度的一种计算方法。在文本处理、信息检索、数据清洗等领域中,这种算法具有重要的应用价值。这里主要介绍了一种基于Levenshtein距离的Java实现。 Levenshtein...
总之,Delphi提供了丰富的工具和功能来处理字符串相似度计算,开发者可以根据具体需求选择合适的算法并进行实现。在实际项目中,理解和运用这些算法可以帮助我们更好地理解和比较文本数据,提升应用程序的功能和用户...
### MySQL 计算字符串相似度 #### 背景与需求 在许多应用场景中,我们需要对两个字符串进行相似度比较,比如搜索引擎中的关键词匹配、文本分析中的近义词识别等。MySQL 提供了多种方法来实现字符串相似度的计算,...
java 计算字符串相似度
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
本文将深入探讨字符串相似度比较的概念、常用算法以及在JavaScript中的实现,同时关注潜在的性能和内存管理问题。 字符串相似度比较旨在量化两个或多个字符串之间的相似程度,通常以百分比形式表示。这种比较不仅...
在IT领域,字符串相似度匹配是一项重要的技术,广泛应用于数据清洗、文本检索、信息过滤、推荐系统等多个场景。本主题将深入探讨“两个字符串相似度匹配”的概念、方法及其实现。 字符串相似度匹配旨在量化两个字符...
在这个"LD的两字符串相似度计算.zip"压缩包中,可能包含了一个名为"readme.txt"的文件,它可能解释了如何使用这个算法或者给出了一个示例。另外,"com"可能是程序代码的组成部分,可能是一个Python、Java或其他编程...
一个实现不同字符串相似度和距离度量的库。目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟、Jaro-Winkler、最长公共子序列、余弦相似度等)。查看下面的汇总表以获取完整列表... python字符串相似度 下载 ...
总的来说,字符串相似度比较是信息技术中的基础工具,深入理解和灵活运用这些算法能帮助我们解决多种实际问题。通过“字符串相似度比较T-2021-7-1.rar”中的内容,我们可以系统学习这一领域的知识,提升处理文本数据...