Блог

Главная - Вопросы по программированию - Как разобрать и перевести строку со словами, содержащими идентичные части

Как разобрать и перевести строку со словами, содержащими идентичные части

#javascript #algorithm #parsing #decode

#javascript #алгоритм #синтаксический анализ #расшифровать

Вопрос:

Мне нужно сделать что-то типа «декодер» для небольшой игры. Это дает вам строку типа:

eGgeggEGgO

Что переводится как «cat», потому что:

 c = eGg  
a = egg  
t = EGgO

Проблема в том, что некоторые слова / буквы имеют идентичные части, такие как eGg и eGgo (K) .

Итак, теоретически я бы представил какой-то «алгоритм», который находит «самое длинное» совпадение, где он находит eGg , пытается eGgo , не может его найти, а затем знает, что это C .

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

Это для Интернета, и у него может быть серверная часть, но я надеюсь просто сделать это на клиенте, поэтому JavaScript — это то, с чего я начинаю. Я доволен версией псевдокода или JavaScript или каким-либо другим языком. Я больше всего озадачен концептуальным «как», чем самим кодированием.

Обновить:

Вот полная карта

   egg:  'A',
  Egg:  'B',
  eGg:  'C',
  EGg:  'D',
  egG:  'E',
  EgG:  'F',
  eGG:  'G',
  EGG:  'H',
  eggo: 'I',
  Eggo: 'J',
  eGgo: 'K',
  EGgo: 'L',
  egGo: 'M',
  EgGo: 'N',
  eGGo: 'O',
  EGGo: 'P',
  eggO: 'Q',
  EggO: 'R',
  eGgO: 'S',
  EGgO: 'T',
  egGO: 'U',
  EgGO: 'V',
  eGGO: 'W',
  EGGO: 'X',
  eggy: 'Y',
  eggs: 'Z'

Комментарии:

1. Пожалуйста, покажите нам алгоритм кодирования, иначе мы не сможем вам помочь. Примера недостаточно, чтобы понять, как работает схема кодирования / декодирования.

2. Да, если у вас нет префиксного кода , его будет сложно расшифровать, вам может потребоваться обратный поиск, и вы можете вообще не добиться успеха.

3. Обновлено, чтобы оно имело полное сопоставление, если это поможет.

4. Вы можете легко маркировать свой ввод, поскольку все символы кода начинаются с e , но заканчиваются другой буквой. Нет необходимости » перебирать все буквы для каждой буквы».

5. О, это умный и, теперь, когда вы упомянули об этом, очевидный шаблон для поиска начала. Спасибо!

Ответ №1:

Это проблема токенизации, поэтому нам нужно грамматическое правило, которое для разграничения токенов.

К счастью, каждый токен начинается с одного из падежей ‘e’, так что все дело в поиске e и разделении непосредственно перед ними.

 const tokenMap = {
  egg:  'A',
  Egg:  'B',
  eGg:  'C',
  EGg:  'D',
  egG:  'E',
  EgG:  'F',
  eGG:  'G',
  EGG:  'H',
  eggo: 'I',
  Eggo: 'J',
  eGgo: 'K',
  EGgo: 'L',
  egGo: 'M',
  EgGo: 'N',
  eGGo: 'O',
  EGGo: 'P',
  eggO: 'Q',
  EggO: 'R',
  eGgO: 'S',
  EGgO: 'T',
  egGO: 'U',
  EgGO: 'V',
  eGGO: 'W',
  EGGO: 'X',
  eggy: 'Y',
  eggs: 'Z'
 }

const enciphered = 'eGgeggEGgO';
const tokens = enciphered.replace(/[e|E]/g, '^$amp;');
const mappedTokens = tokens.split('^').map(key => tokenMap[key])
const deciphered = mappedTokens.join('')
console.log(deciphered)