Mise en œuvre de la Justification du texte par une programmation dynamique
j'essaie de comprendre le concept de programmation dynamique, via le cours sur MIT OCW ici. L'explication sur OCW video est super et tout, mais j'ai l'impression que je ne comprends pas vraiment jusqu'à ce que je implémente l'explication dans le code. Lors de la mise en œuvre, je me réfère à certaines notes de la note de cours ici, en particulier la page 3 de la note.
le problème est que je n'ai aucune idée de comment traduire une partie de la notation mathématique en code. Voici quelques une partie de la solution que j'ai mis en oeuvre (et pense qu'il est mis en œuvre à droite):
import math
paragraph = "Some long lorem ipsum text."
words = paragraph.split(" ")
# Count total length for all strings in a list of strings.
# This function will be used by the badness function below.
def total_length(str_arr):
total = 0
for string in str_arr:
total = total + len(string)
total = total + len(str_arr) # spaces
return total
# Calculate the badness score for a word.
# str_arr is assumed be send as word[i:j] as in the notes
# we don't make i and j as argument since it will require
# global vars then.
def badness(str_arr, page_width):
line_len = total_length(str_arr)
if line_len > page_width:
return float('nan')
else:
return math.pow(page_width - line_len, 3)
maintenant, la partie que je ne comprends pas est sur les points 3 à 5 dans les notes de conférence. Je ne comprends pas et je ne sais pas où commencer à les mettre en œuvre. Jusqu'à présent, j'ai essayé d'itérer la liste des mots, et de compter la méchanceté de chaque soi-disant fin de ligne, comme ceci:
def justifier(str_arr, page_width):
paragraph = str_arr
par_len = len(paragraph)
result = [] # stores each line as list of strings
for i in range(0, par_len):
if i == (par_len - 1):
result.append(paragraph)
else:
dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)]
# Should I do a min(dag), get the index, and declares it as end of line?
mais alors, je ne sais pas comment je peux continuer la fonction, et pour être honnête, je ne comprends pas cela ligne:
dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)]
et comment je vais retourner justifierint (puisque je l'ai déjà décidé de stocker la valeur de retour result, qui est une liste de. Dois-je faire une autre fonction et recommencer à partir de là? Il y a de la récursivité?
Pourriez-vous svp me montrer quoi faire ensuite, et expliquer en quoi c'est de la programmation dynamique? Je ne vois vraiment pas où est la récursion, et quel est le sous-problème.
Merci avant.
4 réponses
Dans le cas où vous avez du mal à comprendre l'idée de base de la programmation dynamique elle-même, ici est mon prendre sur elle:
La programmation dynamique sacrifie essentiellement espace complexitéfuseau complexité (mais l'espace supplémentaire que vous utilisez est généralement très peu par rapport au temps que vous économisez, ce qui rend la programmation dynamique totalement valable si elle est mise en œuvre correctement). Vous stocker les valeurs de chaque appel récursif comme vous (par exemple, dans un tableau ou une dictionnaire) de sorte que vous pouvez éviter de calculer pour la deuxième fois lorsque vous rencontrez le même appel récursif dans une autre branche de l'arbre de récursion.
Et non, vous n' utiliser la récursivité. Voici mon implémentation de la question sur laquelle vous travailliez en utilisant just loops. J'ai suivi le Textalignement.pdf très étroitement lié par AlexSilva. Nous espérons que vous trouverez ce utile.
def length(wordLengths, i, j):
return sum(wordLengths[i- 1:j]) + j - i + 1
def breakLine(text, L):
# wl = lengths of words
wl = [len(word) for word in text.split()]
# n = number of words in the text
n = len(wl)
# total badness of a text l1 ... li
m = dict()
# initialization
m[0] = 0
# auxiliary array
s = dict()
# the actual algorithm
for i in range(1, n + 1):
sums = dict()
k = i
while (length(wl, k, i) <= L and k > 0):
sums[(L - length(wl, k, i))**3 + m[k - 1]] = k
k -= 1
m[i] = min(sums)
s[i] = sums[min(sums)]
# actually do the splitting by working backwords
line = 1
while n > 1:
print("line " + str(line) + ": " + str(s[n]) + "->" + str(n))
n = s[n] - 1
line += 1
pour toute autre personne encore intéressée par ceci: la clé est de revenir en arrière à partir de la fin du texte (comme mentionné ici). Si vous le faites, il vous suffit de comparer des éléments déjà mémorisés.
Dire words est une liste de cordes à emballer selon textwidth. Puis, dans la notation de la conférence, la tâche se réduit à trois lignes de code:
import numpy as np
textwidth = 80
DP = [0]*(len(words)+1)
for i in range(len(words)-1,-1,-1):
DP[i] = np.min([DP[j] + badness(words[i:j],textwidth) for j in range(i+1,len(words)+1)])
Avec:
def badness(line,textwidth):
# Number of gaps
length_line = len(line) - 1
for word in line:
length_line += len(word)
if length_line > textwidth: return float('inf')
return ( textwidth - length_line )**3
il mentionne qu'on peut ajouter une deuxième liste pour garder la trace de les positions de rupture. Vous pouvez le faire en modifiant le code:
DP = [0]*(len(words)+1)
breaks = [0]*(len(words)+1)
for i in range(len(words)-1,-1,-1):
temp = [DP[j] + badness(words[i:j],args.textwidth) for j in range(i+1,len(words)+1)]
index = np.argmin(temp)
# Index plus position in upper list
breaks[i] = index + i + 1
DP[i] = temp[index]
Pour récupérer le texte, il suffit d'utiliser la liste de rupture positions:
def reconstruct_text(words,breaks):
lines = []
linebreaks = []
i = 0
while True:
linebreaks.append(breaks[i])
i = breaks[i]
if i == len(words):
linebreaks.append(0)
break
for i in range( len(linebreaks) ):
lines.append( ' '.join( words[ linebreaks[i-1] : linebreaks[i] ] ).strip() )
return lines
Résultat: (text = reconstruct_text(words,breaks))
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy
eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam
voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet
clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit
amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed
diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet
clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.
On pourrait être tenté d'ajouter un peu d'espaces. C'est assez délicat (puisque l'on pourrait arriver à diverses règles esthétiques) mais un essai naïf pourrait être:
import re
def spacing(text,textwidth,maxspace=4):
for i in range(len(text)):
length_line = len(text[i])
if length_line < textwidth:
status_length = length_line
whitespaces_remain = textwidth - status_length
Nwhitespaces = text[i].count(' ')
# If whitespaces (to add) per whitespace exeeds
# maxspace, don't do anything.
if whitespaces_remain/Nwhitespaces > maxspace-1:pass
else:
text[i] = text[i].replace(' ',' '*( 1 + int(whitespaces_remain/Nwhitespaces)) )
status_length = len(text[i])
# Periods have highest priority for whitespace insertion
periods = text[i].split('.')
# Can we add a whitespace behind each period?
if len(periods) - 1 + status_length <= textwidth:
text[i] = '. '.join(periods).strip()
status_length = len(text[i])
whitespaces_remain = textwidth - status_length
Nwords = len(text[i].split())
Ngaps = Nwords - 1
if whitespaces_remain != 0:factor = Ngaps / whitespaces_remain
# List of whitespaces in line i
gaps = re.findall('\s+', text[i])
temp = text[i].split()
for k in range(Ngaps):
temp[k] = ''.join([temp[k],gaps[k]])
for j in range(whitespaces_remain):
if status_length >= textwidth:pass
else:
replace = temp[int(factor*j)]
replace = ''.join([replace, " "])
temp[int(factor*j)] = replace
text[i] = ''.join(temp)
return text
Ce qui donne:text = spacing(text,textwidth))
Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy
eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam
voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet
clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit
amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam
nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed
diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet
clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.
je viens de voir la conférence et j'ai pensé mettre ici tout ce que je pouvais comprendre. J'ai mis le code dans le même format que celui de l'interlocuteur. J'ai utilisé la récursivité ici, comme la conférence l'a expliqué.
Point #3, définit la récurrence. Il s'agit essentiellement d'un bas à l'approche, où dans vous calculez une valeur de la fonction se rapportant à une entrée plus élevée plus tôt, et puis l'utiliser pour calculer le pour la valeur plus faible entrée.
La conférence l'explique comme :
DP(i) = min(DP(j) + méchanceté(i, j))
pour j qui varie de i+1 à n.
Ici, je varie de n à 0 (de bas en haut!).
As DP (n) = 0 ,
DP(n-1) = DP(n) + méchanceté(n-1, n)
puis vous calculez D(n-2) à partir de D(n-1) et D (n) et vous en retirez un minimum.
De cette façon, vous pouvez descendre jusqu'à i=0 et c'est la réponse finale de la méchanceté!
Au point 4, comme vous pouvez le voir, il y a deux les boucles se passe ici. Un pour moi et l'autre pour j.
Par conséquent, lorsque i=0, j(max) = n, i = 1, j(max) = n-1, ... i = n , j(max) = 0.
par conséquent, temps total = addition de ces valeurs = n (n+1)/2.
D'où O(N^2).
Le point 5 identifie simplement la solution que DP[0]!
Espérons que cette aide!
import math
justification_map = {}
min_map = {}
def total_length(str_arr):
total = 0
for string in str_arr:
total = total + len(string)
total = total + len(str_arr) - 1 # spaces
return total
def badness(str_arr, page_width):
line_len = total_length(str_arr)
if line_len > page_width:
return float('nan')
else:
return math.pow(page_width - line_len, 3)
def justify(i, n, words, page_width):
if i == n:
return 0
ans = []
for j in range(i+1, n+1):
#ans.append(justify(j, n, words, page_width)+ badness(words[i:j], page_width))
ans.append(justification_map[j]+ badness(words[i:j], page_width))
min_map[i] = ans.index(min(ans)) + 1
return min(ans)
def main():
print "Enter page width"
page_width = input()
print "Enter text"
paragraph = input()
words = paragraph.split(' ')
n = len(words)
#justification_map[n] = 0
for i in reversed(range(n+1)):
justification_map[i] = justify(i, n, words, page_width)
print "Minimum badness achieved: ", justification_map[0]
key = 0
while(key <n):
key = key + min_map[key]
print key
if __name__ == '__main__':
main()
C'est ce que je pense selon votre définition.
import math
class Text(object):
def __init__(self, words, width):
self.words = words
self.page_width = width
self.str_arr = words
self.memo = {}
def total_length(self, str):
total = 0
for string in str:
total = total + len(string)
total = total + len(str) # spaces
return total
def badness(self, str):
line_len = self.total_length(str)
if line_len > self.page_width:
return float('nan')
else:
return math.pow(self.page_width - line_len, 3)
def dp(self):
n = len(self.str_arr)
self.memo[n-1] = 0
return self.judge(0)
def judge(self, i):
if i in self.memo:
return self.memo[i]
self.memo[i] = float('inf')
for j in range(i+1, len(self.str_arr)):
bad = self.judge(j) + self.badness(self.str_arr[i:j])
if bad < self.memo[i]:
self.memo[i] = bad
return self.memo[i]