Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » minimale Anzahl an Operationen, um ein Palindrom zu erhalten
Autor
Universität/Hochschule minimale Anzahl an Operationen, um ein Palindrom zu erhalten
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Themenstart: 2021-05-15

Hallo, Gegeben ist ein Eingabe String. Nun soll die minimale Anzahl an Operationen (Zeichen einfügen, Zeichen löschen, Zeichen ändern), die den String in ein Palindrom verwandeln, ausgegeben werden. Ich habe das ganze mit dynamischer Programmierung gelöst, es ähnelt dem klassischen Levensthein Problem, allerdings können die Strings bis zu 1000 Zeichen groß sein und ein zweidimensionales Array ist dafür zu langsam. Hat jemand eine Idee, wie man es ohne zweidimensionales Array und dabei schneller lösen kann? Danke!


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.1, eingetragen 2021-05-15

Anstatt das volle Quadrat zu betrachten, könntest Du Dich auf einen beschränkten Bereich um die Diagonale konzentrieren. Inhaltlich entspräche das der Vorgabe, dass man in der einen "Hälfte" des Strings nicht deutlich mehr Zeichen löschen (bzw. einfügen) darf als in der anderen Hälfte. Natürlich lassen sich Beispiel konstruieren, bei denen die optimale Lösung dann nicht mehr gefunden wird, im Allgemeinen sollte man aber zu brauchbaren Ergebnissen kommen.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.2, vom Themenstarter, eingetragen 2021-05-17

Das hilft mir leider nicht sonderlich, aber danke für deine Antwort!


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.3, eingetragen 2021-05-18

Analog zum Levenshtein-Problem kann man vermutlich auf das zweidimensionale Array verzichten. Asymptotisch bliebe die Laufzeit damit jedoch quadratisch. Andererseits sollte das für Strings der Länge 1000 Zeichen kein Problem sein. (wenige Millisekunden Laufzeit auf normalen Plattformen)


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.4, eingetragen 2021-05-19

Ich habe es mal in Java implementiert. Algorithmus ist von StackOverflow. Diagonalwerte oder deren Nachbarn aus der Levenshteindistanzmatrix zwischen Wort und dessen Umkehrung ergeben die minimale Palindromdistanz. Implementierung mit voller Matrix: palindromDistance(abc) = 1 palindromDistance(abcdcdcbb) = 1 palindromDistance(abcd) = 2 palindromDistance(mohammadsajjadhossain) = 8 // Stackoverflow Testcase palindromDistance(randomWordOfLength=10) in 0ms. palindromDistance(randomWordOfLength=20) in 0ms. palindromDistance(randomWordOfLength=100) in 3ms. palindromDistance(randomWordOfLength=1000) in 36ms. palindromDistance(randomWordOfLength=2000) in 72ms. palindromDistance(randomWordOfLength=5000) in 623ms. palindromDistance(randomWordOfLength=10000) in 4379ms. Speichereffiziente Zwei-Reihen-Variante: efficientDistance(abc) = 1 efficientDistance(abcdcdcbb) = 1 efficientDistance(abcd) = 2 efficientDistance(mohammadsajjadhossain) = 8 efficientDistance(randomWordOfLength=10) in 0ms. efficientDistance(randomWordOfLength=20) in 0ms. efficientDistance(randomWordOfLength=100) in 3ms. efficientDistance(randomWordOfLength=1000) in 33ms. efficientDistance(randomWordOfLength=2000) in 44ms. efficientDistance(randomWordOfLength=5000) in 195ms. efficientDistance(randomWordOfLength=10000) in 822ms. efficientDistance(randomWordOfLength=20000) in 3287ms. efficientDistance(randomWordOfLength=50000) in 20188ms. efficientDistance(randomWordOfLength=100000) in 73963ms.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.5, vom Themenstarter, eingetragen 2021-05-19

Danke für deine Mühe, ich habe den Post auch gelesen :)


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.6, eingetragen 2021-05-19

\quoteon(2021-05-17 16:41 - dvdlly in Beitrag No. 2) Das hilft mir leider nicht sonderlich, aber danke für deine Antwort! \quoteoff Vielleicht könntest Du ja erläutern, warum Dir das nicht hilft. Worin Dein Problem besteht, ist (mir) noch nicht klar geworden. Sind Dir 0,03 Sekunden zu lang? [Die Antwort wurde nach Beitrag No.4 begonnen.]


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.7, vom Themenstarter, eingetragen 2021-05-19

Tut mir Leid, das hätte ich an der Stelle wohl erwähnen sollen. Das Problem ist, dass als Eingabe auch eher konstruierte Strings vorkommen, so dass man mit diesem Vorgehen nicht die minimale Anzahl an Operationen ausgibt - so wie du es beschrieben hast. Allerdings ist es zwingend notwendig, dass der Algorithmus korrekt ist.


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3042
  Beitrag No.8, eingetragen 2021-05-19

Der Algorithmus von Stackoverflow IST korrekt. Er liefert immer die minimale Editierdistanz in quadratischer Worst-Case-Laufzeit. Edit: Poste doch einfach mal deine Implementierung und Testcases. Dann können wir Ergebnisse und Laufzeiten vergleichen.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.9, vom Themenstarter, eingetragen 2021-05-19

Ich habe mich auf das von Kitaktus vorgeschlagene Verfahren bezogen. Ich bin davon ausgegangen, dass er mit dem Einwand "...natürlich lassen sich Beispiele konstruieren, bei denen die optimale Lösung nicht gefunden wird..." Recht hat. Falls er eigentlich den gleichen Algorithmus wie SO meinte, dann hast du natürlich Recht.


   Profil
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.10, eingetragen 2021-05-19

Eine exakte Lösung ohne quadratische Laufzeit ist wohl nicht möglich. Wenn Du also schreibst: "Mein Algorithmus hat quadratische Laufzeit, das ist mir aber zu langsam." dann gibt es mehrer Interpretationen, dafür was Du eigentlich willst: a) einen deutlich schnelleren aber nicht exakten Algorithmus b) einen exakten Algorithmus mit besserem asymptotischem Laufzeitverhalten, den es wohl nicht gibt c) einen exakten Algorithmus mit gleichem asymptotischem Laufzeitverhalten, aber besserem Vorfaktor - schwierig, da Du nicht viel über Deine Algorithmus aussagst d) eine bessere Implementierung Es ist etwas mühsam, wenn Du nicht genau sagst, was Du willst.


   Profil
dvdlly
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 28.12.2016
Mitteilungen: 199
  Beitrag No.11, vom Themenstarter, eingetragen 2021-05-20

Tut mir Leid, ich werde in Zukunft darauf achten etwaiges kenntlich werden zu lassen :)


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6908
Wohnort: Niedersachsen
  Beitrag No.12, eingetragen 2021-05-22

Danke :)


   Profil
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]