0

我有一个包含大约 1000 个字符串的 ArrayList。我想根据与外部给定字符串的相似性对这个列表进行排序。非常接近字符串的字符串将排在最前面。

例如。我有一个像“美女与野兽”这样的字符串。

我的 Arraylist 包含字符串，如：

RedWall
美女与野兽 3
BlueWall
BeautyQueen I
Beast of Rome II
美女与野兽 1
Beast with The Beauty
BlueWall 2
BeautyQueen II
Beast of Rome I
美女与野兽 2
...

所以在对这个数组列表进行排序之后，它应该是这样的......

美女与野兽 1
美女与野兽 2
美女与野兽 3
野兽与美女
BeautyQueen I
BeautyQueen II
Beast of Rome I
Beast of Rome II
BlueWall
BlueWall 2
RedWall

像这样的东西..我不知道美女与野兽3之后的顺序会如何..但它应该选择具有完全相同字符串的字符串作为开头。

我正在寻找一些实际上可以帮助我在 Java 中实现此任务的算法。

我也听说过使用 Levenstein Distance，但我不知道如何将其用于我的任务。

任何指针都会有很大帮助。

4

2 回答 2

2

根据列文斯坦距离http://en.wikipedia.org/wiki/Levenshtein_distance排序。通过这个距离，您可以定义字符串彼此之间的距离。在比较器中实现它。

这是一个实现：http ://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Java

从 sanbhat 获取代码，并用我发布的维基百科的列文斯坦距离替换他的得分函数。

这个想法是，您将每个字符串与您的基本字符串进行比较，并检查距离是否更小或更大。一个视觉示例：想象一个二维平面，其中有一个称为 x 的点。现在您有一个点列表，并希望根据它们到 x 的距离对它们进行排序。您所做的是，您通过计算从 a 和 b 到 x 的距离来比较列表中的两个点 a 和 b。如果 a 到 x 的距离较小，则 a 必须小于 b。

Hth

于 2013-07-21T13:45:01.387 回答
2

我根据您的需要创建了一个自定义比较器，这是代码

  • s是搜索字符串，所有匹配/紧密匹配的字符串都s应该首先出现
  • 我创建了一个Set<String> matches来存储搜索字符串的所有标记（单词）
  • 我创建了一个比较器c，它有一个方法getScore(String)，它基本上根据列表的给定字符串中找到的匹配数与搜索字符串给出一个分数
  • 如果该getScore方法返回0list 的两个字符串，或者两个字符串具有相同数量的匹配项，我将按照它们的自然顺序对它们进行排序。

  • 否则我通过返回 -ve 来提升匹配度最高的字符串

    List<String> l = new ArrayList<String>();
l.add("RedWall");
l.add("Beauty and the Beast 3");
l.add("BlueWall");
l.add("BeautyQueen I");
l.add("Beast of Rome II");
l.add("Beauty and the Beast 1");
l.add("Beast with The Beauty");
l.add("BlueWall 2");
l.add("BeautyQueen II");
l.add("Beast of Rome I");
l.add("Beauty and the Beast 2");

String s = "Beauty and the Beast"; //search string
final Set<String> matches = new HashSet<String>();
for(String tokens : s.split("\\s")) {
    matches.add(tokens.toLowerCase()); //convert the search string into tokens
}

Comparator<String> c = new Comparator<String>() {

    @Override
    public int compare(String o1, String o2) {
        int scoreDiff = getScore(o1) - getScore(o2);
        if((getScore(o1) == 0 && getScore(o2) == 0) || scoreDiff == 0) {
            return o1.compareTo(o2);
        }
        return - (getScore(o1) - getScore(o2));
    }

    private int getScore(String s) {
        int score = 0;
        for(String match : matches) {
            if(s.toLowerCase().contains(match)) {
                score++;
            }
        }
        return score;
    }
};
Collections.sort(l, c);
for(String ss : l) {
    System.out.println(ss);
}

这是输出

Beauty and the Beast 1
Beauty and the Beast 2
Beauty and the Beast 3
Beast with The Beauty
Beast of Rome I
Beast of Rome II
BeautyQueen I
BeautyQueen II
BlueWall
BlueWall 2
RedWall
于 2013-07-21T14:01:51.280 回答