我正在研究在许多短文本行(草堆)中找到非常短的子字符串(模式、指针)。然而，我不太确定在天真、暴力的方法之外应该使用哪种方法。
背景：我正在做一个有趣的附带项目，我收到多个用户的短信聊天日志(从2000-15000行文本到2-50个用户)，我想根据我想出的预定单词在聊天日志中找到所有不同的模式匹配。到目前为止，我正在寻找大约1600种图案，但我可能会寻找更多。
例如，我想找出在一条普通短信日志中使用的与食物相关的单词的数量，如"汉堡包"、"披萨"、"可乐"、"午餐"、"晚餐"、"餐厅"、"麦当劳"。虽然我给出了英语示例，但我的程序实际上会使用韩语。这些指定的单词中的每一个都有自己的分数，我将其分别作为关键字和值放在哈希图中。然后，我展示了与食物相关的单词的得分最高者，以及这些用户在食物单词中使用频率最高的单词。
我目前的方法是通过空格来消除每一行文本，并使用包含模式的包含方法(使用indexOf方法和天真子串搜索算法)来处理草堆中的每一个单词。
wordFromInput.contains(wordFromPattern);
举个例子，有17个用户在聊天，13000行文本和1600个模式，我发现用这种方法整个程序需要12-13秒。在我正在开发的安卓应用程序上，处理时间花了2分30秒，太慢了。
最初，我试图使用哈希图，只获取模式，而不是在ArrayList中搜索它，但后来我意识到这是…
哈希表不可能
我正试图用一个子字符串做什么。
我浏览了Stackoverflow，发现了很多有用的相关问题，比如这两个：
1和2。我更熟悉各种字符串算法(Boyer-Moore、KMP等)
当时我最初认为，对于我的情况来说，天真的方法当然是最糟糕的算法类型，但发现这个问题后，我意识到我的情况(短模式、短文本)实际上可能使用天真的方法更有效。但我想知道是否有什么是我完全忽略了的。
如果有人想更具体地了解我的问题，下面是我的代码片段。
虽然我删除了大部分代码以简化它，但我用来实际匹配子字符串的主要方法在matchWords()方法中。
我知道这是非常丑陋和糟糕的代码(5代表循环…)，所以如果对此有任何建议，我也很乐意听到。
所以要清理一下：
- 聊天日志中的文本行(2000-10000+)，干草堆
- 1600多种图案，针
- 大部分使用朝鲜语字符，尽管也包括一些英语
- 粗暴的天真方法太慢了，但考虑到简短的模式和文本的性质，是否还有其他选择，即使有，它们是否实用
我只是想对我的思考过程提供一些意见，可能还有一些一般性的建议。但另外，如果可能的话，我希望对特定的算法或方法提出一些具体的建议。
您可以用Trie替换哈希表。
使用空格将文本行拆分为多个单词。然后检查单词是否在Trie中。如果它在Trie中，则更新与该单词相关联的计数器。理想情况下，计数器将集成到Trie中。
这个表达式是O(C)，其中C是文本中的字符数。您不太可能避免至少检查一次每个字符。因此，这种方法应该是尽可能好的，至少在大O.方面是这样
然而，听起来你可能不想列出你正在搜索的所有可能的单词。因此，你可能想简单地使用你可以从所有的单词中构建一个计数Trie。如果没有其他东西的话，这可能会让你使用的任何模式匹配算法变得更容易。尽管如此，它可能需要对Trie进行一些修改。
您所描述的内容听起来像是Aho-Corasick字符串匹配算法的一个极好的用例。该算法在源字符串中查找一组模式字符串的所有匹配项，并在线性时间内(加上报告匹配项的时间)进行查找。如果你有一组固定的字符串要搜索，你可以对模式进行线性预处理，以快速搜索所有匹配项。
这里提供了Aho-Corasick的Java实现。我还没有试过，但这可能是一场很好的比赛。
希望这能有所帮助！
我很确定string.contains已经得到了高度优化，所以用其他东西替换它对你没有多大好处。
因此，我怀疑，方法是而不是在聊天词中查找每一个银行单词，而是一次进行多次比较。
第一种方法是创建一个巨大的正则表达式来匹配所有的银行单词。编译它并希望正则表达式包足够高效(很可能是这样)。您将有一个相当长的设置阶段(regex编译)，但匹配应该快得多。
您可以为需要匹配的单词建立索引，并在处理这些单词时对其进行计数。如果你可以使用HashMap来查找每个单词的模式，那么成本将是O(n * m)
您可以对所有可能的单词使用HashMap，然后可以稍后对这些单词进行剖析。
例如，如果你需要匹配红色和苹果，你可以组合的总和
redapple = 1
applered = 0
red = 10
apple = 15
这意味着红色实际上是11(10+1)，苹果是16(15+1)
我不懂韩语，所以我想用同样的策略来修补韩语中的字符串不一定像用英语一样可行，但也许可以用你的韩语知识来应用伪代码中的这种策略，使其发挥作用。(Java当然仍然是一样的，但例如，在朝鲜语中，字母"ough"仍然很有可能是连续的吗？甚至有字母"ouough"吗？但话虽如此，希望这一原则可以应用于
我会使用String.toCharArray来创建一个二维数组(如果需要可变大小，也可以使用ArrayList)。
if (first letter of word matches keyword's first letter)//we have a candidate
skip to last letter of the current word //see comment below
if(last letter of word matches keyword's last letter)//strong candidate
iterate backwards to start+1 checking remainder of letters
我建议跳到最后一个字母的原因是，从统计数据来看，一个单词前两个字母的"辅音、元音"非常高，尤其是名词，因为任何食物都是名词(你给出的几乎所有关键词示例都与辅音、元音的结构相匹配)，所以名词将由很多关键词组成。由于只有5个元音(加上y)，第二个字母"i"出现在关键词"pizza"中的可能性本来就很高，但在那之后，这个词仍然很有可能不匹配。
然而，如果你知道第一个字母和最后一个字母匹配，那么你可能有一个更强的候选者，然后可以反向迭代。我认为，对于更大的数据集，这将比按顺序检查字母更快地淘汰候选人。基本上，你会让太多的假候选者通过第二次迭代，从而增加你的整体条件运算。这听起来可能很小，但在这样的项目中有很多重复，所以微观优化会很快积累起来。
如果这种方法可以应用于一种可能在结构上与英语非常不同的语言中(不过我在这里是出于无知)，那么我认为它可能会为您提供一些效率，无论您是通过迭代char数组、使用扫描仪还是任何其他构造来实现这一点。
诀窍是要意识到，如果你可以将搜索的字符串描述为正则表达式，那么根据定义，你也可以用状态机来描述它。
在你的消息中的每个字符处，为你的1600个模式中的每一个启动一个状态机，并将该字符传递给它。这听起来很可怕，但相信我，大多数模式都会立即终止，所以你并没有真正做大量的工作。请记住，状态机通常可以在每一步使用简单的开关/事例或ch == s.charAt进行编码，因此它们在轻量级方面接近极限。
很明显，当你的一台搜索机在搜索结束时终止时，你知道该怎么办。任何在完全匹配之前终止的都可以立即丢弃。
private static class Matcher {
private final int where;
private final String s;
private int i = 0;
public Matcher ( String s, int where ) {
this.s = s;
this.where = where;
}
public boolean match(char ch) {
return s.charAt(i++) == ch;
}
public int matched() {
return i == s.length() ? where: -1;
}
}
// Words I am looking for.
String[] watchFor = new String[] {"flies", "like", "arrow", "banana", "a"};
// Test string to search.
String test = "Time flies like an arrow, fruit flies like a banana";
public void test() {
// Use a LinkedList because it is O(1) to remove anywhere.
List<Matcher> matchers = new LinkedList<> ();
int pos = 0;
for ( char c : test.toCharArray()) {
// Fire off all of the matchers at this point.
for ( String s : watchFor ) {
matchers.add(new Matcher(s, pos));
}
// Discard all matchers that fail here.
for ( Iterator<Matcher> i = matchers.iterator(); i.hasNext(); ) {
Matcher m = i.next();
// Should it be removed?
boolean remove = !m.match(c);
if ( !remove ) {
// Still matches! Is it complete?
int matched = m.matched();
if ( matched >= 0 ) {
// Todo - Should use getters.
System.out.println(" "+m.s +" found at "+m.where+" active matchers "+matchers.size());
// Complete!
remove = true;
}
}
// Remove it where necessary.
if ( remove ) {
i.remove();
}
}
// Step pos to keep track.
pos += 1;
}
}
打印
flies found at 5 active matchers 6
like found at 11 active matchers 6
a found at 16 active matchers 2
a found at 19 active matchers 2
arrow found at 19 active matchers 6
flies found at 32 active matchers 6
like found at 38 active matchers 6
a found at 43 active matchers 2
a found at 46 active matchers 3
a found at 48 active matchers 3
banana found at 45 active matchers 6
a found at 50 active matchers 2
有几个简单的优化。通过一些简单的预处理，最明显的是使用当前字符来确定哪些匹配器可能适用。
这是一个非常宽泛的问题，所以我不想谈太多细节，但大致来说：
使用类似宽lemmatizer的东西对干草堆进行预处理，通过注意其中所有单词涵盖的主题来创建"仅主题词"版本的消息。例如，任何出现"汉堡包"、"披萨"、"可乐"、"午餐"、"晚餐"、"餐厅"或"麦当劳"的情况都会导致为该消息收集"主题"单词"食物"。有些词可能有多个主题，例如"麦当劳"可能在主题"食品"one_answers"商业"中。大多数单词都没有任何主题。
在这个过程之后，您将得到仅由"主题"单词组成的干草堆。然后创建一个Map<String, Set<Integer>>，并用主题词和包含该主题词的聊天消息ID集填充它。这是主题词到包含它的聊天消息的反向索引。
查找包含所有n个单词的所有文档的运行时代码是琐碎且超快速的-接近O(#terms)：
private Map<String, Set<Integer>> index; // pre-populated
Set<Integer> search(String... topics) {
Set<Integer> results = null;
for (String topic : topics) {
Set<Integer> hits = index.get(topic);
if (hits == null)
return Collections.emptySet();
if (results == null)
results = new HashSet<Integer>(hits);
else
results.retainAll(hits);
if (results.isEmpty())
return Collections.emptySet(); // exit early
}
return results;
}
这将在O(1)附近执行，和告诉您哪些消息共享所有搜索词。如果您只想要这个数字，请使用返回的Set的琐碎size()。