Java indexOf(强力方法)对我或其他一些子串算法更实用吗？

Question

我正在寻找很多短文本(haystack)中很短的子串(模式,针).但是,我不太确定在天真的暴力方法之外使用哪种方法.

背景:我正在做一个有趣的侧面项目,我收到多个用户的短信聊天记录(2000-15000行文本和2-50个用户),我想在聊天中找到所有各种模式匹配根据我提出的预定单词记录日志.到目前为止,我有大约1600种模式,我正在寻找,但我可能会寻找更多.

因此,例如,我想找到在平均文本消息日志中使用的与食物相关的单词的数量,例如"汉堡包","披萨","可乐","午餐","晚餐","餐馆","麦当劳".虽然我给出了英语示例,但实际上我将使用韩语作为我的程序.这些指定单词中的每一个都有各自的分数,我将其分别作为键和值放在哈希映射中.然后,我展示了食物相关单词的最佳得分者以及这些用户用于食物单词的最常用单词.

我目前的方法是通过空格消除每行文本,并通过使用haystack包含模式的contains方法(使用indexOf方法和朴素子串搜索算法)处理大海捞针中的每个单词.

wordFromInput.contains(wordFromPattern);

举一个例子,聊天中有17个用户,13000行文本和1600个模式,我发现这个方法整个程序用了12-13秒.在我正在开发的Android应用程序上,处理需要2分30秒,这太慢了.

最初,我尝试使用哈希映射并仅仅获取模式而不是在ArrayList中搜索它,但我意识到这是......

哈希表不可能

我试图用子串做什么.

我查看了Stackoverflow,发现了很多有用的相关问题,比如这两个:

1和2.我对各种字符串算法(Boyer Moore,KMP等)比较熟悉

我最初认为天真的方法当然是我案例中最糟糕的算法类型,但是在发现这个问题后,我意识到我的情况(简短模式,短文本),实际上可能对天真更有效方法.但我想知道是否有一些我完全忽视的东西.

以下是我的代码片段,但是如果有人想要更具体地看到我的问题.

虽然我删除了大部分代码以简化它,但我使用实际匹配子字符串的主要方法是matchWords()方法.

我知道这是非常丑陋和糟糕的代码(5代表循环...),所以如果有任何建议,我也很高兴听到它.

所以要清理它:

• 来自聊天记录的文本行(2000-10,000 +),haystack
• 1600多种图案,针
• 虽然包括一些英语,但主要使用韩语字符
• 蛮力天真的方法简直太慢,但争论是否有其他替代方案,即使有,但鉴于短模式和文本的性质,它们是否实用.

我只想在思考过程中得到一些意见,可能还有一些一般的建议.但另外,如果可行,我想对特定算法或方法提出一些具体建议.

Answer 1

我很确定string.contains它已经高度优化了，所以用其他东西替换它不会给你带来很多好处。

因此，我怀疑，正确的方法不是寻找聊天单词中的每一个银行单词，而是一次进行多次比较。

第一种方法是创建一个巨大的正则表达式来匹配您的所有银行单词。编译它并希望正则表达式包足够高效（很可能是这样）。您将有一个相当漫长的设置阶段（正则表达式编译），但匹配应该要快得多。