摩尔斯前缀树

一个表示字母表摩尔斯编码的前缀树（也称为“trie”）。字母可以通过从树中对应的节点到根节点的路径进行编码，反转路径上遇到的符号顺序。

•• •—•• ——— •••— • —• • — •—— ——— •—• —•— —••—

import networkx as nx

# Unicode字符表示摩尔斯电码的点/划（或滴/答）
dot = "•"
dash = "—"

# 从字母到代码的直接映射开始
morse_direct_mapping = {
    "a": dot + dash,
    "b": dash + dot * 3,
    "c": dash + dot + dash + dot,
    "d": dash + dot * 2,
    "e": dot,
    "f": dot * 2 + dash + dot,
    "g": dash * 2 + dot,
    "h": dot * 4,
    "i": dot * 2,
    "j": dot + dash * 3,
    "k": dash + dot + dash,
    "l": dot + dash + dot * 2,
    "m": dash * 2,
    "n": dash + dot,
    "o": dash * 3,
    "p": dot + dash * 2 + dot,
    "q": dash * 2 + dot + dash,
    "r": dot + dash + dot,
    "s": dot * 3,
    "t": dash,
    "u": dot * 2 + dash,
    "v": dot * 3 + dash,
    "w": dot + dash * 2,
    "x": dash + dot * 2 + dash,
    "y": dash + dot + dash * 2,
    "z": dash * 2 + dot * 2,
}

### 从该映射中手动构建前缀树

# 一些预处理：按代码长度和字符对原始映射进行排序
# 值
morse_mapping_sorted = dict(
    sorted(morse_direct_mapping.items(), key=lambda item: (len(item[1]), item[1]))
)

# 更多预处理：创建反向映射以简化查找
reverse_mapping = {v: k for k, v in morse_direct_mapping.items()}
reverse_mapping[""] = ""  # 用空字符串表示“根”节点

# 从排序后的映射构建前缀树
G = nx.DiGraph()
for node, char in morse_mapping_sorted.items():
    pred = char[:-1]
    # 将两个字母之间的点/划存储为边属性 "char"
    G.add_edge(reverse_mapping[pred], node, char=char[-1])

# 为了可视化目的，按拓扑顺序排列节点
for i, layer in enumerate(nx.topological_generations(G)):
    for n in layer:
        G.nodes[n]["layer"] = i
pos = nx.multipartite_layout(G, subset_key="layer", align="horizontal")
# 翻转布局，使根节点位于顶部
for k in pos:
    pos[k][-1] *= -1

# 可视化前缀树
nx.draw(G, pos=pos, with_labels=True)
elabels = {(u, v): l for u, v, l in G.edges(data="char")}
nx.draw_networkx_edge_labels(G, pos, edge_labels=elabels)


# 一封信可以通过从给定的字母（节点）开始，沿着路径进行编码
# 根节点
def morse_encode(letter):
    pred = next(G.predecessors(letter))  # 每个字母只有一个前驱
    symbol = G[pred][letter]["char"]
    if pred != "":
        return morse_encode(pred) + symbol  # 反向遍历前缀树
    return symbol


# 验证前缀树编码是否正确
import string

for letter in string.ascii_lowercase:
    assert morse_encode(letter) == morse_direct_mapping[letter]

print(" ".join([morse_encode(ltr) for ltr in "ilovenetworkx"]))