Burrows-Wheeler-Transformation nach Wikipedia

[a.def]

Ich stecke gerade fest und finde einfach nicht heraus wo das Problem ist.
Ich möchte gerne in Delphi die Burrows-Wheeler-Transformation nachschreiben. Dazu habe ich mir das Wikipedia-Beispiel angesehen (LUA) und nach Delphi umgeschrieben.

Wikipedia: https://de.wikipedia.org/wiki/Burrow...ielcode_in_Lua

Delphi

Delphi-Quellcode:

procedure TForm1.Button4Click(Sender: TObject);
var
 i, iTmp, j, len, index: Integer;
 sText, codiert: string;
 matrix: array of string;
begin
 Memo1.Lines.Clear;
 sText := Edit2.Text;
 len := Length(sText) + 1;
 SetLength(matrix, len);

 // Start : .ANANAS.
 // Wanted result: ANANAS..

 // Tabelle mit allen Rotationen des Textes erzeugen
 for i := 1 to len - 1 do
  begin
   matrix[i] := Copy(sText, i, Length(sText)) + Copy(sText, 1, i - 1);
   // matrix[i] = string.sub(text, i) .. string.sub(text, 1, i - 1)
   Memo1.Lines.Add(matrix[i]);
  end;

 // Tabelle sortieren
 for i := 1 to len - 1 do
  begin
   for j := i + 1 to len - 1 do
    begin
     if Length(matrix[i]) > Length(matrix[j]) then
      begin
       matrix[i] := matrix[j];
       matrix[j] := matrix[i];
      end;
    end;
  end;;

 // Aus jeder Zeile das letzte Zeichen nehmen
 codiert := '';
 index := -1;
 for i := 1 to len - 1 do
  begin
   codiert := codiert + Copy(matrix[i], Length(matrix[i]), 1);

   if matrix[i] = sText then
    index := i;
  end;

 ShowMessage(codiert);
end;

Das gewünschte Ergebnis der ersten Transformation (Rotation) ist

1: .ANANAS.

2: ..ANANAS

3: S..ANANA

4: AS..ANAN

5: NAS..ANA

6: ANAS..AN

7: NANAS..A

8: ANANAS..

Mein Ergebnbis ist aber

1: .ANANAS.

2: ANANAS..

3: NANAS..A

4: ANAS..AN

5: NAS..ANA

6: AS..ANAN

7: S..ANANA

8: ..ANANAS

Blickt hier jemand eher durch als ich :idea:

[brechi]

Ich hab mich jetzt nicht genau mit dem Algorithmus auseinandergesetzt aber:

1) der 2. Schritt sortiert den Text

d.h. statt

Delphi-Quellcode:

Length(matrix[i])  > Length(matrix[j])

was immer gleich sein sollte, wird eher ein CompareText benötigt

2) du brauchst eine Hilfsvariable zum Austausch

Delphi-Quellcode:

       h := matrix[i];
       matrix[i] := matrix[j];
       matrix[j] := h;

[a.def]

Danke für die Antwort.
Die beiden Hilfestellungen machen leider keinen Unterschied am aktuellen Ergebnis.

Ich denke es liegt an dieser Zeile hier die nicht die gleiche Funktionalität hat wie die LUA-Zeile

Delphi-Quellcode:

{* Delphi  *} matrix[i] := Copy(sText, i, Length(sText)) + Copy(sText, 1, i - 1);
{* LUA * } // matrix[i] = string.sub(text, i) .. string.sub(text, 1, i - 1)

[Daniel]

Deine Schleifen starten bei Index "1", ein Array in Delphi startet jedoch - soweit nicht anders angegeben - mit dem Index "0".

[a.def]

Zitat:

Zitat von Daniel (Beitrag 1356479)

Deine Schleifen starten bei Index "1", ein Array in Delphi startet jedoch - soweit nicht anders angegeben - mit dem Index "0".

Das ist vollkommen korrekt. Der Einfachheit halber habe ich meinem dynamischen Array die Länge +1 zugewiesen und starte alle Schleifen bei 1 statt 0 so wie es auch im LUA-Code selber ist.
+1, weil sonst der letzte Buchstabe aufgefressen wird (da ich ja bei 1 beginne).

Vom Prinzip her funktioniert meine Transformation ja. Nur die Reihenfolge ist scheinbar umgedreht oder verdreht.

[brechi]

Du solltest trotzdem das von Daniel umsetzen und beim Stringindex + 1 addieren

Delphi-Quellcode:

len := Length(text);
SetLength(matrix, len)

// ...

// Bubblesort
for i := Low(Matrix) to High(Matrix)-1 do begin
  for j := i+1 to High(Matrix) do begin
  end;
end;

//...

Auch wenn ich nie LUA programmiert habe, der Quellcode von Wikipedia scheint nicht zum Ergebnis zu passen. Lass die 1. Schleife rückwärts laufen, dann sollte es klappen

Delphi-Quellcode:

  for i := High(Matrix) downto Low(Matrix) do
     ///...

Es ist aber egal wie rum die Schleife läuft, durch die Sortierung sollte man in beiden Fällen das richtige Endergebnis erhalten.