c# - 找出两个字符串是否模糊的最快方法是什么？ [不是另一个 Levenshtein 帖子]

Question

我想比较两个字符串并确定它们之间是否存在最小相似性，比方说，它们是否相等或大于 70%。我不需要知道确切的相似度，只要它们在一定百分比上相似即可。示例:

黑猫微笑

黑猫哭了

我知道我可以使用 Levenshtein 距离来找出这个，但它太慢了。我需要做数百万次比较，所以我只想预先过滤那些超过一定百分比的人，并且只有在这个时候，才执行 levenhstein 算法。到现在为止，我将字符串拆分成单词 {the, black, cat, smiles} {the, black, cat, cries} 并进行交集。但是拆分太慢了。如果我想将 10000 个句子与 10000 个句子的内存进行比较，拆分可能需要几分钟，而我需要在几秒钟内完成(不超过 1 分钟)。我正在对 ram 内存进行操作，而不是在 DB 中。有没有办法解决这种情况？使用数据库(如 SQL)会更快吗？一些信息将不胜感激。

编辑:这是我在 vb.net 中进行预过滤的代码

 Public Function CompareSegments(s1 As String, s2 As String) As Decimal
            Dim Percentagem As Double = 0
            ' Return 0
            Try
                '-----------------------------
                '------ IMPROVEMENT!!!!!!-----  MORE FILTERING
                '----------------------------
                If s2.Length / s1.Length > 1.6 Or s2.Length / s1.Length < 0.6 Then 'filtering by length comparison. If their lenghts are too much different, they aren't compared. We save some seconds.
                    Return 0
                End If
                Dim NumPalavrasNovas As Integer
                Dim MatrizPalavras1(), MatrizPalavras2() As String
                Dim separador() As String = {" "} 
                MatrizPalavras1 = s1.Split(separador, StringSplitOptions.RemoveEmptyEntries)
                MatrizPalavras2 = s2.Split(separador, StringSplitOptions.RemoveEmptyEntries)
                ' Dim Intersecao As IEnumerable(Of String) = MatrizPalavras1.Intersect(MatrizPalavras2) 
                If MatrizPalavras1.Length > MatrizPalavras2.Length Then
                    NumPalavrasNovas = MatrizPalavras1.Length 
                Else
                    NumPalavrasNovas = MatrizPalavras2.Length 
                End If
                If NumPalavrasNovas <> 0 Then

                    ' Dim j = Intersecao.ToList()
                    ' Percentagem = Intersecao.Count / NumPalavrasNovas
                    Percentagem = Intersect(MatrizPalavras1.ToList, MatrizPalavras2.ToList) / NumPalavrasNovas
                Else
                    Percentagem = 0
                End If
            Catch ex As Exception

            End Try
            Return Percentagem
        End Function

Answer 1

一些一般提示:

您面临准确性和速度之间的典型权衡:如果您可以忍受一些错误，您可以获得更高的速度。

对于可能的错误，您应该决定是否可以容忍误报(字符串看起来相等但不相等)或漏报(字符串看起来不同但不相等)。这将影响选择(见下文)。

您应该将您的“内存”存储在一个数据结构中，该数据结构可以尽可能高效/快速地进行搜索。寻找 O(log n) 可搜索数据结构，如 SortedSet 或 SortedDictionary 或 SortedList。如果你需要经常改变你的内存，插入操作应该是 O(log n) 这排除了 SortedList。如果您想搜索一个范围，例如您应该使用 SortedSet 或自行开发的二叉树。

您应该尽快将传入的字符串转换为可比较和可搜索的形式。例如，如果操作正确，将单词转换为“哈希”的速度非常快。你可以这样做:

字符串 "ABC"被转换成一个 int 散列:

int hash = 'A' + 'B' << 8 + 'C' << 16;

速度非常快，但有一些错误(有其他字符串导致相同的散列)

有了这些想法，您可以很快得到结果:

int hash = 0;
int shift = 0;
foreach(char c in incomingString)
{
    if( c _is whitespace_)
    { 
         // walk binary tree and see if the next word matches
         hash = 0;
         shift = 0;
    }
    else
    {
        hash += c.ToInt32() << shift;
        shift = (shift+8)%24;
    }
}

这很快，因为它仅使用加法(1 个循环)和移位(1 个循环)操作，例如每个字符大约 2 个周期。

如果您希望速度更快，请仅使用每个单词的前 2 或 3(或 N)个字符。如果您希望它更准确，请增加移位和/或将散列存储在 long 中。

这假设您将内存转换为哈希列表的二叉树(每个单词一个哈希)，它允许您遍历树并找出传入的单词序列(哈希)是你内存的一部分，并在发现第一个不匹配后停止整个比较。

如果您不是在第一个不匹配之后，而是在句子之间的距离之后，您可以对哈希执行类似 Lewenshtein 的算法。