余弦相似度计算字符串相似率
功能需求: 最近在做通过爬虫技术去爬取各大相关网站的新闻, 储存到公司数据中. 这里面就有一个技术点, 就是如何保证你已爬取的新闻, 再有相似的新闻
或者一样的新闻, 那就不存储到数据库中.(因为有网站会去引用其它网站新闻, 或者把其它网站新闻拿过来稍微改下内容就发布到自己网站中).
解析方案: 最终就是采用余弦相似度算法, 来计算两个新闻正文的相似度. 现在自己写一篇博客总结下.
一, 理论知识
先推荐一篇博客, 对于余弦相似度算法的理论讲的比较清晰, 我们也是按照这个方式来计算相似度的. 网址: 相似度算法之余弦相似度 https://blog.csdn.net/zz_dd_yy/article/details/51926305 .
1, 说重点
我这边先把计算两个字符串的相似度理论知识再梳理一遍.
(1) 首先是要明白通过向量来计算相识度公式.
(2) 明白: 余弦值越接近 1, 也就是两个向量越相似, 这就叫 "余弦相似性",
余弦值越接近 0, 也就是两个向量越不相似, 也就是这两个字符串越不相似.
2, 案例理论知识
举一个例子来说明, 用上述理论计算文本的相似性. 为了简单起见, 先从句子着手.
句子 A: 这只皮靴号码大了. 那只号码合适.
句子 B: 这只皮靴号码不小, 那只更合适.
怎样计算上面两句话的相似程度?
基本思路是: 如果这两句话的用词越相似, 它们的内容就应该越相似. 因此, 可以从词频入手, 计算它们的相似程度.
第一步, 分词.
句子 A: 这只 / 皮靴 / 号码 / 大了. 那只 / 号码 / 合适.
句子 B: 这只 / 皮靴 / 号码 / 不 / 小, 那只 / 更 / 合适.
第二步, 计算词频.(也就是每个词语出现的频率)
句子 A: 这只 1, 皮靴 1, 号码 2, 大了 1. 那只 1, 合适 1, 不 0, 小 0, 更 0
句子 B: 这只 1, 皮靴 1, 号码 1, 大了 0. 那只 1, 合适 1, 不 1, 小 1, 更 1
第三步, 写出词频向量.
句子 A:(1,1,2,1,1,1,0,0,0)
句子 B:(1,1,1,0,1,1,1,1,1)
第四步: 运用上面的公式: 计算如下:
计算结果中夹角的余弦值为 0.81 非常接近于 1, 所以, 上面的句子 A 和句子 B 是基本相似的
二, 实际开发案例
我把我们实际开发过程中字符串相似率计算代码分享出来.
1,pom.xml
展示一些主要 jar 包
- <!-- 结合操作工具包 -->
- <dependency>
- <groupId>org.apache.commons</groupId>
- <artifactId>commons-lang3</artifactId>
- <version>3.5</version>
- </dependency>
- <!--bean 实体注解工具包 -->
- <dependency>
- <groupId>org.projectlombok</groupId>
- <artifactId>lombok</artifactId>
- </dependency>
- <!-- 汉语言包, 主要用于分词 -->
- <dependency>
- <groupId>com.hankcs</groupId>
- <artifactId>hanlp</artifactId>
- <version>portable-1.6.5</version>
- </dependency>
2,main 方法
- /**
- * 计算两个字符串的相识度
- */
- public class Similarity {
- public static final String content1="今天小小和爸爸一起去摘草莓, 小小说今天的草莓特别的酸, 而且特别的小, 关键价格还贵";
- public static final String content2="今天小小和妈妈一起去草原里采草莓, 今天的草莓味道特别好, 而且价格还挺实惠的";
- public static void main(String[] args) {
- double score=CosineSimilarity.getSimilarity(content1,content2);
- System.out.println("相似度:"+score);
- score=CosineSimilarity.getSimilarity(content1,content1);
- System.out.println("相似度:"+score);
- }
- }
先看运行结果:
通过运行结果得出:
(1) 第一次比较相似率为: 0.772853 (说明这两条句子还是挺相似的), 第二次比较相似率为: 1.0 (说明一模一样).
(2) 我们可以看到这个句子的分词效果, 后面是词性.
- 3,Tokenizer(分词工具类)
- import com.hankcs.hanlp.HanLP;
- import com.hankcs.hanlp.seg.common.Term;
- import java.util.List;
- import java.util.stream.Collectors;
- /**
- * 中文分词工具类 */
- public class Tokenizer {
- /**
- * 分词 */
- public static List<Word> segment(String sentence) {
- //1, 采用 HanLP 中文自然语言处理中标准分词进行分词
- List<Term> termList = HanLP.segment(sentence);
- // 上面控制台打印信息就是这里输出的
- System.out.println(termList.toString());
- //2, 重新封装到 Word 对象中 (term.word 代表分词后的词语, term.nature 代表改词的词性)
- return termList.stream().map(term -> new Word(term.word, term.nature.toString())).collect(Collectors.toList());
- }
- }
- 4,Word(封装分词结果)
这里面真正用到的其实就词名和权重.
- import lombok.Data;
- import java.util.Objects;
- /**
- * 封装分词结果 */
- @Data
- public class Word implements Comparable {
- // 词名
- private String name;
- // 词性
- private String pos;
- // 权重, 用于词向量分析
- private Float weight;
- public Word(String name, String pos) {
- this.name = name;
- this.pos = pos;
- }
- @Override
- public int hashCode() {
- return Objects.hashCode(this.name);
- }
- @Override
- public boolean equals(Object obj) {
- if (obj == null) {
- return false;
- }
- if (getClass() != obj.getClass()) {
- return false;
- }
- final Word other = (Word) obj;
- return Objects.equals(this.name, other.name);
- }
- @Override
- public String toString() {
- StringBuilder str = new StringBuilder();
- if (name != null) {
- str.append(name);
- }
- if (pos != null) {
- str.append("/").append(pos);
- }
- return str.toString();
- }
- @Override
- public int compareTo(Object o) {
- if (this == o) {
- return 0;
- }
- if (this.name == null) {
- return -1;
- }
- if (o == null) {
- return 1;
- }
- if (!(o instanceof Word)) {
- return 1;
- }
- String t = ((Word) o).getName();
- if (t == null) {
- return 1;
- }
- return this.name.compareTo(t);
- }
- }
- 5,CosineSimilarity(相似率具体实现工具类)
- import com.jincou.algorithm.tokenizer.Tokenizer;
- import com.jincou.algorithm.tokenizer.Word;
- import org.apache.commons.lang3.StringUtils;
- import org.slf4j.Logger;
- import org.slf4j.LoggerFactory;
- import org.springframework.util.CollectionUtils;
- import java.math.BigDecimal;
- import java.util.*;
- import java.util.concurrent.ConcurrentHashMap;
- import java.util.concurrent.atomic.AtomicInteger;
- /**
- * 判定方式: 余弦相似度, 通过计算两个向量的夹角余弦值来评估他们的相似度 余弦夹角原理: 向量 a=(x1,y1), 向量 b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2
- * |a|= 根号 [(x1)^2+(y1)^2],|b|= 根号 [(x2)^2+(y2)^2]*/
- public class CosineSimilarity {
- protected static final Logger LOGGER = LoggerFactory.getLogger(CosineSimilarity.class);
- /**
- * 1, 计算两个字符串的相似度
- */
- public static double getSimilarity(String text1, String text2) {
- // 如果 wei 空, 或者字符长度为 0, 则代表完全相同
- if (StringUtils.isBlank(text1) && StringUtils.isBlank(text2)) {
- return 1.0;
- }
- // 如果一个为 0 或者空, 一个不为, 那说明完全不相似
- if (StringUtils.isBlank(text1) || StringUtils.isBlank(text2)) {
- return 0.0;
- }
- // 这个代表如果两个字符串相等那当然返回 1 了 (这个我为了让它也分词计算一下, 所以注释掉了)
- // if (text1.equalsIgnoreCase(text2)) {
- // return 1.0;
- // }
- // 第一步: 进行分词
- List<Word> words1 = Tokenizer.segment(text1);
- List<Word> words2 = Tokenizer.segment(text2);
- return getSimilarity(words1, words2);
- }
- /**
- * 2, 对于计算出的相似度保留小数点后六位
- */
- public static double getSimilarity(List<Word> words1, List<Word> words2) {
- double score = getSimilarityImpl(words1, words2);
- //(int) (score * 1000000 + 0.5) 其实代表保留小数点后六位 , 因为 1034234.213 强制转换不就是 1034234. 对于强制转换添加 0.5 就等于四舍五入
- score = (int) (score * 1000000 + 0.5) / (double) 1000000;
- return score;
- }
- /**
- * 文本相似度计算 判定方式: 余弦相似度, 通过计算两个向量的夹角余弦值来评估他们的相似度 余弦夹角原理: 向量 a=(x1,y1), 向量 b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2
- * |a|= 根号 [(x1)^2+(y1)^2],|b|= 根号 [(x2)^2+(y2)^2]
- */
- public static double getSimilarityImpl(List<Word> words1, List<Word> words2) {
- // 向每一个 Word 对象的属性都注入 weight(权重) 属性值
- taggingWeightByFrequency(words1, words2);
- // 第二步: 计算词频
- // 通过上一步让每个 Word 对象都有权重值, 那么在封装到 map 中 (key 是词, value 是该词出现的次数 (即权重))
- Map<String, Float> weightMap1 = getFastSearchMap(words1);
- Map<String, Float> weightMap2 = getFastSearchMap(words2);
- // 将所有词都装入 set 容器中
- Set<Word> words = new HashSet<>();
- words.addAll(words1);
- words.addAll(words2);
- AtomicFloat ab = new AtomicFloat();// a.b
- AtomicFloat aa = new AtomicFloat();// |a | 的平方
- AtomicFloat bb = new AtomicFloat();// |b | 的平方
- // 第三步: 写出词频向量, 后进行计算
- words.parallelStream().forEach(word -> {
- // 看同一词在 a,b 两个集合出现的此次
- Float x1 = weightMap1.get(word.getName());
- Float x2 = weightMap2.get(word.getName());
- if (x1 != null && x2 != null) {
- //x1x2
- float oneOfTheDimension = x1 * x2;
- //+
- ab.addAndGet(oneOfTheDimension);
- }
- if (x1 != null) {
- //(x1)^2
- float oneOfTheDimension = x1 * x1;
- //+
- aa.addAndGet(oneOfTheDimension);
- }
- if (x2 != null) {
- //(x2)^2
- float oneOfTheDimension = x2 * x2;
- //+
- bb.addAndGet(oneOfTheDimension);
- }
- });
- //|a| 对 aa 开方
- double aaa = Math.sqrt(aa.doubleValue());
- //|b| 对 bb 开方
- double bbb = Math.sqrt(bb.doubleValue());
- // 使用 BigDecimal 保证精确计算浮点数
- //double aabb = aaa * bbb;
- BigDecimal aabb = BigDecimal.valueOf(aaa).multiply(BigDecimal.valueOf(bbb));
- //similarity=a.b/|a|*|b|
- //divide 参数说明: aabb 被除数, 9 表示小数点后保留 9 位, 最后一个表示用标准的四舍五入法
- double cos = BigDecimal.valueOf(ab.get()).divide(aabb, 9, BigDecimal.ROUND_HALF_UP).doubleValue();
- return cos;
- }
- /**
- * 向每一个 Word 对象的属性都注入 weight(权重) 属性值
- */
- protected static void taggingWeightByFrequency(List<Word> words1, List<Word> words2) {
- if (words1.get(0).getWeight() != null && words2.get(0).getWeight() != null) {
- return;
- }
- // 词频统计 (key 是词, value 是该词在这段句子中出现的次数)
- Map<String, AtomicInteger> frequency1 = getFrequency(words1);
- Map<String, AtomicInteger> frequency2 = getFrequency(words2);
- // 如果是 DEBUG 模式输出词频统计信息
- // if (LOGGER.isDebugEnabled()) {
- // LOGGER.debug("词频统计 1:\n{}", getWordsFrequencyString(frequency1));
- // LOGGER.debug("词频统计 2:\n{}", getWordsFrequencyString(frequency2));
- // }
- // 标注权重 (该词出现的次数)
- words1.parallelStream().forEach(word -> word.setWeight(frequency1.get(word.getName()).floatValue()));
- words2.parallelStream().forEach(word -> word.setWeight(frequency2.get(word.getName()).floatValue()));
- }
- /**
- * 统计词频
- * @return 词频统计图
- */
- private static Map<String, AtomicInteger> getFrequency(List<Word> words) {
- Map<String, AtomicInteger> freq = new HashMap<>();
- // 这步很帅哦
- words.forEach(i -> freq.computeIfAbsent(i.getName(), k -> new AtomicInteger()).incrementAndGet());
- return freq;
- }
- /**
- * 输出: 词频统计信息
- */
- private static String getWordsFrequencyString(Map<String, AtomicInteger> frequency) {
- StringBuilder str = new StringBuilder();
- if (frequency != null && !frequency.isEmpty()) {
- AtomicInteger integer = new AtomicInteger();
- frequency.entrySet().stream().sorted((a, b) -> b.getValue().get() - a.getValue().get()).forEach(
- i -> str.append("\t").append(integer.incrementAndGet()).append(",").append(i.getKey()).append("=")
- .append(i.getValue()).append("\n"));
- }
- str.setLength(str.length() - 1);
- return str.toString();
- }
- /**
- * 构造权重快速搜索容器
- */
- protected static Map<String, Float> getFastSearchMap(List<Word> words) {
- if (CollectionUtils.isEmpty(words)) {
- return Collections.emptyMap();
- }
- Map<String, Float> weightMap = new ConcurrentHashMap<>(words.size());
- words.parallelStream().forEach(i -> {
- if (i.getWeight() != null) {
- weightMap.put(i.getName(), i.getWeight());
- } else {
- LOGGER.error("no word weight info:" + i.getName());
- }
- });
- return weightMap;
- }
- }
这个具体实现代码因为思维很紧密所以有些地方写的比较绕, 同时为了性能提升还手写了 AtomicFloat 原子类.
6,AtomicFloat 原子类
- import java.util.concurrent.atomic.AtomicInteger;
- /**
- * jdk 没有 AtomicFloat, 写一个
- */
- public class AtomicFloat extends Number {
- private AtomicInteger bits;
- public AtomicFloat() {
- this(0f);
- }
- public AtomicFloat(float initialValue) {
- bits = new AtomicInteger(Float.floatToIntBits(initialValue));
- }
- // 叠加
- public final float addAndGet(float delta) {
- float expect;
- float update;
- do {
- expect = get();
- update = expect + delta;
- } while (!this.compareAndSet(expect, update));
- return update;
- }
- public final float getAndAdd(float delta) {
- float expect;
- float update;
- do {
- expect = get();
- update = expect + delta;
- } while (!this.compareAndSet(expect, update));
- return expect;
- }
- public final float getAndDecrement() {
- return getAndAdd(-1);
- }
- public final float decrementAndGet() {
- return addAndGet(-1);
- }
- public final float getAndIncrement() {
- return getAndAdd(1);
- }
- public final float incrementAndGet() {
- return addAndGet(1);
- }
- public final float getAndSet(float newValue) {
- float expect;
- do {
- expect = get();
- } while (!this.compareAndSet(expect, newValue));
- return expect;
- }
- public final boolean compareAndSet(float expect, float update) {
- return bits.compareAndSet(Float.floatToIntBits(expect), Float.floatToIntBits(update));
- }
- public final void set(float newValue) {
- bits.set(Float.floatToIntBits(newValue));
- }
- public final float get() {
- return Float.intBitsToFloat(bits.get());
- }
- @Override
- public float floatValue() {
- return get();
- }
- @Override
- public double doubleValue() {
- return (double) floatValue();
- }
- @Override
- public int intValue() {
- return (int) get();
- }
- @Override
- public long longValue() {
- return (long) get();
- }
- @Override
- public String toString() {
- return Float.toString(get());
- }
- }
7, 总结
把大致思路再捋一下:
(1) 先分词: 分词当然要按一定规则, 不然随便分那也没有意义, 那这里通过采用 HanLP 中文自然语言处理中标准分词进行分词.
(2) 统计词频: 就统计上面词出现的次数.
(3) 通过每一个词出现的次数, 变成一个向量, 通过向量公式计算相似率.
我只是偶尔安静下来, 对过去的种种思忖一番. 那些曾经的旧时光里即便有过天真愚钝, 也不值得谴责. 毕竟, 往后的日子, 还很长. 不断鼓励自己,
天一亮, 又是崭新的起点, 又是未知的征程 (上校 3)
来源: https://www.cnblogs.com/qdhxhz/p/9484274.html