java - 使用已知算法比较两个字符串

Question

我正在尝试使用一些众所周知的算法(如 Levenstein distance)来比较两个字符串(产品名称)和 string simmetrics 的不同解决方案库(使用 SmithWatermanGotoh 算法获得最佳结果)。

两个字符串是:

iPhone 3gs 32 GB black

Apple iPhone 3 gs 16GB black

如果某些单词的顺序不同(算法的工作方式是预期的)，Levenstein 在整个字符串上的工作非常糟糕，所以我尝试逐字比较。

我面临的问题是检测用空格字符分隔的相似“单词”的方法 ('3gs'->'3 gs' ; '32 GB'->'16GB')。

我的代码比较较短的(字数，如果 == 则 str.length)字符串和较长的字符串。单词分为 ArrayList<String> .我将 str1 中的每个单词与同一个字符串中的其他单词组合在一起，创建新的数组列表。

这是一个粗略的代码:

foreach(str1)

    foreach(str2)
        res1 = getLevensteinDist
    endforeach

    foreach(combinedstr2)
        res1 = getLevensteinDist
    endforeach      

    return getHigherPercent(res1, res2)

 endforeach

如果 str2 中的单词被拆分，这会起作用，但我不知道如何进行反向操作，检测 str2 中被 str1 拆分的单词。

我希望我至少有点清楚我要做什么。感谢您的帮助。

Answer 1

首先你应该预处理你的字符串，我的意思是你应该从输入字符串中删除“a, the, as, an”和所有常见的动词，数字......，你也应该将每个复数形式转换为单数形式形式，....统一所有的话。然后你可以应用一些字符串匹配算法，或者只是将单词放入hashmap，或者如果它们很多，将它们放入trie，然后运行你的相似度算法。