java是查找字符串中多个指针的最佳方法

Question

我正在用java设计一个解析器，用于在新闻文章中查找股票项目的名称

这篇文章的长度在500到2000字之间。库存物品的数量接近3000件

我认为这是在字符串中找到多个针的问题。我想知道解决这个问题的最佳算法或java库

我假设后缀数组是一个很好的解决方案

请让我知道，如果你知道的算法或一些提示

多谢各位

Answer 1

当所有字符串都是静态的时，后缀是一个很好的选择，也就是说，您应该提前知道文章以及项目的名称，并且它们不会改变。当文章不是静态的或者可能有很多文章需要处理时，Trie将是一个不错的选择。您可以基于库存项目的名称构建Trie，然后枚举文章中的每个位置。它的成本是O（Len（article）*项目名称的平均长度），考虑到您的输入大小，它应该足够有效

此外，您可以使用Aho–Corasick算法来避免枚举文章中的每个位置，并且查找文章中的所有库存项目只需花费O（文章长度）

Answer 2

在您的例子中，似乎可以将输入拆分为标记、单词，然后在非常有限的字典（库存项）中执行查找。 如果使用哈希进行查找，则需要计算单词的哈希值+哈希本身。假设是一个完美的散列函数，这是O（n），其中n是本文中的字符

so（简化）

  Set<String> items...

  String article = getArticle();

  Set<String> found = new HashSet<String>();

 for(String word : article.split(" ")) 
    if(items.contains(word)) 
       found.add(word)

Answer 3

如果我没弄错的话，你想在一个较长的文本中找到子字符串。在C#中，您只需使用子字符串之类的方法。不知道它们是否存在于java中。否则，我将选择Boyer–Moore–Horspool algorithm来搜索子字符串并获取它们在给定文本中的位置

Answer 4

使用String Tokenizer然后循环并比较生成的所有令牌