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

Question

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

显而易见的答案是遍历所有n个字符串并检查当前字符串中存在多少个字符.但是,此算法将频繁运行,并且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维向量.然后你可以计算两个向量的点积,得到两个向量之间角度的余弦,这个值应该与字符串的相似性成比例.

假设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范数) - 但这只会改变数字,因为有限维向量空间中的范数都是等价的.