在已排序的单词列表中搜索不带音调符号的单词

Question

我一直在努力为下面的问题想出一个有效的解决办法。我有一个包含变音符号的单词的排序列表，我希望能够在不使用变音符号的情况下进行搜索。例如，我想用kriz匹配kříž。经过一番头脑风暴后，我想到了以下问题，我想问你们，更有经验的（或聪明的）人，这是最佳的还是有更好的解决方案。我使用的是Python，但问题与语言无关。你知道吗

首先，我提供了这些字符的一个映射，这些字符有一些区分重音的同级。如果是捷克人：

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

现在我可以轻松地在输入上创建单词的所有变体。所以对于“喇嘛”，我得到：[“喇嘛”，“拉玛”，“拉玛”，“拉玛”]。我已经可以用它来搜索匹配这些排列的词了，但是当涉及到像“nepredvidatelny”（不可预测）这样的词时，就会得到13824个排列。即使我的笔记本电脑上有一个闪亮的英特尔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'、'aa'而不是'a'、'aa'、'z'。你知道吗

谢谢大家的评论。你知道吗

编辑：我无法创建任何辅助预计算数据库，该数据库将是原始数据库的副本，但没有音调符号。假设原始数据库太大，无法复制。你知道吗

Answer 1

仅使用标准库（^{}和^{}）可以执行以下操作：

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的。你知道吗

对于python 2，您需要：

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

Answer 2

如前所述，您要做的是将unicode单词（包含音调符号）翻译成最接近的标准24字字母版本。你知道吗

实现这一点的一种方法是创建第二个单词列表（与原文大小相同）以及相应的翻译。然后在翻译后的列表中进行查询，一旦找到匹配项，就在原始列表中查找相应的位置。你知道吗

或者，如果你可以改变原来的名单，你可以翻译所有的地方和剥离重复。你知道吗

Answer 3

看看Unidecode，你可以用它把音调符号转换成最接近的ascii。e、 g.：-unidecode(u'kříž')