java - java比较2个字符串是否包含相同的单词

Question

我正在使用 Levenshtein 距离，它是一种字符串度量，用于测量两个序列之间的差异量，以查找两个字符串之间的差异百分比。我想使用更好的方法来使用字符串中的单词来声明字符串相似。

例如:假设我有一个包含 2 个段落的字符串，第二个字符串仅包含第一个字符串的第二段。

我知道我可以比较每个字符串的第一个单词，然后比较第二个单词等，但如果发生像我提出的最后一个例子这样的情况，那就不会有效。

我在想也许可以将第一个字符串中的第一个单词与第二个字符串中的所有单词进行比较，但我担心这会使过程非常缓慢。

Answer 1

将第一个字符串中的每个单词与第二个字符串中的所有单词进行比较可能会产生比 Levenshtein 距离稍好的性能，但数量级相同。 Levenstein 距离为 O(m*n)，您的算法为 O(m^2)(其中 m 和 n 是字符串的长度)。

如果您只关心匹配单词(例如“color”和“colour”将被视为两个完全不同的字符串)并忽略单词顺序(例如“red color”和“color red”将被视为两个相同的字符串)并且您不关心算法的空间复杂度，您可以创建第一个字符串的单词索引(例如哈希表)，然后比较每个字符串第二个字符串中针对此索引的单词。如果您的索引使用具有恒定时间插入和删除的数据结构，则这会产生复杂度为 O(m+n) 的算法。