Java：在字符串中匹配短语

我有一个数据库和输入字符串中的短语列表（短语可能由一个或多个单词组成）。我需要找出哪些短语出现在输入字符串中。Java：在字符串中匹配短语

有没有一种在Java中执行这种匹配的有效方法？

2011-05-17 medvaržtis

你有一个短语或输入字符串的例子吗？可以使用java或SQL考虑许多解决方案 – VirtualTroll 2011-05-17 19:45:32

示例短语可以是“私募股权”和“软件”。我们假设输入字符串是“美国私募股权公司正在为英国软件集团准备每股425-450便士的出价，本周它显示它已收到与可能收购有关的询问。” 对于这两个短语，我需要得到关于它们在字符串中存在的正面答案。 – 2011-05-17 20:06:09

@medvaržtis：我可能会考虑像aho-corasick或后缀树这样的数据结构。有没有简单的解决方案在Java中也没有在sql – VirtualTroll 2011-05-17 20:29:48

快速黑客是：

构建基于组合的短语
一个正则表达式作一组，列出了至今为止还没有
反复运行find直到所有的短语有相匹配的短语被发现或输入结束时，从剩余词组中删除匹配以找到

这样，输入只被遍历一次，因为请提供您提供的短语数量。如果regexp编译器为多个备选方案生成高效的匹配器，则这应该会产生不错的性能。但是，这取决于您的短语和输入字符串以及Java正则表达式引擎的质量。

示例代码（测试，但没有进行优化或成型为适合的性能）：

public static boolean hasAllPhrasesInInput(List<String> phrases, String input) { 
    Set<String> phrasesToFind = new HashSet<String>(); 
    StringBuilder sb = new StringBuilder(); 
    for (String phrase : phrases) { 
     if (sb.length() > 0) { 
      sb.append('|'); 
     } 
     sb.append(Pattern.quote(phrase)); 
     phrasesToFind.add(phrase.toLowerCase()); 
    } 
    Pattern pattern = Pattern.compile(sb.toString(), Pattern.CASE_INSENSITIVE); 
    Matcher matcher = pattern.matcher(input); 
    while (matcher.find()) { 
     phrasesToFind.remove(matcher.group().toLowerCase()); 
     if (phrasesToFind.isEmpty()) { 
      return true; 
     } 
    } 
    return false; 
}

一些注意事项：

上面的代码将匹配短语词语的子字符串。如果只有完整的单词应该匹配，则需要向生成的正则表达式添加单词边界（“\ b”）。
如果某些短语可能是其他短语的子字符串，则必须修改该代码。
如果您需要匹配非ASCII文本，则应添加正则表达式选项Pattern.UNICODE_CASE，并使用合适的Locale调用toLowerCase(Locale)而不是toLowerCase()。

来源

2011-05-17 21:58:46 markusk

+1因为你写了一些冗长而内容丰富的麻烦。谢谢@markusk。 – Sid 2011-05-17 22:06:06

虽然这不是我需要解决的确切问题，但我明白了并实现了它。谢谢@markusk！ – 2011-05-18 21:06:32

乐意帮忙，@medvaržtis！ – markusk 2011-05-19 06:22:53

这是一个使用java的解决方案。由于你没有指定有关字符串任何你使用我认为一个通用的例子

Pattern p = Pattern.compile("cat"); 
     // Create a matcher with an input string 
Matcher m = p.matcher("one cat," +" two cats in the yard"); 
boolean b = m.matches(); // Should return true

希望帮助

参考：http://java.sun.com/developer/technicalArticles/releases/1.4regex/

来源

2011-05-17 19:49:41 Shaunak

嗯，我认为它应该是m.find（）而不是m.matches。但是，我不认为这是一个合适的解决方案，以及String.contains（）。我在我的数据库中有大约1000个短语。所以，对于每一个短语我都必须再次调用这些方法。我认为调用String.contains（）或Matcher.find（）1000次效率不高。 – 2011-05-17 20:24:08

我不认为你会有使用String.contains（）的性能问题。将1000个匹配的单词从数据库中提取出来很可能比循环遍历它们并将它们与字符串进行比较要慢。我用1000个搜索词和string.contains尝试了你的短语，它花了1ms。 – ScArcher2 2011-05-17 21:45:42

sql = "SELECT phrase " + 
    " FROM phrases " + 
    " WHERE phrase LIKE $1";  
PreparedStatement pstmt = conn.prepareStatement (sql); 
// probably repeated, if more than one input: 
pstmt.setString (1, "%" + input + "%"); 
ResultSet rs = pstmt.executeQuery();

已准备语句进行检查，以适合数据库，并且重复调用速度更快，所以如果您有多个输入，它应该仍然是快速的，循环执行。

当然，您可以将所有的短语加载到RAM中，放入地图中。准备工作缓慢，如果您有多个调用，而不仅仅是一个输入，则速度可能会更快。但是数据库对于搜索通常效率很高。

来源

2011-05-17 20:44:54

根据常见的起点，您可以将数据库中的搜索短语组织到树中。比你可以分析你的字符串逐字符试图匹配到该树的节点。

来源

2011-05-17 20:51:24 Olaf

糟糕！我刚刚意识到@Amine在评论中提到了这个算法。 – Olaf 2011-05-17 21:14:35

Java：在字符串中匹配短语

回答

相关问题