标签: suffix-array

经过相当多的阅读后,我发现了后缀数组和LCP数组所代表的含义.

后缀数组:表示数组每个后缀的_lexicographic等级.

LCP数组:在按字典顺序排序后,包含两个连续后缀之间的最大长度前缀匹配.

几天以来,我一直在努力理解,后缀数组和LCP算法究竟是如何工作的.

这是代码,取自Codeforces:

/*
Suffix array O(n lg^2 n)
LCP table O(n)
*/
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

namespace SuffixArray
{
    const int MAXN = 1 << 21;
    char * S;
    int N, gap;
    int sa[MAXN], pos[MAXN], tmp[MAXN], lcp[MAXN];

    bool sufCmp(int i, int j)
    {
        if (pos[i] != pos[j])
            return pos[i] …

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

我找到了各种后缀数组构造算法的分类,但它已经过时了.我听说过SA-IS,qsufsort和BPR,但我真的不知道它们如何相互比较,也没有更好的算法.考虑到后缀阵列字段现在看起来有多热,我希望其他一些算法在发布之后已经取代了那些算法.我似乎回想起一篇描述一种叫做"分裂"的快速算法的论文,但我现在找不到它的生命.

那么,目前的艺术水平是什么？理想情况下,我想要一份当前最佳算法的简短列表(如果可能的话,还有链接)以及他们相对优势和劣势的快速概述.

我已经读过可以使用最长公共前缀(LCP)来查找字符串中模式的出现次数.

具体来说,您只需要创建文本的后缀数组,对其进行排序,然后不进行二进制搜索以找到范围,以便您可以计算出现次数,只需计算每个连续条目的LCP即可.后缀数组.

虽然使用二进制搜索来查找模式的出现次数是显而易见的,但我无法弄清楚LCP如何帮助找到这里出现的次数.

例如,对于此后缀数组banana:

LCP  Suffix entry
N/A  a  
1    ana  
3    anana  
0    banana  
0    na  
2    nana  

LCP如何帮助找到像"banana"或"na"这样的子字符串的出现次数对我来说并不明显.

有什么帮助搞清楚LCP如何帮助吗？

我只想知道,当后缀树优于增强后缀数组时.

在阅读了使用增强的suf fi x数组替换suf fi x树之后,我再也看不到使用后缀树的理由了.有些方法可能会变得复杂,但您可以使用后缀数组执行所有操作,使用后缀树可以执行的操作,并且需要相同的时间复杂度但内存较少.

一项调查甚至表明,后缀数组更快,因为它们缓存更友好,并且不会产生更多的缓存未命中,然后产生后缀树(因此缓存可以更好地预测数组使用,然后在递归树结构上).

那么,有没有人知道在后缀数组上选择后缀树的原因？

编辑 好的,如果你知道更多告诉我,到目前为止:

• 后缀不允许在线构造
• 一些模式匹配算法在Suffixtrees上运行得更快
• (补充)由于在线构造,你可以将它保存在高清上并扩大现有的后缀树.如果你使用SSD,它也应该安静快速.

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

假设S = abracadabra

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

(注意:S'是附加S了k个EOF字符的原件,k是适合机器字的字符数(我是32位机器,所以k=4)

EOF = '$'

如我错了请纠正我:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

然后,算法说你必须S通过索引到数组W来对后缀数组(名为V)进行排序.

我不完全明白你如何通过索引来排序后缀W.例如:在分选的某一点,假设你得到两个后缀,i并且j,你必须对它们进行比较.由于您正在编入索引W,因此您当时要检查4个字符.
假设它们具有相同的前4个字符.然后,您必须检查每个后缀的下4个字符,并通过从每个后缀的第4个位置访问来完成W.这是正确的吗？这种"将字符包装成文字"真的能加快速度吗？

我需要在String中找到最长的非重叠重复子字符串.我有可用字符串的后缀树和后缀数组.

当允许重叠时,答案是微不足道的(后缀树中最深的父节点).

例如对于String ="acaca"

如果允许重叠,则回答是"aca"但是当不允许重叠时,回答是"ac"或"ca".

我只需要算法或高级想法.

PS:我试过,但我在网上找不到明确的答案.

摘自编程珍珠第15.2节

可在此处查看C代码:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

当我使用suffix-array在Python中实现它时:

example = open("iliad10.txt").read()
def comlen(p, q):
    i = 0
    for x in zip(p, q):
        if x[0] == x[1]:
            i += 1
        else:
            break
    return i

suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:]))  #VERY VERY SLOW

max_len = -1
for i in range(example_len - 1):
    this_len = comlen(example[idx[i]:], example[idx[i+1]:])
    print this_len
    if this_len > max_len:
        max_len = this_len
        maxi = i

我发现这idx.sort一步很慢.我认为它很慢,因为Python需要通过值而不是指针传递子串(如上面的C代码).

测试文件可以从这里 …

我正在看原始论文图3中给出的伪代码,它引入了后缀数组"SUFFIX ARRAYS:一种新的在线字符串搜索方法".

我无法弄清楚第4行和第5行的逻辑(从0开始索引).这些内容如下:

否则,如果 ř<P或瓦特 _{- [R} ≤一个 _{POS [N-1] + R} 然后
大号 _W¯¯ ←Ñ

W是一个长度为"P"的,我们正在寻找和模式r是lcp(A[pos[N-1]:], W).问题是,在几乎所有情况下,这lcp将小于'W'的长度.这个条件是为了处理这种情况(我认为),该模式在字典上大于数组中按字典顺序排列的最大后缀,但它根本不测试这个.另一方面,第2和第3行测试是否W小于词典上最小的后缀似乎很有意义

如果升= P或瓦特_升 ≤一个 _{POS [0] + 1} 然后
大号 _W¯¯ ←0

我相信原始的行应该是这样的:

否则如果 r <P且 w _r > a _{Pos [N-1] + r} 则
L _W ←N.

唯一W可以大于A[pos[N-1]:]它的方式是它是否lcp比模式的长度短(否则,所有W匹配W都不能更大,只有更小或等于我们共享的东西lcp)和如果之后的字符lcp是更大的W比 …

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

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

但是,"content [a:]"会制作内容的副本,当内容变大时,内容会变得非常低效.所以我想知道是否有办法比较两个子串而不必复制它们.我试过使用buffer-builtin,但它没有用.

解决这个问题的最佳方法(性能方面)是什么？我被建议使用后缀树.这是最好的方法吗？