Aufgaben:Exercise 2.13: Inverse Burrows-Wheeler Transformation - Revision history

Hwang at 12:45, 17 November 2022

2022-11-17T12:45:00Z

Javier: Text replacement - "analyse" to "analyze"

2021-09-22T11:47:48Z

Text replacement - "analyse" to "analyze"

Guenter at 14:11, 13 August 2021

2021-08-13T14:11:51Z

Guenter at 08:57, 13 August 2021

2021-08-13T08:57:49Z

Guenter at 08:37, 13 August 2021

2021-08-13T08:37:08Z

Guenter at 08:25, 13 August 2021

2021-08-13T08:25:50Z

Guenter at 08:24, 13 August 2021

2021-08-13T08:24:18Z

Guenter at 08:21, 13 August 2021

2021-08-13T08:21:58Z

Guenter at 12:35, 12 August 2021

2021-08-12T12:35:02Z

Noah at 20:09, 10 August 2021

2021-08-10T20:09:40Z

@@ Line 15: / Line 15: @@
-The graphic shows the result of a BWT, more precisely its L column.&nbsp; The original text is to be reconstructed from this according to the description on the theory page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]],
+The graphic shows the result of a BWT, more precisely its L column.&nbsp; The original text is to be reconstructed from this according to the description in the theory section&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]],
 *in subtask&nbsp; '''(2)'''&nbsp; with the primary index&nbsp; $I = 7$,
 *in subtask&nbsp; '''(3)'''&nbsp; &nbsp; $I = 0$&nbsp; is to be assumed.
@@ Line 27: / Line 27: @@
 <u>Hints:</u>
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further Source Coding Methods]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].
+*In particular, reference is made to the section&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].

@@ Line 3: / Line 3: @@
 }}
-[[File:EN_Inf_A_2_14.png|right|frame|BWT result to be analysed]]
+[[File:EN_Inf_A_2_14.png|right|frame|BWT result to be analyzed]]
 The&nbsp;  "Burrows&ndash;Wheeler Transformation" &ndash; abbreviated&nbsp; $\rm BWT$&nbsp; &ndash; causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.

← Older revision		Revision as of 14:11, 13 August 2021
Line 73:		Line 73:


−	:[[File:~~P_ID2479__Inf_A_2_14b~~.png\|right\|frame\|Inverse BWT with  $I = 7$  (left) or  $I = 0$  (right)]]	+	:[[File:Inf_Z_2_14b_v2.png\|right\|frame\|Inverse BWT with  $I = 7$  (left) or  $I = 0$  (right)]]

	'''(2)'''  The <u>solution suggestion 1</u> is correct:   <b>MEINDEINSEIN</b>, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number  $I = 0$  in each case. For explanation:		'''(2)'''  The <u>solution suggestion 1</u> is correct:   <b>MEINDEINSEIN</b>, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number  $I = 0$  in each case. For explanation:

@@ Line 66: / Line 66: @@
 ===Solution===
 {{ML-Kopf}}
-'''(1)'''&nbsp; <u>Solution suggestion 3</u> is correct:
+'''(1)'''&nbsp; The <u>solution suggestion 3</u> is correct:
-*The first column of the BWT matrix is also called the&nbsp; F&ndash;column&nbsp; and the last column the&nbsp; L&ndash;column&nbsp; (from "<i>First</i>" or "<i>Last</i>").
+*The first column of the BWT matrix is also called the&nbsp; "F column"&nbsp; and the last column the&nbsp; "L column"&nbsp; (from&nbsp; "First"&nbsp; or&nbsp; "Last").
-*Only the&nbsp; L&ndash;column is passed on to the next coding level.
+*Only the&nbsp; "L column" is passed on to the next coding level.
-*The&nbsp; F&ndash;column, which is also needed for the reverse transformation, results from the&nbsp; L&ndash;column&nbsp; by lexicographic sorting.
+*The&nbsp; "F column", which is also needed for the reverse transformation, results from the&nbsp; "L column"&nbsp; by lexicographically sorting.
-'''(2)'''&nbsp;<u>Solution suggestion 1</u> is correct: &nbsp; <b>MEINDEINSEIN</b> is correct, as can be seen from the left-hand representation of the following diagram. <br>Note that the top line represents the line number&nbsp; $I = 0$&nbsp; in each case. For explanation:
+:[[File:P_ID2479__Inf_A_2_14b.png|right|frame|Inverse BWT with&nbsp; $I = 7$&nbsp; (left) or&nbsp; $I = 0$&nbsp; (right)]]
-'''(3)'''&nbsp; Correct is the <u>proposed solution 2</u>: &nbsp; <br><br>$\rm DEINSEINMEIN$, as shown in the graph on the right.
 <br clear=all>
 '''(4)'''&nbsp; Correct is the <u>suggested solution 3</u>:
 *In BWT, four characters here are equal to their predecessors, in the original none.
-*In the F&ndash;column , even more characters would be the same as their respective predecessors (6 in total) due to the lexicographical sorting, but this sorting cannot be reversed without loss.
+*In the&nbsp; "F column",&nbsp; even more characters would be the same as their respective predecessors&nbsp; (6 in total)&nbsp; due to the lexicographical sorting, but this sorting cannot be reversed without loss.
-*Solution suggestion 1 is also wrong: &nbsp; the original and BWT contain exactly the same characters&nbsp; $($three times&nbsp; $\rm E$,&nbsp; three times&nbsp; $\rm I$,&nbsp; three times&nbsp; $\rm N$ and one each of&nbsp; $\rm D$,&nbsp; $\rm M$&nbsp; and&nbsp; $\rm S)$.
+*Solution suggestion 1 is wrong too: &nbsp; <br>The original and BWT contain exactly the same characters&nbsp; $($three times&nbsp; $\rm E$,&nbsp; three times&nbsp; $\rm I$,&nbsp; three times&nbsp; $\rm N$ and one each of&nbsp; $\rm D$,&nbsp; $\rm M$&nbsp; and&nbsp; $\rm S)$.
 {{ML-Fuß}}

@@ Line 25: / Line 25: @@
-Hints:
+<u>Hints:</u>
 *The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further Source Coding Methods]].
 *In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler_transformation|Burrows&ndash;Wheeler Transformation]].
@@ Line 36: / Line 33: @@
 <quiz display=simple>
-{What is the&nbsp; $\text{F&ndash;Spalte}$ associated with the given&nbsp; $\text{L&ndash;Spalte}$&nbsp;?
+{What is the&nbsp; $\text{F column}$ associated with the given&nbsp; $\text{L column}$&nbsp;?
 |type="()"}
 - $\rm SEINMEINDEIN$,
@@ Line 50: / Line 47: @@
-{What happens if the reconstruction&nbsp; $\text{(BWT back transformation})$&nbsp; starts from the wrong primary index&nbsp; $I = 0$&nbsp;?
+{What happens if the reconstruction&nbsp; $\text{(inverse BWT transformation})$&nbsp; starts from the wrong primary index&nbsp; $I = 0$&nbsp;?
 |type="[]"}
-- The result is the original text, read from back to front.
+- $\rm MEINDEINSEIN$,
-+ The result is a cyclic permutation of the original.
++ $\rm DEINSEINMEIN$,
-Why is the Burrows&ndash;Wheeler transform better suited than the original with regard to a later data compression?
+{Why is the Burrows&ndash;Wheeler transformation better suited than the original with regard to a later data compression?
 |type="[]"}
 - It results in more favourable character frequencies.

@@ Line 26: / Line 26: @@
 Hints:
-*The exercise belongs to the chapter&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren|Other source coding methods]].
+*The exercise belongs to the chapter&nbsp; [[Information_Theory/Further_Source_Coding_Methods|Further Source Coding Methods]].
-*In particular, reference is made to the page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler Transformation]].
+*In particular, reference is made to the page&nbsp; [[Information_Theory/Further_Source_Coding_Methods#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler Transformation]].
 *Further information can be found in the two publications mentioned below:
 : '''(1)''' &nbsp; Abel, J.: ''Verlustlose Datenkompression auf Grundlage der Burrows-Wheeler-Transformation''. <br>&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; In: PIK - Praxis der Informationsverarbeitung und Kommunikation, no. 3, vol. 26, S. 140&ndash;144, Sept.  2003.

@@ Line 3: / Line 3: @@
 }}
-[[File:EN_Inf_A_2_14.png|right|frame|To be analysed <br>BWT result]]
+[[File:EN_Inf_A_2_14.png|right|frame|BWT result to be analysed]]
-Die&nbsp;  ''Burrows&ndash;Wheeler&ndash;Transformation'' &ndash; abbreviated&nbsp; $\rm BWT$&nbsp; &ndash; causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.
+The&nbsp;  "Burrows&ndash;Wheeler Transformation" &ndash; abbreviated&nbsp; $\rm BWT$&nbsp; &ndash; causes a blockwise sorting of the characters of a text with the aim of preparing the text for efficient data compression with the help of run-length coding or entropy coding.
-* First, an&nbsp; $N&times;N$&ndash; matrix is generated from a block of length&nbsp; $N$&nbsp;, with each row of this first&ndash;matrix resulting from the preceding row by cyclic left shift.
+* First, an&nbsp; $N&times;N$  matrix is generated from a block of length&nbsp; $N$,&nbsp; with each row of this first matrix resulting from the preceding row by cyclic left shift.
-* Then the matrix is sorted lexicographically&nbsp; (without special characters: &nbsp; alphabetically)&nbsp;.&nbsp; The result of the BWT is the last row of the new BWT matrix, the so-called&nbsp; $\text{L&ndash;column}$&nbsp;  (from "Last", &nbsp; last row of the BWT&ndash;matrix).
+* Then the matrix is sorted lexicographically&nbsp; (without special characters: &nbsp; alphabetically)&nbsp;.&nbsp; The result of the BWT is the last row of the new BWT matrix, the so-called&nbsp; $\text{L column}$&nbsp;  (from "Last").
-* Further, this task refers to the&nbsp; $\text{F&ndash;column}$&nbsp; (from "First", first row of the BWT matrix), which is needed for the inverse Burrows&ndash;Wheeler&ndash;Transformation &nbsp; &#8658; &nbsp; reconstruction of the original text from the L&ndash;column.
+* Further, this task refers to the&nbsp; $\text{F column}$&nbsp; (from "First", first row of the BWT matrix), which is needed for the inverse Burrows&ndash;Wheeler Transformation &nbsp; &#8658; &nbsp; reconstruction of the original text from the L column.
-* For the inverse BWT, the so-called <i>primary index</i>&nbsp; $I$ is also required.&nbsp; This indicates the row of the BWT matrix in which the algorithm must be started.
+* For the inverse BWT, the so-called&nbsp; "primary index"&nbsp; $I$&nbsp; is also required.&nbsp; This indicates the row of the BWT matrix in which the algorithm must be started.
-The graphic shows the result of a BWT, more precisely its L&ndash;column.&nbsp; The original text is to be reconstructed from this according to the description on the theory page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler Transformation]]&nbsp;,
+The graphic shows the result of a BWT, more precisely its L column.&nbsp; The original text is to be reconstructed from this according to the description on the theory page&nbsp; [[Information_Theory/Weitere_Quellencodierverfahren#Burrows.E2.80.93Wheeler.E2.80.93Transformation|Burrows&ndash;Wheeler Transformation]],
-*where in subtask&nbsp; '''(2)'''&nbsp; from the primary index&nbsp; $I = 7$
+*in subtask&nbsp; '''(2)'''&nbsp; with the primary index&nbsp; $I = 7$,
-*and in subtask&nbsp; '''(3)'''&nbsp; &nbsp; $I = 0$&nbsp; is to be assumed.
+*in subtask&nbsp; '''(3)'''&nbsp; &nbsp; $I = 0$&nbsp; is to be assumed.

← Older revision		Revision as of 12:35, 12 August 2021
Line 1:		Line 1:

−	{{quiz-Header\|Buchseite=~~Informationstheorie~~/~~Weitere Quellencodierverfahren~~	+	{{quiz-Header\|Buchseite=Information_Theory/Further_Source_Coding_Methods
	}}		}}