广义后缀树Java实现

Question

15

我正在寻找一种Java实现的广义后缀树（GST），具有以下特点：

在从1000个字符串中创建GST之后，我想找出其中有多少个字符串包含某个其他字符串's'。

搜索必须非常快，因为我需要在约100,000个平均长度为10个字符的候选字符串上应用搜索。

- user119746

嗨，我想知道你最终使用了哪个解决方案，我也遇到了同样的问题！！！ - Julia

请查看以下链接：https://dev59.com/1mox5IYBdhLWcg3wFAU1#9513423。这是有关Ukkonen后缀树算法的内容，供您参考。 - YAMM

5个回答

4

我在Java中创建了一个后缀树，可以让您轻松添加自己的搜索功能和其他匹配算法。我的博客文章Java中的后缀树提供了概述以及下载最新版本的说明。我的Java实现基于Mark Nelson的使用后缀树进行快速字符串搜索文章。 2023-04-01更新 上述后缀树实现的库现在可以在GitHub上的globalmentor-base存储库中的globalmentor-core子项目的com.globalmentor.collections包中找到。

该库的最新版本可使用Maven Central的构件坐标com.globalmentor:globalmentor-core获取。

- Garret Wilson

这篇博客文章很有信息量，但源代码当前不可用（2015年8月），因为它指向 https://svn.globalmentor.com/java/trunk/globalmentor-core/，需要密码才能访问。 - codeDr

我正在尽力将我们的代码库从Subversion转换到Git，并再次公开。这应该会在一两周内完成。如果到时候还没有可用，请随时联系我。干杯。 - Garret Wilson

源代码现在可以通过Git和Maven Central获取。我已经更新了上面的答案，提供了新的位置。 - Garret Wilson

1

感谢 @trincot 指出这一点。我已经更新了这里和博客文章中的链接。 - Garret Wilson

3

- Dr. Max Völkel

1

如果这只是 Mark Nelson 的直接移植，那么它不是一个广义后缀树，只是一个后缀树。 - HorseloverFat

好的，我重新措辞了我的回答。谢谢。 - Dr. Max Völkel

2

你可以在这里找到一个Java实现的广义后缀树。

我尽可能详细地记录了它，因此您可能会发现它很有用。

- abahgat

0

这是我的SuffixTree实现： https://github.com/losvald/sglj/blob/master/src/main/java/org/sglj/util/PATTrie.java 除其他功能外，它还支持在节点中存储任意数据，并查找与前缀相关联的值集合。

- eold

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- HMM · Accepted Answer

尝试使用语义发现工具包。它在text/src/java/org/sd/text/radixtree上有一个实现。