如何对包含1000多个不同字符串的ArrayList根据与另一个给定字符串的相似性进行排序

Question

我有一个包含大约1000个字符串的ArrayList。我想根据与外部给定字符串的相似度对此列表进行排序。与字符串非常接近的字符串将位于顶部。

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

我的Arraylist包含如下字符串：

RedWall

美女与野兽3

BlueWall

BeautyQueen i

罗马野兽2

美女与野兽1

美丽的野兽

BlueWall 2

BeautyQueen II

罗马野兽一号

美女与野兽2

..。

因此，在对此数组列表进行排序后，它应该类似于..

美女与野兽1

美女与野兽2

美女与野兽3

美丽的野兽

BeautyQueen i

BeautyQueen II

罗马野兽一号

罗马野兽2

BlueWall

BlueWall 2

RedWall

像这样的东西..我不知道《美女与野兽3》之后的剧情会怎样。但它应该选择在开头具有完全相同字符串的字符串。

我正在寻找一些算法，可以真正帮助我在Java中实现这项任务。

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

Answer 1

根据levenstein distance http://en.wikipedia.org/wiki/Levenshtein_distance进行排序。通过此距离，您可以定义字符串之间的距离。在比较器中实现这一点。

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

从sanbhat中获取代码，并将他的评分函数替换为与我发布的维基百科之间的levenstein距离。

其想法是，将每个字符串与您的基本字符串进行比较，并检查距离是更小还是更大。一个可视化的例子:想象一个二维平面，有一个叫做x的点。现在你有一个点列表，想要根据它们到x的距离对它们进行排序。你要做的是，通过计算a和b到x的距离来比较列表中的两个点a和b。如果a到x的距离较小，那么a肯定比b小。

Hth

Answer 2

我已经根据您的需要创建了一个自定义比较器，代码如下

• s是搜索字符串，所有与s匹配/紧密匹配的字符串应该首先出现
• 我已经创建了一个Set<String> matches来存储搜索字符串的所有标记(单词)
• 我已经创建了一个比较器c，它具有一个方法getScore(String)，它基本上根据在列表的给定字符串中找到的与搜索字符串<代码>H213<代码>H114的匹配数量，给出一个分数<代码>E218如果<代码>D15方法为两个列表字符串返回<代码>D16，或者如果两个字符串都具有相同数量的匹配项<代码>E218，我在他们的自然ordering.
• else中对它们进行排序，我正在通过返回-ve来提升具有最高匹配度的字符串

列表l=新的ArrayList()；l.add("RedWall")；l.add(“美女与野兽3")；l.add("BlueWall")；l.add("BeautyQueen I")；l.add(”罗马野兽2")；l.add(“美女与野兽1")；l.add(”美女与野兽2")；l.add("BlueWall 2“)；l.add("BeautyQueen II")；l.add(”罗马野兽一号“)；l.add(”美女与野兽2“)；字符串s=“美女与野兽”；//搜索字符串最终设置matches = new HashSet()；for(字符串标记: s.split("\s")) { matches.add(tokens.toLowerCase())；//将搜索字符串转换为标记}比较器c= new比较器(){ @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 getScore= 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