Was ein Palindrom-Prüfer entscheiden muss, bevor er antworten kann

Die Frage ist unbestimmt, bis vier Entscheidungen gefallen sind

Ein Palindrom liest sich vorwärts wie rückwärts gleich. Diese Definition ist nur für eine Folge nackter Kleinbuchstaben vollständig, und fast kein echter Text ist eine solche. Sobald ein Satz Großbuchstaben, Leerzeichen, Kommas oder Akzente enthält, zerfällt die Frage in vier kleinere: Ist ein Großbuchstabe gleich seiner Kleinform, zählen Leerzeichen als Zeichen, zählen Satzzeichen, und ist ein akzentuierter Buchstabe derselbe Buchstabe wie seine Grundform? Vier Ja-Nein-Antworten, sechzehn Kombinationen, und die maßgeblichen bilden eine verschachtelte Folge, in der jede mehr Sätze zulässt als die vorige.

Die Tabelle oben ist genau diese Folge, angewandt auf sechs Sätze, ausgeführt statt behauptet. Lies sie Spalte für Spalte, und jede Spalte verdient ihren Platz: Leerraum allein befördert den italienischen Satz, Satzzeichen allein den englischen, und das Falten diakritischer Zeichen allein den französischen, den spanischen und den portugiesischen. Ein Prüfer, der eine dieser Entscheidungen fest verdrahtet, beantwortet eine andere Frage als die gestellte - und zwar stillschweigend.

Vier Sätze, vier verschiedene Haltepunkte

Beginnen wir mit dem englischen Satz, denn ihn zitiert jeder. A man, a plan, a canal: Panama ist so getippt kein Palindrom - das große A am einen Ende steht einem kleinen a am anderen gegenüber. Falte die Schreibung, und es ist immer noch keines: Die Leerzeichen fallen nicht symmetrisch. Entferne den Leerraum, und es ist immer noch keines, denn ein Komma und ein Doppelpunkt bleiben. Entferne zusätzlich die Satzzeichen, und endlich ist es eines: amanaplanacanalpanama, einundzwanzig Zeichen, symmetrisch. Drei Regeln mussten eingeschaltet werden, bevor die berühmte Antwort erschien.

Der deutsche Satz Ein Esel lese nie hält einen Schritt früher an als alles andere in der Tabelle. Falte die Schreibung, und er ist bereits ein Palindrom: einesellesenie liest sich in beide Richtungen gleich, und der Satz mit seinen Leerzeichen ebenfalls, denn seine Wortlängen - drei, vier, vier, drei - sind von Bauart her symmetrisch. Ein Prüfer, der immer den Leerraum entfernt, gibt hier die richtige Antwort, aber aus dem falschen Grund, und er wird dir nie sagen können, dass dieser Satz im stärkeren Sinn ein Palindrom ist, bei dem auch die Leerzeichen stimmen. Das zweite deutsche Beispiel, O, Genie, der Herr ehre dein Ego!, braucht nur die Satzzeichenregel.

Die drei romanischen Sätze brauchen alle die vierte Regel und scheitern an jeder früheren. Ésope reste ici et se repose ergibt mit entfernten Satzzeichen, aber erhaltenen Akzenten die Kette ésoperesteicietserepose, deren Umkehrung esoperesteicietsereposé lautet - der Akzent ist vom ersten Zeichen ans letzte gewandert, und die Ketten unterscheiden sich. Faltet man das diakritische Zeichen, werden beide zu esoperesteicietserepose. Dasselbe gilt für dábale…, dessen Umkehrung auf á endet, und für socorram-me…, wo das ô an der falschen Stelle landet. Was das praktisch bedeutet: Ein für das Englische gebauter Prüfer meldet drei einwandfreie europäische Palindrome als Fehlschlag - ohne jede Fehlermeldung.

Auch das Umkehren einer Zeichenkette ist nicht eine Operation

Jeder Palindrom-Prüfer vergleicht einen Text mit seiner Umkehrung, und in dieser Umkehrung steckt die zweite Hälfte des Problems. Die Einzeiler-Umkehrung, die alle schreiben - s.split('').reverse().join('') -, kehrt UTF-16-Codeeinheiten um. Ein Begleitartikel dieser Reihe behandelt, was ein Zeichen ist; die Folge hier lautet: Jedes Zeichen außerhalb der mehrsprachigen Basisebene wird in zwei Codeeinheiten gespeichert, und sie einzeln umzukehren vertauscht das Paar. Kehr ça va 😀 so um, und das Ergebnis enthält ein niedriges Ersatzzeichen gefolgt von einem hohen: acht Codepunkte statt sieben, und isWellFormed() liefert falsch. Auf dem Bildschirm steht ein Ersatzkästchen.

Die übliche Abhilfe kehrt stattdessen Codepunkte um: [...s].reverse().join(''). Das repariert das Emoji - ça va 😀 wird zu 😀 av aç, weiterhin sieben Codepunkte - und reicht immer noch nicht. Nimm José in zerlegter Form, wo das é ein e mit nachfolgendem kombinierendem Akut ist: fünf Codepunkte, vier Grapheme. Die Umkehrung der Codepunkte stellt den kombinierenden Akzent voran, wo er keinen Buchstaben mehr zum Andocken hat, und lässt ein nacktes e zurück: Das Ergebnis hat fünf Grapheme, wo vier waren, und der Akzent zeichnet sich über nichts. Der deutsche Fall ist noch anschaulicher. Zerlege Grüße und kehr die Codepunkte um, und du erhältst eß̈urG: Der Umlaut ist vom u abgesprungen und auf dem ß gelandet.

Emoji, die aus mehreren Codepunkten bestehen, scheitern genauso. Die Familie 👨‍👩‍👧 besteht aus drei Personen, verbunden durch Nullbreiten-Verbinder: sechzehn Codeeinheiten, dreizehn Codepunkte, ein Graphem. Die Umkehrung ihrer Codepunkte erzeugt eine Familie, die als 👧‍👩‍👨 erscheint - Tochter, Mutter, Vater -, also ein anderes Emoji und kein umgekehrtes; die Umkehrung ihrer Codeeinheiten erzeugt etwas, das in Bruchstücken erscheint. Nur die Umkehrung nach Graphemgruppen lässt sie unversehrt.

Nach Graphemgruppen umkehren

Eine Graphemgruppe ist Unicodes Name für das, was eine Leserin ein Zeichen nennt: ein Grundbuchstabe samt allem, was sich damit verbindet, oder eine ganze Emoji-Sequenz. JavaScript legt die Segmentierungsregeln über Intl.Segmenter direkt offen, und eine korrekte Umkehrung braucht drei Zeilen: einen Segmentierer mit der Granularität 'grapheme' bauen, seine Ausgabe ausbreiten, umkehren, zusammenfügen. Bei allen obigen Beispielen tut sie das Richtige: Das Emoji überlebt, die Familie bleibt eine Familie, und das zerlegte Grüße kommt als eßürG zurück, mit dem Umlaut weiterhin auf seinem u.

Darunter verbirgt sich eine Normalisierungsentscheidung, und das französische Wort été zeigt sie in einer Zeile. In zusammengesetzter Form sind es drei Codepunkte, und ihre Umkehrung gibt été zurück: ein Palindrom. In zerlegter Form sind es fünf Codepunkte, ihre Umkehrung ergibt eine Kette mit falsch platzierten Akzenten, und dasselbe sichtbare Wort gilt als kein Palindrom. Die Umkehrung nach Graphemgruppen liefert in beiden Formen die richtige Antwort - vergleicht man die beiden Formen jedoch miteinander, bleiben sie ungleich, weshalb ein Prüfer zuerst nach NFC normalisieren sollte. Der Artikel dieser Reihe über Akzente behandelt die Formen NFC und NFD vollständig.

Ein Zahlenpalindrom ist ein anderes Problem

Zahlen sehen nach dem einfachen Fall aus und sind es nicht. Ein Zahlenpalindrom ist eine Eigenschaft eines Werts in einer Basis, ein Textpalindrom eine Eigenschaft einer Darstellung. 12321 ist im Zehnersystem ein Palindrom. Für eine Leserin dargestellt hört es das in jeder Locale dieses Artikels auf zu sein: 12,321 umgekehrt ergibt 123,21 im Englischen, 12.321 umgekehrt ergibt 123.21 im Deutschen, Spanischen und Italienischen, und 12 321 umgekehrt ergibt 123 21 im Französischen und Portugiesischen - wobei das Trennzeichen im Französischen ein schmales geschütztes Leerzeichen U+202F und im Portugiesischen ein gewöhnliches geschütztes Leerzeichen U+00A0 ist, zwei unsichtbare Zeichen, die ein naiver Vergleich ohnehin als verschieden behandelt.

Aus derselben Unterscheidung folgen drei weitere Unterschiede. Ein Vorzeichen ist ein Zeichen, aber keine Ziffer: -121 kehrt sich als Text zu 121- um und scheitert, während als Wert die Frage, ob eine negative Zahl ein Palindrom sein kann, eine Konvention ist, die man wählen muss. Ein Dezimaltrennzeichen ist ebenfalls ein Zeichen: 0,1 kehrt sich zu 1,0 um, zwei verschiedene Ketten, die verschiedene Werte bezeichnen. Und führende Nullen gibt es im Text, nicht in der Zahl: 010 ist als Text ein Palindrom, als Zahl ist es 10 und keines. Ist deine Eingabe eine Zahl, entferne die Formatierung und arbeite auf den Ziffern; ist sie ein Text, der zufällig numerisch aussieht, sag es und behandle ihn als Text.

Was zu bauen ist, der Reihe nach

Das Rezept, das alle sechs Sprachen übersteht, ist kurz. Normalisiere zuerst nach NFC, damit derselbe sichtbare Text stets dieselbe Darstellung hat. Wende dann die Regeln an, die du entschieden haben und benennen kannst: Kleinschreibung, Leerraum entfernen, alles entfernen, was weder Buchstabe noch Ziffer ist, diakritische Zeichen falten, indem du zerlegen und die Marken entfernst. Kehr danach nach Graphemgruppen um und vergleiche. Vier Schritte, und jeder davon ist eine Entscheidung, die du in der Oberfläche zeigen kannst, statt sie als Voreinstellung im Code zu verstecken.

Eine letzte Bemerkung zur Umkehrung, denn sie ist widersinnig und verbirgt Fehler. Zweimaliges Umkehren liefert stets die ursprüngliche Zeichenkette zurück, gleich nach welcher Einheit man umkehrt - Codeeinheiten, Codepunkte und Grapheme sind allesamt Involutionen auf der Folge, die sie bearbeiten. Ein Hin-und-zurück-Test sagt also nichts darüber aus, ob deine Umkehrung korrekt ist. Der einzige Test, der die kaputten Fälle fängt, ist der Blick auf das Zwischenergebnis, und der schnellste Blick ist das Zählen der Grapheme davor und danach: bei einem zerlegten José sind es vier und fünf.

Häufige Fragen

Ist A man, a plan, a canal: Panama nun ein Palindrom oder nicht?

Nach der üblichen Regel ja; so getippt nein. Falte die Schreibung, entferne die Leerzeichen und die Satzzeichen, und es wird amanaplanacanalpanama, das symmetrisch ist. Behalte eines der drei, ist es keines. Das ist keine Fangfrage - es ist genau das, was die Formel „unter Missachtung von Schreibung, Leerzeichen und Satzzeichen“ in jeder Lehrbuchdefinition leistet, und ein Werkzeug, das die drei Regeln einzeln schalten lässt, sagt die Wahrheit, statt sie zu verbergen.

Warum ist beim Umkehren meines Textes ein kaputtes Kästchen erschienen?

Weil die Umkehrung auf UTF-16-Codeeinheiten gearbeitet hat und dein Text ein Zeichen außerhalb der mehrsprachigen Basisebene enthielt - ein Emoji, ein seltenes CJK-Ideogramm, ein mathematisches Symbol. Diese werden als Ersatzzeichenpaar gespeichert, und die beiden Hälften umzukehren erzeugt eine Folge, die keine Schriftart darstellen kann. Prüfe es mit isWellFormed(), das bei einer solchen Kette falsch liefert, und stell die Umkehrung mit Intl.Segmenter auf Graphemgruppen um.

Soll ein Palindrom-Prüfer Akzente ignorieren?

Er sollte die Wahl anbieten und standardmäßig falten, denn die Wortspieltradition im Französischen, Spanischen und Portugiesischen behandelt é und e als denselben Buchstaben. Ohne Faltung hören drei der sechs Sätze der Tabelle auf, Palindrome zu sein: Ésope reste ici et se repose, Dábale arroz a la zorra el abad und Socorram-me, subi no ônibus em Marrocos scheitern allesamt an ihrem ersten und letzten Zeichen. Falte, indem du nach NFD zerlegst, die kombinierenden Marken löschen und wieder zusammensetzen - der Akzent-Artikel dieser Reihe erklärt, warum das nicht dasselbe ist wie Buchstaben einzeln zu ersetzen.

Ist 12321 ein Palindrom?

Als Zahl im Zehnersystem ja. Als dargestellter Text nein - in jeder Locale dieses Artikels. Für eine Leserin formatiert wird sie zu 12,321 im Englischen und zu 12.321 oder 12 321 anderswo, und die Umkehrung dieser Ketten ergibt 123,21, 123.21 und 123 21. Prüfe Zahlen, arbeite auf den Ziffern und entscheide ausdrücklich über Vorzeichen, Dezimaltrennzeichen und führende Nullen: -121 kehrt sich zu 121- um, 0,1 zu 1,0, und 010 ist als Text ein Palindrom, während die bezeichnete Zahl 10 ist.

Gibt zweimaliges Umkehren immer das Original zurück?

Ja, und genau deshalb ist ein Hin-und-zurück-Test hier wertlos. Die Umkehrung nach Codeeinheiten, nach Codepunkten und nach Graphemgruppen sind allesamt Involutionen: Wende eine davon zweimal an, und du erhältst die Eingabe zurück, selbst wenn die einfache Umkehrung dazwischen eine kaputte Kette erzeugt hat. Prüfe stattdessen das Zwischenergebnis - vergleiche die Graphemzahl davor und danach oder rufe isWellFormed() darauf auf.

Kann ein einzelnes Wort ohne all diese Regeln ein Palindrom sein?

Ja, und das sind die einzigen Fälle, in denen die Frage eine Antwort hat. Durchgehend kleingeschriebene ASCII-Wörter wie racecar, radar, kayak, das französische ressasser, das spanische reconocer, das italienische onorarono und das portugiesische reviver sind ganz ohne Regelwerk Palindrome - Zeichen für Zeichen überprüft. Schreibe sie groß an, brauchst du die Schreibungsregel: Reliefpfeiler, Rentner und Lagerregal sind erst Palindrome, sobald der Anfangsbuchstabe gefaltet ist, und das ist eine Regel, nicht vier.