我正在使用 Levenshtein 距离，这是一个字符串度量，用于测量两个序列之间的差异量，以找到两个字符串之间的差异百分比。我想使用更好的方法来声明字符串是相似的使用字符串中的单词。
例如：假设我有一个包含 2 个段落的字符串，而第二个字符串仅包含第一个字符串的第二个段落。
我知道我可以比较每个字符串的第一个单词，然后是第二个等，但是如果发生像我提出的最后一个示例这样的情况，那将无效。
我在想也许将第一个字符串中的第一个单词与第二个字符串中的所有单词进行比较，但我担心这会使过程非常缓慢。
问问题
774 次
1 回答
1
将第一个字符串中的每个单词与第二个字符串中的所有单词进行比较可能会产生比 Levenshtein 距离稍好的性能，但数量级相同。Levenstein 距离为 O(m*n)，您的算法为 O(m^2)（其中 m 和 n 是字符串的长度）。
如果您只关心匹配单词（例如“color”和“color”将被视为两个完全不同的字符串）并且忽略单词顺序（例如“red color”和“color red”将被视为两个相同的字符串）和您不关心算法的空间复杂度，您可以创建第一个字符串的单词索引（例如哈希表），然后将第二个字符串中的每个单词与该索引进行比较。如果您的索引使用具有恒定时间插入和删除的数据结构，这会产生复杂度 O(m+n) 的算法。
于 2012-07-23T16:48:10.717 回答