Trouver anagrammes intéressants

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

Question

Dites que $ a_1a_2 \ ldots a_n $ et b_1b_2 $ \ ldots b_n $ sont deux chaînes de la même longueur. Un anagramming de deux chaînes est une application bijective $ p: [1 \ ldots n] \ de [1 \ ldots n] $ tel que $ a_i = b_ {p (i)} $ pour chaque $ i $.

Il pourrait y avoir plus d'un anagramming pour la même paire de cordes. Par exemple, si $ a = $ `abcab` et $ b = $ cabab nous $ p_1 [1,2,3,4,5] \ à [4,5,1,2,3] $ et $ p_2 [ 1,2,3,4,5] \ à [2,5,1,4,3] $, entre autres.

Nous allons dire que le poids $ w (p) $ d'un anagramming $ p $ est le nombre de coupes, il faut faire dans la première chaîne pour obtenir des morceaux qui peuvent être réarrangées pour obtenir la deuxième chaîne. Formellement, ce nombre de valeurs de i $ \ in [1 \ ldots n-1] $ dont $ p (i) 1 \ ne p (i + 1) $. Autrement dit, il est le nombre de points où $ p $ fait pas augmentation par exemple exactement 1.Pour, $ w (p_1) = 1 $ et $ w (p_2) = 4 $, parce que $ p_1 coupes de $ 12345 une fois, dans les morceaux 123 et 45 et $ p_2 coupes de $ 12345 quatre fois, en cinq morceaux.

Supposons qu'il existe un anagramming pour deux cordes $ a $ et $ b $. Ensuite, au moins un anagramming doit avoir moins de poids. Disons que ce celui-ci est plus léger . (Il pourrait y avoir plusieurs anagrammings légers,. Je ne me soucie pas parce que je suis intéressé seulement dans les poids)

Question

Je veux un algorithme qui, étant donné deux chaînes pour lesquelles une anagramming existe, efficacement donne le poids exact du plus léger anagramming des deux chaînes. Il est bien si l'algorithme donne aussi un léger anagramming, mais il n'a pas besoin.

Il est une question assez simple pour générer tous les anagrammings et les peser, mais il peut y avoir beaucoup, donc je préférerais une méthode qui trouve anagrammings lumière directement.

Motivation

La raison pour laquelle ce problème est d'intérêt est la suivante. Il est très facile de faire l'ordinateur recherche le dictionnaire et trouver des anagrammes, des paires de mots qui contiennent exactement les mêmes lettres. Mais la plupart des anagrammes produits sont sans intérêt. Par exemple, les plus longs exemples figurent dans le deuxième dictionnaire international de Webster sont:

  

cholecystoduodenostomy
  duodenocholecystostomy

Le problème doit être clair: ce sont sans intérêt car ils admettent un anagramming très léger que le simple échange du cholecysto, duedeno, et les articles de stomy, pour un poids de 2. D'autre part, cet exemple beaucoup plus court est beaucoup plus surprenant et intéressant:

  

côte
  coupe

Ici, le plus léger anagramming a un poids 8.

J'ai un programme qui utilise cette méthode pour trouver des anagrammes intéressantes, à savoir ceux pour lesquels tous les anagrammings sont d'un poids élevé. Mais il le fait en générant et en pesant tous les anagrammings possibles, ce qui est lent.

Était-ce utile?

La solution

Ce problème est connu comme le « problème minimum de partition chaîne commune. » (Plus précisément, la réponse dans le problème de la partition de chaîne commune minimum est égale à la réponse à votre problème plus 1.) Malheureusement, il est NP-difficile, même avec la restriction que chaque lettre se produit au plus deux fois dans chacune des chaînes d'entrée, comme cela est prouvé par Goldstein, Kilman, et Zheng [GKZ05]. Cela signifie qu'aucun algorithme polynomial existe à moins que P = NP. (Bien sûr, si chaque lettre se produit au plus une fois, le problème est trivial parce qu'il n'y a qu'un seul anagramming.)

Du côté positif, les mêmes auteurs [GKZ05] donner un polynôme temps algorithme 1,1037-approximation sous la même restriction. (A « 1.1037- approximation algorithme » signifie un algorithme qui ne peut pas émettre la réponse correcte A mais il est garanti pour délivrer en sortie une valeur B de telle sorte que a = B = 1,1037 a ). Ils donnent également un linéaire à temps algorithme 4-approximation sous la restriction plus faible que chaque lettre se produit au plus trois fois dans chacune des chaînes d'entrée.

[GKZ05] Avraham Goldstein, Petr Kolman, et Jie Zheng. problème de partition chaîne commune minimale: dureté et approximations. électronique Journal of Combinatorics , 12, article R50 2005. http : //www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Autres conseils

Ceci est un suivi à Tsuyoshi réponse de Ito ci-dessus , résumant la partie la plus pertinente de la papier GKZ05 il a cité.

Le document prouve une réduction du problème Maximal ensemble indépendant ( MIS ). Construire un graphe $ G $ dont les sommets sont des paires $ (i, j) de telle sorte que $ $ $ a_i = b_j et a_ {$ i + 1} = {b_ j + 1} $. Se connecter vertices $ (i, j) $ et $ (k, \ ell) $ (où $ i=k $) avec un bord à chaque fois qu'il est impossible qu'un anagramming pourrait cartographier tous $ i \ j mapsto $ et $ i + 1 \ mapsto j + 1 $ et $ k \ mapsto \ ell $ et k $ + 1 \ mapsto \ ell + 1 $. Cela est facile à détecter; une telle cartographie est impossible exactement si l'une des conditions suivantes est remplie:

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

Dites le graphe résultant $ G $ a un ensemble indépendant maximal de $ de taille $. Ensuite, le poids de anagramming minimum est exactement $ n-s-1 $, où $ n $ est la longueur des cordes $ a $ et $ b $. (L'inverse est également titulaire:... Un anagramming faible poids se traduit directement dans un grand SIG pour $ G $ Pour plus de détails, voir pp 4-5 du document)

Par exemple, considérons les deux chaînes yttrious et touristy. Le graphique correspondant a deux sommets, l'un pour la paire de ou partagée et une pour la paire de ri partagée. Il n'y a pas de bord entre les sommets, car il est possible d'avoir une anagramming qui associe à la fois ou à ou et ri à ri; ou on peut vérifier que les trois conditions ci-dessus tout ne. Ainsi, le graphique a évidemment un SIG de 2 $ = taille $ et de poids de anagramming minimum est en effet 8-2-1 = 5, ce qui correspond à la y|t|t|ri|ou|s de anagramming ? de t|ou|ri|s|t|y.

D'autre part, envisager derater et treader. Cette fois, le graphique a trois sommets:

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

2 et 3 sont incompatibles, et 1 et 3 sont incompatibles, mais 1 et 2 sont compatibles. Ainsi, le SIG unique, a une taille $ s = 2 $ et contient les sommets 1 et 2. Le anagramming correspondant du poids 7-2-1 = 4 est der|a|t|e|r ? t|r|e|a|der.

Il ne couvre pas l'algorithme exact que vous aviez à l'esprit (qui la réponse Tsuyoshi Ito fait ), mais essayer d'obtenir au problème sous-jacent de trouver « intéressant » anagrammes ...

Ma première pensée était d'utiliser une variante modifier distance, où les changements atomiques sont pondérés en fonction de leur « interestingness » plutôt que l'habituel « difficulté » ou de « pondération confusability ». Bien sûr, il semble peu probable que vous puissiez efficacement coder les transformations vraiment intéressantes de cette façon, car ils sont susceptibles d'être non locale et donc courir sur les questions NP-complets de MIS, etc.

Ainsi, la réflexion serait de construire un alignement lettre à lettre entre les mots (à la alignements de traduction automatique), puis de marquer eux-mêmes alignements pour « interestingness » (par exemple, en comptant les alignements qui ont des lettres adjacentes à des lettres non adjacents, ou le nombre d'alignements chacun des croix d'alignement, etc;., puis les combiner ou modèle tel via log-linéaire)

Troisième idée est d'abandonner complètement regarder la structure du anagramming lui-même, et regardez plutôt la sémantique des mots. Souvent, ce qui fait un anagram « intéressant » est l'incongruité entre les significations des mots impliqués. Donc, essayez quelque chose comme le calcul de leur distance en WordNet, ou similaire.

Le problème peut être formulée en termes de groupes permutation.

Maintenant, un groupe de permutation contient tous les « anagram bouge », à la fois primitive (permutation de deux lettres) et composite de séquences de mouvements primitifs. Il semble que vous êtes intéressé que dans un sous-ensemble des permutations possibles. Je vais tenter de les définir.

D'abord, rappeler la notation des permutations, à savoir, le soi-disant :

  • $ () $ permutation pas moyen.
  • $ (1) $ 1 moyen est échangé avec 1, qui est aussi pas permutation.
  • $ (12) $ moyens 1 et 2 sont permutées.
  • $ (123) $ 1 remplace moyens 2 qui remplace 3 qui remplace une (une rotation).
  • et donc un

Ces simples 'cycles' sont composés pour décrire les permutations plus complexes.

Il semble que les mouvements qui vous intéressent sont (pour un mot de longueur $ n $):

Ces mouvements constituent la base de votre algorithme. Ce que vous intéresse est de trouver la plus petite séquence de ces mouvements pour passer d'un mot à l'autre.

Je ne sais pas tout algorithme pour calculer ce, en dehors de la recherche de la force brute, mais au moins il y a une vision plus claire (je l'espère) description de ce que les mouvements primitifs sont. (Et peut-être quelques-uns du groupe théoricienne parmi nous peut pointer vers un algorithme approprié.)

Pour cholecystoduodenostomy / duodenocholecystostome, je remarque que si vous avez attribué un numéro à chaque caractère décrivant à quel point il a été déplacé en tant que delta, vous auriez quelque chose comme 7 7 8, puis de -7s, puis 6 des 0. Ce n'est pas juste parce que certains caractères peuvent avoir été répétées (la deuxième c ne se avança 2, pas de retour 7) etc mais toujours très « longueur de course codable » parce que vous voyez les mêmes deltas de suite.

Comparer à côte / section où vous voyez quelque chose comme (2) (+ 5) (+ 5) (- 3) (- 1) (+ 3) .... beaucoup moins "RLL codable".

Peut-être le caractère aléatoire des deltas pourrait vous donner un « score » quant à la façon intéressant est l'anagramme?

Non affilié à cs.stackexchange
scroll top