通过关键词匹配web端域名与移动端app的一次尝试

最近工作中拿到了一些web端应用的资料，现在正在做的方向却是移动端app，为了把这些资料有效利用起来，需要找到其中各域名所可能对应的移动端应用。在网络上搜索了一圈无果之后，决定自己用关键词匹配的方法尝试一下。

首先尝试直接将域名信息拆解，剔除掉无关的前后缀，提取关键词。同时，依据这些关键词去跟，之前在谷歌商店中爬取的应用包名进行匹配。

但得到的结果有限，原因是域名与包名二者间往往并不存在直接的包含关系，而是各执其词地描述着应用的服务名，虽然这些细微的差异能人为地一眼看出来，但无法通过in()直接判断，看来需要使用更敏锐的字符串匹配算法。

参照下面这篇博客的三种方法一一进行了尝试，最后选定了这种情况下，与手动匹配直觉上最相符的“最长公共子字符串百分比”作为度量，为每个域名都匹配上了和它具有最大“最长公共子字符串百分比”的包名，作为后续移动端应用分析的参考。

放一个自己用的脚本作为参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# -- coding: utf-8 --**
# from urllib import request,parse
import json,requests
import os
import pandas as pd
import difflib
    
df = pd.read_csv("<包名信息>")

appdict = dict()
applist = df['apkName'].dropna().tolist()
# 设包名为行索引
ndf = df.set_index('packageName')
ndf['domain'] = ''

# 循环域名列表，找到最匹配的字符
for apk in top['package_name'].dropna().tolist():
    name = ndf.at[apk,'apkName']
    maxsize = 0
    # 每次循环只记录最大值索引，减少开销
    web = 0
    for app in appInfo:
        # 利用difflib中的语句匹配器，计算最长公共子字符串百分比
        match = difflib.SequenceMatcher(None, app[0], name).find_longest_match(0, len(app[0]), 0, len(name))
        if match.size > maxsize:
            maxsize = match.size
            web = appInfo.index(app)
    ndf.at[apk,'domain'] = appInfo[web][0]

ndf = ndf.dropna().to_csv('<输出目录>', index='apkName')

在日常的工具开发过程中，经常会碰到需要进行字符串匹配的问题。

无论是想设计一种新的数据库查询算法，实现一定程度的模糊匹配，还是想自动化处理大批文本的对照工作，将自己从头晕眼花的人工比较中解放出来。

都需要一种方法将相似的字符串匹配在一起，而当它们在表述习惯与形式上存在着些许不同，无法简单地进行完整匹配时，则涉及到部分字符串匹配问题。

三种处理字符串比较时常用的度量方式

部分字符串匹配的核心问题在于找到一个贴近我们需求的方法，该方法能自动计算两个字符串之间的相似度。
下面将讨论Python中三种处理字符串比较时常用的度量方式：

  • Jaccard距离
  • 最长公共子字符串百分比
  • Levenshtein相似性

三种方式

Jaccard距离

最简单的方法之一是使用Jaccard距离。

简单来说，它计算的是两个字符串中，相同的唯一字符数与总和的唯一字符数之比。（此处的唯一字符数是指字符串去重后独特的字符数量）

以下是Python中计算Jaccard距离的实现：

1
2
3
4
5
6
7
8
9
def jaccard_similarity(s1: str, s2: str)->float:
    """Computes the Jaccard similarity score between s1 and s2."""
    return len(set(s1) & set(s2)) / len(set(s1) | set(s2))

if __name__ == "__main__":
    s1 = "String matching is not easy"
    s2 = "Compare two strings is not easy"
    jaccard_sim = jaccard_similarity(s1, s2)
    print(f"The Jaccard similarity between {s1} and {s2} is {jaccard_sim}")

Jaccard距离的优点是实现简单，速度快，相应的，由于这种方法并不考虑字符的顺序，可靠性不高。

Jaccard距离

最长公共子字符串百分比

最长公共子字符串是指两个字符串中所共有的最长子字符串。

它的计算方式也很容易理解，即将相似性度量为最长公共子字符串的长度与两个字符串间最小长度的比。

以下是Python中计算最长公共子字符串百分比的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from difflib import SequenceMatcher

def longest_common_substring(s1: str, s2: str) -> str:
    """Computes the longest common substring of s1 and s2"""
    seq_matcher = SequenceMatcher(isjunk=None, a=s1, b=s2)
    match = seq_matcher.find_longest_match(0, len(s1), 0, len(s2))

    if match.size:
        return s1[match.a : match.a + match.size]
    else:
        return ""

def longest_common_substring_percentage(s1 : str, s2 : str) -> float:
    """Computes the longest common substring percentage of s1 and s2"""
    assert min(len(s1), len(s2)) > 0, "One of the given string is empty"
    return len(longest_common_substring(s1, s2))/min(len(s1), len(s2))

最长公共子字符串百分比的优点是考虑到了字符的顺序，缺点是实现难度相对较高。

最长公共子字符串百分比

Levenshtein相似性

Levenshtein距离是编辑距离的一种。通用的编辑距离允许为字符串的每种修改类型定义权重，而Levenshtein距离对所有字符串修改的权重均设为1。

Levenshtein距离的计算是字符串为匹配另一个字符串所需的最小修改数。

修改一般可以有3种类型：

  • 插入：添加额外字符
  • 删除：删除原有字符
  • 替换：替换字符

值得注意的是，有的计算方式中会将“替换”视为“删除”+“插入”的操作。

以下是Python中计算Levenshtein距离的实现：

1
2
3
4
5
6
7
from difflib import SequenceMatcher

from Levenshtein import distance
def levenshtein_distance_percentage(s1: str, s2: str) -> float:
    """Computes the Levenshtein dis"""
    assert min(len(s1), len(s2)) > 0, "One of the given string is empty"
    return 1. - distance(s1, s2) / min(len(s1), len(s2))

Levenshtein距离的优点是有助于了解匹配字符串需要多少修改，缺点是实现难度相对高。

Levenshtein距离

参考资料：

部分字符串匹配 https://mindee.com/blog/partial-string-matching/

difflib官方文档 https://docs.python.org/3/library/difflib.html

find_longest_match使用方法 https://stackoverflow.com/questions/18715688/find-common-substring-between-two-strings