0

我正在尝试使用一些众所周知的算法来比较两个字符串（产品名称），例如Levenstein 距离和字符串 simmetrics的不同解决方案库（使用SmithWatermanGotoh alg获得了最佳结果）。

两个字符串是：

iPhone 3gs 32 GB 黑色

苹果 iPhone 3 gs 16GB 黑色

如果某些单词的顺序不同（这是算法工作方式所预期的），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 中拆分的单词。

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

4

4 回答 4

1

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

于 2013-08-23T10:13:14.813 回答
0

看看 TF-IDF。它专门用于计算文本特征之间的相似性。

http://nlp.stanford.edu/IR-book/html/htmledition/tf-idf-weighting-1.html

于 2013-08-23T14:47:24.017 回答
0

尝试将其中一个字符串拆分为单词，然后为 eash 单词运行 SmithWaterman 并使用 SmithWaterman 的分数作为相似性度量。

于 2013-08-23T21:16:28.470 回答
0

13 年前，我编写了自己的三元模糊搜索算法实现，名为“Wilbur-Khovayko 算法”。

你可以在这里下载：http: //olegh.cc.st/wilbur-khovayko.tar.gz

它为输入的搜索词搜索“N个最接近的词”。

术语列表 - 在文件 termlist.txt 中 N - 在变量 lim 中，文件 findtest.c

算法非常快：在旧的 Sun 200mHz 上，它在 100,000 个条目中搜索 100 个最接近的词约 0.3 秒。

于 2013-08-24T00:58:51.073 回答