替換密碼與字典

Question

我家的任務是基於已知和有限字典破譯一個句子。

實施例： 字典 - 顯示，吹塑，而

則代碼12345 8291來作爲輸入。 如果我們將檢查的可能性唯一的選擇是「while show」。

有人可以給我一個方向或一個已知的算法來處理這個問題。 僞代碼或java會很好。

感謝

Answer 1

您需要實現某種回溯或其他搜索技術。我建議採用以下方法：

1. 創建一個密碼到字符轉換表。最初，每個密碼（數字）映射到0（無）。
2. 處理輸入。每次遇到一個未分配的密碼數字時，您都可以根據字典選擇字母，以及迄今已確定的內容。如果沒有可分配的字母，回溯（或以任何方式報告失敗對您的搜索技術有意義）。將每個選項添加到您的搜索控制邏輯。 （例如，如果您正在使用回溯，請保存選項列表並在轉換表中記錄任意選項，如果您回溯到該點，請指定另一個選項。）
3. 繼續進行，直到您完成或你用盡了選擇。

編輯：在步驟2中，困難的部分是確定什麼字母（如果有的話）可以分配給下一個密碼數字。假設我們正在跟蹤解碼的當前單詞，並且我們想要處理單詞中的下一個密碼數字。我們已經制作了密碼數字分配的全球地圖。邏輯可能是這樣的（在Java中上下的僞代碼）：

Set assignableLetters(String wordSoFar, int nextCipher) { 
    Character assignment = map.get(nextCipher); 
    Set set = new Set(); 
    if (assignment != null) { 
     // The next cipher is already assigned. Add the assignment to the 
     // return set only if it is compatible with the dictionary contents 
     if (dictionary.hasWordsWithPrefix(wordSoFar + assignment)) { 
      set.add(assignment); 
     } 
    } else { 
     // The next cipher is not assigned. We will return a set of all 
     // compatible characters that can be assigned to it. 
     for (Character c : unassignedCharacters()) { 
      if (dictionary.hasWordsWithPrefix(wordSoFar + c)) { 
       set.add(c); 
      } 
     } 
    } 
    return set; 
} 

如果返回空集，當前分配（被稱爲方法之前）與字典不兼容，搜索必須原路返回。否則，搜索應該從集合中一次選擇一個任務並繼續，必要時回溯。

而不是嘗試每個未分配的字符並詢問字典是否兼容，它可能更有效（但在邏輯上相當於）直接查詢字典中的兼容下一個字符列表並與未分配的字符集相交。