多字符替换密码算法

Question

我的问题如下。我有一个替换列表，包括对字母表中每个字母的一个替换，还有一些对多个字母组的替换。例如，在我的密码中 p 变成 b，l 变成 w，e 变成 i，但是 le 变成 by，ple 变成 memi。

因此，虽然我可以想到一些 simple/naive 方法来实现此密码，但效率不是很高，我想知道最有效的方法是什么。答案不必使用任何特定语言，通用的结构化英语算法就可以了，但如果必须使用某种语言，我更喜欢 C++ 或 Java 或类似语言。

编辑：我不需要这个密码是可破译的，一种将所有单个字母映射到字母 'w' 但将字符串 'had' 映射到字符串 'jon' 的算法相反也应该没问题（然后字符串 "Mary had a little lamb." 将变为 "Wwww jon w wwwwww wwww."）。

我希望算法完全通用。

Answer 1

一种可能的方法是使用确定性自动机。最接近您的问题和常用示例是 Aho–Corasick string matching algorithm。不同之处在于，您不想匹配，而是希望在某个转换时发出密码。通常在每次转换时，您都会发出或不发出密码。在你的例子中

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

自动机（在 Erlang 中类似于伪代码）

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 对于任何其他字符都是可变的。

多字符替换密码算法

Multi-character substitution cipher algorithm

algorithm

encryption

substring

substitution

string-substitution