algorithm - 在不评估所有元素对的情况下查找字符串集合中的元素相似性

Question

所以问题集是这样的:

A = {'abc', 'abc', 'abd', 'bcde', 'acbdg', ...}

使用某种类型的 string metric像 Levenshtein 距离一样，它很容易找到 2 个字符串之间字符串相似性的某种启发式方法。

但是，我想在不评估集合中的所有字符串对(O(N^2) 问题)的情况下确定某种基于整个集合的启发式方法，让我对整体相似性有一个很好的了解在所有字符串之间。

蛮力法是:

                          Sum(Metric(All Pairs in A))
CollectionSimilarity(A) = ---------------------------
                                 N*(N+1)/2

有没有一种方法可以在不评估每一对的情况下评估整个集合 A 的相似性？

Answer 1

您始终可以使用一些近似值(例如采样对)。根据 N 的大小，该值应收敛于 NlogN 个样本。