根据提供的关键字对文本进行排序

Question

我有一组字符串和一组关键字。

例如字符串1:据报道，甲骨文和三星电子已经建立了一种新的合作伙伴关系，通过这种合作，他们将共同提供移动云服务。在上周四的一次会议上，甲骨文公司的联合首席执行官马克赫德和三星电子移动业务负责人申钟坤举行了会谈。

字符串2:这是一些随机字符串。

关键词:甲骨文，三星

函数应该返回字符串1作为具有最高秩的函数。我可以搜索每个字符串的每个关键字，但这将花费太多的时间，因为将有大量的字符串和一组巨大的关键字。

Answer 1

创建一个数据结构，将出现在任何字符串中的每个术语映射到它所显示的所有字符串。

Map<String,List<Integer>> keyword2stringId;

如果一个字符串多次包含相同的关键字，您可以简单地多次将它添加到List中，或者--如果您愿意--使用一个稍微不同的映射，它允许您保持计数：

Map<String,List<Pair<Integer,Integer>>> keyword2pair; // pair = id + count

然后，对于每个关键字，您可以查找相关字符串并找到重叠程度最高的字符串，例如：

// count the occurrences of all keywords in the different strings
int[] counts = new int[strings.length];
for (String keyword : keywords) {
     for (Integer index : keyword2stringId.get(keyword)) {
         if (index != null) {
             counts[index]++;
         }
     }
}

// find the string that has the highest number of keywords
int maxCount = 0; 
int maxIndex = -1;
for (int i = 0; i < counts.length; i++) {
    if (counts[i] > maxCount) {
        maxCount = counts[i];
        maxIndex = i;
    }
}

// return the highest ranked string or 
// 'null' if no matching document was found
if (maxIndex == -1) {
    return null;
} else {
    return strings[maxIndex];
}

这种方法的优点是您可以离线计算您的地图(即只计算一次)，然后再一次又一次地用于不同的查询。

Answer 2

看起来你应该尝试一些搜索引擎或搜索库，比如卢塞尼或索尔。

Lucene Core，我们的旗舰子项目，提供基于Java的索引和搜索技术，以及拼写检查、点击突出显示和高级分析/标记化功能。 Solr是建立在Apache™上的流行、快速、开放源码的企业搜索平台。

这两种东西都支持你做你需要做的事情--搜索一些关键字并对它们进行排序。

Answer 3

这个程序不能少于O(n)复杂度，也就是说，您必须用每个关键字检查字符串中的每个单词。

现在，您唯一能做的就是一次对每个字符串执行检查：

public int getRank(String string, String[] keyword) {
    int rank = 0;
    for (String word : string.split(" "))
        for (String key : keyword)
            if (word.equals(key))
                rank++;
    return rank;
}

在这个简单的例子中，rank是在字符串中每次出现关键字时增加的int。然后为每个字符串填充一个级别数组：

String[] strings = new String[]{"...", "...", "...", "...", ...};
String[] keyword = new String[]{"...", "...", "...", "...", ...};

int[] ranks = new int[stringsNumber];
for (int i = 0; i < stringsNumber; i++)
    ranks[i] = getRank(strings[i], keyword);