为含完整字符串与子串的字典列表分配唯一ID

我有一个由字符串（如人名）组成的字典列表，其中的字符串可能是完整名称或片段，示例如下：

names = [
    {"text": "Alice"},
    {"text": "Bob"},
    {"text": "Bob Ross"},
    {"text": "Twain"},
    {"text": "Ross"},
    {"text": "Alice Twain"},
    {"text": "Alice"},
    {"text": "Charles"},
]

我希望为每个字典添加一个ID，要求关联的完整字符串与子串对应相同的唯一ID。我已编写一个按长度降序排序字符串列表的函数：

def sortlen(lst):
    lst.sort(key=len, reverse=True)
    return lst

执行print(sortlen([name["text"] for name in names]))后得到：

['Alice Twain', 'Bob Ross', 'Charles', 'Alice', 'Twain', 'Alice', 'Ross', 'Bob']

期望最终结果如下：

names = [
    {"text": "Alice", "id": 2},
    {"text": "Bob", "id": 1},
    {"text": "Bob Ross", "id": 1},
    {"text": "Twain", "id": 2},
    {"text": "Ross", "id": 1},
    {"text": "Alice Twain", "id": 2},
    {"text": "Alice", "id": 2},
    {"text": "Charles", "id": 3},
]

但不确定如何对降序排序后的字符串列表应用合适的算法或代码。

核心思路：从最长的完整名称开始分配ID，再将其包含的子串映射到同一ID，确保关联名称共用ID。具体步骤如下：

1. 生成去重且按长度降序排序的名称列表，优先处理完整名称
2. 创建名称-ID映射字典，给未分配ID的完整名称分配新ID，同时将其包含的子串（存在于原列表的）关联到同一ID
3. 遍历原字典列表，通过映射字典填充每个字典的id字段

完整代码实现 #

names = [
    {"text": "Alice"},
    {"text": "Bob"},
    {"text": "Bob Ross"},
    {"text": "Twain"},
    {"text": "Ross"},
    {"text": "Alice Twain"},
    {"text": "Alice"},
    {"text": "Charles"},
]

def sortlen(lst):
    lst.sort(key=len, reverse=True)
    return lst

# 提取所有唯一名称并按长度降序排序
unique_names = list({name["text"] for name in names})
sorted_unique = sortlen(unique_names)

# 初始化映射字典与ID计数器
name_to_id = {}
current_id = 1

# 收集原列表中所有出现过的名称，快速判断子串是否存在
existing_names = {name["text"] for name in names}

for full_name in sorted_unique:
    if full_name not in name_to_id:
        # 给当前完整名称分配ID
        name_to_id[full_name] = current_id
        # 将完整名称的子串（存在于原列表的）映射到同一ID
        for part in full_name.split():
            if part in existing_names:
                name_to_id[part] = current_id
        current_id += 1

# 为原列表的每个字典添加id字段
for item in names:
    item["id"] = name_to_id[item["text"]]

# 输出结果
print("names = [")
for item in names:
    print(f"    {item},")
print("]")

代码说明 #

• 去重排序：避免重复处理相同名称，确保最长的完整名称先被处理，保证子串能关联到正确的完整名称ID
• 子串关联：拆分完整名称为单个部分，若子串在原列表中存在，则直接映射到同一ID
• 填充ID：通过预先生成的映射字典，快速给原列表的每个字典添加ID，效率较高

运行代码后即可得到预期结果。

内容的提问来源于stack exchange，提问作者Robert Alexander