подход к решению двух символов столбца шифрования текста

Question

У меня есть абзац текста, зашифрованный столбцами из двух символов.Цель моего задания - расшифровать его:

|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

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

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

Answer 1

Еще пара идей:

• Кавычки, после каждой открытой кавычки должна быть заключительная кавычка после нее.
• Прописные буквы, обычно начало предложения или существительное и т. Д. (Любойприменяются дополнительные правила грамматики
• Используйте достаточно маленький словарь, чтобы вместить все в память, и подсчитать количество допустимых слов в определенном расположении.

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

Допустим, текущее расположение столбцов по умолчанию:

|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 Вт /Количество хромосом, которые начинаются случайным образом (имейте в виду, что «случайное» назначение не может иметь повторяющихся номеров и должно быть действительным)

Затем запустите функцию пригодности для каждого назначения или несколько функций пригодности, если хотитечтобы разбить его таким образом. Начните с одной супер-фитнес-функции, которая присваивает фитнес-значение для каждого задания.

Только взятьон набирает 50% хромосом и переносит их в следующее поколение, где вы создаете «детские» хромосомы на основе вашего выбора функции кроссовера и вероятности мутации - для этого типа проблемы я рекомендую очень легкую функцию кроссовера (или ни одной...) и приличный уровень мутаций.Если вы можете найти столбцы, которые не способствуют значению слов / фитнес-функции, тогда, возможно, переверните их.

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

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

Одна последняя идея: попытаться абстрагироваться от «первого столбца, второго столбца» и назначить столбцы на куски, образующие слова, потому что только потому, что [1,4,6 ....] образует «»его "" она "и т. д. не означает, что он принадлежит с самого начала.

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

РЕДАКТИРОВАТЬ: Другой подход

Снова на основе словарного подхода, но вы бы сосредоточились на выборе первых нескольких столбцовMns перед остальными, и если он разваливается, и вы не получаете слова в какой-либо конкретной строке, это означает, что ваши предыдущие выборы были неправильными, и вам нужно будет вернуться назад.

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

Теперь у вас есть работающая строка, выберите соседнююгрести вправоЕсли он либо образует полные слова, либо все еще имеет допустимые слова (при условии отсутствия пробела, означающего конец слова).Повторите.

Если никакие смежные строки невозможны с учетом вашего предыдущего выбора, вернитесь на одну строку назад влево и не выбирайте ту же вещь снова.

Слабость в том, что вашему словарю потребуетсясодержит все слова в вашем предложении, а также все варианты слов.Возможно, вам потребуется придумать эвристику, аналогичную фитнес-функции, которая говорит: «90% слов совпадают, так что это все еще допустимая попытка ...» или что-то в этом роде.