Interessante Anagramme finden

cs.stackexchange https://cs.stackexchange.com/questions/2259

Frage

Sagen Sie, dass $ a_1a_2 ldots a_n $ und $ b_1b_2 ldots b_n $ zwei Strings derselben Länge sind. Ein Anagramming von zwei Zeichenfolgen ist eine bijektive Zuordnung $ p: [1 ldots n] to [1 ldots n] $ so, dass $ a_i = b_ {p (i)} $ für jeden $ i $.

Es könnte mehr als eine Anagramming für das gleiche Paar Strings geben. Zum Beispiel, wenn $ A = $ `~ abcab` und $ b = $cabab Wir haben $ P_1 [1,2,3,4,5] bis [4,5,1,2,3] und $ P_2 [1,2,3,4,5] bis [2,5, $ P_2, $ P_2, [2,5, 1,4,3] $ unter anderem.

Wir werden das sagen, das Gewicht $ w (p) $ von A Anagramming $ p $ ist die Anzahl der Kürzungen, die man in der ersten Saite machen muss, um Stücke zu erhalten, die neu arrangiert werden können, um die zweite Zeichenfolge zu erhalten. Formal, dies ist die Anzahl der Werte von $ i in [1 ldots n-1] $, für die $ p (i) +1 ne p (i+1) $. Das heißt, es ist die Anzahl der Punkte, an denen $ P $ tut nicht Erhöhen Sie genau 1. Beispiel zum Beispiel, $ W (p_1) = 1 $ und $ W (p_2) = 4 $, weil $ p_1 $ schneidet 12345 Einmal in die Stücke 123 und 45, und $ p_2 $ Cuts 12345 Viermal in fünf Stücke.

Angenommen, es gibt eine Anagramming für zwei Saiten $ a $ und $ B $. Dann muss mindestens ein Anagramming am wenigsten Gewicht haben. Nehmen wir an, dies ist dieser ist Leicht. (Es könnte mehrere leichteste Anagrammings geben; es ist mir egal, weil ich nur an den Gewichten interessiert bin.)

Frage

Ich möchte einen Algorithmus, der angesichts von zwei Saiten, für die ein Anagramming existiert, effizient existiert ergibt das genaue Gewicht der leichtesten Anagramming der beiden Saiten. Es ist in Ordnung, wenn der Algorithmus auch eine leichteste Anagramming liefert, aber es muss nicht erforderlich.

Es ist eine ziemlich einfache Angelegenheit, alle Anagrammings zu erzeugen und sie zu wiegen, aber es kann viele geben, daher würde ich eine Methode bevorzugen, die leichte Anagrammings direkt findet.

Motivation

Der Grund, warum dieses Problem von Interesse ist, ist wie folgt. Es ist sehr einfach, das Computer das Wörterbuch durchzuführen und Anagramme zu finden, Wörterpaare, die genau die gleichen Buchstaben enthalten. Aber viele der produzierten Anagramme sind uninteressant. Zum Beispiel sind die längsten Beispiele, die im zweiten internationalen Wörterbuch von Webster zu finden sind:

Cholecystoduodenostomie
Duodenocholecystostomie

Das Problem sollte klar sein: Diese sind uninteressant, weil sie eine sehr leichte Anagrammierung zugeben, die einfach das austauscht cholecysto, duedeno, und stomy Abschnitte für ein Gewicht von 2. Andererseits ist so viel kürzeres Beispiel viel überraschender und interessanter:

Küste
Abschnitt

Hier hat die leichteste Anagramming Gewicht 8.

Ich habe ein Programm, das diese Methode verwendet, um interessante Anagramme zu lokalisieren, nämlich diejenigen, für die alle Anagrammings von hohem Gewicht sind. Aber dies geschieht, indem alle möglichen Anagrammings erzeugt und abwägen, was langsam ist.

War es hilfreich?

Lösung

Dieses Problem wird als „Mindestproblem für gemeinsame String -Partition“ bezeichnet. (Genauer gesagt entspricht die Antwort im Mindestproblem der gemeinsamen String-Partition der Antwort in Ihrem Problem plus 1.) Leider ist es NP-HART, selbst wenn die Einschränkung, dass jeder Buchstaben höchsten wird von Goldstein, Kilman und Zheng [GKZ05] bewiesen. Dies bedeutet, dass kein Polynom-Zeit-Algorithmus existiert, es sei denn, P = NP. (Wenn jeder Buchstabe höchstens einmal auftritt, ist das Problem trivial, da nur eine Anagramming vorliegt.)

Positiv zu vermerken ist, dass dieselben Autoren [GKZ05] unter derselben Einschränkung einen Polynom-Zeit-1,1037-Anerkennungsalgorithmus geben. (A “1.1037-Näherungsalgorithmus”Bedeutet einen Algorithmus, der möglicherweise nicht die richtige Antwort ausgibt EIN wird jedoch garantiert einen Wert ausgeben B so dass EIN ≤ B ≤ 1.1037EIN.) Sie geben auch einen 4-Anerkennungsalgorithmus für lineare Zeit mit einer schwächeren Einschränkung, dass jeder Buchstabe höchstens dreimal in jedem der Eingangszeichenfolgen auftritt.

GKZ05] Avraham Goldstein, Petr Kolman und Jie Zheng. Mindestproblem für String Partition: Härte und Annäherungen. Elektronisches Journal of Combinatorics, 12, Artikel R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Andere Tipps

Dies ist ein Follow -up zu Tsuyoshi Itos Antwort oben, Zusammenfassung des relevantesten Teils der GKZ05 Papier Er zitierte.

Das Papier zeigt eine Reduzierung des maximalen unabhängigen Satzes (Mis) Problem. Konstruieren Sie ein Diagramm $ g $, dessen Eckpunkte Paare $ (i, j) $ sind, so dass $ a_i = b_j $ und $ a_ {i+1} = b_ {j+1} $. Verbinden Sie Scheitelpunkte $ (i, j) $ und $ (k, ell) $ (wobei $ i d $ $) mit einer Kante mit einem Vorsprung ist, wenn es unmöglich ist, dass eine Anagrammierung alle $ i MapSto J $ und $ i+ zuordnen kann 1 MAPSTO J+1 $ und $ K MAPSTO ELL $ und $ K+1 MAPSTO ell+1 $. Dies ist leicht zu erkennen; Eine solche Zuordnung ist genau, ob einer der folgenden Aussagen gilt:

  1. $ i = k $ und $ j ne ell $
  2. $ i+1 = k $ und $ j+1 ne ell $
  3. $ i+1

Angenommen, das resultierende Diagramm $ g $ hat eine maximale unabhängige Größe von Größe $ S $. Dann beträgt das minimale Anagramming-Gewicht genau $ NS-1 $, wobei $ n $ die Länge der Zeichenfolgen $ a $ und $ B $ ist. (Das Converse gilt auch: Eine niedrige Anagramming führt direkt in einen großen MIS für $ g $. Für Einzelheiten siehe S. 4–5 des Papiers.)

Betrachten Sie zum Beispiel die beiden Saiten yttrious und touristy. Die entsprechende Grafik hat zwei Eckpunkte, eine für die gemeinsam genutzten ou Paar und eines für die gemeinsam genutzten ri Paar. Es gibt keine Kante zwischen den Eckpunkten ou zu ou und ri zu ri; Oder man kann überprüfen, ob die drei Bedingungen vor allem fehlschlagen. Das Diagramm hat also offensichtlich einen MIS-von Größe $ S = 2 $ und das minimale Anagramming-Gewicht beträgt in der Tat 8-2-1 = 5, was dem Anagramming entspricht y|t|t|ri|ou|s ↔ t|ou|ri|s|t|y.'

Andererseits überlegen derater und treader. Diesmal enthält die Grafik drei Eckpunkte:

  1. DErater + treaDEr
  2. dERater + treadER
  3. deratER + treadER

2 und 3 sind inkompatibel und 1 und 3 sind unvereinbar, 1 und 2 sind jedoch kompatibel. Der eindeutige MIS hat also die Größe $ s = 2 $ und enthält die Eckpunkte 1 und 2. Die entsprechende Anagrammierung von Gewicht 7-2-1 = 4 ist der|a|t|e|r ↔ t|r|e|a|der.

Es deckt nicht den genauen Algorithmus ab, den Sie im Sinn hatten (welche Tsuyoshi Itos Antwort tut es), aber versuchen, das zugrunde liegende Problem zu finden, "interessante" Anagramme zu finden ...

Mein erster Gedanke war, eine Variation der Bearbeitungsdistanz zu verwenden, bei der die atomaren Veränderungen eher nach ihrer "Interessante" als nach den üblichen "Schwierigkeitsgrad" oder "Verwechseldigkeit" gewichtet werden. Natürlich ist es unwahrscheinlich, dass Sie die wirklich interessanten Transformationen auf diese Weise effizient codieren können, da sie wahrscheinlich nicht lokal sind und daher auf die NP-Complete-Themen von MIS stoßen usw.

Der zweite Gedanke wäre also, eine Buchstabe-zu-Buch-Ausrichtung zwischen den Wörtern (à la Maschinenübersetzungsausrichtungen) zu konstruieren und dann die Ausrichtungen selbst für "interessante benachbarte Buchstaben oder wie viele Ausrichtungen jede Ausrichtung überschreitet usw. und dann alle über loglineares Modell oder dergleichen kombinieren).

Die dritte Idee besteht darin, die Struktur der Anagramming selbst vollständig aufzugeben und stattdessen die Semantik der Wörter zu betrachten. Oft macht ein Anagramm "interessant" die Inkongruenz zwischen den Bedeutungen der beteiligten Wörter. Probieren Sie also so etwas wie das Berechnen ihrer Distanz in WordNet oder ähnlich.

Das Problem kann in Bezug auf die formuliert werden Permutationsgruppen.

Jetzt enthält eine Permutationsgruppe alle "Anagram -Moves", sowohl primitive (zwei Buchstaben) als auch zusammengesetzt von Sequenzen primitiver Bewegungen. Es scheint, dass Sie nur an einer Teilmenge der möglichen Permutationen interessiert sind. Ich werde versuchen, diese zu definieren.

Erinnern Sie sich zunächst an die Notation für Permutationen, nämlich die sogenannten Zyklusnotation:

  • $ () $ bedeutet keine Permutation.
  • $ (1) $ bedeutet, dass 1 mit 1 getauscht wird, was auch keine Permutation ist.
  • $ (12) $ bedeutet 1 und 2 werden ausgetauscht.
  • $ (123) $ bedeutet 1 ersetzt 2, was 3 ersetzt, was 1 (eine Rotation) ersetzt.
  • und so weiter

Diese einfachen "Zyklen" sind zusammengesetzt, um komplexere Permutationen zu beschreiben.

Es scheint, dass die Bewegungen, an denen Sie interessiert sind, sind (für ein Wort mit Länge $ n $):

  • Swaps von Paaren einzelner Zeichen: Dies sind die Swaps wie $ (12) $
  • Swaps von Paaren von 2 aufeinanderfolgenden Zeichen: Dies sind Permutationen des Formulars $ (a b) (a+1 b+1) $, wobei $ a> 0 $ und $ B
  • ...
  • Swaps von Paaren aufeinanderfolgende Zeichen: Dies sind Permutationen der Form $ (a b) (a+1 b+1) cdots (a+i-1 b+i-1) $ wobei $ a> 0 $, $ a+i-1 le b $ und $ b+i-1 le n $.

Diese Bewegungen bilden die Grundlage für Ihren Algorithmus. Was Sie interessiert, ist die kleinste Sequenz dieser Bewegungen, um sich von einem Wort zum nächsten zu bewegen.

Ich kenne keinen Algorithmus, um dies zu berechnen, abgesehen von der Brute Force -Suche, aber zumindest gibt es jetzt eine klarere (ich hoffe) Beschreibung der primitiven Bewegungen. (Und vielleicht können ein Gruppentheoretiker unter uns auf einen geeigneten Algorithmus hinweisen.)

Für Cholecystoduodenostomie/Duodenocholecystostome stelle ich fest, dass Sie, wenn Sie jedem Charakter eine Nummer zuweisen würden, wie viel es als Delta bewegt wurde, etwas wie 7 7, dann 8 -7s, dann 6 0er haben. Das ist nicht richtig, da einige Zeichen möglicherweise wiederholt wurden (das zweite C hat sich nur 2, nicht zurück 7) usw., aber immer noch sehr "länge codable", da Sie dieselben Deltas in einer Reihe sehen.

Vergleichen Sie mit Coastline/Sectional, wo Sie so etwas wie (+2) (+5) (+5) (-3) (-1) (+3) .... viel weniger "Lauflänge codierbar" sehen.

Vielleicht könnte die Zufälligkeit der Deltas Ihnen eine "Punktzahl" geben, wie interessant das Anagramm ist?

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top