Burrows–Wheeler transform: Difference between revisions
Content added Content deleted
Line 1,353: | Line 1,353: | ||
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT" |
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT" |
||
</pre> |
</pre> |
||
=={{header|lang}}== |
|||
{{trans|lang}} |
|||
<lang lang>Module Module1 |
|||
ReadOnly STX As Char = Chr(&H2) |
|||
ReadOnly ETX As Char = Chr(&H3) |
|||
Sub Rotate(Of T)(a As T()) |
|||
Dim o = a.Last |
|||
For i = a.Length - 1 To 1 Step -1 |
|||
a(i) = a(i - 1) |
|||
Next |
|||
a(0) = o |
|||
End Sub |
|||
Private Function Compare(s1 As String, s2 As String) As Integer |
|||
Dim i = 0 |
|||
While i < s1.Length AndAlso i < s2.Length |
|||
Dim a = s1(i) |
|||
Dim b = s2(i) |
|||
If a < b Then |
|||
Return -1 |
|||
End If |
|||
If b < a Then |
|||
Return 1 |
|||
End If |
|||
i += 1 |
|||
End While |
|||
If s1.Length < s2.Length Then |
|||
Return -1 |
|||
End If |
|||
If s2.Length < s1.Length Then |
|||
Return 1 |
|||
End If |
|||
Return 0 |
|||
End Function |
|||
Function Bwt(s As String) As String |
|||
If s.Any(Function(c) c = STX OrElse c = ETX) Then |
|||
Throw New ArgumentException("Input can't contain STX or ETX") |
|||
End If |
|||
Dim ss = (STX + s + ETX).ToCharArray |
|||
Dim table As New List(Of String) |
|||
For i = 0 To ss.Length - 1 |
|||
table.Add(New String(ss)) |
|||
Rotate(ss) |
|||
Next |
|||
table.Sort(Function(a As String, b As String) Compare(a, b)) |
|||
Return New String(table.Select(Function(a) a.Last).ToArray) |
|||
End Function |
|||
Function Ibwt(r As String) As String |
|||
Dim len = r.Length |
|||
Dim sa(len - 1) As String |
|||
Dim table As New List(Of String)(sa) |
|||
For i = 0 To len - 1 |
|||
For j = 0 To len - 1 |
|||
table(j) = r(j) + table(j) |
|||
Next |
|||
table.Sort(Function(a As String, b As String) Compare(a, b)) |
|||
Next |
|||
For Each row In table |
|||
If row.Last = ETX Then |
|||
Return row.Substring(1, len - 2) |
|||
End If |
|||
Next |
|||
Return "" |
|||
End Function |
|||
Function MakePrintable(s As String) As String |
|||
Return s.Replace(STX, "^").Replace(ETX, "|") |
|||
End Function |
|||
Sub Main() |
|||
Dim tests As String() = { |
|||
"banana", |
|||
"appellee", |
|||
"dogwood", |
|||
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?", |
|||
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES", |
|||
STX + "ABC" + ETX |
|||
} |
|||
For Each test In tests |
|||
Console.WriteLine(MakePrintable(test)) |
|||
Console.Write(" --> ") |
|||
Dim t = "" |
|||
Try |
|||
t = Bwt(test) |
|||
Console.WriteLine(MakePrintable(t)) |
|||
Catch ex As Exception |
|||
Console.WriteLine("ERROR: {0}", ex.Message) |
|||
End Try |
|||
Dim r = Ibwt(t) |
|||
Console.WriteLine(" --> {0}", r) |
|||
Console.WriteLine() |
|||
Next |
|||
End Sub |
|||
End Module</lang> |
|||
{{out}} |
|||
<pre>banana |
|||
--> |annb^aa |
|||
--> banana |
|||
appellee |
|||
--> |e^elplepa |
|||
--> appellee |
|||
dogwood |
|||
--> |do^oodwg |
|||
--> dogwood |
|||
TO BE OR NOT TO BE OR WANT TO BE OR NOT? |
|||
--> |?OOORREEETTRTW BBB ATTT NNOOONOO^ |
|||
--> TO BE OR NOT TO BE OR WANT TO BE OR NOT? |
|||
SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|||
--> |STEXYDST.E.IXXIIXXSSMPPS.B..EE.^.USFXDIIOIIIT |
|||
--> SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|||
^ABC| |
|||
--> ERROR: Input can't contain STX or ETX |
|||
--></pre> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |