标签: suffix-array

这是从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,但它没有用.

我们需要在两个字符串之间找到最短的不常见子字符串,即如果我们有两个字符串a,b那么我们需要找到其中最短子字符串的长度a不是子字符串b.

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

要求解决的复杂度不超过n*lg(n)

我正在寻找一个有效的数据结构来在一组非常庞大的字符串上进行字符串/模式匹配.我发现了try,suffix-trees和suffix-arrays.但到目前为止,我无法在C/C++中找到一个现成的实现(并且我自己实现它似乎很难并且容易出错).但是我仍然不确定Suffix-Arrays是否真的是我正在寻找的东西......我已经尝试过libdivsufsort和esaxx,但是无法找到如何根据我的需要使用它们:

我想使用一组预定义的字符串,使用通配符(甚至是正则表达式)来匹配用户输入.我有一个庞大的预定义字符串列表,即

"什么是*？" "什么是XYZ？" "多少*？" ...

现在我想找到最匹配的字符串(如果有的话,那就完全匹配).即用户输入:>什么是XYZ？应该找到"什么是XYZ？" 而不是"什么是*？",而是"什么是东西？" 应该找到"什么是*？" (假设*是任何字符数的通配符).

构建结构不是时间关键的(并且结构不必具有超空间效率),但搜索不应该花费太长时间.怎么可以轻松完成？欢迎任何框架/库或代码示例

谢谢

我成功地为我正在编写的压缩测试平台实现了一个BWT阶段(使用常规字符串排序).我可以应用BWT然后反BWT变换,输出匹配输入.现在我想加速使用后缀数组创建BW索引表.我找到了2个相对简单的,假设快速的O(n)算法用于后缀数组创建,DC3和SA-IS都带有C++/C源代码.我尝试使用这些源代码(开箱即用的编译SA-IS源代码也可以在这里找到),但无法获得正确的后缀数组/ BWT索引表.这就是我所做的:

1. T =输入数据,SA =输出后缀数组,n = T的大小,K =字母大小,BWT = BWT索引表

2. 我处理8位字节,但两种算法都需要一个零字节形式的唯一标记/ EOF标记(DC3需要3,SA-IS需要一个),因此我将所有输入数据转换为32位整数,增加所有符号均为1,并附加标记零字节.这是T.

3. 我创建了一个整数输出数组SA(DC3的大小为n,KA-IS的大小为n +)并应用算法.我得到的结果类似于我的排序BWT变换,但有些值是奇数(见更新1).两种算法的结果也略有不同.SA-IS算法在前面产生一个超额索引值,因此所有结果都需要被一个索引(SA [i] = SA [i + 1])左侧复制.

4. 要将后缀数组转换为正确的BWT索引,我从后缀数组值中减去1,做一个模数并且应该有BWT索引(根据这个):BWT [i] =(SA [i] -1)%n .

这是我的代码,用于提供SA算法并转换为BWT.您应该能够或多或少地从论文中插入SA构造代码:

std::vector<int32_t> SuffixArray::generate(const std::vector<uint8_t> & data)
{
    std::vector<int32_t> SA;
    if (data.size() >= 2)
    {
        //copy data over. we need to append 3 zero bytes, 
        //as the algorithm expects T[n]=T[n+1]=T[n+2]=0
        //also increase the symbol value by 1, because the algorithm alphabet is [1,K]
        //(0 is …

我们可以使用带后缀链接的factor-oracle(此处为纸)来计算多个字符串的最长公共子字符串吗？这里,substring表示原始字符串的任何部分.例如,"abc"是"ffabcgg"的子串,而"abg"则不是.

我已经找到一种方法来计算两个字符串的最大长度公共子s1和s2.它通过使用不在其中的字符连接两个字符串来工作,例如'$'.然后,对于s具有长度的连接字符串的每个前缀i >= |s1| + 2,我们计算其LRS(最长重复后缀)长度lrs[i]和sp[i](其LRS的第一次出现的结束位置).最后,答案是

max{lrs[i]| i >= |s1| + 2 and sp[i] <= |s1|}

我编写了一个使用这种方法的C++程序,可以|s1|+|s2| <= 200000使用因子oracle 在我的笔记本电脑上解决200ms内的问题.

s1 = 'ffabcgg'
s2 = 'gfbcge'
s = s1+'$'+s2 
  = 'ffabcgg$gfbcge'
p: 0 1 2 3 4 5 6 7 8 9 10 11 12 13
s:  f f a b c g g $ g f  b  c  g …

我最近一直在更新我的算法知识，并一直在阅读后缀数组。我读过的每篇文章都将它们定义为单个搜索字符串上的后缀数组，但有些文章提到了将其概括为整个搜索字符串列表的“微不足道”，但我不知道如何。

假设我正在尝试对单词列表执行简单的子字符串搜索，并希望返回与给定子字符串匹配的单词列表。天真的方法似乎是在我的列表中的单词之间插入字典结束字符“$”，将它们连接在一起，然后从结果中生成后缀树。但这似乎会产生大量不相关的条目。如果我创建一个 'banana$muffin' 的源字符串，那么我最终会为我永远不会使用的 'ana$muffin' 生成后缀。

我很感激有关如何正确执行此操作的任何提示，或者更好的是，指向一些处理这种情况的算法文本的指针。

有人对在哪里可以找到后缀数组的 C# 实现有任何建议吗？我宁愿不要重新发明轮子......

我有一个后缀数组SA和一个数组L,它存储两个连续后缀之间的LCP长度(最长公共前缀),即

L[i]=LCP(SA[i-1],SA[i]) where 1<=i<=|SA|

它也在这里描述.

我应该如何使用此数组L来找到给定的两个后缀x和y之间的LCP(x,y)？

我真的想了解一个如何为给定模式构造一个好的后缀表的例子.问题是,我无法绕过它.我看了很多例子,但不知道数字的来源.

所以这里是:下面的示例演示了如何使用ANPANMAN模式构造一个Good Suffix Table:

Index | Mismatch | Shift | goodCharShift
-----------------------------------------------
  0   |         N|   1   | goodCharShift[0]==1
  1   |        AN|   8   | goodCharShift[1]==8
  2   |       MAN|   3   | goodCharShift[2]==3
  3   |      NMAN|   6   | goodCharShift[3]==6
  4   |     ANMAN|   6   | goodCharShift[4]==6
  5   |    PANMAN|   6   | goodCharShift[5]==6
  0   |   NPANMAN|   6   | goodCharShift[6]==6
  0   |  ANPANMAN|   6   | goodCharShift[7]==6

对此事的任何帮助都非常感谢.我根本不知道如何得到这些数字.谢谢!

今天我尝试使用scala创建后缀数组.我能够用大量代码完成它但后来我听说可以通过使用压缩和排序仅使用几行来创建它.

我现在遇到的问题是从一开始.我尝试使用二进制搜索和zipWithIndex创建以下"树",但到目前为止我还没有能够创建任何东西.我甚至不知道是否有可能只使用一条线,但我打赌它是大声笑.

我想做的是从一个词"芝士蛋糕"得到一个Seq:

 Seq((cheesecake, 0),
     (heesecake, 1),
     (eesecake, 2),
     (esecake, 3),
     (secake, 4),
     (ecake, 5),
     (cake, 6),
     (ake, 7),
     (ke, 8),
     (e, 9))

有人会把我推到正确的道路上吗？