概述

功能需求：最近在做通過爬蟲技術(shù)去爬取各大相關(guān)網(wǎng)站的新聞，儲(chǔ)存到公司數(shù)據(jù)中。這里面就有一個(gè)技術(shù)點(diǎn)，就是如何保證你已爬取的新聞，再有相似的新聞

或者一樣的新聞，那就不存儲(chǔ)到數(shù)據(jù)庫(kù)中。（因?yàn)橛芯W(wǎng)站會(huì)去引用其它網(wǎng)站新聞，或者把其它網(wǎng)站新聞拿過來稍微改下內(nèi)容就發(fā)布到自己網(wǎng)站中）。

解析方案：最終就是采用余弦相似度算法，來計(jì)算兩個(gè)新聞?wù)牡南嗨贫取，F(xiàn)在自己寫一篇博客總結(jié)下。

一、理論知識(shí)

先推薦一篇博客，對(duì)于余弦相似度算法的理論講的比較清晰，我們也是按照這個(gè)方式來計(jì)算相似度的。網(wǎng)址：相似度算法之余弦相似度。

1、說重點(diǎn)

我這邊先把計(jì)算兩個(gè)字符串的相似度理論知識(shí)再梳理一遍。

（1）首先是要明白通過向量來計(jì)算相識(shí)度公式。

（2）明白：余弦值越接近1，也就是兩個(gè)向量越相似，這就叫'余弦相似性'，余弦值越接近0，也就是兩個(gè)向量越不相似，也就是這兩個(gè)字符串越不相似。

2、案例理論知識(shí)

舉一個(gè)例子來說明，用上述理論計(jì)算文本的相似性。為了簡(jiǎn)單起見，先從句子著手。

句子A：這只皮靴號(hào)碼大了。那只號(hào)碼合適。

句子B：這只皮靴號(hào)碼不小，那只更合適。

怎樣計(jì)算上面兩句話的相似程度？

基本思路是：如果這兩句話的用詞越相似，它們的內(nèi)容就應(yīng)該越相似。因此，可以從詞頻入手，計(jì)算它們的相似程度。

第一步，分詞。

句子A：這只/皮靴/號(hào)碼/大了。那只/號(hào)碼/合適。

句子B：這只/皮靴/號(hào)碼/不/小，那只/更/合適。

第二步，計(jì)算詞頻。（也就是每個(gè)詞語出現(xiàn)的頻率）

句子A：這只1，皮靴1，號(hào)碼2，大了1。那只1，合適1，不0，小0，更0

句子B：這只1，皮靴1，號(hào)碼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)

第四步：運(yùn)用上面的公式：計(jì)算如下：

計(jì)算結(jié)果中夾角的余弦值為0.81非常接近于1，所以，上面的句子A和句子B是基本相似的

二、實(shí)際開發(fā)案例

我把我們實(shí)際開發(fā)過程中字符串相似率計(jì)算代碼分享出來。

1、pom.xml

展示一些主要jar包

<!--結(jié)合操作工具包--><dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-lang3</artifactId> <version>3.5</version></dependency><!--bean實(shí)體注解工具包--> <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方法

/** * 計(jì)算兩個(gè)字符串的相識(shí)度 */public class Similarity { public static final String content1='今天小小和爸爸一起去摘草莓，小小說今天的草莓特別的酸，而且特別的小，關(guān)鍵價(jià)格還貴'; public static final String content2='今天小小和媽媽一起去草原里采草莓，今天的草莓味道特別好，而且價(jià)格還挺實(shí)惠的'; 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); } }

先看運(yùn)行結(jié)果：

通過運(yùn)行結(jié)果得出：

（1）第一次比較相似率為：0.772853 （說明這兩條句子還是挺相似的），第二次比較相似率為：1.0 （說明一模一樣）。

（2）我們可以看到這個(gè)句子的分詞效果，后面是詞性。

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中文自然語言處理中標(biāo)準(zhǔn)分詞進(jìn)行分詞List<Term> termList = HanLP.segment(sentence);//上面控制臺(tái)打印信息就是這里輸出的System.out.println(termList.toString());//2、重新封裝到Word對(duì)象中（term.word代表分詞后的詞語，term.nature代表改詞的詞性）return termList.stream().map(term -> new Word(term.word, term.nature.toString())).collect(Collectors.toList()); }}4、Word（封裝分詞結(jié)果）

這里面真正用到的其實(shí)就詞名和權(quán)重。

import lombok.Data;import java.util.Objects;/** * 封裝分詞結(jié)果*/@Datapublic class Word implements Comparable { // 詞名 private String name; // 詞性 private String pos; // 權(quán)重，用于詞向量分析 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（相似率具體實(shí)現(xiàn)工具類）

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;/** * 判定方式：余弦相似度，通過計(jì)算兩個(gè)向量的夾角余弦值來評(píng)估他們的相似度 余弦夾角原理： 向量a=(x1,y1),向量b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2 * |a|=根號(hào)[(x1)^2+(y1)^2],|b|=根號(hào)[(x2)^2+(y2)^2]*/public class CosineSimilarity { protected static final Logger LOGGER = LoggerFactory.getLogger(CosineSimilarity.class); /** * 1、計(jì)算兩個(gè)字符串的相似度 */ public static double getSimilarity(String text1, String text2) {//如果wei空，或者字符長(zhǎng)度為0，則代表完全相同if (StringUtils.isBlank(text1) && StringUtils.isBlank(text2)) { return 1.0;}//如果一個(gè)為0或者空，一個(gè)不為，那說明完全不相似if (StringUtils.isBlank(text1) || StringUtils.isBlank(text2)) { return 0.0;}//這個(gè)代表如果兩個(gè)字符串相等那當(dāng)然返回1了（這個(gè)我為了讓它也分詞計(jì)算一下，所以注釋掉了）//if (text1.equalsIgnoreCase(text2)) {// return 1.0;//}//第一步：進(jìn)行分詞List<Word> words1 = Tokenizer.segment(text1);List<Word> words2 = Tokenizer.segment(text2);return getSimilarity(words1, words2); } /** * 2、對(duì)于計(jì)算出的相似度保留小數(shù)點(diǎn)后六位 */ public static double getSimilarity(List<Word> words1, List<Word> words2) {double score = getSimilarityImpl(words1, words2);//(int) (score * 1000000 + 0.5)其實(shí)代表保留小數(shù)點(diǎn)后六位 ,因?yàn)?034234.213強(qiáng)制轉(zhuǎn)換不就是1034234。對(duì)于強(qiáng)制轉(zhuǎn)換添加0.5就等于四舍五入score = (int) (score * 1000000 + 0.5) / (double) 1000000;return score; } /** * 文本相似度計(jì)算 判定方式：余弦相似度，通過計(jì)算兩個(gè)向量的夾角余弦值來評(píng)估他們的相似度 余弦夾角原理： 向量a=(x1,y1),向量b=(x2,y2) similarity=a.b/|a|*|b| a.b=x1x2+y1y2 * |a|=根號(hào)[(x1)^2+(y1)^2],|b|=根號(hào)[(x2)^2+(y2)^2] */ public static double getSimilarityImpl(List<Word> words1, List<Word> words2) {// 向每一個(gè)Word對(duì)象的屬性都注入weight（權(quán)重）屬性值taggingWeightByFrequency(words1, words2);//第二步：計(jì)算詞頻//通過上一步讓每個(gè)Word對(duì)象都有權(quán)重值，那么在封裝到map中（key是詞，value是該詞出現(xiàn)的次數(shù)（即權(quán)重））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.bAtomicFloat aa = new AtomicFloat();// |a|的平方AtomicFloat bb = new AtomicFloat();// |b|的平方// 第三步：寫出詞頻向量，后進(jìn)行計(jì)算words.parallelStream().forEach(word -> { //看同一詞在a、b兩個(gè)集合出現(xiàn)的此次 Float x1 = weightMap1.get(word.getName()); Float x2 = weightMap2.get(word.getName()); if (x1 != null && x2 != null) {//x1x2float oneOfTheDimension = x1 * x2;//+ab.addAndGet(oneOfTheDimension); } if (x1 != null) {//(x1)^2float oneOfTheDimension = x1 * x1;//+aa.addAndGet(oneOfTheDimension); } if (x2 != null) {//(x2)^2float oneOfTheDimension = x2 * x2;//+bb.addAndGet(oneOfTheDimension); }});//|a| 對(duì)aa開方double aaa = Math.sqrt(aa.doubleValue());//|b| 對(duì)bb開方double bbb = Math.sqrt(bb.doubleValue());//使用BigDecimal保證精確計(jì)算浮點(diǎn)數(shù)//double aabb = aaa * bbb;BigDecimal aabb = BigDecimal.valueOf(aaa).multiply(BigDecimal.valueOf(bbb));//similarity=a.b/|a|*|b|//divide參數(shù)說明：aabb被除數(shù),9表示小數(shù)點(diǎn)后保留9位，最后一個(gè)表示用標(biāo)準(zhǔn)的四舍五入法double cos = BigDecimal.valueOf(ab.get()).divide(aabb, 9, BigDecimal.ROUND_HALF_UP).doubleValue();return cos; } /** * 向每一個(gè)Word對(duì)象的屬性都注入weight（權(quán)重）屬性值 */ protected static void taggingWeightByFrequency(List<Word> words1, List<Word> words2) {if (words1.get(0).getWeight() != null && words2.get(0).getWeight() != null) { return;}//詞頻統(tǒng)計(jì)（key是詞，value是該詞在這段句子中出現(xiàn)的次數(shù)）Map<String, AtomicInteger> frequency1 = getFrequency(words1);Map<String, AtomicInteger> frequency2 = getFrequency(words2);//如果是DEBUG模式輸出詞頻統(tǒng)計(jì)信息//if (LOGGER.isDebugEnabled()) {// LOGGER.debug('詞頻統(tǒng)計(jì)1：n{}', getWordsFrequencyString(frequency1));// LOGGER.debug('詞頻統(tǒng)計(jì)2：n{}', getWordsFrequencyString(frequency2));//}// 標(biāo)注權(quán)重（該詞出現(xiàn)的次數(shù)）words1.parallelStream().forEach(word -> word.setWeight(frequency1.get(word.getName()).floatValue()));words2.parallelStream().forEach(word -> word.setWeight(frequency2.get(word.getName()).floatValue())); } /** * 統(tǒng)計(jì)詞頻 * @return 詞頻統(tǒng)計(jì)圖 */ 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; } /** * 輸出：詞頻統(tǒng)計(jì)信息 */ 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(); } /** * 構(gòu)造權(quán)重快速搜索容器 */ 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; }}

這個(gè)具體實(shí)現(xiàn)代碼因?yàn)樗季S很緊密所以有些地方寫的比較繞，同時(shí)還手寫了AtomicFloat原子類。

6、AtomicFloat原子類

import java.util.concurrent.atomic.AtomicInteger;/** * jdk沒有AtomicFloat，寫一個(gè) */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()); }}三、總結(jié)

把大致思路再捋一下：

（1）先分詞：分詞當(dāng)然要按一定規(guī)則，不然隨便分那也沒有意義，那這里通過采用HanLP中文自然語言處理中標(biāo)準(zhǔn)分詞進(jìn)行分詞。

（2）統(tǒng)計(jì)詞頻：就統(tǒng)計(jì)上面詞出現(xiàn)的次數(shù)。

（3）通過每一個(gè)詞出現(xiàn)的次數(shù)，變成一個(gè)向量，通過向量公式計(jì)算相似率。

以上就是java算法之余弦相似度計(jì)算字符串相似率的詳細(xì)內(nèi)容，更多關(guān)于java算法的資料請(qǐng)關(guān)注好吧啦網(wǎng)其它相關(guān)文章！