logo标签列表

如何最佳匹配两个字符串？

databasealgorithmstringmatching
3

您知道有哪些好的算法可以匹配两个字符串，并返回这两个字符串匹配的百分比吗？

而且，有些算法可以与数据库一起使用吗？

5个回答
8

Levenstein distance（编辑距离）是一种衡量方法。它基本上告诉你，从第一个字符串到第二个字符串需要编辑、删除或添加多少个字符。我不确定是否有一些数据库系统支持它。

但我确定，一种更简化的算法Soundex在某些数据库系统中得到了支持。

2

这取决于您对相似性的标准。其他人已经向您介绍了Levenstein距离（编辑距离是相同的）。这通常非常好，而且明显比像soundex这样的东西更独立于语言。但请注意，Levenstein距离不能很好地处理转换。因此：

Levenstein("copy", "cpoy") == 2

如果你正在处理人类输入，那么转置是相当常见的。无论这是否是一个问题，都取决于你对相似度的度量标准。
我记得已经有一段时间了，但我相信Postgresql内置或作为contrib C模块可用的levenstein()函数可以解决这个问题。
1

我认为你要找的问题叫做编辑距离。一般来说，计算它是很昂贵的，但如果你正在寻找与其他字符串编辑距离较小的字符串，那么情况就不那么糟糕了。维基百科文章中有更多信息。

1

如何最好地匹配两个字符串？让它们出去喝杯咖啡，如果感觉合适，再去吃晚饭和看电影。或者也许他们可以一起编程？这真的取决于这些字符串的情况。即使是喝咖啡有时候也可能会很棘手。

0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接