java - Java中的字符串搜索算法

Question

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

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

我在监督我需要做的不是纯匹配（结果很差）这一事实时犯了一个错误，但我需要一些更松散的匹配函数，当字符串包含在另一个字符串中时它也会返回结果。

我用Radix Trie做到了这一点；它非常快并且效果很好，但现在我想我的工作没用，因为 trie 只返回完全匹配。：/

该算法应该很快，但不是最优先考虑的，会兼顾速度和复杂性。

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

谢谢！

score 4 · Accepted Answer

您可能会发现后缀树很有用（它们在概念上与 Tries 相似）。

每个字符串，您以 ^ 开头并以 $ 结尾，并创建一个包含所有附加字符串的后缀树。空间使用量将是 O(n)，并且可能比您使用的 trie 更糟。

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

~~抱歉，我没有方便地引用 Java 实现。~~

找到了一个有用的 stackoverflow 答案：Generalized Suffix Tree Java Implementation

score 2 · Accepted Answer

您可以使用BM 算法在文本文件中搜索单个模式，并对列表中的所有模式重复此算法。

另一个最佳解决方案是使用多模式搜索算法，例如：Aho–Corasick 字符串匹配算法

score 1 · Accepted Answer

正则表达式绝对是你最好的选择。它们写起来可能有点乱，但它们是唯一能让你进行更松散匹配的方法，而无需一系列难以理解的 if/else 或 switch 语句。

另外，它们将比替代方案快得多。

score 0 · Accepted Answer

为什么不使用 java 中的 indexOf 方法。根据内存的可用性，阅读内容。执行 indexOf 并获取您需要的所有行。加载下一组内容。

如果从文件中读取，请使用 nio 流。

可能是这个想法不好，但我相信java。它将使用最好的算法。

如果你使用正则表达式会更好。

score 0 · Accepted Answer

我不完全确定我是否正确理解了这个问题，但听起来正则表达式可以完成这项工作

5 回答 5