java算法之余弦相似度計算字符串相似率

目錄

概述

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

或者一樣的新聞，那就不存儲到數據庫中。（因為有網(wǎng)站會(huì )去引用其它網(wǎng)站新聞，或者把其它網(wǎng)站新聞拿過(guò)來(lái)稍微改下內容就發(fā)布到自己網(wǎng)站中）。

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

一、理論知識

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

1、說(shuō)重點(diǎn)

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

（1）首先是要明白通過(guò)向量來(lái)計算相識度公式。

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

2、案例理論知識

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

句子A：這只皮靴號碼大了。那只號碼合適。

句子B：這只皮靴號碼不小，那只更合適。

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

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

第一步，分詞。

句子A：這只/皮靴/號碼/大了。那只/號碼/合適。

句子B：這只/皮靴/號碼/不/小，那只/更/合適。

第二步，計算詞頻。（也就是每個(gè)詞語(yǔ)出現的頻率）

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

句子B：這只1，皮靴1，號碼1，大了0。那只1，合適1，不1，小1，更1

第三步，寫(xiě)出詞頻向量。

句子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是基本相似的

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

我把我們實(shí)際開(kāi)發(fā)過(guò)程中字符串相似率計算代碼分享出來(lái)。

1、pom.xml

展示一些主要jar包

<!--結合操作工具包-->
<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>
<!--漢語(yǔ)言包，主要用于分詞-->
<dependency>
    <groupId>com.hankcs</groupId>
    <artifactId>hanlp</artifactId>
    <version>portable-1.6.5</version>
</dependency>

2、main方法

/**
 * 計算兩個(gè)字符串的相識度
 */
public class Similarity {

    public static final  String content1="今天小小和爸爸一起去摘草莓，小小說(shuō)今天的草莓特別的酸，而且特別的小，關(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);
    }
    
}

先看運行結果：

通過(guò)運行結果得出：

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

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

3、Tokenizer（分詞工具類(lèi)）

import com.hankcs.hanlp.HanLP;
import com.hankcs.hanlp.seg.common.Term;
import java.util.List;
import java.util.stream.Collectors;


/**
 * 中文分詞工具類(lèi)*/
public class Tokenizer {

    /**
     * 分詞*/
    public static List<Word> segment(String sentence) {

        //1、 采用HanLP中文自然語(yǔ)言處理中標準分詞進(jìn)行分詞
        List<Term> termList = HanLP.segment(sentence);

        //上面控制臺打印信息就是這里輸出的
        System.out.println(termList.toString());

        //2、重新封裝到Word對象中（term.word代表分詞后的詞語(yǔ)，term.nature代表改詞的詞性）
        return termList.stream().map(term -> new Word(term.word, term.nature.toString())).collect(Collectors.toList());
    }
}

4、Word（封裝分詞結果）

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

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（相似率具體實(shí)現工具類(lèi)）

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;

/**
 * 判定方式：余弦相似度，通過(guò)計算兩個(gè)向量的夾角余弦值來(lái)評估他們的相似度 余弦?jiàn)A角原理： 向量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、計算兩個(gè)字符串的相似度
     */
    public static double getSimilarity(String text1, String text2) {

        //如果wei空，或者字符長(cháng)度為0，則代表完全相同
        if (StringUtils.isBlank(text1) && StringUtils.isBlank(text2)) {
            return 1.0;
        }
        //如果一個(gè)為0或者空，一個(gè)不為，那說(shuō)明完全不相似
        if (StringUtils.isBlank(text1) || StringUtils.isBlank(text2)) {
            return 0.0;
        }
        //這個(gè)代表如果兩個(gè)字符串相等那當然返回1了（這個(gè)我為了讓它也分詞計算一下，所以注釋掉了）
//        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、對于計算出的相似度保留小數點(diǎn)后六位
     */
    public static double getSimilarity(List<Word> words1, List<Word> words2) {

        double score = getSimilarityImpl(words1, words2);

        //(int) (score * 1000000 + 0.5)其實(shí)代表保留小數點(diǎn)后六位 ,因為1034234.213強制轉換不就是1034234。對于強制轉換添加0.5就等于四舍五入
        score = (int) (score * 1000000 + 0.5) / (double) 1000000;

        return score;
    }

    /**
     * 文本相似度計算 判定方式：余弦相似度，通過(guò)計算兩個(gè)向量的夾角余弦值來(lái)評估他們的相似度 余弦?jiàn)A角原理： 向量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) {

        // 向每一個(gè)Word對象的屬性都注入weight（權重）屬性值
        taggingWeightByFrequency(words1, words2);

        //第二步：計算詞頻
        //通過(guò)上一步讓每個(gè)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|的平方

        // 第三步：寫(xiě)出詞頻向量，后進(jìn)行計算
        words.parallelStream().forEach(word -> {
            //看同一詞在a、b兩個(gè)集合出現的此次
            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開(kāi)方
        double aaa = Math.sqrt(aa.doubleValue());
        //|b| 對bb開(kāi)方
        double bbb = Math.sqrt(bb.doubleValue());

        //使用BigDecimal保證精確計算浮點(diǎn)數
        //double aabb = aaa * bbb;
        BigDecimal aabb = BigDecimal.valueOf(aaa).multiply(BigDecimal.valueOf(bbb));

        //similarity=a.b/|a|*|b|
        //divide參數說(shuō)明：aabb被除數,9表示小數點(diǎn)后保留9位，最后一個(gè)表示用標準的四舍五入法
        double cos = BigDecimal.valueOf(ab.get()).divide(aabb, 9, BigDecimal.ROUND_HALF_UP).doubleValue();
        return cos;
    }


    /**
     * 向每一個(gè)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;
    }

}

這個(gè)具體實(shí)現代碼因為思維很緊密所以有些地方寫(xiě)的比較繞，同時(shí)還手寫(xiě)了AtomicFloat原子類(lèi)。

6、AtomicFloat原子類(lèi)

import java.util.concurrent.atomic.AtomicInteger;

/**
 * jdk沒(méi)有AtomicFloat，寫(xiě)一個(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());
    }
}

三、總結

把大致思路再捋一下：

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

（2）統計詞頻：就統計上面詞出現的次數。

（3）通過(guò)每一個(gè)詞出現的次數，變成一個(gè)向量，通過(guò)向量公式計算相似率。

以上就是java算法之余弦相似度計算字符串相似率的詳細內容，更多關(guān)于java算法的資料請關(guān)注腳本之家其它相關(guān)文章！