Я собираюсь бросить свою шляпу на ринг с обалденной здесь. Вы можете преобразовать строку в пригодный для использования формат с помощью
arr = np.array([verse]).view(np.uint32)
Вы можете замаскировать места, где следующий символ является диакритическим:
mask = np.empty(arr.shape, dtype=np.bool)
np.bitwise_and((arr[1:] > lower), (arr[1:] < upper), out=mask[:-1])
mask[-1] = False
Здесь диапазон [upper, lower] - это выдуманный способ проверки на диакритические знаки. Реализуйте фактическую проверку так, как вам нравится. В этом примере я использовал полноразмерную форму bitwise_and с empty, чтобы избежать потенциально дорогого добавления последнего элемента.
Теперь, если у вас есть числовой метод для кодирования вашего кода, указывает на число, которое, я уверен, вы можете векторизовать, вы можете сделать что-то вроде:
combined = combine(letters=arr[mask], diacritics=arr[1:][mask[:-1]])
Чтобы получить оставшихся нескомбинированных персонажей, вам необходимо удалить как диалектику, так и символы, с которыми они связаны. Самый простой способ, которым я могу придумать, это смазать маску вправо и отрицать ее. Опять же, я предполагаю, что у вас есть векторизованный метод для кодирования отдельных символов:
smeared = mask.copy()
smeared[1:] |= mask[:-1]
single = encode(arr[~smeared])
Объединение результата в окончательный массив концептуально просто, но требует нескольких шагов. Результат будет np.count_nonzeros(mask) элементов короче, чем вход, поскольку диакритические знаки удаляются. Нам нужно сместить все элементы маски на величину их индекса. Вот один из способов сделать это:
ind = np.flatnonzero(mask)
nnz = ind.size
ind -= np.arange(nnz)
output = np.empty(arr.size - nnz, dtype='U1')
output[ind] = combined
# mask of unmodified elements
out_mask = np.ones(output.size, dtype=np.bool)
out_mask[ind] = False
output[out_mask] = single
Причина, по которой я предлагаю numpy, заключается в том, что он должен обрабатывать несколько миллионов символов за считанные секунды. Возвращение вывода в виде строки должно быть простым.
Предлагаемая реализация
Я обдумывал ваш вопрос и решил поиграть с некоторыми таймингами и возможными реализациями. Моя идея состояла в том, чтобы отобразить символы Unicode в 0x0621-0x063A , 0x0641-0x064A (26 + 10 = 36 букв) в младшие 6 битов uint16 и символы 0x064B-0x0652 (8 диакритических знаков) до следующих старших 3 битов, предполагая, что это фактически единственные диакритические знаки, которые вам нужны:
def encode_py(char):
char = ord(char) - 0x0621
if char >= 0x20:
char -= 5
return char
def combine_py(char, diacritic):
return encode_py(char) | ((ord(diacritic) - 0x064A) << 6)
В натуральном выражении:
def encode_numpy(chars):
chars = chars - 0x0621
return np.subtract(chars, 5, where=chars > 0x20, out=chars)
def combine_numpy(chars, diacritics):
chars = encode_numpy(chars)
chars |= (diacritics - 0x064A) << 6
return chars
Вы можете выбрать дальнейшее кодирование, чтобы немного сократить представление, но я бы не рекомендовал его. Это представление имеет то преимущество, что оно не зависит от стихов, поэтому вы можете сравнивать части разных стихов, а также не беспокоиться о том, какое представление вы получите в зависимости от того, сколько стихов вы закодировали вместе. Вы даже можете замаскировать верхние биты всех кодов для сравнения необработанных символов без диакритических знаков.
Итак, допустим, что ваш стих представляет собой набор случайно сгенерированных чисел в этих диапазонах, причем диакритические знаки генерируются случайным образом, следуя не более одной буквы каждая. Мы можем легко сгенерировать строку длиной около миллиона для сравнительных целей:
import random
random.seed(0xB00B5)
alphabet = list(range(0x0621, 0x063B)) + list(range(0x0641, 0x064B))
diactitics = list(range(0x064B, 0x0653))
alphabet = [chr(x) for x in alphabet]
diactitics = [chr(x) for x in diactitics]
def sample(n=1000000, d=0.25):
while n:
yield random.choice(alphabet)
n -= 1
if n and random.random() < d:
yield random.choice(diactitics)
n -= 1
data = ''.join(sample())
Эти данные имеют совершенно случайно распределенные символы, с вероятностью примерно 25% любого символа, сопровождаемого диакритическим знаком. Генерация на моем не слишком мощном ноутбуке занимает всего несколько секунд.
Преобразование numpy будет выглядеть так:
def convert_numpy(verse):
arr = np.array([verse]).view(np.uint32)
mask = np.empty(arr.shape, dtype=np.bool)
mask[:-1] = (arr[1:] >= 0x064B)
mask[-1] = False
combined = combine_numpy(chars=arr[mask], diacritics=arr[1:][mask[:-1]])
smeared = mask.copy()
smeared[1:] |= mask[:-1]
single = encode_numpy(arr[~smeared])
ind = np.flatnonzero(mask)
nnz = ind.size
ind -= np.arange(nnz)
output = np.empty(arr.size - nnz, dtype=np.uint16)
output[ind] = combined
# mask of unmodified elements
out_mask = np.ones(output.size, dtype=np.bool)
out_mask[ind] = False
output[out_mask] = single
return output
Ориентиры
А теперь давайте %timeit посмотрим, как все пойдет. Во-первых, вот другие реализации. Я преобразовываю все в массив или список целых чисел для честного сравнения. Я также внес небольшие изменения, чтобы функции возвращали списки с одинаковыми величинами для проверки точности:
from itertools import tee, zip_longest
from functools import reduce
def is_diacritic(c):
return ord(c) >= 0x064B
def pairwise(iterable, fillvalue):
""" Slightly modified itertools pairwise recipe
s -> (s0,s1), (s1,s2), (s2, s3), ...
"""
a, b = tee(iterable)
next(b, None)
return zip_longest(a, b, fillvalue=fillvalue)
def combine_py2(char, diacritic):
return char | ((ord(diacritic) - 0x064A) << 6)
def convert_FHTMitchell(verse):
def convert(verse):
was_diacritic = False # variable to keep track of diacritics -- stops us checking same character twice
# fillvalue will not be encoded but ensures last char is read
for this_char, next_char in pairwise(verse, fillvalue='-'):
if was_diacritic: # last next_char (so this_char) is diacritic
was_diacritic = False
elif is_diacritic(next_char):
yield combine_py(this_char, next_char)
was_diacritic = True
else:
yield encode_py(this_char)
return list(convert(verse))
def convert_tobias_k_1(verse):
return reduce(lambda lst, x: lst + [encode_py(x)] if not is_diacritic(x) else lst[:-1] + [combine_py2(lst[-1], x)], verse, [])
def convert_tobias_k_2(verse):
res = []
for x in verse:
if not is_diacritic(x):
res.append(encode_py(x))
else:
res[-1] = combine_py2(res[-1], x)
return res
def convert_tobias_k_3(verse):
return [combine_py(x, y) if y and is_diacritic(y) else encode_py(x) for x, y in zip_longest(verse, verse[1:], fillvalue="") if not is_diacritic(x)]
Теперь по времени:
%timeit result_FHTMitchell = convert_FHTMitchell(data)
338 ms ± 5.09 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit result_tobias_k_1 = convert_tobias_k_1(data)
Aborted, took > 5min to run. Appears to scale quadratically with input size: not OK!
%timeit result_tobias_k_2 = convert_tobias_k_2(data)
357 ms ± 4.94 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit result_tobias_k_3 = convert_tobias_k_3(data)
466 ms ± 4.62 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit result_numpy = convert_numpy(data)
30.2 µs ± 162 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
Сравнение полученных массивов / списков показывает, что они также равны:
np.array_equal(result_FHTMitchell, result_tobias_k_2) # True
np.array_equal(result_tobias_k_2, result_tobias_k_3) # True
np.array_equal(result_tobias_k_3, result_numpy) # True
Я использую array_equal здесь, потому что он выполняет все необходимые преобразования типов для проверки фактических данных.
Итак, мораль этой истории в том, что есть много способов сделать это, и разбор нескольких миллионов символов не должен быть чрезмерно дорогим сам по себе, пока вы не столкнетесь с перекрестными ссылками и другими действительно трудоемкими задачами. , Главное, что нужно сделать, это не использовать reduce в списках, так как вы будете перераспределять на больше, чем нужно. Даже простой цикл for отлично подойдет для ваших целей. Хотя numpy примерно в десять раз быстрее, чем другие реализации, он не дает огромного преимущества.
Декодирование
Ради полноты, вот функция для декодирования ваших результатов:
def decode(arr):
mask = (arr > 0x3F)
nnz = np.count_nonzero(mask)
ind = np.flatnonzero(mask) + np.arange(nnz)
diacritics = (arr[mask] >> 6) + 41
characters = (arr & 0x3F)
characters[characters >= 27] += 5
output = np.empty(arr.size + nnz, dtype='U1').view(np.uint32)
output[ind] = characters[mask]
output[ind + 1] = diacritics
output_mask = np.zeros(output.size, dtype=np.bool)
output_mask[ind] = output_mask[ind + 1] = True
output[~output_mask] = characters[~mask]
output += 0x0621
return output.base.view(f'U{output.size}').item()
В качестве примечания, работа, которую я здесь сделал, вдохновила этот вопрос: Преобразование массива кодовых точек в и из строк