def str_to_id_labels(d):
    """
    Converts labels given in underscore format to integer IDs.

    For instance, the label "37_18_22_" could be mapped to ID 17. The new
    dictionary as well as the key mappings are returned.

    Return
    ------
    new_dict, str_to_id, id_to_str : (dict, dict, dict)
    """
    label_types = set()
    for key in d:
        for _, _, label in d[key]:
            label_types.add(label)

    key_sorter = lambda x: [int(i) for i in x.split("_") if i != ""]
    str_to_id = {
        s: i for i, s in enumerate(sorted(label_types, key=key_sorter))
        }
    id_to_str = {
        i: s for i, s in enumerate(sorted(label_types, key=key_sorter))
        }

    new_dict = {}
    for key in d:
        new_dict[key] = []
        for start, end, label in d[key]:
            new_dict[key].append((start, end, str_to_id[label]))

    return new_dict, str_to_id, id_to_str