Trasformata di Burrows-Wheeler

[Oromis92]

scrivere un programma che effettui la trasformata di burrows-wheeler su una stringa e ne riporti il risultato.

link: http://it.wikipedia.org/wiki/Trasformata_di_Burrows-Wheeler
La trasformata di Burrows-Wheeler (abbreviata con BWT) è un algoritmo usato nei programmi di compressione dati come bzip2. È stata inventata da Michael Burrows e David Wheeler.
Quando una stringa di caratteri viene sottoposta alla BWT, nessuno di questi cambia di valore perché la trasformazione permuta soltanto l'ordine dei caratteri. Se la stringa originale contiene molte ripetizioni di certe sottostringhe, allora nella stringa trasformata troveremo diversi punti in cui lo stesso carattere si ripete tante volte. Ciò è utile per la compressione perché diventa facile comprimere una stringa in cui compaiono lunghe sequenze di caratteri tutti uguali.

ecco la mia soluzione (PERL, of corse) :

while ($text = <>) {
chomp $text;
@text = split //,$text;
$length = length($text);
@array = ($text);
for ($j=0;$j<$length;$j++) {
for ($i=0;$i<$length;$i++) {
$string .= $text[ ($i-($j+1)) ];
}
$array[$j+1] = $string;
$string = "";
}
pop(@array);
#print "[DEBUG] @array\n";
@array = sort(@array);
#print "[DEBUG] @array\n\n";
$text = "";
for ($k=0;$k<=$#array;$k++) {
$text .= substr($array[$k],($length)-1,1);
}
print "$text\n";
}

usate come test vector questa stringa:

stringa originale ==> TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO
stringa trasformata ==> OIIEEAEO..LDTTNN.RRRRRRRTNTTLEAAIOEEEENTRDRTTETTTTATNNTTNNAAO....OU.T

 

[_Wizard]

Python:

#!/usr/bin/python
def search(c,s):
	a = [];
	for i in range(0,len(s)):
		if s[i] == c:
			a.append(s.index(s[i]));
	return a;
def Trasformata(s):
	r,v,c = [],[],[];
	for i in range(0,len(s)):
		if not s[i] in v:
			v.append(s[i]);
			r.append(search(s[i],s));
	for i in range(0,len(r)):
		for j in range(0,len(r[i])):
			c.append(s[r[i][j]]);
	return "".join(c);
print Trasformata("TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO");

 

[imported_ShuraBozz]

C:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

void strsort(char **str);
void transform(char *str);

int main()
{
    char whbu[]="TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO";
    transform(whbu);
    printf("%s\n",whbu);
    return 0;
}

void transform(char *str){
    int i,j,lung = strlen(str);
    char **tran;
    tran = (char**)calloc(lung,sizeof(char*));
    for(i=0;i<lung;i++)
        tran[i] = (char*)calloc(lung,sizeof(char));
    strcpy(tran[0],str);
    for(i=1;i<lung;i++){
        tran[i][0] = tran[i-1][lung-1];
        for(j=1;j<lung;j++)
            tran[i][j] = tran[i-1][j-1];
    }
    strsort(tran);
    for(i=0;i<lung;i++)
        str[i]=tran[i][lung-1];
}

void strsort(char **str){
    int i,j,k,lung = strlen(str[0]);
    char temp[lung];
    for(i=0;i<lung;i++){
        for(j=i;j<lung;j++){
            for(k=0;k<lung;k++){
                if(str[i][k]>str[j][k]){
                    strcpy(temp,str[i]);
                    strcpy(str[i],str[j]);
                    strcpy(str[j],temp);
                    break;
                }
                if(str[i][k]<str[j][k])
                    break;
            }
        }
    }
}

PHP:

#!/usr/bin/php

<?php
$str = $argv[1];
$lung = strlen($str);
$trans[0] = $str;
for($i=1;$i<$lung;$i++){
    $trans[$i][0] = $trans[$i-1][$lung-1];
    for($j=1;$j<$lung;$j++)
        $trans[$i][$j] = $trans[$i-1][$j-1];
}
sort($trans);
for($i=0;$i<$lung;$i++)
    $str[$i] = $trans[$i][$lung-1];
echo $str."\n";
?>

Per il PHP:

~TBozz~:~/sources/trasformata$ ./trasformata.php TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO

OOIIEEAEO..LDTTNN.RRRRRRRTNTTLEAAIOEEEENTRDRTTETTTTATNNTTNNAA....OU.T

 

[HackLife]

Python

def BWT(arg):
    trans = []
    for i in range(0,len(arg)):
        trans.append(arg[i:]+arg[:i])
    trans.sort()
    out = ''
    for i in trans:
        out+= trans[trans.index(i)][len(trans[trans.index(i)])-1]
    return out

print BWT("TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRETATRE.TROTTERELLANDOø")

Prevede l'inserimento di un carattere di EOF come ø (potrebbe essere non stampabile)

 

[oldVolp]

Anche se un po' tardi, ecco la mia versione in C:

/**
 * @Author: oldVolp
 * @Date: 28/09/09
 * Burrows–Wheeler transform (BWT)
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** allocaMatrice(int dim);
char*  nextRotation(char *stringa, int dim);
char*  trasformataBW(char *stringa);
void   ordinaMatrice(char **matrix, int dim);

int main(int argc, char *argv[])
{
    char *stringa = "TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO";

    printf("Input:  %s\n", stringa);
    printf("Output: %s\n", trasformataBW(stringa));

    return 0;
}

char** allocaMatrice(int dim)
{
    char **matrice;
    int    colonne;

    matrice = (char**)calloc(dim, sizeof(char*));
    for (colonne = 0; colonne < dim; colonne++)
        matrice[colonne] = (char*)calloc(dim, sizeof(char));

    return matrice;
}

char* nextRotation(char *stringa, int dim)
{
    char *newStr = (char*)malloc(dim*sizeof(char));
    char chTmp;
    int  i;

    memcpy(newStr, stringa, dim);
    chTmp = newStr[dim-1];

    for (i = dim-1; i > 0; i--)
        newStr[i] = newStr[i-1];
    newStr[0] = chTmp;

    return newStr;
}

char* trasformataBW(char *stringa)
{
    int    nRotation, i;
    int    dim = strlen(stringa);
    char **matrix = allocaMatrice(dim+1);
    char  *tmpStr = (char*)malloc(dim+1);

    // Effettuo e memorizzo tutte le rotazioni
    nRotation = 1;
    strcpy(matrix[0], stringa);
    do
    {
        strcpy(matrix[nRotation], nextRotation(matrix[nRotation-1], dim));
        nRotation++;
    } while (nRotation < dim);

    // Ordino la matrice
    ordinaMatrice(matrix, dim);

    // Ricavo la stringa trasformata
    for (i = 0; i < dim+1; i++)
        tmpStr[i] = matrix[i][dim-1];

    return tmpStr;
}

void ordinaMatrice(char **matrix, int dim)
{
    char *tmpStr = (char*)malloc(sizeof(char)*strlen(matrix[0]));
    int   i, j;

    // Bubble Sort
    for (i = 0; i < dim-1; i++)
    {
        for ( j = i+1; j < dim; j++)
        {
            if (strcmp(matrix[i], matrix[j]) == 1)
            {
                strcpy(tmpStr, matrix[i]);
                strcpy(matrix[i], matrix[j]);
                strcpy(matrix[j], tmpStr);
            }
        }
    }
}

Risultato:

Input:  TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO
Output: OIIEEAEO..LDTTNN.RRRRRRRTNTTLEAAIOEEEENTRDRTTETTTTATNNTTNNAAO....OU.T

 

[lumo]

in falcon

function burrowswheeler( string )
   array = []
   
   for i in [string.len()-1:0]
      string = string[1:] + string[0]
      array += string
   end

   arraySort( array )
   return "".merge( [].mfcomp( { x => x[-1] }, array ) )
end



> burrowswheeler( "TRENTATRE.TRENTINI.ANDARONO.A.TRENTO.TUTTI.E.TRENTATRE.TROTTERELLANDO" )