如何在Python中通过折叠实现Unicode字符串匹配

Question

我有一个应用程序实现了增量搜索。它有一个包含unicode字符串的目录，用来和给定的“关键”字符串进行匹配。如果目录中的字符串包含关键字符串中的所有字符，并且这些字符的顺序也对，那么这个目录字符串就算是“命中”。如果关键字符在目录字符串中聚集得更紧密，那么这个匹配的排名会更高。

总之，这个功能运行得很好，能够准确匹配unicode字符串，比如“öst”可以匹配“Östblocket”或者“röst”或者“röd sten”。

不过，现在我想实现字符折叠，因为在某些情况下，像“á”或“é”这样的目录字符和关键字符“a”或“e”之间并不需要区分。

举个例子：“Ole”应该能够匹配“Olé”。

我该如何在Python中最好地实现这个unicode折叠匹配器呢？效率很重要，因为我需要将成千上万的目录字符串与短的关键字符串进行匹配。

它不需要转换成ascii；实际上，算法的输出字符串可以是unicode。保留一个字符总比去掉它要好。

---

我不知道该接受哪个答案，因为我用了一点两者的结合。采用NKFD分解并去掉组合标记几乎就完成了，我只是添加了一些自定义的音译。现在这个模块看起来是这样的：（警告，包含unicode字符，因为这样编辑起来更方便。）

# -*- encoding: UTF-8 -*-

import unicodedata
from unicodedata import normalize, category

def _folditems():
    _folding_table = {
        # general non-decomposing characters
        # FIXME: This is not complete
        u"ł" : u"l",
        u"œ" : u"oe",
        u"ð" : u"d",
        u"þ" : u"th",
        u"ß" : u"ss",
        # germano-scandinavic canonical transliterations
        u"ü" : u"ue",
        u"å" : u"aa",
        u"ä" : u"ae",
        u"æ" : u"ae",
        u"ö" : u"oe",
        u"ø" : u"oe",
    }

    for c, rep in _folding_table.iteritems():
        yield (ord(c.upper()), rep.title())
        yield (ord(c), rep)

folding_table = dict(_folditems())

def tofolded(ustr):
    u"""Fold @ustr

    Return a unicode str where composed characters are replaced by
    their base, and extended latin characters are replaced by
    similar basic latin characters.

    >>> tofolded(u"Wyłącz")
    u'Wylacz'
    >>> tofolded(u"naïveté")
    u'naivete'

    Characters from other scripts are not transliterated.

    >>> tofolded(u"Ἑλλάς") == u'Ελλας'
    True

    (These doctests pass, but should they fail, they fail hard)
    """
    srcstr = normalize("NFKD", ustr.translate(folding_table))
    return u"".join(c for c in srcstr if category(c) != 'Mn')

if __name__ == '__main__':
    import doctest
    doctest.testmod()

（另外，如果有人对实际匹配感兴趣：我会提前为所有目录构建折叠字符串，并将折叠版本放入已经存在的目录对象别名属性中。）

Answer 1

一个通用的解决方案（特别适合搜索标准化和生成网址后缀）是 unidecode 模块：

http://pypi.python.org/pypi/Unidecode

这个模块是 Perl 语言中的 Text::Unidecode 模块的移植版。虽然它不是很完整，但它可以翻译所有我找到的拉丁字母字符，还能把西里尔字母、中文等转换成拉丁字母，甚至能正确处理全角字符。

通常来说，最好是把你不想在最终结果中出现的字符去掉，或者用其他字符替代（比如 "äßœ$" 会被转换成 "assoe$"，所以你可能想去掉那些不是字母或数字的字符）。对于那些应该被转换但不该出现的字符（比如 § 变成 SS，€ 变成 EU），你需要先清理输入：

input_str = u'äßœ$'
input_str = u''.join([ch if ch.isalnum() else u'-' for ch in input_str])
input_str = str(unidecode(input_str)).lower()

这段代码会把所有非字母数字的字符替换成一个占位符，然后再进行转换，并把字符串转换成小写。

Answer 2

对于我的应用，我在其他评论中已经提到过：我想要一个unicode的结果，并且不处理未处理的字符。

在这种情况下，正确的方法是创建一个UCA排序器对象，并将其强度设置为仅进行初级比较，这样就完全忽略了重音符号。

我在这个回答中展示了如何使用Perl来实现这一点。第一个排序器对象的强度是你需要的，而第二个则考虑了重音符号以解决平局。

你会注意到，在进行这些比较时，没有任何字符串受到影响：原始数据保持不变。

Answer 3

你可以使用这个 strip_accents 函数来去掉重音符号：

def strip_accents(s):
   return ''.join((c for c in unicodedata.normalize('NFD', unicode(s)) if unicodedata.category(c) != 'Mn'))

>>> strip_accents(u'Östblocket')
'Ostblocket'