方法來解決兩個字符列爭奪一個文本

我有一段文字由兩個字符的列加擾。我的任務的目的是要解讀它：方法來解決兩個字符列爭奪一個文本

|de| | f|Cl|nf|ed|au| i|ti| |ma|ha|or|nn|ou| S|on|nd|on| 
|ry| |is|th|is| b|eo|as| | |f |wh| o|ic| t|, | |he|h | 
|ab| |la|pr|od|ge|ob| m|an| |s |is|el|ti|ng|il|d |ua|c | 
|he| |ea|of|ho| m| t|et|ha| | t|od|ds|e |ki| c|t |ng|br| 
|wo|m,|to|yo|hi|ve|u | t|ob| |pr|d |s |us| s|ul|le|ol|e | 
| t|ca| t|wi| M|d |th|"A|ma|l |he| p|at|ap|it|he|ti|le|er| 
|ry|d |un|Th|" |io|eo|n,|is| |bl|f |pu|Co|ic| o|he|at|mm| 
|hi| | |in| | | t| | | | |ye| |ar| |s | | |. |

我目前的做法找到列的正確順序是試圖根據單詞出現計數標準遞歸地找到每個列的最佳位置。

算法的核心的僞代碼，我在腦海裏：

function unscramble(scrambledMatrix,indexOfColumnIveJustMoved) 
    for each column on scrambledMatrix as currentIndex=>currentColumn 
     if (currentIndex!=indexOfColumnIveJustMoved) 
      maxRepeatedWords=0;maxIndex=0; 
      for (i=0;i<numberOfColumnsOfScrambledMatrix;i++) 
       repWordsCount=countRepWords(moveFromToOn(currentIndex,i,scrambledMatrix)) 
       if (maxRepeatedWords<repWordsCount) 
        maxRepeatedWords=repWordsCount; 
        maxIndex=i; 
       endif 
      endfor 
      if (maxIndex!=currentIndex) 
       return unscramble(moveFromToOn(currentIndex,maxIndex,scrambledMatrix),maxIndex); //recursive call 
      endif 
     endif 
    endfor 
    return(scrambledMatrix); //returns the unscrambled matrix; 
endfunction

該算法停止時，沒有列在迭代後每個移動。我猜它應該適用於任何語言（儘管我只對英文解決方案感興趣），只要寫作基於由字母組成的單詞並且樣本足夠大。

任何其他方法或改進建議？我想知道這個問題的最佳解決方案（可能是一個基於字典的尋找常見單詞出現的字典？如何重建算法以避免遞歸，會更快？）。

來源

2012-02-16 NotGaeL

一對夫婦更多的想法：

行情，爲每個打開的報價必須有後，最終報價。
大寫字母，通常開始一句話或名詞等（適用
任何額外的語法規則使用一個足夠小字典，以適應所有在內存中，並計算在特定安排的有效字數。

的一種方式，但通常這種方法是最花時間consuming-之一是使用遺傳算法。

可以說，當前的列默認設置是

|de| | f|Cl|nf|ed|au| i|ti| |ma|ha|or|nn|ou| S|on|nd|on| 
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18] <--- define this to be a chromosome

您可以創建100,1000 W在所述開始隨機分配（記住「隨機」分配不能有重複的數字，而且必須是有效的）染色體/ E號的人口

然後在運行健身功能每個任務或多個健身功能，如果你想打破這種方式。從一個超級健身功能開始，爲每項任務分配一個健身值。

只需將前50％的染色體移動到下一代，根據您選擇的交叉函數和突變概率創建「兒童」染色體，對於此類問題，我建議您輕交叉函數（或無...）和一個體面的變異率。如果你可以找到那些對詞彙/健身功能沒有貢獻的欄目，那麼可以翻轉那些欄目。

繼續這麼做幾代人，看看評分最高的任務是如何看起來像每一代的，你會期望在某個時刻有效的高原，這將是你的正確任務。

這種方法只能比適用於健身功能的蠻力更好，但它也可能變得相當不錯。

最後一個想法：嘗試從「第一列，第二列」抽象出來，並將列分成組成單詞的塊，因爲僅僅因爲[1,4,6 ....]變成「「」他「」她「等，並不意味着它在一開始就屬於正確。

我有一種不同的方法，我喜歡更好，我認爲動態算法會更適合這個。

編輯：另一種方法

同樣基於字典的方法，但你會專注於其餘部分之前選擇第幾列，而如果它分崩離析，你是不是任何特定的行中獲得的話這意味着你之前的選擇是錯誤的，你需要回溯。

選擇第1行..很有可能在這裏沒有太多單詞，但是您會將自己縮小到您的字典的子集 - 子集中包含以第一列中的字符開頭的單詞。

現在你有一個工作的行，選擇一個相鄰的行在右邊。如果它形成完整的單詞或仍然有可能的有效單詞（因爲沒有空格表示單詞的結尾）。重複。

如果在先前的選擇中沒有可能的相鄰行，則向左返回一行，並且不要再次選擇相同的事物。

這裏的弱點是你的字典需要包含你的句子中的所有單詞，以及單詞的所有變體。您可能需要提出一種與健身功能類似的啓發式方法，即「90％的單詞匹配，所以這仍然是一個有效的嘗試......」或類似的東西。

來源

2012-02-22 23:30:08

方法來解決兩個字符列爭奪一個文本

回答

相關問題