时间戳

首页 > 解决方案 > 哪种字符串距离算法可以检测微小的变化？

java - 哪种字符串距离算法可以检测微小的变化？

问题描述

我正在开发一个网络钓鱼电子邮件过滤器项目，作为猜测电子邮件是否为网络钓鱼的第一步，我想在不使用外部 API 的情况下比较可见文本和链接的基础 URL。

例如：

<a href="http://faceb00k.com">Facebook</a>

<a href="http://facedook.com">Facebook</a>

是网络钓鱼的高指标。

最初，我只知道 Levenshtein 距离，我认为这是一个很好的衡量标准，但后来我意识到标准化后它并不是这类任务的一个很好的指标，因为它几乎不高于 0.5。

通过规范化，我的意思是：

normalized = levenshtein / MAX(a.length, b.length)

其他似乎效果更好的算法是cosine distance和Jaro-Winkler Distance。

在上述情况下，将它们都小写和修剪，并删除协议和顶级域后，如下代码所示：

public interface RegEx {
    String PROTOCOL = "^http(s)?://";
    String WWW_PREFIX = "www\\.";
    String TOP_LEVEL_DOMAIN = "\\.[A-z0-9\\-]*$";
}

.

import org.apache.commons.text.similarity.CosineDistance;
import org.apache.commons.text.similarity.JaccardDistance;
import org.apache.commons.text.similarity.JaroWinklerDistance;
import org.apache.commons.text.similarity.LevenshteinDistance;

import java.util.regex.Pattern;

public class Test implements RegEx {
    public static void main(String[] args) {
        String text = "Facebook";
        String url = "https://www.facedook.com";

        System.out.println("Text: " + text);
        System.out.println("URL: " + url + "\n");

        // RegEx
        Pattern protocolPattern = Pattern.compile(PROTOCOL);
        Pattern prefixPattern = Pattern.compile(WWW_PREFIX);
        Pattern topLevelDomainPattern = Pattern.compile(TOP_LEVEL_DOMAIN);

        // Remove protocol
        text = protocolPattern.matcher(text).replaceAll("");
        url = protocolPattern.matcher(url).replaceAll("");

        // Remove www prefix
        text = prefixPattern.matcher(text).replaceAll("");
        url = prefixPattern.matcher(url).replaceAll("");

        // Remove Top Level Domain
        text = topLevelDomainPattern.matcher(text).replaceAll("");
        url = topLevelDomainPattern.matcher(url).replaceAll("");


        text = text.toLowerCase().trim();
        url = url.toLowerCase().trim();

        System.out.println("Text: " + text);
        System.out.println("URL: " + url + "\n");

        double levenshteinDistance = new LevenshteinDistance().apply(text, url);
        double normalizedLevenshteinDistance = levenshteinDistance / (double) Math.max(text.length(), url.length());
        System.out.println("Normalized Levenshtein Distance: " + normalizedLevenshteinDistance);

        double cosineDistance = new CosineDistance().apply(text, url);
        System.out.println("Cosine Distance: " + cosineDistance);

        double jaccardDistance = new JaccardDistance().apply(text, url);
        System.out.println("Jaccard Distance: " + jaccardDistance);

        double jaroVinklerDistance = new JaroWinklerDistance().apply(text, url);
        System.out.println("JaroWinkler Disance: " + jaroVinklerDistance);
    }
}

这些是我在控制台中得到的距离：

Text: Facebook
URL: https://www.facedook.com

Text: facebook
URL: facedook

Normalized Levenshtein Distance: 0.125
Cosine Distance: 1.0
Jaccard Distance: 0.25
JaroWinkler Disance: 0.95

因此我们可以清楚地看到，余弦距离和Jaro-Winkler距离似乎对网络钓鱼链接检测具有正确的洞察力。

它们是否适合此目的，或者是否有其他距离函数更适合此任务？更好地解释我在寻找什么，如果一个字符被另一个看起来类似于人眼的字符替换，字符串之间是否有一些距离函数会给出更高的值/距离？

标签： javasimilaritycosine-similarityjaro-winkler

解决方案

推荐阅读