Поиск слов без диакритики в отсортированном списке слов

Question

Я пытался найти эффективное решение для следующей проблемы. У меня есть отсортированный список слов, содержащих диакритические знаки, и я хочу иметь возможность выполнять поиск без использования диакритики. Так, например, я хочу сопоставить «kříž», просто используя «kriz». После небольшого мозгового штурма я придумал следующее, и я хочу спросить вас, более опытные (или умные), оптимально ли это или есть лучшее решение. Я использую Python, но проблема не зависит от языка.

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

cz_map = {'a' : ('á',), ... 'e' : ('é', 'ě') ... } 

Теперь я могу легко создать все варианты слова на входе. Поэтому для «ламы» я получаю: ['lama', 'láma', 'lamá', 'lámá']. Я уже мог использовать это для поиска слов, которые соответствуют любой из этих перестановок, но когда дело доходит до таких слов, как «непредвидательный» (непредсказуемый), получается 13824 перестановки. Несмотря на то, что у моего ноутбука яркий логотип Intel i5 на нем, это на мой вкус слишком наивное решение.

Вот улучшение, которое я придумал. Словарь слов, которые я использую, имеет вариант бинарного поиска для сопоставления префикса (возвращает слово в нижнем индексе с соответствующим префиксом), что очень полезно в этом случае. Я начинаю с первого символа, ища его префикс существования в словаре, и если он есть, я складываю его для следующего символа, который будет протестирован, добавленный ко всем этим сложным последовательностям. Таким образом, я распространяю только те строки, которые приводят к совпадению. Вот код:

def dia_search(word, cmap, dictionary): 
    prefixes = [''] 
    for c in word: 
     # each character maps to itself 
     subchars = [c] 
     # and some diacritical siblings if they exist 
     if cmap.has_key(c): 
      subchars += cmap[c] 
     # build a list of matching prefixes for the next round 
     prefixes = [p+s for s in subchars 
         for p in prefixes 
         if dictionary.psearch(p+s)>0] 
    return prefixes 

Этот метод дает очень хорошие результаты, но может быть еще лучше? Или есть метод, который не нуждается в сопоставлении символов, как в этом случае? Я не уверен, что это актуально, но словарь, который я использую, не сортируется никакими правилами сортировки, поэтому последовательность - это «a», «z», «a», «a», «á», «z», как и следовало ожидать.

Спасибо за комментарии.

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

Answer 1

Посмотрите на Unidecode, используя который вы можете фактически преобразовать диакритические знаки в ближайший ascii. e.g.:- unidecode(u'kříž')

Answer 2

используя стандартную библиотеку только (str.maketrans и str.translate), вы можете сделать это:

intab = "řížéě" # ...add all the other characters 
outtab = "rizee" # and the characters you want them translated to 
transtab = str.maketrans(intab, outtab) 

strg = "abc kříž def "; 
print(strg.translate(transtab)) # abc kriz def 

это для Python3.

для питона 2 вы должны:

from string import maketrans 
transtab = maketrans(intab, outtab) 
# the rest remains the same 

Answer 3

Как было предложено, что вы хотите сделать, это перевести ваши Юникода слова (содержащие диакритические) до ближайшего стандартного 24 слов алфавита версии.

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

Или, если вы можете изменить исходный список, вы можете перевести все на месте и разделить дубликаты.