目录

前言

一、字符串距离的几种计算方法

1、Levenshtein 距离

2、Overlap Coefficient计算

3、Q-gram Matching

4、余弦相似性计算

二、基于余弦相似性的基地名称对比

1、加载百科中的基地信息列表

2、设置忽略词列表 

3、将数据库地名和Excel进行对比

三、总结

前言

        在之前的一篇漂亮国的全球的基地博客中，我们曾经对漂亮国的全球基地进行了一些梳理。博文中使用的数据来源，重点是参考以为博主分享的KML的数据，同时针对其国内的基地部署信息，我们从互联网百科的数据中搜寻到一些。其实拿到这两份数据的时候，是存在一些问题的，比如，KML的数据它的基地名称都是英文的，而在互联网上公开的数据中，良莠不齐，有的是中文的，有的是英文，有的中英文都有，而且可能还存在同样的英文，它的描述不一样的情况，比如下面的场景：

XXX Air Base 空军基地 

XXX Air Station 航空站

        可能不同的信息来源，其主要的名称对应的真实位置表示的是同一个。再比如漂亮国驻小日子的基地列表。

Idesuna Jima Air Range 

FAC 6078 出砂岛炸射练习场 Idesuna Jima Range 训练 冲绳渡名喜村

        上面一行是从KML中解析出来的基地名称，而下面是从某百科中得到的数据。 当我们将句子的影响词(当出现在军事基地的领域中的某些特定词，如Air、Base、Station、Range等这些词去掉后）其主要的地点就是同一个，通过对比主要关键词的相似性，为我们实现将两个地名进行对齐，甚至可以设定一个阈值，当两个字符串的相似性超过多少（比如超过90%）就认为这是同一个地点，从而可以实现将基地的中文名和所驻地的国家、城市等信息进行一一匹配。从而减少人工对比的工作。

        随着现代技术的快速发展，文本相似度计算有很多种方法，甚至可以用大数据、自然语言处理还可以结合人工智能的方法来实现精确的文本相似性判断。但是本文不想实现那么复杂的架构，只想简单快速的解决两个地址的快速匹配问题。博客以Java编程为例，讲解了在Java中求解两个字符串的几种方法。通过求解编辑距离、Q-gram Matching、还有余弦相似性计算，通过对比不同的方法，调用Apache 的Common-text中基于余弦的字符相似性得到了比较比错的结果。算法比较简单，主要想说明两个字符串的不同距离的计算，对于更复杂的模型，大家感兴趣的可以搜索相关的科研论文来学习。

一、字符串距离的几种计算方法

        为了比较字符的相似性，我们通过通过对比距离（把两个字符串的距离计算出来，当然这个距离的计算是有讲究的，具体的算法就是我们说的距离算法，不同的距离算法，得到的值是不一样的）。因此这里我们打算讲将在Java当中，有哪些距离的计算方法以及如何编写相应的代码。

1、Levenshtein 距离

        计算将一个字符串转换为另一个字符串所需的最少单字符编辑操作（插入、删除或替换）的数量。在下面这个示例中，levenshteinDistance方法使用动态规划来计算两个字符串之间的Levenshtein Distance。calculateNormalizedLevenshteinDistance方法则使用这个距离和两个字符串长度的最大值来计算标准化的Levenshtein Distance。 main方法中给出了两个示例字符串s1和s2，并调用calculateNormalizedLevenshteinDistance方法来计算并打印它们的Normalized Levenshtein Distance。根据这个得分，你可以设定一个阈值来判断两个字符串是否相似。例如，如果Normalized Levenshtein Distance小于0.2（即80%的字符是匹配的），你可以认为这两个字符串是相似的。这个阈值可以根据你的具体需求进行调整。

<code>package com.yelang.project;

public class NormalizedLevenshteinDistance {

// 计算Levenshtein Distance

public static int levenshteinDistance(String s1, String s2) {

int[][] dp = new int[s1.length() + 1][s2.length() + 1];

for (int i = 0; i <= s1.length(); i++) {

dp[i][0] = i;

}

for (int j = 0; j <= s2.length(); j++) {

dp[0][j] = j;

}

for (int i = 1; i <= s1.length(); i++) {

for (int j = 1; j <= s2.length(); j++) {

int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;

dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + cost);

}

}

return dp[s1.length()][s2.length()];

}

// 计算Normalized Levenshtein Distance

public static double calculateNormalizedLevenshteinDistance(String s1, String s2) {

int distance = levenshteinDistance(s1, s2);

int maxLength = Math.max(s1.length(), s2.length());

return (double) distance / maxLength;

}

public static void main(String[] args) {

String s1 = "Camp Humphreys";

String s2 = "United States Army Garrison-Humphreys";

double normalizedDistance = calculateNormalizedLevenshteinDistance(s1, s2);

System.out.println("Normalized Levenshtein Distance: " + normalizedDistance);

}

}

        运行上述程序后，得到的结果如下，表示两个字符串的相似度是0.67：

Normalized Levenshtein Distance: 0.6756756756756757

2、Overlap Coefficient计算

        Overlap Coefficient是通过计算两个字符串的最长公共子序列的长度来求两者的相似度的。这种算法有弊有利，在主要的关键词不同而基地的信息完一致的情况下，比如xxx air base 和xx1 air base,通过计算得到的结果一定及其相似，因为这两个字符串的最长公共序列很长啊，计算机看起来就像是完全一致的。

package com.yelang.project;

public class OverlapCoefficient {

// 计算最长公共子序列的长度

public static int longestCommonSubsequence(String s1, String s2) {

int len1 = s1.length();

int len2 = s2.length();

int[][] dp = new int[len1 + 1][len2 + 1];

for (int i = 1; i <= len1; i++) {

for (int j = 1; j <= len2; j++) {

if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

dp[i][j] = dp[i - 1][j - 1] + 1;

} else {

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

}

}

}

return dp[len1][len2];

}

// 计算Overlap Coefficient

public static double calculateOverlapCoefficient(String s1, String s2) {

int lcsLength = longestCommonSubsequence(s1, s2);

int minLength = Math.min(s1.length(), s2.length());

return (double) lcsLength / minLength;

}

public static void main(String[] args) {

String s1 = "Camp Humphreys";

String s2 = "United States Army Garrison-Humphreys";

double overlapCoefficient = calculateOverlapCoefficient(s1, s2);

System.out.println("Overlap Coefficient: " + overlapCoefficient);

}

}

        运行以上程序后，得到的结果是：

Overlap Coefficient: 0.8571428571428571

        它判定是85%的相似度，貌似看起来比第一种距离很接近真相，你换个词去测试就发现，这种算法其实很蠢。

3、Q-gram Matching

        Q-gram Matching是一种基于子串的字符串相似度计算方法，其中Q表示子串的长度。对于两个字符串，计算它们共有的Q-gram（长度为Q的连续子串）的数量，然后将这个数量除以两个字符串中Q-gram数量较少的那个， 得到相似度的比例。下面给出它的Java实现：

package com.yelang.project;

import java.util.HashSet;

import java.util.Set;

public class QGramMatching {

/**

* 在这个示例中，calculateQGrams方法接受一个字符串和一个整数Q，然后返回该字符串所有可能的Q-gram的集合。calculateQGramSimilarity方法接受两个字符串和一个整数Q，计算它们的Q-gram集合，并找出共有的Q-gram数量，然后计算相似度。main方法中给出了两个示例字符串s1和s2，以及Q-gram的长度Q，并调用calculateQGramSimilarity方法来计算并打印它们的Q-gram相似度。

请注意，Q-gram的长度Q是一个参数，可以根据具体应用场景进行调整。较短的Q值可以捕捉到更细粒度的相似性，而较长的Q值则可以捕捉到更宽泛的相似性。此外，相似度的阈值可以根据实际需求设定，以判断两个字符串是否相似。

*/

// 计算字符串的Q-gram集合

public static Set<String> calculateQGrams(String s, int q) {

Set<String> qGrams = new HashSet<>();

for (int i = 0; i <= s.length() - q; i++) {

qGrams.add(s.substring(i, i + q));

}

return qGrams;

}

// 计算两个字符串的Q-gram相似度

public static double calculateQGramSimilarity(String s1, String s2, int q) {

Set<String> qGrams1 = calculateQGrams(s1, q);

Set<String> qGrams2 = calculateQGrams(s2, q);

// 计算两个集合的交集

Set<String> intersection = new HashSet<>(qGrams1);

intersection.retainAll(qGrams2);

// 计算相似度

double similarity = intersection.size() / (double) Math.min(qGrams1.size(), qGrams2.size());

return similarity;

}

public static void main(String[] args) {

String s1 = "Camp Humphreys";

String s2 = "United States Army Garrison-Humphreys";

// Misawa Air Range<==>Misawa Air Base:similar = 0.9058216273156766

// Gun Training Area<==>Tsuken Jima Training Area:similar = 0.9202830114233174

int q = 3; // Q-gram的长度

double qGramSimilarity = calculateQGramSimilarity(s1, s2, q);

System.out.println("Q-gram Similarity (Q=" + q + "): " + qGramSimilarity);code>

}

}

        运行以上的程序，得到以下的执行结果：

Q-gram Similarity (Q=3): 0.5833333333333334

4、余弦相似性计算

<code>package com.yelang.project.extend.militarytopics.domain;

import java.io.Serializable;

import com.yelang.framework.aspectj.lang.annotation.Excel;

import com.yelang.framework.aspectj.lang.annotation.Excel.Type;

import lombok.Data;

import lombok.ToString;

@Data

@ToString

public class WebSiteMilitaryBase implements Serializable{

private static final long serialVersionUID = -4620277223946004351L;

@Excel(name = "设施管理代码", type = Type.IMPORT)

private String manageCode;

@Excel(name = "基地英文名称")

private String enName;

@Excel(name = "基地中文名称")

private String cnName;

@Excel(name = "用途")

private String useTo;

@Excel(name = "驻地国家中文名")

private String cnCountry;

@Excel(name = "驻地国家英文名")

private String enCountry;

@Excel(name = "驻地城市中文名")

private String cnCity;

}

        然后定义Excel的读取方法，关键代码如下所示：

public void readJapanData() {

try {

File file = new File("C:/Users/Administrator/Desktop/基地/驻日美军基地.xlsx");

FileInputStream fis = new FileInputStream(file);

ExcelUtil<WebSiteMilitaryBase> util = new ExcelUtil<WebSiteMilitaryBase>(WebSiteMilitaryBase.class);

List<WebSiteMilitaryBase> dataList = util.importExcel(fis);

System.out.println(dataList.size());

for(WebSiteMilitaryBase base : dataList) {

System.out.println(base);

}

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (Exception e) {

e.printStackTrace();

}

}

        运行一下代码，测试一下是否读取成功，如果在控制台中看到以下信息说明解析成功。

2、设置忽略词列表 

        其实忽略词和权重打分的作用是差不多的，忽略词就是在字符串中没有什么影响的词，这里需要注意的是要结合场景来说明。比如当前是均事领域，类似与Air base等这些在相关基地中的字符串中就可以忽略掉。忽略词设置好之后，在进行字符串的相似性计算时，需要把两个字符串进行忽略词替换。关键代码如下：

<code>/**

* 去掉需要忽略的关键词

* @param source

* @return

*/

private String ignoreKeyWords(String source) {

// Barracks 军营 Service Area 服务中心 Air Station 航空站 Air Base 空军基地 Camp 营地 Recreation Center 娱乐中心 Communications Station 通信站

// Transmitter Site 发射站 Communication Site 通信站点 Training 训练 Airfield机场 Ammunition Depot 弹药库 Port 港口 Pier 码头 Dependent Housing 家属区

// Depot 仓库 Landing Field 着陆场 Corps 兵团 Naval 海军

String [] keyWords = {"Barracks","Service Area","Station","Air","Base","Camp","Area","Recreation Center","Communications","Station",

"Transmitter","Site","Communication","Training","Airfield","Annex","Ammunition","Port","Pier","Dependent","Housing","Depot"

,"Storage","Range","Center","Landing Field","Corps","Naval","Marine"};

for(String keyword : keyWords) {

source = source.replace(keyword, "").trim();

}

return source;

}

3、将数据库地名和Excel进行对比

        在这里 ，我们需要将需要对比的数据从数据库中查询出来，然后跟Excel表格中的进行对比。经过忽略词的设置后，我们对比最后的计算结果，最后得到两个字符串的相似性。当两个字符串的相似度大于90%，我们即可认为是统一地点，当然这里最好需要人工审核。

@Test

public void evalJapanCosineSimilarity() {

QueryWrapper<UsaMilitaryBase> queryWrapper = new QueryWrapper<UsaMilitaryBase>();

queryWrapper.isNull("cn_name");//查询基地中文名为空的数据

List<UsaMilitaryBase> dbList = this.militaryBaseService.list(queryWrapper);

System.out.println(dbList.size());

try {

File file = new File("C:/Users/Administrator/Desktop/基地/驻日美军基地.xlsx");

FileInputStream fis = new FileInputStream(file);

ExcelUtil<WebSiteMilitaryBase> util = new ExcelUtil<WebSiteMilitaryBase>(WebSiteMilitaryBase.class);

List<WebSiteMilitaryBase> excelDataList = util.importExcel(fis);

System.out.println(excelDataList.size());

int index = 0;

for(WebSiteMilitaryBase base : excelDataList) {

for(UsaMilitaryBase dbBase : dbList) {

String dbEnName = dbBase.getEnName();

dbEnName = ignoreKeyWords(dbEnName);

String excelEnName = base.getEnName();

excelEnName = ignoreKeyWords(excelEnName);

Double similar = this.getSimilar(dbEnName, excelEnName);

if(similar >= 0.85) {

System.out.println(dbEnName + "<==>" + excelEnName + "\t similar = " + similar);

System.out.println(base);

index ++;

}else {

continue;

}

}

}

System.out.println(index);

} catch (FileNotFoundException e) {

e.printStackTrace();

} catch (Exception e) {

e.printStackTrace();

}

}

        下面我们来执行上述的代码，看看最终符合我们条件的有多少？

Misawa<==>Misawa similar = 0.9999999999999998

WebSiteMilitaryBase(manageCode=FAC 2001, enName=Misawa Air Base, cnName=三泽空军基地, useTo=航空基地, cnCountry=日本, enCountry=Japan, cnCity=青森县三泽市)

Idesuna Jima<==>Idesuna Jima similar = 1.0

WebSiteMilitaryBase(manageCode=FAC 6078, enName=Idesuna Jima Range, cnName=出砂岛炸射练习场, useTo=训练, cnCountry=日本, enCountry=Japan, cnCity=冲绳渡名喜村)

Kawakami<==>Kawakami similar = 1.0

WebSiteMilitaryBase(manageCode=FAC 4083, enName=Kawakami Ammunition Depot, cnName=川上弹药库, useTo=存储, cnCountry=日本, enCountry=Japan, cnCity=广岛县东广岛市)

Hiro<==>Hiro similar = 1.0

WebSiteMilitaryBase(manageCode=FAC 4084, enName=Hiro Ammunition Depot, cnName=广弹药库, useTo=存储, cnCountry=日本, enCountry=Japan, cnCity=广岛县吴市)

Kure 6<==>Kure No.6 similar = 0.8660254037844386

WebSiteMilitaryBase(manageCode=FAC 4152, enName=Kure Pier No.6, cnName=吴市6号码头, useTo=港口设施, cnCountry=日本, enCountry=Japan, cnCity=广岛县吴市)

Torii<==>Torii similar = 0.9999999999999999

WebSiteMilitaryBase(manageCode=FAC 6036, enName=Torii Communications Station, cnName=鸟居通讯站, useTo=通信, cnCountry=日本, enCountry=Japan, cnCity=冲绳县读谷村)

Naha<==>Naha similar = 1.0000000000000002

WebSiteMilitaryBase(manageCode=FAC 6064, enName=Naha Port, cnName=那霸港湾设施, useTo=港口设施, cnCountry=日本, enCountry=Japan, cnCity=冲绳县那霸市)

Fleet Activities Chinhae KS<==>United States Fleet Activities Yokosuka similar = 0.8653323061113575

WebSiteMilitaryBase(manageCode=FAC 3099, enName=United States Fleet Activities Yokosuka, cnName=横须贺美国舰队基地, useTo=港口设施, cnCountry=日本, enCountry=Japan, cnCity=神奈川县横须贺市)

Fleet Activities Chinhae KS (Yechon)<==>United States Fleet Activities Sasebo similar = 0.8560516500077061

WebSiteMilitaryBase(manageCode=FAC 5029, enName=United States Fleet Activities Sasebo, cnName=佐世保美国舰队基地, useTo=港口设施, cnCountry=日本, enCountry=Japan, cnCity=长崎县佐世保市)

Fleet Activities Chinhae KS<==>United States Fleet Activities Sasebo similar = 0.8994681014529727

WebSiteMilitaryBase(manageCode=FAC 5029, enName=United States Fleet Activities Sasebo, cnName=佐世保美国舰队基地, useTo=港口设施, cnCountry=日本, enCountry=Japan, cnCity=长崎县佐世保市)

Hiro<==>Hario similar = 0.8944271909999159

WebSiteMilitaryBase(manageCode=FAC 5119, enName=Hario Dependent Housing Area, cnName=针尾军眷住宅区, useTo=住宅, cnCountry=日本, enCountry=Japan, cnCity=长崎县佐世保市)

Fleet Activities Chinhae KS (Yongsan Garrison)<==>Makiminato ( Kinser) similar = 0.8663164754169591

WebSiteMilitaryBase(manageCode=FAC 6056, enName=Makiminato Service Area (Camp Kinser), cnName=牧港补给地区（金瑟营）, useTo=后勤, cnCountry=日本, enCountry=Japan, cnCity=冲绳县浦添市)

San Vito Dei Normanni<==>Makiminato ( Kinser) similar = 0.8524007579586305

WebSiteMilitaryBase(manageCode=FAC 6056, enName=Makiminato Service Area (Camp Kinser), cnName=牧港补给地区（金瑟营）, useTo=后勤, cnCountry=日本, enCountry=Japan, cnCity=冲绳县浦添市)

13

      可以很直观的看到，经过计算，有的地名已经完全匹配，比如Hiro<==>Hiro     similar = 1.0和Idesuna Jima<==>Idesuna Jima     similar = 1.0。这些数据可以认为是一个地点了。

三、总结

        以上就是本文的主要内容，博客以Java编程为例，讲解了在Java中求解两个字符串的几种方法。通过求解编辑距离、Q-gram Matching、还有余弦相似性计算，通过对比不同的方法，调用Apache 的Common-text中基于余弦的字符相似性得到了比较比错的结果。最后讲解了一个实际的案例，将之前我们采集的漂亮数据库数据和百科的数据进行对齐。为下一步做数据关联和挖掘打下坚实的基础。行文仓促，定有许多的不足之处，如有任何不当或者表达不准确的地方，还恳请各位专家和朋友在评论区留言平指正，不胜感激。