Burrows-Wheeler變換無EOF字符

我需要在線性時間內執行一個衆所周知的Burrows-Wheeler變換。我發現了一個帶後綴排序和EOF字符的解決方案，但添加EOF會改變轉換。例如：考慮串bcababa和兩個旋轉Burrows-Wheeler變換無EOF字符

S1 = abababc
S2 = ababcab

很顯然，S1 S2 <。現在以EOF字符：

S1 =巴＃BC
S2 = ABA＃bcab

現在S2 < S1。由此產生的轉型將有所不同。我如何在沒有EOF的情況下執行BWT？

2012-05-10 user8078

您需要在字符串中使用EOF字符才能使BWT正常工作，否則您無法執行反向變換以恢復原始字符串。沒有EOF，字符串「ba」和「ab」具有相同的轉換版本（「ba」）。使用EOF，轉換不同

ab  ba 

a b |  a | b 
b | a  b a | 
| a b  | b a

即ab將「| ab」和ba轉換爲「b | a」。

BWT需要EOF，因爲它標記字符循環開始的位置。

回覆：這樣做沒有EOF字符，根據維基百科，

由於輸入字符串的任何轉動將導致相同的變換的串中，BWT不能被不添加「EOF」倒標記到輸入，或者用信息擴充輸出，例如作爲索引，這使得可以從識別其所有旋轉的類別的輸入字符串。

有變換，通過該變換的串唯一地識別原始的雙射的版本。在這個版本中，每個字符串都有一個唯一的相同長度的倒數。

雙射變換的計算方法是首先將輸入分解爲Lyndon單詞的非遞增序列 ; Chen-Fox-Lyndon定理存在這樣的因式分解，可以在線性時間中找到。然後，算法將所有這些單詞的所有旋轉排序在一起;如在通常的Burrows-Wheeler變換中那樣，這產生了n個字符串的排序序列。然後通過在這個排序的列表中挑選這些字符串中的每個字符串的最後一個字符，獲得轉換後的字符串。

來源

2012-05-10 05:23:21

它的功課，我不需要進行解碼。 – user8078

我會解決與EOF字符的問題。如果我想讓一個學生能夠解決這個問題而沒有EOF角色，因爲「他/她只能找到沒有它的解決方案」，我會讓那個學生失敗。 –

檢查是由自動系統執行的，如果我使用EOF，我會得到一個「錯誤的答案」。 – user8078

通過計算與自身串聯的字符串的後綴數組，您可以執行不帶EOF字符的線性時間和空間的轉換。然後遍歷後綴數組。如果當前後綴數組值小於n，請向輸出數組添加從後綴數組中當前值所表示的位置開始的旋轉的最後一個字符。然而，這種方法將產生稍微不同的BWT轉換結果，因爲字符串旋轉不像EOF字符存在那樣排序。

的更詳細說明可以在這裏找到：http://www.quora.com/Algorithms/How-I-can-optimize-burrows-wheeler-transform-and-inverse-transform-to-work-in-O-n-time-O-n-space

來源

2012-12-21 01:21:43

是否使用等效於與自身方法連接的字符串的EOF字符？我得到的結果似乎不一樣。使用一個EOF字符，「\ 0」，這應該是比所有其他字符下，我得到'PTR：13，字符串：「CTAAAACACGAGA \ 0GATGCAGGTATTTTATGTTAGTGATGCATTTTATGGCTCCCCGAGCATATC」' 使用級聯輸入方法，我得到，' ptr：12，str：「TAAAACACGAGACGATGCGGATATTTTATGTTAGTGATGCATTTTATGGCTCCCCGAGCATATC」' 即使我們忽略NUL終止符，輸出仍然不同。 – DSnet

@ DSnet你使用了什麼輸入字符串？ AGCTTTTCATTCTGACTGCAACGGGCAATATGTCTCTGTGTGGATTAAAAAAAGAGTCTCTGAC？ –

@ DSnet ...好的，我可以重現你的結果。如果我有時間，我會調查。謝謝！ –

我知道這個線程是很老，但我有同樣的問題，並提出了以下解決方案：

找到辭書最小字符串旋轉並保存偏移（扭轉需要）（I使用林登因式分解）
使用上旋轉串正常BWT算法（這產生右輸出，因爲所有交易算法asume該字符串之後是按字典順序最小炭）
反轉：使用例如unbwt向後搜索開始於索引0和corrosponding字符寫入保存的偏移

來源

2015-07-18 13:25:08 Christoph

Burrows-Wheeler變換無EOF字符

回答

相關問題