我正在研究如何在许多短文本行(haystack)中找到非常短的子字符串(pattern、needle)。但是，我不太确定在幼稚的蛮力方法之外使用哪种方法。
背景:我正在做一个有趣的副项目，我收到多个用户的短信聊天记录(从 2000-15000 行文本和 2-50 个用户的任何地方)，我想找到所有各种模式匹配根据我想出的预定词在聊天记录中。到目前为止，我正在寻找大约 1600 种模式，但我可能会寻找更多。
例如，我想找出平均短信日志中使用的食物相关词的数量，例如“汉堡包”、“比萨饼”、“可乐”、“午餐”、“晚餐”、“餐厅” 》、《麦当劳》。虽然我给出了英语示例，但实际上我会在我的程序中使用韩语。这些指定的单词中的每一个都会有自己的分数，我将其分别作为键和值放入 HashMap 中。然后，我会显示与食物相关的词的最高得分者以及这些用户对食物词使用最频繁的词。
我目前的方法是通过空格消除每一行文本，并使用 haystack 包含模式的 contains 方法(使用 indexOf 方法和朴素的子字符串搜索算法)处理 haystack 中的每个单词。
wordFromInput.contains(wordFromPattern);
举个例子，有 17 个用户在聊天，13000 行文本和 1600 个模式，我发现使用这种方法整个程序需要 12-13 秒。在我正在开发的 Android 应用程序上，处理时间为 2 分 30 秒，这太慢了。
最初，我尝试使用 HashMap 并仅获取模式而不是在 ArrayList 中搜索它，但后来我意识到那是...
对于我试图用子字符串做的事情。
我浏览了 Stackoverflow，发现了很多有用的相关问题，例如这两个:
1和 2 .我对各种字符串算法(Boyer Moore、KMP 等)比较熟悉
当时我最初认为朴素方法当然是对我的情况最糟糕的算法类型，但发现 this question ，我已经意识到我的案例(短模式，短文本)实际上可能使用天真的方法更有效。但我想知道是否有什么我完全忽略了。
这是一个snippet of my code尽管如果有人想更具体地了解我的问题。
虽然我删除了大部分代码以简化它，但我用来实际匹配子字符串的主要方法是 matchWords() 方法。
我知道那是非常丑陋和糟糕的代码(5 个 for 循环...)，所以如果对此有任何建议，我也很高兴听到。
所以要清理它:
我只需要一些关于我的思考过程的意见，可能还有一些一般性建议。但另外，如果可能的话，我想要一些针对特定算法或方法的具体建议。
最佳答案
您可以 replace the hashtable with a Trie .
将文本行拆分为单词，使用空格分隔单词。然后检查单词是否在 Trie 中。如果它在 Trie 中，则更新与该词关联的计数器。理想情况下，计数器将集成到 Trie 中。
这个方法是 O(C)，其中 C 是文本中的字符数。您不太可能避免至少检查每个字符一次。因此，至少在大 O 方面，这种方法应该尽可能好。
但是，听起来您可能不想列出所有可能要搜索的词。因此，您可能想简单地使用您可以从所有单词构建一个计数 Trie。如果不出意外，这可能会使您使用的任何模式匹配算法变得更容易。虽然，它可能需要对 Trie 进行一些修改。
关于java - Java indexOf(蛮力法)对我或其他一些子串算法会更实用吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22120747/
我试图在一个项目中使用rake，如果我把所有东西都放到Rakefile中，它会很大并且很难读取/找到东西，所以我试着将每个命名空间放在lib/rake中它自己的文件中，我添加了这个到我的rake文件的顶部:Dir['#{File.dirname(__FILE__)}/lib/rake/*.rake'].map{|f|requiref}它加载文件没问题，但没有任务。我现在只有一个.rake文件作为测试，名为“servers.rake”，它看起来像这样:namespace:serverdotask:testdoputs"test"endend所以当我运行rakeserver:testid时
我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚
我想用ruby编写一个小的命令行实用程序并将其作为gem分发。我知道安装后，Guard、Sass和Thor等某些gem可以从命令行自行运行。为了让gem像二进制文件一样可用，我需要在我的gemspec中指定什么。 最佳答案 Gem::Specification.newdo|s|...s.executable='name_of_executable'...endhttp://docs.rubygems.org/read/chapter/20 关于ruby-在Ruby中编写命令行实用程序
我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/
我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www
我需要一些关于TDD概念的帮助。假设我有以下代码defexecute(command)casecommandwhen"c"create_new_characterwhen"i"display_inventoryendenddefcreate_new_character#dostufftocreatenewcharacterenddefdisplay_inventory#dostufftodisplayinventoryend现在我不确定要为什么编写单元测试。如果我为execute方法编写单元测试，那不是几乎涵盖了我对create_new_character和display_invent
我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我
什么是ruby的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht
目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非
这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/