Module Bwt_sol


module Bwt_sol: sig .. end
Uma Solução do Problema B - Teoria da computação 2011/2012 - Burrow-Wheeler Transform (BWT)

Seja p uma palavra dada como input, calcular BWT(p)=(p':string,i:int).

A solução apresentada escolhe representar a matriz de rotação como uma lista de string.

Poder-se-ia ter optado por uma matrix nxn de caracteres, ou um vector de strings, ou uma lista /vector de listas de caracter etc...

Daremos neste ficheiro, duas versões duma solução possível: a versão iterativa (com ciclos) e a versão recursiva (dando preferência a funções recursivas)


val pal : string
pal: a palavra por transformar
val tam : int
tam: tamanho da palavra por transformar

Versão iterativa da construção da matriz de rotação (visto aqui como uma lista de string)
val perm : string list Pervasives.ref
perm é uma referência para a matriz de rotação. Começa por conter a palavra original
val new_l : string list
ordenar a matriz de rotação. No caso das listas, a lista ordenada construida e devolvida. No caso dos vectores o proprio vector em parâmetro é ordenado "in-place"
val mk_rotation_matrix : int -> string -> int -> string list -> string list
Versão recursiva da construção da matriz de rotação (visto aqui como uma lista de string).

mk_rotation_matrix n p acc : contrói a matriz de rotação.

n: número de palavras que falta rodar e inserir (inicalizada com tam-1)

p: próxima palavra por rodar e inserir (inicializada com pal)

tamanho: tamanho da palavra p (inicializada por tam)

acc: lista das palavras já tratadas (no final, e após ordenação, acc será a matriz de rotação). Inicializada com a lista cquem contem pal.


Vamos proceder de forma iterativa para construir/mostrar a palavra final e descobrir onde se encontra a palavra original na matriz de rotação
val onde : int Pervasives.ref
onde: indice onde está a palavra original. Inicializada como -1

De forma recursiva agora:

print_and_find ori mat t i pos: imprime a ultima letra de cada string de mat e devolve a posição da primeira ocorrência de ori em mat

ori: palavra original

mat: matriz de rotação (uma lista de string)

t: tamanho da palavra

i: posição actual na matriz de rotação (valor inicial = 0)

pos: posição da primeira ocorrência da palavra original na matriz (com valor inicial igual a -1)

val print_and_find : string -> string list -> int -> int -> int -> unit

invoca o processo recursivo de resolução
val main : unit -> unit