Existe-t-il des algorithmes intelligemment efficaces pour effectuer un calcul sur l'espace des partitions d'une chaîne?

Question

Je suis en train de travailler sur un projet statistique qui consiste à itérer de toutes les manières possibles pour partitionner une collection de chaînes et exécuter un calcul simple sur chacune d'elles. Plus précisément, chaque sous-chaîne possible a une probabilité qui lui est associée, et j'essaie d'obtenir la somme à travers toutes les partitions du produit de la probabilité de sous-chaîne dans la partition. Par exemple, si la chaîne est 'abc', alors il y aurait des probabilités pour 'a', 'b', 'c', 'ab', 'bc' et 'abc'. Il y a quatre partitions possibles de la chaîne: 'abc', 'ab | c', 'a | bc' et 'a | b | c'. L'algorithme doit trouver le produit des probabilités des composants pour chaque partitionnement, puis additionner les quatre nombres résultants.

Actuellement, j'ai écrit un itérateur python qui utilise des représentations binaires d'entiers pour les partitions (par exemple 00, 01, 10, 11 pour l'exemple ci-dessus) et parcourt simplement les entiers. Malheureusement, cela est extrêmement lent pour les chaînes de plus de 20 caractères.

Quelqu'un peut-il penser à une manière intelligente d'effectuer cette opération sans simplement parcourir chaque partition une à la fois? Je suis coincé là-dessus depuis des jours maintenant.

En réponse à certains commentaires ici quelques informations supplémentaires:
La chaîne peut être à peu près tout, par exemple « foobar (foo2) » - notre alphabet est alphanumérique minuscule, plus tous les trois types d'accolades (« (», "[", "{"), tirets et espaces
Le but est d'obtenir la vraisemblance de la chaîne donnée par les vraisemblances de 'mot' individuels Donc L (S = 'abc') = P ('abc') + P ('ab') P ('c') + P ('a') P ('bc') + P ('a') P ('b') P ('c') (Ici "P ('abc ') "indique la probabilité du' mot '' abc ', tandis que' L (S = 'abc') 'est la probabilité statistique d'observer la chaîne' abc ').

Answer 1

Une solution Dynamic Programming (si je comprends bien la question à droite):

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 complexité est O (N) il sera facilement résoudre le problème pour N = 20.

Comment pourquoi ce travail:

• Tout ce que vous multipliez par probs['a']*probs['b'] vous aussi multiplier par probs['ab']
• Merci à la Distributive Property de multiplication et d'addition, vous pouvez résumer les deux ensemble et multiplier ce single somme par toutes ses suites.
• Pour chaque dernière sous-chaîne possible, elle ajoute la somme de toutes les divisions se terminant par celle en ajoutant sa probabilité multipliée par la somme de toutes les probabilités des chemins précédents. (Phrasé alternative serait appréciée. Mon python est mieux que mon anglais ..)

Answer 2

D'abord, le profil pour trouver le goulot d'étranglement

Si le goulot d'étranglement est simplement le nombre massif de partitions possibles, je recommande la parallélisation, éventuellement via multiprocessing. Si ce n'est pas encore suffisant, vous pouvez regarder dans un cluster Beowulf.

Si le goulot d'étranglement est juste que le calcul est lent, essayez d'effectuer un décorticage en C. C'est assez facile à faire via ctypes.

En outre, je ne suis pas vraiment sûr de la façon dont vous stockez les partitions, mais vous pourriez probablement réduire la consommation de mémoire en utilisant une chaîne et un suffix array. Si votre goulot d'étranglement est en train d'échanger et/ou de manquer le cache, cela pourrait être une grande victoire.

Answer 3

Vos sous-chaînes vont être réutilisés encore et encore par les chaînes plus longues, la mise en cache de sorte que les valeurs à l'aide d'une technique memoizing semble comme un chose évidente à essayer. C'est juste un compromis spatio-temporel. L'implémentation la plus simple consiste à utiliser un dictionnaire pour mettre en cache les valeurs au fur et à mesure que vous les calculez. Faire une recherche de dictionnaire pour chaque calcul de chaîne; Si ce n'est pas dans le dictionnaire, calculez-le et ajoutez-le. Les appels suivants utiliseront la valeur pré-calculée. Si la recherche de dictionnaire est plus rapide que le calcul, vous avez de la chance.

Je me rends compte que vous utilisez Python, mais ... comme note complémentaire qui peut vous intéresser, si vous faites cela en Perl, vous n'avez même pas besoin d'écrire du code; le construit en Memoize module fera la mise en cache pour vous!

Answer 4

Vous pouvez obtenir une réduction mineure de la quantité de calcul par un petit refactoring basé sur les propriétés associatives de l'arithmétique (et de la concaténation de chaînes) même si je ne suis pas sûr que ce sera un changeur de vie. L'idée de base serait la suivante:

considérer une chaîne longue, par ex. 'abcdefghik', 10-long, pour la définitude sans perte de généralité. Dans une approche naïve, vous multipliez p (a) par les nombreuses partitions du 9-tail, p (ab) par les nombreuses partitions du 8-tail, etc; en particulier p (a) et p (b) multiplieront exactement les mêmes partitions du 8-queue (tous) que p (ab) - 3 multiplications et deux sommes parmi eux. Pour que facteur sur:

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

et nous en sommes à 2 multiplications et 1 somme pour cette partie, après avoir sauvé 1 produit et 1 somme. pour couvrir toutes les partitions avec un point de partage juste à droite de 'b'. En ce qui concerne les partitions avec une scission juste à droite de « c »,

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

les économies de montage, en partie grâce à la refactorisation interne - mais bien sûr, il faut faire attention à double comptage. Je pense que cette approche peut être généralisée - commencer par le point médian et considérer toutes les partitions qui y sont séparées, séparément (et récursivement) pour la partie gauche et droite, en multipliant et en sommant; puis ajoutez toutes les partitions qui n'ont pas de division ici, par ex. dans l'exemple, les moitiés étant 'abcde' à gauche et 'fghik' à droite, la seconde partie concerne toutes les partitions où 'ef' est ensemble plutôt qu'éparpillé - donc "effondre" toutes les probabilités en considérant que 'ef 'comme une nouvelle' super-lettre 'X, et il vous reste une chaîne plus courte,' abcdXghik '(bien sûr les probabilités pour les sous-chaînes de cette carte directement aux originaux, par exemple le p (cdXg) dans la nouvelle chaîne est juste exactement le p (cdefg) dans l'original).

Answer 5

Vous devriez regarder dans le module itertools. Il peut créer un générateur pour vous qui est très rapide. Compte tenu de votre chaîne d'entrée, il vous fournira toutes les permutations possibles. En fonction de ce dont vous avez besoin, il y a aussi un générateur combinations(). Je ne suis pas sûr si vous regardez "b | ca" quand vous regardez "abc", mais de toute façon, ce module peut vous être utile.