Wp/prg/Burrowas-Wheeleras transfōrmaciōni

Burrowas-Wheeleras transfōrmaciōni - zentlin rīpawiskwas (stringas) permutaciōni, kawīda gruppina zentlins tīt, kāi šai subbai zentlāi stalāi prēi sin be kawīdan ast etwartinnaminan šlāit papilniminan dātan. Rīpawiskwas transfōrmitan sen šan transfōrmisnan ast lānguis kōmpresitun, jāuku sta ast zāngan en kōmpresiōnis algōritmamans pirzdau tērpausnan move-to-front enkōdisnan be run-length enkōdisnan. Burrowas-Wheeleras transfōrmaciōni ast delīkan stesse bzip be bzip2 algōrtimans.

Transfōrmaciōnis algōritman

Turīntei dātan ōriginālin rīpawiskan stesse ilgan $n$ , ēmpirzdan prawerru papilnintun di sen wangas zentlin. Panzdau prawerru per rīpawiskwan stesse iglan $n+1$ generītun wissans $n+1$ rōtaciōnins be enpeisātun en $(n+1)\times (n+1)$ matricis rīndans. Ripīntei, prawerru teikātun di leksikōgrafiskai be panzdauma matricis kōluni ast transfōrmaciōnis wērtibi.

Transfōrmaciōni

Enēisenis

Wissas rōtaciōnis

Rīndan sōrtisna

Panzdaumas kōlunis
etrinksnā

Izēisenis
Panzdauma kōluni

AS_ASMA_KAS_AS_ASMA|

AS_ASMA_KAS_AS_ASMA|
S_ASMA_KAS_AS_ASMA|A
_ASMA_KAS_AS_ASMA|AS
ASMA_KAS_AS_ASMA|AS_
SMA_KAS_AS_ASMA|AS_A
MA_KAS_AS_ASMA|AS_AS
A_KAS_AS_ASMA|AS_ASM
_KAS_AS_ASMA|AS_ASMA
KAS_AS_ASMA|AS_ASMA_
AS_AS_ASMA|AS_ASMA_K
S_AS_ASMA|AS_ASMA_KA
_AS_ASMA|AS_ASMA_KAS
AS_ASMA|AS_ASMA_KAS_
S_ASMA|AS_ASMA_KAS_A
_ASMA|AS_ASMA_KAS_AS
ASMA|AS_ASMA_KAS_AS_
SMA|AS_ASMA_KAS_AS_A
MA|AS_ASMA_KAS_AS_AS
A|AS_ASMA_KAS_AS_ASM
|AS_ASMA_KAS_AS_ASMA

ASMA_KAS_AS_ASMA|AS_
ASMA|AS_ASMA_KAS_AS_
AS_ASMA_KAS_AS_ASMA|
AS_ASMA|AS_ASMA_KAS_
AS_AS_ASMA|AS_ASMA_K
A_KAS_AS_ASMA|AS_ASM
A|AS_ASMA_KAS_AS_ASM
KAS_AS_ASMA|AS_ASMA_
MA_KAS_AS_ASMA|AS_AS
MA|AS_ASMA_KAS_AS_AS
SMA_KAS_AS_ASMA|AS_A
SMA|AS_ASMA_KAS_AS_A
S_ASMA_KAS_AS_ASMA|A
S_ASMA|AS_ASMA_KAS_A
S_AS_ASMA|AS_ASMA_KA
_ASMA_KAS_AS_ASMA|AS
_ASMA|AS_ASMA_KAS_AS
_AS_ASMA|AS_ASMA_KAS
_KAS_AS_ASMA|AS_ASMA
|AS_ASMA_KAS_AS_ASMA

ASMA_KAS_AS_ASMA|AS_
ASMA|AS_ASMA_KAS_AS_
AS_ASMA_KAS_AS_ASMA|</span>
AS_ASMA|AS_ASMA_KAS_
AS_AS_ASMA|AS_ASMA_K
A_KAS_AS_ASMA|AS_ASM
A|AS_ASMA_KAS_AS_ASM
KAS_AS_ASMA|AS_ASMA_
MA_KAS_AS_ASMA|AS_AS
MA|AS_ASMA_KAS_AS_AS
SMA_KAS_AS_ASMA|AS_A
SMA|AS_ASMA_KAS_AS_A
S_ASMA_KAS_AS_ASMA|A
S_ASMA|AS_ASMA_KAS_A
S_AS_ASMA|AS_ASMA_KA
_ASMA_KAS_AS_ASMA|AS
_ASMA|AS_ASMA_KAS_AS
_AS_ASMA|AS_ASMA_KAS
_KAS_AS_ASMA|AS_ASMA
|AS_ASMA_KAS_AS_ASMA

__|_KMM_SSAAAAASSSAA

Pythōnas funkciōni realizintī šan algōritman:

def BW(s):
	l=[s[i:]+s[:i] for i in range(len(s))] # generīs listin stēisan rotaciōnin
	l=sorted(l)                            # sōrtis listin
	return .join([i[-1] for i in l])       # wartinnais panzdauma kōlunin

Rōtaciōnis generisnā imma $O(n^{2})$ mīnisnas. En realitātei šin algōritman ast realizītan sen ōriginalas rīpawiskwas waidīntajans.

Etwartinewīngis transfōrmaciōnis algōritman

Seīsei $l$ enēisenis per etwartinewīngin trnasfōrmaciōnin. Sōrtis $l$ be preidāis iz kāiran ōriginalin $l$ . Gaūnimai matricin $(n+1)\times 2$ . Sōrtimai rīndans be preidāimai prei kāiran enēisenin. Gaūnimai matricin $(n+1)\times 3$ . Paāntrinantei šans zāngans gaūnimai matricin $(n+1)\times (n+1)$ Iz šan matrīcin etrīnkimai rīndan wangināntin si sen |. Sta ast ōriginala rīpawisku.

Etwartinewīngi transfōrmaciōni
Enēisenis
__\|_KMM_SSAAAAASSSAA
Preidāis 1	Sōrtis 1	Preidāis 2	Sōrtis 2	Preidāis 3	Sōrtis 3	Preidāis 4	Sōrtis 4
_ _ \| _ K M M _ S S A A A A A S S S A A	A A A A A A A K M M S S S S S _ _ _ _ \|	_A _A \|A _A KA MA MA _K SM SM AS AS AS AS AS S_ S_ S_ A_ A\|	AS AS AS AS AS A_ A\| KA MA MA SM SM S_ S_ S_ _A _A _A _K \|A	_AS _AS \|AS _AS KAS MA_ MA\| _KA SMA SMA ASM ASM AS_ AS_ AS_ S_A S_A S_A A_K A\|A	ASM ASM AS_ AS_ AS_ A_K A\|A KAS MA_ MA\| SMA SMA S_A S_A S_A _AS _AS _AS _KA \|AS	_ASM _ASM \|AS_ _AS_ KAS_ MA_K MA\|A _KAS SMA_ SMA\| ASMA ASMA AS_A AS_A AS_A S_AS S_AS S_AS A_KA A\|AS	ASMA ASMA AS_A AS_A AS_A A_KA A\|AS KAS_ MA_K MA\|A SMA_ SMA\| S_AS S_AS S_AS _ASM _ASM _AS_ _KAS \|AS_
Preidāis 17	Sōrtis 17	Preidāis 18	Sōrtis 18	Preidāis 19	Sōrtis 19	Preidāis 20	Sōrtis 20
_ASMA_KAS_AS_ASMA _ASMA\|AS_ASMA_KAS \|AS_ASMA_KAS_AS_A _AS_ASMA\|AS_ASMA_ KAS_AS_ASMA\|AS_AS MA_KAS_AS_ASMA\|AS MA\|AS_ASMA_KAS_AS _KAS_AS_ASMA\|AS_A SMA_KAS_AS_ASMA\|A SMA\|AS_ASMA_KAS_A ASMA_KAS_AS_ASMA\| ASMA\|AS_ASMA_KAS_ AS_ASMA_KAS_AS_AS AS_ASMA\|AS_ASMA_K AS_AS_ASMA\|AS_ASM S_ASMA_KAS_AS_ASM S_ASMA\|AS_ASMA_KA S_AS_ASMA\|AS_ASMA A_KAS_AS_ASMA\|AS_ A\|AS_ASMA_KAS_AS_	ASMA_KAS_AS_ASMA\| ASMA\|AS_ASMA_KAS_ AS_ASMA_KAS_AS_AS AS_ASMA\|AS_ASMA_K AS_AS_ASMA\|AS_ASM A_KAS_AS_ASMA\|AS_ A\|AS_ASMA_KAS_AS_ KAS_AS_ASMA\|AS_AS MA_KAS_AS_ASMA\|AS MA\|AS_ASMA_KAS_AS SMA_KAS_AS_ASMA\|A SMA\|AS_ASMA_KAS_A S_ASMA_KAS_AS_ASM S_ASMA\|AS_ASMA_KA S_AS_ASMA\|AS_ASMA _ASMA_KAS_AS_ASMA _ASMA\|AS_ASMA_KAS _AS_ASMA\|AS_ASMA_ _KAS_AS_ASMA\|AS_A \|AS_ASMA_KAS_AS_A	_ASMA_KAS_AS_ASMA\| _ASMA\|AS_ASMA_KAS_ \|AS_ASMA_KAS_AS_AS _AS_ASMA\|AS_ASMA_K KAS_AS_ASMA\|AS_ASM MA_KAS_AS_ASMA\|AS_ MA\|AS_ASMA_KAS_AS_ _KAS_AS_ASMA\|AS_AS SMA_KAS_AS_ASMA\|AS SMA\|AS_ASMA_KAS_AS ASMA_KAS_AS_ASMA\|A ASMA\|AS_ASMA_KAS_A AS_ASMA_KAS_AS_ASM AS_ASMA\|AS_ASMA_KA AS_AS_ASMA\|AS_ASMA S_ASMA_KAS_AS_ASMA S_ASMA\|AS_ASMA_KAS S_AS_ASMA\|AS_ASMA_ A_KAS_AS_ASMA\|AS_A A\|AS_ASMA_KAS_AS_A	ASMA_KAS_AS_ASMA\|A ASMA\|AS_ASMA_KAS_A AS_ASMA_KAS_AS_ASM AS_ASMA\|AS_ASMA_KA AS_AS_ASMA\|AS_ASMA A_KAS_AS_ASMA\|AS_A A\|AS_ASMA_KAS_AS_A KAS_AS_ASMA\|AS_ASM MA_KAS_AS_ASMA\|AS_ MA\|AS_ASMA_KAS_AS_ SMA_KAS_AS_ASMA\|AS SMA\|AS_ASMA_KAS_AS S_ASMA_KAS_AS_ASMA S_ASMA\|AS_ASMA_KAS S_AS_ASMA\|AS_ASMA_ _ASMA_KAS_AS_ASMA\| _ASMA\|AS_ASMA_KAS_ _AS_ASMA\|AS_ASMA_K _KAS_AS_ASMA\|AS_AS \|AS_ASMA_KAS_AS_AS	_ASMA_KAS_AS_ASMA\|A _ASMA\|AS_ASMA_KAS_A \|AS_ASMA_KAS_AS_ASM _AS_ASMA\|AS_ASMA_KA KAS_AS_ASMA\|AS_ASMA MA_KAS_AS_ASMA\|AS_A MA\|AS_ASMA_KAS_AS_A _KAS_AS_ASMA\|AS_ASM SMA_KAS_AS_ASMA\|AS_ SMA\|AS_ASMA_KAS_AS_ ASMA_KAS_AS_ASMA\|AS ASMA\|AS_ASMA_KAS_AS AS_ASMA_KAS_AS_ASMA AS_ASMA\|AS_ASMA_KAS AS_AS_ASMA\|AS_ASMA_ S_ASMA_KAS_AS_ASMA\| S_ASMA\|AS_ASMA_KAS_ S_AS_ASMA\|AS_ASMA_K A_KAS_AS_ASMA\|AS_AS A\|AS_ASMA_KAS_AS_AS	ASMA_KAS_AS_ASMA\|AS ASMA\|AS_ASMA_KAS_AS AS_ASMA_KAS_AS_ASMA AS_ASMA\|AS_ASMA_KAS AS_AS_ASMA\|AS_ASMA_ A_KAS_AS_ASMA\|AS_AS A\|AS_ASMA_KAS_AS_AS KAS_AS_ASMA\|AS_ASMA MA_KAS_AS_ASMA\|AS_A MA\|AS_ASMA_KAS_AS_A SMA_KAS_AS_ASMA\|AS_ SMA\|AS_ASMA_KAS_AS_ S_ASMA_KAS_AS_ASMA\| S_ASMA\|AS_ASMA_KAS_ S_AS_ASMA\|AS_ASMA_K _ASMA_KAS_AS_ASMA\|A _ASMA\|AS_ASMA_KAS_A _AS_ASMA\|AS_ASMA_KA _KAS_AS_ASMA\|AS_ASM \|AS_ASMA_KAS_AS_ASM	_ASMA_KAS_AS_ASMA\|AS _ASMA\|AS_ASMA_KAS_AS \|AS_ASMA_KAS_AS_ASMA _AS_ASMA\|AS_ASMA_KAS KAS_AS_ASMA\|AS_ASMA_ MA_KAS_AS_ASMA\|AS_AS MA\|AS_ASMA_KAS_AS_AS _KAS_AS_ASMA\|AS_ASMA SMA_KAS_AS_ASMA\|AS_A SMA\|AS_ASMA_KAS_AS_A ASMA_KAS_AS_ASMA\|AS_ ASMA\|AS_ASMA_KAS_AS_ AS_ASMA_KAS_AS_ASMA\| AS_ASMA\|AS_ASMA_KAS_ AS_AS_ASMA\|AS_ASMA_K S_ASMA_KAS_AS_ASMA\|A S_ASMA\|AS_ASMA_KAS_A S_AS_ASMA\|AS_ASMA_KA A_KAS_AS_ASMA\|AS_ASM A\|AS_ASMA_KAS_AS_ASM	ASMA_KAS_AS_ASMA\|AS_ ASMA\|AS_ASMA_KAS_AS_ AS_ASMA_KAS_AS_ASMA\| AS_ASMA\|AS_ASMA_KAS_ AS_AS_ASMA\|AS_ASMA_K A_KAS_AS_ASMA\|AS_ASM A\|AS_ASMA_KAS_AS_ASM KAS_AS_ASMA\|AS_ASMA_ MA_KAS_AS_ASMA\|AS_AS MA\|AS_ASMA_KAS_AS_AS SMA_KAS_AS_ASMA\|AS_A SMA\|AS_ASMA_KAS_AS_A S_ASMA_KAS_AS_ASMA\|A S_ASMA\|AS_ASMA_KAS_A S_AS_ASMA\|AS_ASMA_KA _ASMA_KAS_AS_ASMA\|AS _ASMA\|AS_ASMA_KAS_AS _AS_ASMA\|AS_ASMA_KAS _KAS_AS_ASMA\|AS_ASMA \|AS_ASMA_KAS_AS_ASMA
Output
AS_ASMA_KAS_AS_ASMA\|

Pythōnas funkciōni realizintī šan algōritman:

def IBW(l,z):
	l1=l                                      # generīs pirman kōlunin
	for i in range(len(l)-1):                 # generīs ripīntins kōlunins
		l1=map(.join,zip(l,sorted(l1)))   # sōrtis matricis rīndans be preidāis enēisenin prei kāiran
	l1=l1[0]                                  # reducīs matricin en pirman rīndan
	z=l1.index(z)                             # wangas zentlas pōziciōni
	return l1[z+1:]+l1[:z]                    # segēis rōtaciōnin, kāi | ēilai na wangan

Izwinaīnai autengīnsenei