python - 用字符串在字典中找到最近的键？

Question

我正在尝试找到一种方法来找到字典中最接近字符串的键。示例:

data = {'1a': 'This is 1a', '1d': 'This is 1d', '1f': 'This is 1f', '1e': 'This is 1e'}
find_nearest(data, '1b')
#This would return key '1a'

我找到了其他例子，但大多数都与数字有关。示例:

data[num] if num in data else data[min(data.keys(), key=lambda k: abs(k-num))]

我找到了一个看起来很有希望的代码:

from sortedcontainers import SortedDict
sd = SortedDict((key, value) for key, value in data)

# Bisect for the index of the desired key.
index = sd.bisect(200)

# With that index, lookup the key.
key = sd.iloc[index]

# You can also look ahead or behind to find the nearest key.
behind = sd.iloc[index - 1]
ahead = sd.iloc[index + 1]

所以我尝试了这个，这是我的代码:

from sortedcontainers import SortedDict
data = {'1a': 'This is 1a', '1d': 'This is 1d', '1f': 'This is 1f', '1e': 'This is 1e'}
sd = SortedDict((key,value) for key,value in data.items())

index = sd.bisect('1b')

key = sd.iloc[index]
print(key)

但是当我运行这段代码时它返回:

1d #Instead of '1a'

我已经尝试了各种方法来让代码正常工作，但我似乎无法做到正确。有谁知道实现此目标的快速有效方法？

Answer 1

平分时，如果找不到精确的索引匹配，算法有 2 个选择。它可以返回左边对象的索引，也可以返回右边对象的索引。看起来 bisect 是 bisect_right 的别名。你可以使用 bisect_left相反……

当然，这不一定更接近(您还没有真正定义更接近的意思)。事实上，即使像 difflib.SequenceMatcher.ratio() 这样的东西也可能对示例没有帮助，因为它只是查看匹配元素与非匹配元素的比率。

你可以尝试这样的事情:

def find_closest(sd, expected):
    index = sd.bisect(expected)
    closest_lower = sd.iloc[index]
    try: 
        closest_upper = sd.iloc[index]
    except IndexError:
        return closest_lower

    # assumption -- Your keys are hex values.
    # this assumption could be completely wrong, but demonstrates
    # how to think of defining a measure of "closeness"
    var expected_as_int = int(expected, 16)
    def distance(val):
        return int(val, 16) - expected_as_int

    return min([closest_lower, closest_upper], key=distance)