從左對齊到左對齊的算法算法

最近我在一次採訪中被要求設計一種算法，將左對齊的輸入字符串（每行末尾有空格）轉換爲正確（沒有空格完整行的結尾），與MS Word中的類似。我向他提出了一些基本的解決方案，包括計算每行的字數和空格數，然後在所有空間中平均分配它們（他要求我假定可以在字之間分配空間）。但後來他讓我考慮整篇文章，然後修改文本，以便文字之間的空間不均勻分配不可避免時，文本的美不失。從左對齊到左對齊的算法算法

那時我無法想到任何適當的解決方案。後來他告訴我這是通過動態編程完成的。我不確定是否已經有一些標準算法。如果是，請分享一些有用的鏈接。

PS：我提出的解決方案非常抽象的想法，因此我沒有任何代碼來顯示我已經嘗試過的所有東西。理由：http://en.wikipedia.org/wiki/Justification_(typesetting)

來源

2013-08-06 Rajat Shah

如果分數空間可以分佈，那麼不均勻空間分佈是不可避免的嗎？它們最多不同於一個像素，肉眼難以察覺。 – IVlad

請記住，我們需要確保每行中的最後一個單詞觸及正確的邊界！當然，除了最後一行。 –

是的。設'd'爲最後一個詞到右邊界的距離。讓'x'爲單詞之間的空格數（'單詞 - 1'）。爲每個空格添加'd/x'，最後一個單詞將觸及右邊緣。如果'd'是以像素爲單位的，則必須將其餘的'd％x'像素添加到第一個'd％x'空間或隨機添加。要麼應該看起來不錯。 – IVlad

的標準算法打破段成線很可能還是克努特&賽普拉斯的算法，由Knuth的排版系統TeX使用。的算法，該算法「通過明智地使用動態編程的技術避免了回溯」在

描述

唐納德·E Knuth的和Michael F.賽普拉斯，軟件 - 實踐與經驗 11（1981）1119- 1184 DOI: 10.1002/spe.4380111102, 也有貨數字版式，Ch。 3，第67-155頁。

的算法是基於考慮每一個可能的換行符，從段落的開頭開始，併爲每一個尋找前述換行符給出最佳結果那麼遠的順序。由於整個序列由序列中的最後一個換行符決定，因此當添加新的潛在中斷點時，只需要考慮當前線路的潛在起點，從而生成高效的算法。

的算法的簡化版本（沒有例如連字），可這樣來描述：

Add start of paragraph to list of active breakpoints 
For each possible breakpoint (space) B_n, starting from the beginning: 
    For each breakpoint in active list as B_a: 
     If B_a is too far away from B_n: 
      Delete B_a from active list 
     else 
      Calculate badness of line from B_a to B_n 
      Add B_n to active list 
      If using B_a minimizes cumulative badness from start to B_n: 
      Record B_a and cumulative badness as best path to B_n 

The result is a linked list of breakpoints to use. 

The badness of lines under consideration can be calculated like this: 

Each space is assigned a nominal width, a strechability, and a shrinkability. 
The badness is then calculated as the ratio of stretching or shrinking used, 
relative to what is allowed, raised e.g. to the third power (in order to 
ensure that several slightly bad lines are prefered over one really bad one)

一個圖示的說明可以在各種語言http://defoe.sourceforge.net/folio/knuth-plass.html

實現中可以找到可在網絡上，例如 Bram Stein在Javascript中的實現：http://www.bramstein.com/projects/typeset/

來源

2013-08-06 22:22:38

答案應該是獨立的，即不依賴於閱讀某些外部資源（甚至沒有提供鏈接，所以我們必須自己去查找）。所以你至少應該給出一個關於算法的高級概述。 – Dukeling

@Dukeling由於該算法在通過發佈者可獲得的最佳66頁科學論文中描述，並且在網絡上的其他地方沒有廣泛使用，我認爲引用是足夠的鏈接。不過，我現在已經添加了算法的簡化描述，以及鏈接到包含更好描述的網頁。 –

你能舉一個在c＃中的例子嗎？ –

我做了Space-Inserter功能:)

但是隻是插入一個空格，直到線寬小於所需的寬度。

public static List<string> GetText(string text, int width) 
    { 
     string[] palabras = text.Split(' '); 
     StringBuilder sb1 = new StringBuilder(); 
     StringBuilder sb2 = new StringBuilder(); 
     int length = palabras.Length; 
     List<string> resultado = new List<string>(); 
     for (int i = 0; i < length; i++) 
     { 
      sb1.AppendFormat("{0} ", palabras[i]); 
      if (sb1.ToString().Length > width) 
      { 
       resultado.Add(sb2.ToString()); 
       sb1 = new StringBuilder(); 
       sb2 = new StringBuilder(); 
       sb1.AppendFormat("{0} ", palabras[i]); 
      } 
      else 
      { 
       sb2.AppendFormat("{0} ", palabras[i]); 
      } 
     } 
     resultado.Add(sb2.ToString()); 

     List<string> resultado2 = new List<string>(); 
     string temp; 

     int index1, index2, salto; 
     string target; 
     int limite = resultado.Count; 
     foreach (var item in resultado) 
     { 
      target = " "; 
      temp = item.ToString().Trim(); 
      index1 = 0; index2 = 0; salto = 2; 

      if (limite <= 1) 
      { 
       resultado2.Add(temp); 
       break; 
      } 
      while (temp.Length <= width) 
      { 
       if (temp.IndexOf(target, index2) < 0) 
       { 
        index1 = 0; index2 = 0; 
        target = target + " "; 
        salto++; 
       } 
       index1 = temp.IndexOf(target, index2); 
       temp = temp.Insert(temp.IndexOf(target, index2), " "); 
       index2 = index1 + salto; 

      } 
      limite--; 
      resultado2.Add(temp); 
     } 
     return resultado2; 
    }

希望它有幫助！

來源

2016-07-07 16:12:29

從左對齊到左對齊的算法算法

回答

相關問題