Замена cypher со словарем

Question

мое домашнее задание - расшифровать предложение на основе известного и конечного словаря.

Пример: Dict - показать, удар, в то время как

затем код 12345 8291 пришел в качестве входных данных. , если мы проверим возможности, единственным вариантом является «пока показ».

Может кто-нибудь дать мне направление или известный алгоритм, который справляется с этой проблемой. Псевдокод или java будет отличным.

благодарит

Answer 1

Вы должны реализовать какое-то откаты или другой техники поиска. Я бы предложил следующий подход:

1. Создайте таблицу шифрованных символов. Первоначально каждый шифр (цифра) отображается в 0 (ничего).
2. Обработать входной сигнал. Каждый раз, когда вы сталкиваетесь с непризнанной цифрой шифрования, у вас есть выбор букв на основе словаря и того, что было определено до сих пор. Если нет назначаемых букв, откат (или отказ отчета каким-либо образом имеет смысл для вашей техники поиска). Добавьте каждый выбор в свою логику управления поиском. (Например, если вы используете backtracking, сохраните список вариантов и запишите произвольный выбор в таблице переводов. Если вы вернетесь к этой точке, назначьте другой вариант.)
3. Продолжайте, пока вы не дойдете до конца или у вас заканчиваются выборы.

EDIT: На шаге 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; 
} 

Если это возвращает пустой набор, текущее задание (до вызова метода) несовместимо со словарем и поиск должен возвращаться назад. В противном случае поиск должен выбрать одно задание за раз из набора и продолжить, если необходимо, откат.

Вместо того, чтобы пробовать каждый неназначенный символ и запрашивать словарь, совместим ли он, может быть более эффективным (но логически эквивалентным) запросить словарь непосредственно для списка совместимых следующих символов и пересечь его с неназначенным набором символов.