Encontrar anagramas interesantes

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

Pregunta

decir que a_1a_2 $ \ ldots a_n $ y $ b_1b_2 \ ldots $ b_n son dos cadenas de la misma longitud. Un anagramico de dos cadenas es un biyectiva mapeo $ p: [1 \ ldots n] \ a [1 \ ldots n] $ tal que $ a_i = b_ {p (i)} $ por cada $ i $.

Es posible que haya más de un anagramico para el mismo par de cuerdas. Por ejemplo, si $ a = $ `abcab` y $ b = $ cabab tenemos $ p_1 [1,2,3,4,5] \ a [4,5,1,2,3] $ y $ p_2 [ 1,2,3,4,5] \ a [2,5,1,4,3] $, entre otros.

Vamos a decir que el peso $ w (p) $ de un anagramico $ P $ es el número de cortes se debe hacer en la primera cadena de obtener trozos que se pueden reorganizar para obtener la segunda cadena. Formalmente, este el número de valores de $ i \ in [1 \ ldots n-1] $ para los que $ p (i) 1 \ ne p (i + 1) $. Es decir, es el número de puntos en los que $ p $ hace no incremento exactamente 1.Por ejemplo, $ w (p_1) = 1 $ y $ w (p_2) = 4 $, porque $ $ recortes P_1 12345 una vez, en los trozos 123 y 45, y $ $ recortes p_2 12345 cuatro veces, en cinco trozos.

Supongamos que existe una anagramico por dos cadenas $ a $ y $ b $. Entonces al menos uno anagramico debe tener menos peso. Digamos que este es éste más ligero . (Puede haber múltiples anagrammings más ligeros;. No me importa porque estoy interesado sólo en los pesos)

Pregunta

Quiero un algoritmo que, dado dos cadenas para los que existe un anagramico, de manera eficiente produce el peso exacto de la anagramico más ligero de las dos cadenas. Está bien si el algoritmo también se obtiene un anagramico más ligero, pero no es necesario.

Es una cuestión bastante simple para generar todas anagrammings y pesarlos, pero puede haber muchos, por lo que yo preferiría un método que encuentra anagrammings luz directa.

Motivation

La razón de este problema es de interés es la siguiente. Es muy fácil de hacer búsquedas en la computadora el diccionario y encontrar anagramas, pares de palabras que contienen exactamente las mismas letras. Pero muchos de los anagramas son producidos sin interés. Por ejemplo, los ejemplos más largas que se encuentran en International Dictionary de Webster En segundo lugar son:

cholecystoduodenostomy
duodenocholecystostomy

El problema debe quedar claro: estos son poco interesantes porque admiten un anagramico muy ligero que el simple intercambio del cholecysto, secciones duedeno y stomy, para un peso de 2. Por otro lado, este ejemplo mucho más corto es mucho más sorprendente e interesante:

costa
sección

Aquí el anagramico más ligero tiene un peso 8.

Tengo un programa que utiliza este método para localizar anagramas interesantes, a saber, aquellos para los cuales todos los anagrammings son de gran peso. Pero lo hace mediante la generación y un peso de todos los posibles anagrammings, que es lento.

¿Fue útil?

Solución

Este problema se conoce como el “problema mínimo de la partición cadena común.” (De manera más precisa, la respuesta en el problema de la partición de cadena mínimo común es igual a la respuesta en su problema más 1.) Por desgracia, es NP-difícil, incluso con la restricción de que cada letra se produce a lo sumo dos veces en cada una de las cadenas de entrada, como se se prueba por Goldstein, Kilman, y Zheng [GKZ05]. Esto significa que ningún algoritmo de tiempo polinómico existe a menos que P = NP. (Por supuesto, si cada letra se produce como máximo una vez, entonces el problema es trivial, ya que sólo hay una anagramico.)

En el lado positivo, los mismos autores [GKZ05] dan un polinomio en tiempo algoritmo 1,1037-aproximación bajo la misma restricción. (A “1.1037- aproximación algoritmo ” significa un algoritmo que puede no emitir la respuesta correcta A pero está garantizada a la salida un valor B tal que a = B = 1,1037 a .) también dan una -tiempo lineal algoritmo 4-aproximación bajo la restricción más débil que cada letra se produce en más tres veces en cada una de las cadenas de entrada.

[GKZ05] Avraham Goldstein, Petr Kolman, y Jie Zheng. cadena mínimo común problema de la partición: La dureza y aproximaciones. Revista Electrónica de Combinatoria , 12, artículo R50, 2005. http : //www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50

Otros consejos

Este es un seguimiento a la respuesta de Tsuyoshi Ito anteriormente , resumiendo la parte más relevante de la papel GKZ05 citó.

En el documento se demuestra una reducción en el conjunto independiente máximo ( MIS ) problema. Construir un gráfico $ G $ cuyos vértices son pares $ (i, j) $ tal que $ a_i = b_j $ y $ a_ {i + 1} = b_ {j + 1} $. Conectar los vértices $ (i, j) y $ $ (k, \ ell) $ (donde $ i=k $) con un borde cada vez que es imposible que un anagramico podría mapear todos $ i \ mapsto j $ e $ i + 1 \ mapsto j + 1 $ y $ k \ mapsto \ ell $ y $ k + 1 \ mapsto \ ell + 1 $. Esto es fácil de detectar; un mapeo de este tipo es imposible con exactitud si una de las siguientes bodegas:

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

Say la gráfica resultante $ G $ tiene un conjunto independiente máxima de tamaño $ s $. A continuación, el peso mínimo anagramico es exactamente $ n-s-1 $, donde $ n $ es la longitud de las cadenas $ a $ y $ b $. (Lo contrario sostiene también:... Un anagramico de bajo peso se traduce directamente en un gran MIS para $ G $ Para más detalles, ver pp 4-5 del papel)

Por ejemplo, considere las dos cadenas yttrious y touristy. El gráfico correspondiente tiene dos vértices, uno para el par ou compartida y uno para el par ri compartido. No existe una arista entre los vértices, ya que es posible tener un anagramico que mapea tanto ou a ou y ri a ri; o se puede comprobar que las tres condiciones anteriores fallan todos. Así que el gráfico tiene obviamente un MIS de tamaño $ s = 2 $ y el peso mínimo anagramico es de hecho 8-2-1 = 5, correspondiente a la y|t|t|ri|ou|s anagramico ? t|ou|ri|s|t|y '.

Por otro lado, considere derater y treader. Esta vez la gráfica tiene tres vértices:

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

2 y 3 son incompatibles, y 1 y 3 son incompatibles, pero 1 y 2 son compatibles. Así que la única MIS tiene un tamaño de $ s = 2 $ y contiene los vértices 1 y 2. El anagramico correspondiente de peso 7-2-1 = 4 es der|a|t|e|r ? t|r|e|a|der.

No cubre el algoritmo exacto que tenía en mente (que la respuesta de Tsuyoshi Ito hace ), pero tratando de conseguir en el problema subyacente de la búsqueda de "interesante" anagramas ...

Lo primero que pensé fue utilizar alguna variación en la distancia de edición, donde los cambios atómicos se ponderan en función de su posibilidad de confusión "ponderaciones" "interestingness" en lugar de la "dificultad" o habitual. Por supuesto, no parece probable que se puede codificar de manera eficiente las transformaciones realmente interesantes de esta manera, ya que son propensos a ser no local y por lo tanto encontrarse con los problemas NP-completos de MIS, etc.

Por lo tanto, el segundo pensamiento sería construir una alineación letras a la carta entre las palabras (a la alineaciones de traducción automática), y después de marcar las alineaciones a sí mismos para "interestingness" (por ejemplo, contando las alineaciones que tienen las letras adyacentes a las letras no adyacentes, o cuántas alineaciones cada alineación cruces, etc;. y luego ellos combinar todo el modelo a través de loglineales o tal)

Tercera idea es abandonar por completo mirando a la estructura de la propia anagramico, y en lugar de mirar a la semántica de las palabras. A menudo, lo que hace que un anagrama "interesante" es la incongruencia entre los significados de las palabras involucradas. Así que trate de algo así como el cálculo de la distancia en WordNet, o similar.

El problema se puede expresar en términos de permutación grupos .

Ahora, un grupo de la permutación contiene todos los "anagrama mueve", tanto primitiva (intercambiando dos letras) y compuesta de secuencias de movimientos primitivos. Parece que usted está interesado en sólo un subconjunto de las posibles permutaciones. Voy a tratar de definir estos.

En primer lugar, hay que recordar la notación para las permutaciones, a saber, el llamado notación ciclo :

  • $ () $ sin medios de permutación.
  • $ (1) $ medio 1 se intercambia con 1, que es también no permutación.
  • $ (12) $ medios 1 y 2 se intercambian.
  • $ (123) $ medios 1 sustituye 2 que sustituye 3 que sustituye a 1 (una rotación).
  • y así uno

se componen Estos simples 'ciclos' para describir permutaciones más complejos.

Parece que los movimientos que interesan son (para una palabra de longitud $ n $):

Estos movimientos son la base de su algoritmo. Lo que interesa es encontrar la secuencia más pequeño de estos movimientos para pasar de una palabra a la otra.

No sé ningún algoritmo para calcular esto, aparte de la búsqueda de fuerza bruta, pero al menos ahora hay una clara (espero) descripción de lo que los movimientos son primitivos. (Y tal vez algún grupo teórico de entre nosotros puede apuntar a un algoritmo apropiado.)

For cholecystoduodenostomy/duodenocholecystostome, I notice that if you assigned a number to each character describing how much it was moved as a delta, you would have some thing like 7 7's, then 8 -7s, then 6 0's. That is not right because some chars may have been repeated (the second c only moved forward 2, not back 7) etc but still very "run length encodable" because you see the same deltas in a row.

Compare to coastline/sectional, where you see something like (+2)(+5)(+5)(-3)(-1)(+3)....much less "run length encodable".

Perhaps the randomness of the deltas could give you a "score" as to how interesting the anagram is?

No afiliado a cs.stackexchange
scroll top