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

StackOverflow https://stackoverflow.com/questions/859441

  •  21-08-2019
  •  | 
  •  

题

由于列表L的正字符串，并输入字符串S，什么是找L中的字符串包含存在于S中的大多数人物的有效途径？我们想找到L中的字符串是最密切由包含在S中的字母。

答案显然是遍历所有的n串和检查，看看有多少个字符当前字符串中存在S.然而，这种算法将频繁地运行，而n字符串列表L将被存储在数据库中...手动遍历所有N个字符串将需要类似的N *平方公尺，其中n为L串的数量大哦，m是L所有字符串的最大长度，以及最大S的长度...在这种情况下米实际上是150的常数。

难道还有比只是一个简单的循环更好的办法？有没有一种数据结构，我可以加载n个字符串放到会给我快速的搜索能力吗？是否有使用关于每个所述n字符串将执行比环路？

的更好的预先计算的元数据的算法

我知道有很多爱好者在那里，是进入算法。所以，请大家帮忙！

谢谢！

有帮助吗？

解决方案

如果您有子后，一个特里或Patrica线索可能是一个很好的起点

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

               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) 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范数）例如 - 但是这将只改变号码，因为在有限维向量空间规范都是等效的

其他提示

听起来像是你需要一个特里。尝试使用搜索类似的方式拼写检查器将工作的话。因此，如果串S在相同的顺序的字符串以L字符，那么这可能为你工作。

如果然而，在S中的字符的顺序是不相关的 - 就像一组拼字游戏的牌，你要搜索的最长的一句话 - 那么这是不是你的解决方案。

你想要的是一个 BK-树。这有点不直观，但很凉爽 - 和它使得有可能一个的Levenshtein（编辑）为O距离阈值内搜索元件（log n）的时间

如果你关心你的输入字符串排序，使用它们原样。如果你没有，你可以将它们插入到BK-树（或与他们查询）之前的单个字符排序。

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

这是相当沉重的，但这样是你问什么。它谈论字的相似性，和字符错位。

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

在我看来，该字符的顺序是不是在你的问题很重要，但你正在寻找的字S的“近字谜游戏。”

如果这是这样，那么你可以代表在集合L的每一个字为26个的整数数组（假设你的字母表有26个字母）。可以作为S类似于26点的整数的数组;现在要找到你刚才通过集合L运行一次，并计算S-矢量和电流L-向量之间的距离度量的最佳匹配，但是要定义距离度量（例如欧几里德/加总广场或曼哈顿绝对差/和）。这是O（n）的算法，因为矢量具有恒定的长度。

下面是已经被伟大的工作对我来说是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
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top