问题标签 [suffix-array]

这是在python中从字符串构建后缀数组的一种非常简单的方法：

但是，“content[a:]”会复制内容，当内容变大时效率会非常低。所以我想知道是否有一种方法可以比较两个子字符串而不必复制它们。我尝试使用内置缓冲区，但没有奏效。

Does anyone have any suggestions about where I can find a C# implementation for suffix arrays? I'd prefer not to reinvent the wheel...

我正在寻找一种有效的 n 阶马尔可夫链方法来生成给定一组示例文本的随机文本字符串。我目前有一个使用多层地图的 Java 实现，但它很笨重。后缀数组非常适合我的需求，但我不清楚这是否可以在 Java 中有效实现。

在 CI 中可能会执行以下操作：

这在 Java 中变得很棘手，因为我必须获取 的子字符串exampleText，或者变成suffixArray索引数组或其他东西。

对 Java 中的一个好的方法有什么建议吗？

我在http://portal.acm.org/citation.cfm?id=1813708中实现了利用后缀数组查找最长公共子串的算法。该算法涉及为字符串构造一个后缀数组，该数组是一组给定字符串与称为哨兵的字符串分隔符的串联。例如，如果给定字符串 a、b 和 c，则会创建一个新字符串 d，它是 a$1b$2c$3，其中 $1、$2、$3 是标记每个字符串结尾的标记字符。标记字符必须是唯一的，并且在字典顺序上少于 a、b 和 c 中的所有其他字符。

我的问题围绕 Python 中哨兵字符的表示展开。如果 a、b 和 c 是 ASCII 字符串，我想我可能需要将这些字符串转换为 UTF-8 并将它们的范围从 0-127 转移到更高的范围，以便有可用的字符在字典上少于那些在字符串。如果这看起来合理，那么在 Python 中重新映射字符以使其范围为 N-127+N 的最有效机制是什么，其中 N 是提供的字符串数？

我正在阅读有关在字符串中查找子字符串的后缀数组方法，请参见（http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845），例如

其中 SuffixArray 是后缀数组的一个实现，而 find_substring 是一种搜索子字符串开始位置的方法。

我的问题是如何在允许子字符串中有给定数量的不匹配的同时实现此搜索？例如，

其中不匹配可被视为错误阈值。在这种情况下，它应该能够匹配“aza”并返回“aza”子字符串的起始位置。另请注意，“abr”有 2 个不匹配！所以应该先退货。理想情况下，该方法应该返回所有可能的事件。

有任何想法吗？或解决此类问题的其他方法？谢谢

我正在阅读 Burrows 和 Wheeler 论文中的块排序算法。这是算法的一个步骤：

假设 S=abracadabra

初始化一个包含 N 个单词 W[0, ... , N - 1] 的数组 W，使得 W[i] 包含字符 S'[i, ... , i + k - 1] 的排列，以便整数比较这些词与 k 字符串的字典比较一致。将字符打包成单词有两个好处：它允许使用对齐的内存访问一次比较两个前缀 k 字节，并且它允许消除许多缓慢的情况

（注意：S'是原始的，附加S了 kEOF个字符，k 是适合机器字的字符数（我在 32 位机器中，所以k=4）

如我错了请纠正我：

然后，算法说你必须通过索引S数组来对（命名为 V）的后缀数组进行排序。W

我不完全理解如何通过索引来对后缀进行排序W。例如：在排序的某个时刻，假设你有两个后缀，i和j，你必须比较它们。由于您正在索引W，因此您当时正在检查 4 个字符。
假设它们具有相同的前 4 个字符。然后，您必须检查每个后缀的下一个 4 个字符，并通过从W. 这是正确的吗？这种“将字符打包成单词”真的可以加快速度吗？

我正在尝试实现块排序。这是来自 Burrows Wheeler 的论文。

（在此步骤之前，您创建一个 S 的 V 后缀数组）

Q4。[基数排序]
对 V 的元素进行排序，使用每个后缀的前两个字符作为排序键。这可以使用基数排序有效地完成。

所以我知道您正在使用基数排序对后缀进行排序。
这应该如何更新数组 V？只有在基数排序完成后，我才能知道后缀的排序位置。假设第 4 个后缀最终成为排序后的第一个。所以 V[0] = i。在这种情况下，我们知道（因为我告诉过你）i = 4。但是算法如何知道这一点，因为我们没有跟踪它们的位置。我应该创建一个包含后缀及其后缀编号的类吗？

两个密切相关的数据结构是后缀树和后缀数组。根据我的阅读，后缀树比后缀数组更快、更强大、更灵活、内存效率更高。但是，在这个较早的问题中，最重要的答案之一提到后缀数组在实践中得到了更广泛的使用。我没有任何使用这些结构的经验，但现在对于需要它们提供的功能的问题（例如快速子字符串检查），我似乎总是更喜欢后缀树而不是后缀数组。

在什么情况下后缀数组比后缀树更可取？

（顺便说一下，虽然这个问题与我所链接的问题有关，但我认为这不是一个完全重复的问题，因为我只对后缀数组和后缀树的比较感兴趣，完全不考虑尝试. 但是，如果您不同意，我会理解这个问题是否要关闭。）

我正在寻找一种快速的后缀数组构造算法。我对易于实现和原始速度比渐近复杂性更感兴趣（我知道可以在 O(n) 时间内通过后缀树构造后缀数组，但这需要很多空间；显然其他算法有糟糕的最坏情况大 O 复杂性，但在实践中运行得非常快）。我不介意生成 LCP 数组作为副产品的算法，因为无论如何我都需要一个用于我自己的目的。

我找到了各种后缀数组构造算法的分类，但它已经过时了。我听说过SA-IS、qsufsort和BPR，但我真的不知道它们之间的比较，也不知道是否有更好的算法。考虑到 suffix-array 领域现在看起来有多热，我希望其他一些算法在它们发布后已经取代了它们。我似乎记得曾经看过一篇描述一种名为“split”的快速算法的论文，但我现在一辈子都找不到它。

那么，目前最先进的技术是什么？理想情况下，我想要一份当前最佳算法的简短列表（如果可能，请附上链接）并快速概述它们的相对优势和劣势。

对于两个字符串 A 和 B，我们将字符串的相似度定义为两个字符串共有的最长前缀的长度。例如，字符串“abc”和“abd”的相似度为2，而字符串“aaa”和“aaab”的相似度为3。计算字符串S与其每个后缀的相似度之和

这是我的解决方案...

我们如何使用后缀数组来解决这个问题？