Получить строку, которая является срединной точкой между двумя другими строками

Имеется ли библиотека или фрагмент кода, который может принимать две строки и возвращать точную или приблизительную строку в середине строки между двумя строками?

Предпочтительно, код будет в Python.

Справочная информация:

Это кажется простой проблемой на поверхности, но я как бы борюсь с ней:

Очевидно, что средняя точка между "A" и "C" будет "B".
При кодировании base64, средняя точка между "A" и "B", вероятно, будет "Ag"
С кодировкой UTF-8 я не уверен, какой будет действительная средняя точка, потому что средний символ выглядит как управляющий символ: U+0088 c2 88 <control>

Практическое применение:

Причина, по которой я спрашиваю, заключается в том, что я надеялся написать алгоритм типа map-reduce, чтобы читать все записи из нашей базы данных и обрабатывать их. Первичными ключами в базе данных являются строки с кодировкой UTF-8 со случайными распределениями символов. База данных, которую мы используем, - это Cassandra.

Был надежд получить самый низкий ключ и самый высокий ключ из базы данных, а затем разбить его на два диапазона, найдя среднюю точку, а затем разбить эти два диапазона на два небольших раздела, найдя каждую из своих средних точек, пока я не несколько тысяч разделов, то я мог читать каждый раздел асинхронно.

Пример, если строки были закодированы по базе 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)

Ответ 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. Для вашей проблемы может не иметь значения, какой именно характер вы используете для замены, если вы согласны.

Однако, поскольку вы пытаетесь разбить данные и, похоже, не слишком заботитесь о строчном представлении середины, другой вариант состоит в том, чтобы просто оставить представление средней точки как целое число и преобразовать ключи в целые числа делая раздел. В зависимости от масштаба вашей проблемы этот вариант может быть или не быть выполнимым.

Ответ 2

Здесь общее решение, которое дает приблизительную середину m между любыми двумя строками Unicode a и b, такими, что a < m < b, если это возможно:

from os.path import commonprefix

# This should be set according to the range and frequency of
# characters used.
MIDCHAR = u'm'


def midpoint(a, b):
    prefix = commonprefix((a, b))
    p = len(prefix)
    # Find the codepoints at the position where the strings differ.
    ca = ord(a[p]) if len(a) > p else None
    cb = ord(b[p])
    # Find the approximate middle code point.
    cm = (cb // 2 if ca is None else (ca + cb) // 2)
    # If a middle code point was found, add it and return.
    if ca < cm < cb:
        return prefix + unichr(cm)
    # If b still has more characters after this, then just use
    # b code point and return.
    if len(b) > p + 1:
        return prefix + unichr(cb)
    # Otherwise, if cb == 0, then a and b are consecutive so there
    # is no midpoint. Return a.
    if cb == 0:
        return a
    # Otherwise, use part of a and an extra character so that
    # the result is greater than a.
    i = p + 1
    while i < len(a) and a[i] >= MIDCHAR:
        i += 1
    return a[:i] + MIDCHAR

Функция предполагает, что a < b. Кроме этого, он должен работать с произвольными строками Unicode, даже с символами u'\x00'. Также обратите внимание, что он может возвращать строки, содержащие u'\x00' или другие нестандартные кодовые точки. Если нет средней точки из-за b == a + u'\x00', возвращается a.

Ответ 3

Если вы посмотрите на метод JAVA StringTokinizer, он будет делать то, что вы хотите, и многое другое.