Алгоритм шифрования с многосимвольной заменой

Моя проблема заключается в следующем. У меня есть список замен, в том числе одна замена для каждой буквы алфавита, а также некоторые замены для групп из более чем одной буквы. Например, в моем шифре p становится b, l становится w, e становится i, но le становится by, а ple становится memi.

Итак, хотя я могу придумать несколько простых/наивных способов реализации этого шифра, он не очень эффективен, и мне было интересно, какой самый эффективный способ сделать это. Ответ не обязательно должен быть на каком-то конкретном языке, подойдет общий структурированный английский алгоритм, но если он должен быть на каком-то языке, я бы предпочел C++ или Java или аналогичный.

РЕДАКТИРОВАТЬ: мне не нужно, чтобы этот шифр был расшифровываемым, алгоритм, который сопоставлял все отдельные буквы с буквой «w», но вместо этого сопоставлял строку «had» со строкой «jon», тоже должен быть в порядке (тогда строка " У Мэри был маленький ягненок.» станет «Wwww jon w wwwwww wwww.»).

Я бы хотел, чтобы алгоритм был полностью общим.


encryption substring substitution algorithm string-substitution
person Pedro Carvalho    schedule 20.06.2015    source источник
comment
Я полагаю, вы обеспечили уникальность и однозначность алфавита? У вас есть где-то весь алфавит, т.е. все правила замены?   -  person Lasse V. Karlsen    schedule 20.06.2015
comment
Что вы подразумеваете под уникальным и однозначным? Мне не нужно, чтобы этот шифр можно было расшифровать, алгоритм, который сопоставляет все отдельные буквы с буквой w, но вместо этого сопоставляет строку «had» со строкой «jon», также должен быть выполним. Я бы хотел, чтобы алгоритм был полностью общим.   -  person Pedro Carvalho    schedule 20.06.2015
comment
Эм, что? Почему вам не нужен этот шифр, чтобы его можно было расшифровать? Это не имеет смысла для меня. Слово «шифр» почти всегда используется в сочетании с шифрованием, которое имеет аналог дешифрования и, следовательно, поддается расшифровке. Вы строите хеш-алгоритм?   -  person Lasse V. Karlsen    schedule 20.06.2015
comment
Нет, я создаю язык ролевых игр в Second Life. Перевод будет тайно отправлен уже намеченной цели, мне просто нужно, чтобы это звучало круто для посторонних.   -  person Pedro Carvalho    schedule 21.06.2015
comment
А, тогда я понимаю. Я думаю, что kek - подходящий ответ здесь, тогда :)   -  person Lasse V. Karlsen    schedule 21.06.2015

Ответы (1)


arrow_upward
0
arrow_downward

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

p -> b
l -> w
e -> i
le -> by
ple -> memi

Автомат (в Эрланге как псевдокод)

start(p) -> p(next());
start(l) -> l(next());
start(e) -> e(next());
...

p(l) -> pl(next);
p(X) -> emit(b), start(X).

l(e) -> emit(by), start(next());
l(X) -> emit(w), start(X).

e(X) -> emit(i), start(X).

pl(e) -> emit(memi), start(next());
pl(X) -> emit(b), l(X).

Если вы не знакомы с Erlang, start(), p() — это функции для одного состояния. Каждая строка с -> представляет собой один переход, а действия следуют за ->. emit() — это функция, которая выдает шифр, а next() — функция, возвращающая следующий символ. X является переменной для любого другого символа.

person Hynek -Pichi- Vychodil    schedule 20.06.2015
comment
Однако разве это не потребует от меня жестко запрограммировать правила перехода? Этот автомат выглядит очень специфично для того примера, который я привел. Я бы хотел что-то, что имеет правила подстановки в качестве входных данных, а не часть кода. - person Pedro Carvalho; 20.06.2015
comment
Существует алгоритм, который генерирует автомат для любого шифра, который вы определили так, как вы описали в своем вопросе. Создание этого алгоритма является сложной частью решения, но вы можете вдохновиться алгоритмом, используемым для создания Aho-Corasic. - person Hynek -Pichi- Vychodil; 20.06.2015
comment
И какова его временная и пространственная сложность в зависимости от количества переходов и размера шифруемой строки? У меня уже есть алгоритм, который делает то, что я хочу, но это занимает слишком много времени (около 0,25~0,5 с для двухстрочного предложения). Кроме того, я не думаю, что язык, которым я ограничен (en.wikipedia.org/wiki/Linden_Scripting_Language) достаточно мощный, чтобы построить алгоритм, эффективно генерирующий этот автомат на основе входных данных. - person Pedro Carvalho; 20.06.2015
comment
Если бы вы прочитали связанную статью в Википедии, вы бы знали, когда словарь шаблонов известен заранее (например, база данных компьютерных вирусов), построение автомата может быть выполнено один раз в автономном режиме, а скомпилированный автомат сохранен для последующего использования. В этом случае время его выполнения линейно зависит от длины входных данных и количества совпавших записей. что отвечает на оба ваших вопроса. Вы можете сгенерировать автомат на другом языке и сгенерировать код LSL. - person Hynek -Pichi- Vychodil; 20.06.2015
comment
Я читал это, и дело в том, что словарь шаблонов заранее не известен, он является частью ввода, и я не могу использовать другой язык, так как ввод также происходит из SL. Пользователь дает программе произвольный словарь шаблонов в качестве входных данных, а затем дает ей строку для шифрования с использованием этого шаблона. - person Pedro Carvalho; 20.06.2015