Burrows–Wheeler transform: Difference between revisions
Added Go
m (→{{header|zkl}}: tweak) |
(Added Go) |
||
Line 5:
Source: [[wp:Burrows–Wheeler_transform|Burrows–Wheeler transform]]
=={{header|Go}}==
{{trans|Python}}
<lang go>package main
import (
"fmt"
"sort"
"strings"
)
const stx = "\002"
const etx = "\003"
func bwt(s string) (string, error) {
if strings.Index(s, stx) >= 0 || strings.Index(s, etx) >= 0 {
return "", fmt.Errorf("String can't contain STX or ETX")
}
s = stx + s + etx
le := len(s)
table := make([]string, le)
table[0] = s
for i := 1; i < le; i++ {
table[i] = s[i:] + s[:i]
}
sort.Strings(table)
lastBytes := make([]byte, le)
for i := 0; i < le; i++ {
lastBytes[i] = table[i][le-1]
}
return string(lastBytes), nil
}
func ibwt(r string) string {
le := len(r)
table := make([]string, le)
for range table {
for i := 0; i < le; i++ {
table[i] = r[i:i+1] + table[i]
}
sort.Strings(table)
}
for _, row := range table {
if strings.HasSuffix(row, etx) {
return row[1 : le-1]
}
}
return ""
}
func makePrintable(s string) string {
// substitute ^ for STX and | for ETX to print results
t := strings.Replace(s, stx, "^", 1)
return strings.Replace(t, etx, "|", 1)
}
func main() {
tests := []string{
"banana",
"appellee",
"dogwood",
"TO BE OR NOT TO BE OR WANT TO BE OR NOT?",
"SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES",
"\002ABC\003",
}
for _, test := range tests {
fmt.Println(makePrintable(test))
fmt.Print(" --> ")
t, err := bwt(test)
if err != nil {
fmt.Println("ERROR:", err)
} else {
fmt.Println(makePrintable(t))
}
r := ibwt(t)
fmt.Println(" -->", r, "\n")
}
}</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: String can't contain STX or ETX
-->
</pre>
=={{header|Python}}==
| |||