- 浏览: 134818 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
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/1988169
当时没有给出变位词相似度算法,现在补上一个简单相似度算法:
一.是变位词与彻底不是变位词都有明确的定义
二.其余情况处理如下:
1. 取两个单词长度较大的作为基准单词,如:abc与acff 则取acff作为基准单词。
2. 计算要增删多少个单词才能使长度小的单词达到长度大的那样,以 abc、acff为例:abc要删除b增加ff,则需要操作3个字母
3. 相似度公式 1 - 操作的字母数/基准单词长度 ,上例则为:1 - 3/4 = 0.25
算法的核心思想很简单: 取向长单词靠拢所需的操作次数来计算相似度
算法的缺陷:
举例说明 abc 与 cbc 在本算法中相似度为 1/3;正常人看应该为 2/3。
以后再改进吧!
http://zhuyufufu.iteye.com/blog/1988169
当时没有给出变位词相似度算法,现在补上一个简单相似度算法:
一.是变位词与彻底不是变位词都有明确的定义
二.其余情况处理如下:
1. 取两个单词长度较大的作为基准单词,如:abc与acff 则取acff作为基准单词。
2. 计算要增删多少个单词才能使长度小的单词达到长度大的那样,以 abc、acff为例:abc要删除b增加ff,则需要操作3个字母
3. 相似度公式 1 - 操作的字母数/基准单词长度 ,上例则为:1 - 3/4 = 0.25
算法的核心思想很简单: 取向长单词靠拢所需的操作次数来计算相似度
算法的缺陷:
举例说明 abc 与 cbc 在本算法中相似度为 1/3;正常人看应该为 2/3。
以后再改进吧!
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. 取两个单词长度较大的作为基准单词,如:abc与acff 则取acff作为基准单词。 * 2. 计算要增删多少个单词才能使长度小的单词达到长度大的那样,以 abc、acff为例:abc要删除b增加ff,则需要操作3个字母 * 3. 相似度公式 1 - 操作的字母数/基准单词长度 ,上例则为:1 - 3/4 = 0.25 */ //是变位词,返回1 if(isAnagram(wordA, wordB)){ return 1f; } if(isNotAnagram(wordA, wordB)){ return 0f; } //基准单词 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(); } } } } }
发表评论
-
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 2204package 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合并的问题,现贴出来, ...
相关推荐
基于编辑距离结合词性的词相似度算法,梅筱,刘海鹏,现有的词语相似度算法大多依赖于外部知识(知网、同义词词林等),导致其只能解决外部知识以内的词语,或者单纯依赖词语本身的某
余弦相似度算法文本相似度算法的对比及python实现五种常见的相似度算法:余弦相似度(cosine_similarity)、jaccard相似度、编辑距离(Levenshtein)、MinHash、SimHash + 海明距离。
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
针对现有相似度算法存在查全率和查准率不高的问题,提出了一种基于本体的综合加权案例相似度算法。综合考虑案例的各个属性,分别采用不同的属性相似度计算方法,根据各个属性的重要程度加权,计算出案例的相似度。以...
Java 实现推荐系统 两个字符串 余弦相似度 算法。
主要介绍了Java基于余弦方法实现的计算相似度算法,简单说明了余弦相似性的概念、原理并结合实例形式分析了java实现余弦相似性算法的相关操作技巧,需要的朋友可以参考下
Matlab余弦相似度算法判断图片相似度并识别源代码 Matlab 余弦相似度 图像匹配 可直接运行 Matlab余弦相似度算法判断图片相似度并识别源代码 Matlab 余弦相似度 图像匹配 可直接运行
易语言文本相似度算法源码,文本相似度算法,文本_相似度,min
余弦相似度算法
(python)使用余弦相似度算法计算两个文本的相似度的简单实现
毕业设计,一个饭店管理系统,亮点是用余弦相似度算法写了个推荐菜的功能 毕业设计,一个饭店管理系统,亮点是用余弦相似度算法写了个推荐菜的功能 毕业设计,一个饭店管理系统,亮点是用余弦相似度算法写了个推荐菜...
易语言源码易语言文本相似度算法源码.rar 易语言源码易语言文本相似度算法源码.rar 易语言源码易语言文本相似度算法源码.rar 易语言源码易语言文本相似度算法源码.rar 易语言源码易语言文本相似度算法源码.rar ...
1.数据预处理 2.基于相似度算法的三类指标 3.以 AUC 为度量标准的指标对比 4.以 precision 为度量标准的指标对比
基于语义相似度的中文文本相似度算法研究.pdf基于语义相似度的中文文本相似度算法研究.pdf基于语义相似度的中文文本相似度算法研究.pdf
该算法是用于文本相似的判定,同时也可以判定两个用户的相似性。算法是以C#实现的,封装完毕,如有急要可以留言哦
仿谷歌的图像相似度的算法,代码很全,具有很强的学习性!
余弦相似度算法
算法 文本相似度算法,首先对文本分词,然后计算词频,生成词频向量,使用余弦相似度算法进行计算
余弦相似度算法
这个文件中包含了三种图像相似度的计算方法,分别是灰度分布计算方法、颜色分布直方图计算方法、还有结构相似度SSIM计算方法。