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

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

一些一般提示：

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

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

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

您应该尽快将传入的字符串转换为可比较和可搜索的形式。例如，如果正确完成，将单词转换为 "hash" 的速度非常快。你可以这样做：

字符串 "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 个）字符。如果你想让它更准确，增加 shift and/or store hash in a long.

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

如果你不是在第一个不匹配之后，而是在句子之间的距离之后，你可以在哈希。

Answer 2

看这篇论文：

Detecting Near-Duplicates in Large-Scale Short Text Databases

Abstract. Near-duplicates are abundant in short text databases. Detecting and eliminating them is of great importance. SimFinder proposed in this paper is a fast algorithm to identify all near-duplicates in large-scale short text databases. An ad hoc term weighting scheme is employed to measure each term’s dis- criminative ability. A certain number of terms with higher weights are seletect as features for each short text. SimFinder generates several fingerprints for each text, and only texts with at least one fingerprint in common are compared with each other. An optimization procedure is employed in SimFinder to make it more efficient. Experiments indicate that SimFinder is an effective solution for short text duplicate detection with almost linear time and storage complexity. Both precision and recall of SimFinder are promising

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

Which is the fastest way to find out if two strings are fuzzy? [Not another Levenshtein post]

c#

vb.net

string

performance

fuzzy-search