Aja*_*jay 8 python string algorithm hash cluster-analysis
有没有一种方法来计算字符串的一般"相似性得分"？在某种程度上,我不是将两个字符串比较在一起,而是我为每个字符串得到一些数字/分数(哈希),以后可以告诉我两个字符串是或不相似.两个相似的字符串应该具有相似(接近)的分数/哈希值.
让我们将这些字符串和分数视为一个例子:
你好世界1000
你好,世界!1010
你好地球1125
Foo bar 3250
FooBarbar 3750
Foo Bar!3300
Foo世界!2350
你可以看到Hello world!和Hello世界是相似的,他们的分数彼此接近.
这样,通过从其他分数中减去给定的字符串分数然后对其绝对值进行排序,可以找到与给定字符串最相似的字符串.
我的最终目标是:会有流式日志消息(只有纯消息),我想找到这些消息的模式(某种正则表达式类型).但是只有当我可以使用类似的字符串时它才会启动.我再次关注我应该为每个字符串获得一些数字/分数(哈希)并且可以告诉我两个字符串是否相似
TL; DR:Python BK-tree
有趣的问题.我在这个领域的经验有限,但由于Levenshtein距离满足三角不等式,我认为必须有一种方法来计算与原点的某种绝对距离,以便在不直接执行的情况下找到彼此附近的字符串.比较整个数据库中的所有条目.
在搜索与此相关的一些术语时,我发现了一个特别有趣的论点:马修亚当斯卡拉计算中度量空间的方面.
在第26页,他讨论了基于kd-trees和其他的相似性度量,但得出结论:
但是,一般度量空间不提供这些技术所需的几何.对于没有其他假设的一般度量空间,基于距离的方法必须使用基于距离的方法,该方法仅基于它们彼此的距离来索引点.Burkhard和Keller [35]在1973年提供了第一个这样的索引结构之一,现在称为BK树的首字母.在BK树中,假设度量具有一些离散的返回值,每个内部节点包含有利位置,子树对应于度量标准的不同值.
有关BK树如何工作的博客文章可以在这里找到.
在论文中,Skala继续描述这个问题的其他解决方案,包括VP树和GH树.第6章基于Levenshtein编辑距离分析距离.他还为字符串提供了一些其他有趣的距离指标.
我还发现了多维度量和度量数据结构的基础,这似乎与您的问题相关.