获取两个其他字符串之间的中点字符串

Question

是否有可用的库或代码片段,可以使用两个字符串并返回两个字符串之间的精确或近似中点字符串？

优选地,代码将是Python.

背景:

这似乎是表面上的一个简单问题,但我有点挣扎:

• 显然,"A"和"C"之间的中点字符串将是"B".
• 使用base64编码,"A"和"B"之间的中点字符串可能是"Ag"
• 使用UTF-8编码,我不确定有效的中点是什么,因为中间字符似乎是一个控制字符: U+0088 c2 88 <control>

实际应用:

我问的原因是因为我希望编写map-reduce类型算法来读取数据库中的所有条目并处理它们.数据库中的主键是UTF-8编码的字符串,具有随机的字符分布.我们使用的数据库是Cassandra.

希望从数据库中获得最低密钥和最高密钥,然后通过找到中点将其分成两个范围,然后通过查找每个中间点将这两个范围分成两个较小的部分,直到我有几千个部分,然后我可以异步读取每个部分.

如果字符串是base-16编码的示例:(某些中点是近似值):

Starting highest and lowest keys:  '000'                'FFF'
                                   /   \              /       \
                              '000'     '8'         '8'       'FFF'
                              /   \     /  \       /  \       /   \
Result:                  '000'    '4' '4'  '8'   '8'  'B8'  'B8'  'FFF'
(After 3 levels of recursion)

Answer 1

不幸的是，并非所有字节序列都是有效的 UTF-8，因此仅取 UTF-8 值的中点并不简单，如下所示。

def midpoint(s, e):
    '''Midpoint of start and end strings'''
    (sb, eb) = (int.from_bytes(bytes(x, 'utf-8'), byteorder='big') for x in (s, e))
    midpoint = int((eb - sb) / 2 + sb)

    midpoint_bytes = midpoint.to_bytes((midpoint.bit_length() // 8) + 1, byteorder='big')
    return midpoint_bytes.decode('utf-8')

基本上，此代码将每个字符串转换为由内存中字节序列表示的整数，找到这两个整数的中点，并尝试再次将“中点”字节解释为 UTF-8。

根据您想要的具体行为，下一步可能是用midpoint_bytes某种替换字符替换无效字节，以形成有效的 UTF-8 字符串。对于您的问题，只要保持一致，使用哪个字符进行替换可能并不重要。

但是，由于您尝试对数据进行分区并且似乎不太关心中点的字符串表示形式，因此另一种选择是将中点表示形式保留为整数，并在进行分区时将键转换为整数。根据您的问题的规模，此选项可能可行，也可能不可行。