4

给定一个包含 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 个字符串中的每一个的元数据，其性能会比循环更好？

我知道有很多极客都在研究算法。所以请帮忙！

谢谢！

4

6 回答 6

6

如果您追求子字符串，Trie或 Patrica trie 可能是一个很好的起点。

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

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

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

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

假设只有m = 3一个大小为 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)rhr = 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 范数）——但这只会改变数字，因为有限维向量空间中的范数都是等价的。

于 2009-05-13T18:20:13.813 回答
1

听起来你需要尝试一下。尝试用于搜索类似于拼写检查器工作方式的单词。因此，如果字符串 S 的字符顺序与 L 中的字符串相同，那么这可能对您有用。

但是，如果 S 中的字符顺序不相关——比如一组拼字游戏，而你想搜索最长的单词——那么这不是你的解决方案。

于 2009-05-13T18:08:20.993 回答
1

你想要的是BK-Tree。这有点不直观，但非常酷 - 它可以在 O(log n) 时间内搜索 levenshtein（编辑）距离阈值内的元素。

如果您关心输入字符串的顺序，请按原样使用它们。如果不这样做，您可以在将单个字符插入 BK-Tree（或使用它们进行查询）之前对它们进行排序。

于 2009-05-13T23:18:13.157 回答
0

我相信你在找什么可以在这里找到：基于模糊逻辑的搜索技术

它很重，但你所要求的也是如此。它谈论单词相似性和字符错位。

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M
于 2009-05-13T19:02:04.807 回答
0

在我看来，字符的顺序在您的问题中并不重要，但您正在搜索单词 S 的“近字谜”。

如果是这样，那么您可以将集合 L 中的每个单词表示为 26 个整数的数组（假设您的字母表有 26 个字母）。您可以将 S 类似地表示为 26 个整数的数组；现在要找到最佳匹配，您只需在集合 L 中运行一次并计算 S 向量和当前 L 向量之间的距离度量，但是您想定义距离度量（例如欧几里得 / 平方和或曼哈顿/ 绝对差之和）。这是 O(n) 算法，因为向量具有恒定长度。

于 2009-05-13T20:42:43.143 回答
0

这是一个对我来说非常有用的 T-SQL 函数，它为您提供了编辑距离：

例子：

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

功能：

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END
于 2010-09-27T06:05:38.657 回答