35

我在使用 PHP levenshtein函数比较字符串方面取得了一些成功。

但是，对于包含交换位置的子字符串的两个字符串，算法将它们计为全新的子字符串。

例如：

levenshtein("The quick brown fox", "brown quick The fox"); // 10 differences

被视为具有以下共同点：

levenshtein("The quick brown fox", "The quiet swine flu"); // 9 differences

我更喜欢一种算法，它看到前两个更相似。

我怎么能想出一个比较函数来识别已经切换位置的子字符串与编辑不同？

我想到的一种可能的方法是在比较之前将字符串中的所有单词按字母顺序排列。这将单词的原始顺序完全排除在比较之外。然而，这样做的一个缺点是，仅更改单词的第一个字母会造成比更改单个字母更大的干扰。

我想要实现的是比较关于人的两个作为自由文本字符串的事实，并确定这些事实表明相同事实的可能性有多大。事实可能是某人就读的学校，例如他们的雇主或出版商的名称。两个记录可能有相同的学校拼写不同，单词的顺序不同，多余的单词等，所以如果我们要很好地猜测它们指的是同一所学校，匹配必须有点模糊。到目前为止，它在拼写错误方面效果很好（我使用的是类似于变音位的语音算法），但如果你切换学校中常见的单词顺序，效果就很差：“xxx 学院”vs “xxx学院”。

4

9 回答 9

24

N-gram

使用N-gram，它支持跨整个文本的多字符换位。

一般的想法是，您将有问题的两个字符串拆分为所有可能的 2-3 个字符子字符串（n-gram），并将两个字符串之间共享的 n-gram 的数量视为它们的相似性度量。然后可以通过将共享数除以较长字符串中的 n-gram 总数来规范化。这是微不足道的计算，但相当强大。

对于例句：

A. The quick brown fox
B. brown quick The fox
C. The quiet swine flu

A 和 B 共享18 个 2 克

A 和 C 只共享8 个 2 克

总共有20个可能。

Gravano 等人对此进行了更详细的讨论。纸。

tf-idf 和余弦相似度

一个不那么简单但基于信息论的替代方案是使用术语词频-逆文档频率 (tf-idf)来衡量标记，构造句子向量，然后使用余弦相似度作为相似度度量。

算法是：

  1. 计算每个句子的 2 字符标记频率 (tf)。
  2. 计算逆句子频率 (idf)，它是语料库中所有句子的数量（在本例中为 3）除以特定标记在所有句子中出现的次数的对数。在这种情况下， th在所有句子中，因此它的信息内容为零（log（3/3）=0）。 以色列国防军公式
  3. 通过将 tf 和 idf 表中的相应单元相乘来生成 tf-idf 矩阵。 tfidf
  4. 最后，计算所有句子对的余弦相似度矩阵，其中 A 和 B 是 tf-idf 表中相应标记的权重。范围从 0（不相似）到 1（相等）。
    余弦相似度
    相似矩阵

Levenshtein 修改和 Metaphone

关于其他答案。Damerau–Levenshtein修改仅支持两个相邻字符的转置。Metaphone旨在匹配听起来相同的单词，而不是用于相似性匹配。

于 2011-02-21T22:41:19.623 回答
9

这简单。只需在单词而不是字母上使用Damerau-Levenshtein距离。

于 2009-05-06T05:24:34.173 回答
6

在空间上爆炸，对数组进行排序，内爆，然后进行 Levenshtein。

于 2009-05-06T17:06:14.910 回答
3

你也可以试试这个。（只是一个额外的建议）

$one = metaphone("The quick brown fox"); // 0KKBRNFKS
$two = metaphone("brown quick The fox"); // BRNKK0FKS
$three = metaphone("The quiet swine flu"); // 0KTSWNFL

similar_text($one, $two, $percent1); // 66.666666666667
similar_text($one, $three, $percent2); // 47.058823529412
similar_text($two, $three, $percent3); // 23.529411764706

这将表明第一和第二比一和三以及二和三更相似。

于 2009-05-06T09:34:45.557 回答
3

我一直在拼写检查器中实施 levenshtein 。

您要求的是将转置计为 1 次编辑。

如果您只想计算一个单词的换位，这很容易。然而，对于 2 个或更多单词的转置，算法的添加是最坏的情况!(max(wordorder1.length(), wordorder2.length()))。向已经是二次的算法添加非线性子算法不是一个好主意。

这就是它的工作方式。

if (wordorder1[n] == wordorder2[n-1])
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1, workarray[x-2, y-2]);
}
  else
{
  min(workarray[x-1, y] + 1, workarray[x, y-1] + 1);
}

只是为了触摸换位。如果您想要所有换位，则必须从该点开始对每个位置进行向后比较

1[n] == 2[n-2].... 1[n] == 2[0]....

所以你明白他们为什么不把它包括在标准方法中。

于 2009-06-05T19:44:12.203 回答
1

接受此答案并进行以下更改：

void match(trie t, char* w, string s, int budget){
  if (budget < 0) return;
  if (*w=='\0') print s;
  foreach (char c, subtrie t1 in t){
    /* try matching or replacing c */
    match(t1, w+1, s+c, (*w==c ? budget : budget-1));
    /* try deleting c */
    match(t1, w, s, budget-1);
  }
  /* try inserting *w */
  match(t, w+1, s + *w, budget-1);
  /* TRY SWAPPING FIRST TWO CHARACTERS */
  if (w[1]){
    swap(w[0], w[1]);
    match(t, w, s, budget-1);
    swap(w[0], w[1]);
  }
}

这是在 trie 中进行字典搜索，但对于匹配单个单词，这是相同的想法。你在做分支和绑定，在任何时候，你都可以做任何你喜欢的改变，只要你给它一个成本。

于 2009-05-06T17:24:49.200 回答
1

消除两个字符串之间的重复单词，然后使用 Levenshtein。

于 2009-05-06T17:41:49.627 回答
1

我相信这是使用向量空间搜索引擎的一个典型例子。

在这种技术中，每个文档本质上都变成了一个向量，其维度与整个语料库中的不同单词一样多；然后类似的文档会占据该向量空间中的相邻区域。该模型的一个很好的特性是查询也只是文档：要回答查询，您只需计算它们在向量空间中的位置，您的结果就是您能找到的最接近的文档。我确信那里有 PHP 的 get-and-go 解决方案。

要模糊向量空间的结果，您可以考虑使用词干提取/相似自然语言处理技术，并使用 levenshtein 为出现在您的整体词汇表中的相似词构建辅助查询。

于 2010-08-07T20:57:56.987 回答
0

如果第一个字符串是 A，第二个字符串是 B：

  1. 将 A 和 B 拆分为单词
  2. 对于 A 中的每个单词，找到 B 中的最佳匹配单词（使用 levenshtein）
  3. 从 B 中删除该单词并将其放入 B* 中与 A 中匹配单词相同的索引处。
  4. 现在比较 A 和 B*

例子：

A: The quick brown fox
B: Quick blue fox the
B*: the Quick blue fox

您可以通过多次执行来改进第 2 步，首先只找到完全匹配，然后在 A 中找到 B* 中没有同伴的单词的紧密匹配，然后是不太紧密的匹配，等等。

于 2011-01-29T23:48:41.283 回答