如何在Python中使用折叠实现Unicode字符串匹配

Question

我有一个应用程序实现增量搜索。我有一个Unicode字符串目录需要匹配并将它们与给定的“键”字符串匹配；如果目录字符串包含了所有按照顺序的键中的字符，它是一个“命中”，如果键字符在目录字符串中聚集，则排名更高。

无论如何，这个应用程序可以完美地匹配Unicode，并且"öst"会匹配"Östblocket"或"röst"或"röd sten" 。

现在我想要实现折叠（Folding），因为有些情况下，区分目录字符（例如“á”或“é”）和键字符（例如“a”或“e”）是没有用处的。

例如："Ole" 应该匹配 "Olé"。

我该如何最好地在Python中实现这个Unicode-folding匹配器？效率很重要，因为我需要将数千个目录字符串与短的给定键匹配。

它不必将其转换为ASCII；事实上，算法的输出字符串可以是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()

（如果有人感兴趣，实际匹配的方法是：我预先为我的所有目录构建了折叠字符串，并将折叠版本放入已经可用的目录对象别名属性中。）

- u0b34a0f6ae

---

这真的很酷，对于自动完成人名可能非常有用，因为大多数人在搜索名字时不会介意重音符号。我正在研究如何在Java中执行类似的操作。这似乎处理了一些情况：http://java.sun.com/javase/6/docs/api/java/text/Collator.html。 - João Silva

请注意，如果您希望将它们变为去除重音符号，则可能需要从上面的特殊情况表中省略“ü、å、ä、ö”。这些双元音扩展是我从自己的角度想要的（更正确地说是降低了我的语言水平）；在其他语言中，所有这些事情都有不幸的例外（例如西班牙语的ü）。 - u0b34a0f6ae

请查看Python 3的Unicode规范化unicodedata.normalize。这个问题来自2009年。 - JimB

Answer 1

您可以使用 这个 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'

- João Silva

---

这样做会在字符串中留下未处理的字符，而不是剥离它们，这是好的。'Dźwięk -> Dzwiek' 但 'Wyłącz -> Wyłacz'; 然后我可以在此基础上添加特殊情况。 - u0b34a0f6ae

我接受这个答案，因为过滤规范化几乎走到了最后。请查看更新的问题以了解我使用的内容。 - u0b34a0f6ae

然而，请注意您想要过滤NFKD；这是一种没有严格等价的分解，例如下标字符被转换为普通数字。 - u0b34a0f6ae

Answer 2

对于我的应用程序，我已在另一个评论中解决了这个问题：我想要一个Unicode结果，并保留未处理的字符。在这种情况下，正确的方法是创建一个UCA排序器对象，并将其强度设置为仅在主要强度比较，从而完全忽略变音符号。我在这个答案中展示了如何使用Perl来实现这一点。第一个排序器对象具有所需的强度，而第二个排序器对象考虑了重音符号以进行排名。您会注意到，在进行这些比较时没有对字符串进行修改：原始数据保持不变。

- tchrist

Answer 3

一个通用的解决方案（尤其是用于搜索规范化和生成slug）是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()

这将用虚拟替换符号替换所有非字母数字字符，然后转换字符串并将其转换为小写。

- Alan Plum

---

谢谢您的建议。我的应用程序是多语言的，我不确定是否想要将其过度转换为严格的ASCII别名。我的当前解决方案具有不同但很酷的功能，例如日文字符“ヘ”将与“ペ”匹配，就像“a”将与“ä”匹配一样；去除变音符号更加通用，尽管我还没有确定这是否有用（我只有来自西方用户的反馈）。 - u0b34a0f6ae

在什么情况下，您希望 'ペ'（pe）与 'ヘ'（he）匹配？ - simon

Answer 4

这个怎么样？

normalize('NFKD', unicode_string).encode('ASCII', 'ignore').lower()

摘自这里（西班牙语）http://python.org.ar/pyar/Recetario/NormalizarCaracteresUnicode

- Esteban Feldman

---

对于我的应用程序，我已经在另一个评论中解决了这个问题：我想要一个Unicode结果，并且不处理未处理的字符。 - u0b34a0f6ae

Answer 5

看一下这个：ftp://alan.smcvt.edu/hefferon/unicode2ascii.py

可能不完整，但可以帮助你入门。

- stefanw

---

这个脚本很有启发性，但是我其实不想再将它转换成纯ASCII了。请查看更新后的问题，了解我现在使用的是什么。 - u0b34a0f6ae