AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Burrows-Wheeler-Transformation nach Wikipedia

Ein Thema von a.def · begonnen am 18. Dez 2016 · letzter Beitrag vom 18. Dez 2016
Antwort Antwort
a.def
(Gast)

n/a Beiträge
 
#1

Burrows-Wheeler-Transformation nach Wikipedia

  Alt 18. Dez 2016, 00:35
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
  Mit Zitat antworten Zitat
brechi

Registriert seit: 30. Jan 2004
823 Beiträge
 
#2

AW: Burrows-Wheeler-Transformation nach Wikipedia

  Alt 18. Dez 2016, 09:50
Ich hab mich jetzt nicht genau mit dem Algorithmus auseinandergesetzt aber:

1) der 2. Schritt sortiert den Text

d.h. statt 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;

Geändert von brechi (18. Dez 2016 um 09:52 Uhr)
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#3

AW: Burrows-Wheeler-Transformation nach Wikipedia

  Alt 18. Dez 2016, 10:35
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)
  Mit Zitat antworten Zitat
Daniel
(Co-Admin)

Registriert seit: 30. Mai 2002
Ort: Hamburg
13.919 Beiträge
 
Delphi 10.4 Sydney
 
#4

AW: Burrows-Wheeler-Transformation nach Wikipedia

  Alt 18. Dez 2016, 10:56
Deine Schleifen starten bei Index "1", ein Array in Delphi startet jedoch - soweit nicht anders angegeben - mit dem Index "0".
Daniel R. Wolf
mit Grüßen aus Hamburg
  Mit Zitat antworten Zitat
a.def
(Gast)

n/a Beiträge
 
#5

AW: Burrows-Wheeler-Transformation nach Wikipedia

  Alt 18. Dez 2016, 10:59
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.
  Mit Zitat antworten Zitat
brechi

Registriert seit: 30. Jan 2004
823 Beiträge
 
#6

AW: Burrows-Wheeler-Transformation nach Wikipedia

  Alt 18. Dez 2016, 13:00
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.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 06:24 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz