riteme.github.io
riteme.github.io copied to clipboard
riteme
诱导排序与SA-IS算法 - riteme.site
我有一个问题，就是我们为什么要用induce sort而不是bucket sort排序LMS substring 是因为时间复杂度吗？另外楼主可不可以详细说一下induce sort的具体做法？
@MTonyM
- 诱导排序和基数排序的复杂度是一样的，但是诱导排序最大的优势在于它访问内存的时候是连续的，提高了缓冲命中率，因此在实际效率上高于基数排序。
- 2.3 节和 2.4 节好像已经写了吧......虽然确实这中间大部分是直接翻译原论文的，有点晦涩QAQ。第 4 节是个完整的运行示例，里面包括了每次递归的两次诱导排序的完整过程。
樓主你是生信專業嗎？因為生信有一款很有名的比對軟件叫做bowtie2，他裡面對於后缀排序是用類似DC3的算法，用的是DC1024，被公認是目前最快的。但是我覺得SAIS無論在空間還是時間完全可以吊打DC系列，我教授卻說他們當初用libdivsufsort的時候發現很慢，我不太相信，為此我還跟他吵。。。。
@avis9ditiu 没有..我现在是高三，之前学过 OI（信息学奥林匹克竞赛），这篇文章也是当时学 OI 时写的。 DC1024 我确实没听说过。我只知道目前内陆 OI 界，DC3算法普遍跑不赢 SAIS。有可能是我们的 DC3 的实现不够精细。生信领域的情况实在不熟悉... OI 界的情况在这里可以看到，目前第一版全部都是 SAIS 算法。当然相比生信而言，这里数据确实比较小。可能大规模的操作 SAIS 没有优势？
你在“2.4 对LMS子串排序”那邊，説唯一需要改的是“确定每个桶S型桶的起始位置。将每一个LMS子串的首字母按照任意顺序放入对应的桶中。”
這裡面説的“任意順序”我不太明白？意思是我不管从左往右扫或者从右往左扫都是可以保證結果一定對嗎？
@fsafadsfdsaferwrds
博主，有点不理解，如果一直对S1进行压缩的话，最后在没有相同字符的受跳出递归，那如何知道原来LMS的排序是怎么样的呢？
得到 S1 后 LMS 子串就没用了。
对 LMS 子串进行排序不需要 S1 的后缀数组。
刚试了一下你的代码，好像运行结果不太对
网页上的这份代码可以通过 UOJ #35：http://uoj.ac/submission/285057
请检查是不是调用 SAIS 时的参数 S 没有按照算法的要求，在末尾添加特殊字符。
好的感谢，我跟着代码走一遍试试！
On Thu, 13 Sep 2018 at 14:32, riteme [email protected] wrote:
@fsafadsfdsaferwrds https://github.com/fsafadsfdsaferwrds
博主，有点不理解，如果一直对S1进行压缩的话，最后在没有相同字符的受跳出递归，那如何知道原来LMS的排序是怎么样的呢？
得到 S1 后 LMS 子串就没用了。 对 LMS 子串进行排序不需要 S1 的后缀数组。
刚试了一下你的代码，好像运行结果不太对
网页上的这份代码可以通过 UOJ #35 http://uoj.ac/problem/35： http://uoj.ac/submission/285057 请检查是不是调用 SAIS 时的参数 S 没有按照算法的要求，在末尾添加特殊字符。
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/riteme/riteme.github.io/issues/28#issuecomment-420880018, or mute the thread https://github.com/notifications/unsubscribe-auth/Agic80u5igPfDfQH9GgEqZiI4GaXIgiKks5uad_JgaJpZM4N_fAg .
博主两处“根据引理2.2”得知“S型的后缀字典序更大”，“由于L型后缀更小，因此总是先排布L型后缀，再排布S型后缀”这里，不太能懂，后缀类型定义和引理中都说的是的S比L后缀小不是吗
~~或者说引理写错了嘤该是$A>B$~~
@tianYaru 确实是的 qaq，之前这个引理 2.2 被人指出 $A$ 和 $B$ 的类型写反了，当时只是简单改了下，没想到还是有问题。还是您多谢指出了文章中的错误！ 我准备待会重新检查一下全文......
@a1b3c7d9
非常抱歉一直没有回复。前段时间比较忙...今天又重新看了一遍这个算法，说一点我的看法吧，不一定完全对（这篇博客从写出来后就一直有小问题，实在不敢说自己就是全对的 QAQ
- “因此上面的算法实际上是在对每个LMS前缀进行排序。” 这个确实有问题。严谨的讲要除去长度为 1 的 LMS 前缀，原论文里面就是这么说的。对我们而言只要知道最后放入 LMS 后缀时实际上放的是 LMS 子串就行了，因为这个诱导排序的过程是一个不断在左侧加字符的过程。
- LMS 子串定义时要不要删掉最后一个字符。 我觉得不太行...如果删掉最后一个字符，那实际上可能会有一个 LMS 子串是另外一个 LMS 子串的真前缀，递归的时候可能会出问题（不知道你是不是写过代码发现其实没问题 QAQ）。实际上最后一个字符的功能和哨兵字符差不多，LMS 子串排序的结果也是包含这个字符的。当然删掉最后一个字符后的顺序也是一样的，在定义里面包含这个字符避免这里有麻烦。
若S1=2210有重复值2，递归调用SA-IS（）是对S1=2210进行排序吗？然后返回的SA1是否是3210？ 你觉得S1在整个算法中的作用是什么呢？因为即使有重复的值，最后SA也是按照字典序正确排列了。 我看了yuta mori对该论文算法的实现，他大概是需要这个S1值快速进行BWT算法。但是这个算法里面我不太清楚为啥要用到S1。
@Daisy-gj
-
“递归调用SA-IS（）是对S1=2210进行排序吗？” 是
-
“然后返回的SA1是否是3210？” 是
-
你觉得S1在整个算法中的作用是什么呢？
- S1 是 LMS 子串 之间的相对顺序，SA1 是
*型后缀之间的相对顺序（引理 2.8） - 我们需要知道相同的 LMS 子串 所代表的后缀 之间的字典序。不可能有两个后缀是一样的。
- 例如 S =
bcacbcab#，LMS 子串分别为bca、acb、bca、ab#和#。S1 为32310，我们需要知道bcacbcab#和bcab#谁大谁小。引理 2.8 告诉我们递归即可。
大佬，我懂了！nb!
| | 高锦 | | [email protected] | 签名由网易邮箱大师定制
在2020年11月3日 10:57，Xue Zhenliang[email protected] 写道：
@Daisy-gj
“递归调用SA-IS（）是对S1=2210进行排序吗？” 是
“然后返回的SA1是否是3210？” 是
你觉得S1在整个算法中的作用是什么呢？
S1 是 LMS 子串 之间的相对顺序，SA1 是 * 型后缀之间的相对顺序（引理 2.8） 我们需要知道相同的 LMS 子串 所代表的后缀 之间的字典序。不可能有两个后缀是一样的。 例如 S = bcacbcab#，LMS 子串分别为 bca、acb、bca、ab# 和 #。S1 为 32310，我们需要知道 bcacbcab# 和 bcab# 谁大谁小。引理 2.8 告诉我们递归即可。
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.