Burrowas-Wheeleras transfōrmaciōni

Iz Prūsiska Wikipēdija
Sākais en: nawigaciōni, laukīsna
Rindā 1: Rindā 1:
'''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. 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.
'''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. 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====
+
===Transfōrmaciōnis algōritman===
Turīntei dātan ōriginālin rīpawiskan stesse ilgan <math>n</math>, ēmpirzdan prawerru papilnintun di sen wangas zentlin. Panzdau prawerru per rīpawiskwan stesse iglan <math>n+1</math> generītun wissans <math>n+1</math> rōtaciōnins be enpeisātun en <math>(n+1) \times (n+1)</math> matricis rīndans. Ripīntei, prawerru teikātun di leksikōgrafiskai be panzdauma matricis kōluni ast transfōrmaciōnis wērtibi.
Turīntei dātan ōriginālin rīpawiskan stesse ilgan <math>n</math>, ēmpirzdan prawerru papilnintun di sen wangas zentlin. Panzdau prawerru per rīpawiskwan stesse iglan <math>n+1</math> generītun wissans <math>n+1</math> rōtaciōnins be enpeisātun en <math>(n+1) \times (n+1)</math> matricis rīndans. Ripīntei, prawerru teikātun di leksikōgrafiskai be panzdauma matricis kōluni ast transfōrmaciōnis wērtibi.
Rindā 83: Rindā 83:
  __<span>|</span>_KMM_SSAAAAASSSAA
  __<span>|</span>_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 <math>O(n^2)</math> mīnisnas. En realitātei šin algōritman ast realizītan sen ōriginalas rīpawiskwas waidīntajans.
===Etwartinewīngis transfōrmaciōnis algōritman===
===Etwartinewīngis transfōrmaciōnis algōritman===
Rindā 457: Rindā 466:
  AS_ASMA_KAS_AS_ASMA<span>|</span>
  AS_ASMA_KAS_AS_ASMA<span>|</span>
|}
|}
 +
 +
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
 +
 +
[[Category:Infōrmatiki]]
 +
 +
[[English:Burrows–Wheeler_transform]]
 +
[[Deutsch:Burrows-Wheeler-Transformation]]
 +
[[Polski:Transformata_Burrowsa-Wheelera]]
 +
[[Русский:Преобразование Барроуза — Уилера]]

Wersiōni kāigi iz 08:30, 4 sallaws 2014

Persōniskas pagaptis