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

Question

我有一个 ArrayList，其中包含大约 1000 个字符串。我想根据与外部给定字符串的相似性对该列表进行排序。与弦非常接近的弦将出现在顶部。

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

我的数组列表包含如下字符串:

红墙
美女与野兽3
蓝墙
选美皇后I
罗马野兽II
美女与野兽1
野兽与美女
蓝墙2
选美皇后II
罗马野兽I
美女与野兽2
...

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

美女与野兽1
美女与野兽2
美女与野兽3
野兽与美女
选美皇后I
选美皇后II
罗马野兽I
罗马野兽II
蓝墙
蓝墙2
红墙

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

我正在寻找一些算法，它实际上可以帮助我在 Java 中实现这个任务。

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

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

Answer 1

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

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

• 否则我将通过返回 -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