代码之家 › 专栏 › 技术社区 › Julia

Java中的字符串搜索算法

string-search string-matching matching algorithm java

2

Julia · 技术社区 · 16 年前

我正在做大量数据的字符串匹配。

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

我犯了一个错误,因为我需要做的不是纯粹的匹配(结果很差),但是我需要一些更宽松的匹配函数,当字符串包含在另一个字符串中时,它也会返回结果。

我做这个的时候 Radix Trie 很快,很好用,但现在我想我的工作没用,因为trie只返回精确的匹配。:

该算法应该很快,但不是最高优先级,这将与速度和复杂性相结合。

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

谢谢您!

5 回复 | 直到 13 年前

1

3

Community Mohan Dere 9 年前

你可能会发现 Suffix Trees 有用(它们在概念上与尝试相似)。

每个字符串前加^并以$结尾,然后创建所有附加字符串的后缀树。空间使用将是O(N),可能会比您为特里亚所拥有的更糟。

如果现在需要搜索字符串s,可以很容易地在o(s_)时间内搜索,就像trie一样,得到的匹配将是子字符串匹配(基本上,您将匹配一些字符串的后缀)。

~~对不起,我没有对Java实现的引用。~~

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

2

1

chimeracoder 16 年前

正则表达式绝对是您的最佳选择。它们编写起来可能有点混乱,但它们是唯一一种可以在没有不可理解的if/else或switch语句系列的情况下进行松散匹配的方法。

另外,他们会比替代方案快得多。

3

1

Wajdy Essam 16 年前

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

另一个最好的解决方案是使用多模式搜索算法,如: AhoâCorasick string matching algorithm

4

0

Xzhsh 16 年前

我不完全确定我是否正确理解了这个问题,但听起来正则表达式可以解决这个问题。

5

0

Mukeshkoshym 13 年前

为什么不使用Java中的索引方法呢?根据内存的可用性,读取内容。执行indexof并获取所需的所有行。加载下一组内容。

如果从文件读取,则使用NIO流。

可能是想法不好,但我相信Java。它将使用最佳算法。

最好使用正则表达式。