一尘不染

Java中的字符串搜索算法

algorithm

我正在与大量数据进行字符串匹配。

编辑:我正在将包含在一个大列表中的单词与一些本体文本文件进行匹配。我从本体中获取每个文件,并在每个文件行的第三个String与列表中的任何单词之间搜索匹配项。

在检查我需要做的不是纯粹匹配(结果很差)这一事实时,我犯了一个错误,但是我需要一些松散的匹配函数,当该字符串包含在另一个字符串中时,该函数也将返回结果。

我用板蓝根做到了;
速度非常快而且效果很好,但是现在我想我的工作毫无用处,因为trie只返回完全匹配的内容。:/

  • 这样做的算法类型是字符串搜索算法?
  • 有人可以推荐一些他有经验的Java实现吗?

该算法应该是快速的,但不是最高优先级,会牺牲速度和复杂性。

我非常感谢所有建议/示例/解释/链接!

谢谢!


阅读 285

收藏
2020-07-28

共1个答案

一尘不染

您可能会发现后缀树很有用(它们在概念上与Tries类似)。

每个字符串都以^开头,以$结尾,并创建所有附加字符串的后缀树。空间使用量将为O(n),可能会比您尝试使用的空间差。

如果现在需要搜索字符串s,则可以在O(| s |)时间内轻松完成,就像trie一样,获得的匹配项将是子字符串匹配项(基本上,您将匹配某个字符串的后缀)。

抱歉,我没有方便的Java实现参考。

找到了一个有用的stackoverflow答案:通用后缀树Java实现

其中包含:http : //illya-keeplearning.blogspot.com/2009/04/suffix-
trees-java-ukkonens-algorithm.html

依次具有:源代码:http :
//illya.yolasite.com/resources/suffix-
tree.zip

2020-07-28