Burrows–Wheeler transform: Difference between revisions
→{{header|zkl}}
Line 1,353:
BWT("SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES") = "STEXYDST.E.IXXIIXXSSMPPS.B..EE.$.USFXDIIOIIIT"
</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}}==
| |||