Thực hiện biện minh văn bản với lập trình động

Question

Tôi đang cố gắng hiểu khái niệm về Lập trình động, thông qua khóa học về MIT OCW here. Lời giải thích về video OCW thật tuyệt vời và tất cả, nhưng tôi cảm thấy như tôi không thực sự hiểu nó cho đến khi tôi thực hiện lời giải thích thành mã. Trong khi triển khai, tôi tham khảo một số ghi chú từ bài giảng here, đặc biệt là trang 3 của ghi chú.

Vấn đề là, tôi không biết cách dịch một số ký hiệu toán học thành mã. Dưới đây là một phần giải pháp mà tôi đã triển khai (và nghĩ rằng nó đã được triển khai đúng):

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) 

Bây giờ phần tôi không hiểu là từ 3 đến 5 trong bài giảng. Tôi thực sự không hiểu và không biết bắt đầu triển khai ở đâu. Cho đến nay, tôi đã thử lặp lại danh sách các từ và tính mức độ xấu của mỗi dòng bị cáo buộc là như sau:

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? 

Nhưng sau đó, tôi không biết làm thế nào tôi có thể tiếp tục chức năng và phải trung thực, tôi không hiểu dòng này:

dag = [badness(paragraph[i:j], page_width) + justifier(paragraph[j:], page_width) for j in range(i + 1, par_len + 1)] 

và làm thế nào tôi sẽ trở lại justifier như một int (kể từ khi tôi đã quyết định để lưu trữ giá trị trả về trong result, mà là một danh sách tôi có nên thực hiện một. chức năng và recurse từ đó? Nên có bất kỳ đệ quy nào cả?

Bạn có thể vui lòng cho tôi biết phải làm gì tiếp theo không và giải thích đây là chương trình động? Tôi thực sự không thể nhìn thấy nơi đệ quy là, và những gì các subproblem được.

Cảm ơn trước đây.

Answer 1

Trong trường hợp bạn gặp khó khăn khi tìm hiểu các ý tưởng cốt lõi của lập trình năng động bản thân ở đây là quan điểm của tôi về nó:

lập trình động cơ bản là phải hy sinh không gian phức tạp cho thời gian phức tạp (nhưng không gian thêm bạn sử dụng là thường là rất ít so với thời gian bạn lưu, làm cho chương trình động hoàn toàn đáng giá nếu được triển khai chính xác). Bạn lưu trữ các giá trị từ mỗi cuộc gọi đệ quy khi bạn đi (ví dụ: trong một mảng hoặc từ điển) để bạn có thể tránh tính toán lần thứ hai khi bạn chạy vào cùng một cuộc gọi đệ quy trong một nhánh khác của cây đệ quy.

Và không bạn làm không phải sử dụng đệ quy. Đây là việc thực hiện của tôi về câu hỏi mà bạn đang làm việc chỉ bằng cách sử dụng các vòng lặp. Tôi theo sau TextAlignment.pdf được liên kết bởi AlexSilva rất chặt chẽ. Hy vọng rằng bạn thấy điều này hữu ích.

 

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 

Answer 2

Đây là những gì tôi nghĩ rằng theo định nghĩa của bạn.

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] 

Answer 3

Tôi vừa xem bài giảng và suy nghĩ sẽ đặt ở đây bất cứ điều gì tôi có thể hiểu được. Tôi đã đặt trong các mã trong các định dạng tương tự như của người hỏi. Tôi đã sử dụng đệ quy ở đây, như bài giảng đã giải thích.
Điểm số 3, xác định sự lặp lại.Đây là cơ bản một đáy để tiếp cận, trong đó trong bạn tính toán một giá trị của hàm liên quan đến một đầu vào cao hơn trước đó, và sau đó sử dụng nó để tính toán cho đầu vào có giá trị thấp hơn.
Bài giảng giải thích như sau:
DP (i) = min (DP (j) + độ tàn (i, j))
cho j thay đổi từ i + 1 đến n.
Ở đây, tôi thay đổi từ n đến 0 (từ dưới lên trên!).
Khi DP (n) = 0,
DP (n-1) = DP (n) + độ xấu (n-1, n)
và sau đó bạn tính D (n-2) từ D (n-1) và D (n) và tận dụng tối thiểu chúng.
Bằng cách này bạn có thể đi xuống cho đến i = 0 và đó là câu trả lời cuối cùng của sự xấu!
Ở điểm # 4, bạn có thể thấy, có hai vòng lặp đang diễn ra tại đây. Một cho i và cái kia bên trong i cho j.
Do đó, khi i = 0, j (tối đa) = n, i = 1, j (max) = n-1, ... i = n, j (tối đa) = 0,
do đó tổng thời gian = bổ sung trong số này = n (n + 1)/2.
Do đó O (n^2).
Điểm # 5 chỉ xác định giải pháp DP [0]!
Hy vọng điều này sẽ hữu ích!

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() 

Answer 4

Đối với bất kỳ ai khác vẫn quan tâm đến điều này: Điều quan trọng là di chuyển lùi từ cuối văn bản (như đã đề cập here). Nếu bạn làm như vậy, bạn chỉ cần so sánh các yếu tố đã được ghi nhớ.

Nói, words là danh sách các chuỗi được gói theo textwidth. Sau đó, trong các ký hiệu của các bài giảng, nhiệm vụ giảm ba dòng mã:

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)]) 

Với:

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 

Ông nói rằng người ta có thể thêm một danh sách thứ hai để theo dõi các vị trí vi phạm . Bạn có thể làm như vậy bằng cách thay đổi mã để:

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] 

Để phục hồi các văn bản, chỉ cần sử dụng danh sách các vị trí vi phạm:

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 

Kết quả: (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. 

Một có thể bị cám dỗ để thêm một số khoảng trắng. Điều này là khá khó khăn (vì người ta có thể đưa ra quy tắc thẩm mỹ khác nhau) nhưng thử ngây thơ có thể là:

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 

gì mang đến cho bạn: (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.