Burrowas-Wheeleras transfōrmaciōni

Iz Prūsiska Wikipēdija
Sākais en: nawigaciōni, laukīsna

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|
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(n2) 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

En kitēimans billins
Persōniskas pagaptis