¿Hay algún algoritmo hábilmente eficiente para realizar un cálculo sobre el espacio de particiones de una cadena?

Question

Estoy trabajando en un proyecto estadístico que implica iterar sobre todas las formas posibles de particionar una colección de cadenas y ejecutar un cálculo simple en cada una. Específicamente, cada posible subcadena tiene una probabilidad asociada, y estoy tratando de obtener la suma en todas las particiones del producto de la probabilidad de subcadena en la partición.

Por ejemplo, si la cadena es 'abc', entonces habría probabilidades para 'a', 'b', 'c', 'ab,' bc 'y' abc '. Hay cuatro particiones posibles de la cadena: 'abc', 'ab | c', 'a | bc' y 'a | b | c'. El algoritmo necesita encontrar el producto de las probabilidades del componente para cada partición, luego sumar los cuatro números resultantes.

Actualmente, he escrito un iterador de Python que usa representaciones binarias de enteros para las particiones (por ejemplo, 00, 01, 10, 11 para el ejemplo anterior) y simplemente recorre los enteros. Desafortunadamente, esto es inmensamente lento para cadenas de más de 20 caracteres.

¿Alguien puede pensar en una forma inteligente de realizar esta operación sin simplemente ejecutar cada partición una a la vez? He estado atrapado en esto por días ahora.

En respuesta a algunos comentarios aquí hay más información:
La cadena puede ser casi cualquier cosa, por ejemplo, "foobar (foo2)". - nuestro alfabeto es alfanumérico en minúscula más los tres tipos de llaves (" (", " [", " {"), guiones y espacios.
El objetivo es obtener la probabilidad de la cadena dada las probabilidades individuales de 'palabra'. Entonces L (S = 'abc') = P ('abc') + P ('ab') P ('c') + P ('a') P ('bc') + P ('a') P ('b') P ('c') (Aquí '' P ('abc') '' indica la probabilidad de la 'palabra' 'abc', mientras que '' L (S = 'abc') '' es el probabilidad estadística de observar la cadena 'abc').

Answer 1

Una solución Programación dinámica (si entendí bien la pregunta):

def dynProgSolution(text, probs):
  probUpTo = [1]
  for i in range(1, len(text)+1):
    cur = sum(v*probs[text[k:i]] for k, v in enumerate(probUpTo))
    probUpTo.append(cur)
  return probUpTo[-1]

print dynProgSolution(
  'abc',
  {'a': 0.1, 'b': 0.2, 'c': 0.3,
   'ab': 0.4, 'bc': 0.5, 'abc': 0.6}
  )

La complejidad es O (N ² ) por lo que resolverá fácilmente el problema para N = 20.

Cómo funciona esto:

• Todo lo que multiplicará por probs ['a'] * probs ['b'] también multiplicará por probs['ab'font>
• Gracias a la Propiedad distributiva de multiplicación y suma, puede sumar esos dos juntos y multiplique esta suma única por todas sus continuaciones.
• Por cada última subcadena posible, agrega la suma de todas las divisiones que terminan con eso al sumar su probabilidad multiplicada por la suma de todas las probabilidades de las rutas anteriores. (se agradecería la redacción alternativa. mi python es mejor que mi inglés ..)

Answer 2

Primero, perfil para encontrar el cuello de botella.

Si el cuello de botella es simplemente la gran cantidad de particiones posibles, recomiendo la paralelización, posiblemente a través de < code> multiprocesamiento . Si eso todavía no es suficiente, puede buscar en un Beowulf cluster.

Si el cuello de botella es solo que el cálculo es lento, intente bombardear a C. Es bastante fácil hacerlo a través de ctypes .

Además, no estoy realmente seguro de cómo está almacenando las particiones, pero probablemente podría aplastar el consumo de memoria bastante bien utilizando una cadena y un matriz de sufijos . Si su cuello de botella se está intercambiando y / o se pierde la memoria caché, eso podría ser una gran victoria.

Answer 3

Sus subcadenas serán reutilizadas una y otra vez por las cadenas más largas, por lo que el almacenamiento en caché de los valores utilizando un memorando parece algo obvio para probar. Esto es solo una compensación espacio-tiempo. La implementación más simple es usar un diccionario para almacenar en caché los valores a medida que los calcula. Haga una búsqueda en el diccionario para cada cálculo de cadena; si no está en el diccionario, calcule y agréguelo. Las llamadas posteriores utilizarán el valor precalculado. Si la búsqueda en el diccionario es más rápida que el cálculo, estás de suerte.

Me doy cuenta de que estás usando Python, pero ... como nota al margen que puede ser de interés, si haces esto en Perl, ni siquiera tienes que escribir ningún código; ¡El módulo Memoize hará el almacenamiento en caché por usted!

Answer 4

Puede obtener una reducción menor de la cantidad de cálculo mediante una pequeña refactorización basada en las propiedades asociativas de la aritmética (y la concatenación de cadenas), aunque no estoy seguro de que cambie la vida. La idea central sería la siguiente:

considere una cadena larga, p. ej. 'abcdefghik', de 10 largos, para una definición sin pérdida de generalidad. En un enfoque ingenuo, estarías multiplicando p (a) por las muchas particiones de la cola 9, p (ab) por las particiones de la cola 8, etc. en particular, p (a) yp (b) multiplicarán exactamente las mismas particiones de la cola 8 (todas ellas) que p (ab) lo hará: 3 multiplicaciones y dos sumas entre ellas. Así que factoriza eso:

(p(ab) + p(a) * p(b)) * (partitions of the 8-tail)

y hemos reducido 2 multiplicaciones y 1 suma para esta parte, habiendo guardado 1 producto y 1 suma. para cubrir todas las particiones con un punto de división justo a la derecha de 'b'. Cuando se trata de particiones con una división justo a la derecha de 'c',

(p(abc) + p(ab) * p(c) + p(a) * (p(b)*p(c)+p(bc)) * (partitions of the 7-tail)

el ahorro se acumula, en parte gracias a la refactorización interna, aunque, por supuesto, hay que tener cuidado con el doble conteo. Estoy pensando que este enfoque puede ser generalizado: comience con el punto medio y considere todas las particiones que tienen una división allí, por separado (y recursivamente) para la parte izquierda y derecha, multiplicando y sumando; luego agregue todas las particiones que NO tienen una división allí, p. en el ejemplo, las mitades están 'abcde' a la izquierda y 'fghik' a la derecha, la segunda parte trata de todas las particiones donde 'ef' están juntas en lugar de separadas, por lo que '' colapso '' todas las probabilidades considerando que 'ef' como un nuevo 'superletter' X, y te queda una cadena más corta, 'abcdXghik' (por supuesto, las probabilidades para las subcadenas de ESO se asignan directamente a los originales, por ejemplo, p ( cdXg) en la nueva cadena es exactamente el p (cdefg) en el original).

Answer 5

Debería buscar en el módulo itertools . Puede crear un generador para usted que es muy rápido. Dada su cadena de entrada, le proporcionará todas las permutaciones posibles. Dependiendo de lo que necesite, también hay un generador de combinaciones () . No estoy muy seguro si estás viendo "b | ca" cuando estás viendo "abc" pero de cualquier manera, este módulo puede resultarle útil.