使用相同字符查找最接近字符串的算法

Question

给定一个包含 n 个字符串的列表 L 和一个输入字符串 S，找到 L 中包含 S 中存在的最多字符的字符串的有效方法是什么？我们想在 L 中找到与 S 中包含的字母最接近的字符串。

显而易见的答案是遍历所有n个字符串，并检查当前字符串中有多少个字符存在于S中。但是这个算法会被频繁运行，n个字符串的列表L将存储在数据库中...手动遍历所有 n 个字符串需要类似于 n*m^2 的 big-Oh，其中 n 是 L 中的字符串数，m 是 L 中任何字符串的最大长度，以及最大长度S 的长度...在这种情况下，m 实际上是一个常数 150。

有没有比简单循环更好的方法？是否有一种数据结构可以将 n 个字符串加载到其中，从而提供快速搜索能力？是否有一种算法使用关于 n 个字符串中的每一个的预先计算的元数据，其性能会比循环更好？

我知道有很多极客都热衷于算法。所以请帮忙!

谢谢!

Answer 1

如果你在子串之后，一个Trie或者 Patrica trie 可能是一个很好的起点。

如果你不关心顺序，只关心每个符号或字母的数量，我会计算所有字符串的直方图，然后将它们与输入的直方图进行比较。

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

如果您只考虑不区分大小写的拉丁字母，这会将成本降低到 O(26 * m + n) 加上一次预处理。

如果 m 是常量，您可以通过对其进行归一化，将直方图解释为 26 维单位球体上的 26 维向量。然后你可以计算Dot Product两个向量的夹角的余弦值，这个值应该与字符串的相似度成正比。

假设 m = 3，字母表 A = { 'U', 'V', 'W' } 只有三个大小，以及以下字符串列表.

L = { "UUU", "UVW", "WUU" }

直方图如下。

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

直方图 h = (x, y, z) 归一化为 h' = (x/r, y/r, z/r) 和 r 直方图 h 的欧几里德范数 - 即 r = sqrt(x² + y² + z²)。

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

输入 S = "VVW" 具有直方图 hs = (0, 2, 1) 和归一化直方图 hs' = (0.000, 0.894 , 0.447)。

现在我们可以计算两个直方图h1 = (a, b, c) 和h2 = (x, y, z) 的相似度作为欧式距离两个直方图。

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

对于我们得到的例子。

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

因此“UVW”最接近“VVW”(数字越小表示相似度越高)。

使用归一化直方图 h1' = (a', b', c') 和 h2' = (x', y', z') 我们可以将距离计算为两个直方图的点积。

d'(h1', h2') = a'x' + b'y' + c'z'

对于我们得到的例子。

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

再次确定“UVW”最接近“VVW”(数字越大表示相似度越高)。

两个版本产生不同的数字，但结果总是相同的。也可以使用其他范数——例如曼哈顿距离(L1 范数)——但这只会改变数字，因为有限维向量空间中的范数都是等价的。