Реализация выравнивания текста с помощью динамического программирования
Я пытаюсь понять концепцию динамического программирования через курс MIT OCW здесь. Объяснение по видео в OCW великолепен и все, но я чувствую, что не понимаю его до тех пор, пока не внедрил объяснение в код. Во время реализации я ссылаюсь на некоторые примечания из лекции здесь, особенно на стр. 3 примечания.
Проблема в том, что я не знаю, как перевести некоторые математические обозначения в код. Вот часть решения, которое я реализовал (и думаю, что оно реализовано правильно):
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)
Теперь часть, которую я не понимаю, находится в пунктах 3-5 в лекциях. Я буквально не понимаю и не знаю, с чего начать их внедрять. До сих пор я пробовал перебирать список слов и считал, что каждый из них якобы заканчивается, например:
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?
Но тогда я не знаю, как я могу продолжить эту функцию, и, честно говоря, я не понимаю эту строку:
dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)]
и как я вернусь justifier как int (так как я уже решил сохранить возвращаемое значение в result, что является списком. Должен ли я делать еще одну функцию и рекурсировать оттуда? рекурсия вообще?
Не могли бы вы показать мне, что делать дальше, и объяснить, как это динамическое программирование? Я действительно не вижу, где рекурсия, и что такое подзадача.
Спасибо раньше.
Ответы
Ответ 1
Если у вас возникли проблемы с пониманием основной идеи самого динамического программирования, здесь я беру на себя это:
Динамическое программирование по существу приносит в жертву сложность пространства для временной сложности (но дополнительное пространство, которое вы используете, обычно очень мало по сравнению с тем временем, которое вы сохраняете, делая динамическое программирование вполне оправданным, если оно выполнено правильно). Вы сохраняете значения из каждого рекурсивного вызова по ходу (например, в массиве или в словаре), поэтому во втором случае вы можете избежать вычислений при выполнении того же рекурсивного вызова в другой ветке дерева рекурсии.
И нет, вам не нужно использовать рекурсию. Вот моя реализация вопроса, над которым вы работали, используя только циклы. Я внимательно следил за TextAlignment.pdf, связанным с AlexSilva. Надеюсь, вы найдете это полезным.
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
Ответ 2
Для кого-то еще заинтересованного в этом: ключ должен двигаться назад от конца текста (как упоминалось здесь).
Если вы это сделаете, вы просто сравните уже запомненные элементы.
Скажем, words - список строк, которые должны быть завернуты в соответствии с textwidth. Затем в обозначениях лекции задача сводится к трем строкам кода:
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)])
С
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
Он упоминает, что можно добавить второй список, чтобы отслеживать позиции нарушения. Вы можете сделать это, изменив код на:
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]
Чтобы восстановить текст, просто используйте список ломающихся позиций:
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
Результат: (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.
Возможно, у вас возникнет соблазн добавить некоторые пробелы. Это довольно сложно (поскольку можно придумать различные эстетические правила), но наивная попытка может быть:
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
Что дает: (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.
Ответ 3
Это то, что я думаю в соответствии с вашим определением.
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]
Ответ 4
Я только что увидел лекцию, и мысль была бы поставлена здесь, что я мог понять. Я поставил код в том же формате, что и вопросщика. Я использовал рекурсию здесь, как объяснила лекция.
Точка № 3 определяет повторение. Это, в основном, дно для приближения, где вы вычисляете значение функции, относящееся к более высокому входу раньше, а затем используйте его для вычисления для более низкого значения входа.
Лекция объясняет это как:
DP (i) = min (DP (j) + badness (i, j))
для j, которая изменяется от я + 1 до n.
Здесь я варьируется от n до 0 (снизу вверх!).
Поскольку DP (n) = 0,
DP (n-1) = DP (n) + badness (n-1, n)
и затем вы вычисляете D (n-2) из D (n-1) и D (n) и берете минимум из них.
Таким образом, вы можете спуститься до я = 0 и получить окончательный ответ о плохом настроении!
В пункте № 4, как вы можете видеть, здесь есть две петли. Один для я и другой внутри я для j.
Следовательно, когда я = 0, j (max) = n, я = 1, j (max) = n-1,... я = n, j (max) = 0.
следовательно, общее время = добавление этих чисел = n (n + 1)/2.
Следовательно, O (n ^ 2).
Точка №5 просто определяет решение, которое DP [0]!
Надеюсь это поможет!
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()
