Cython convert string to unicode

Question

I am trying to use this lib https://github.com/pytries/datrie to manipulate Chinese text .

But I encounter a problem - it has problem to encode decode Chinese unicode:

import datrie
text = htmls_2_text(input_dir)
trie = datrie.Trie(''.join(set(text))) # about 2221 unique chars
trie['今天天气真好'] = 111
trie['今天好'] = 222
trie['今天'] = 444

print(trie.items())

[('今义', 444), ('今义义傲兢于', 111), ('今义于', 222)]

unique chars: https://pastebin.com/n2i280i8

The result is wrong, obviously there is a decoding/encoding error.

---

Then I look into source code https://github.com/pytries/datrie/blob/master/src/datrie.pyx

cdef cdatrie.AlphaChar* new_alpha_char_from_unicode(unicode txt):
    """
    Converts Python unicode string to libdatrie's AlphaChar* format.
    libdatrie wants null-terminated array of 4-byte LE symbols.
    The caller should free the result of this function.
    """
    cdef int txt_len = len(txt)
    cdef int size = (txt_len + 1) * sizeof(cdatrie.AlphaChar)

    # allocate buffer
    cdef cdatrie.AlphaChar* data = <cdatrie.AlphaChar*> malloc(size)
    if data is NULL:
        raise MemoryError()

    # Copy text contents to buffer.
    # XXX: is it safe? The safe alternative is to decode txt
    # to utf32_le and then use memcpy to copy the content:
    #
    #    py_str = txt.encode('utf_32_le')
    #    cdef char* c_str = py_str
    #    string.memcpy(data, c_str, size-1)
    #
    # but the following is much (say 10x) faster and this
    # function is really in a hot spot.
    cdef int i = 0
    for char in txt:
        data[i] = <cdatrie.AlphaChar> char
        i+=1

    # Buffer must be null-terminated (last 4 bytes must be zero).
    data[txt_len] = 0
    return data


cdef unicode unicode_from_alpha_char(cdatrie.AlphaChar* key, int len=0):
    """
    Converts libdatrie's AlphaChar* to Python unicode.
    """
    cdef int length = len
    if length == 0:
        length = cdatrie.alpha_char_strlen(key)*sizeof(cdatrie.AlphaChar)
    cdef char* c_str = <char*> key
    return c_str[:length].decode('utf_32_le')

I have tried use the commented block txt.encode('utf_32_le') to replace current faster trick, nether work.

I don't see there is any wrong in this code , what is the problem ?

Answer 1

It looks like the issue is that this datrie package supports at most 255 values for characters in the keyset: https://github.com/pytries/datrie/blob/master/libdatrie/datrie/alpha-map.h#L59

I recommend using marisa_trie::RecordTrie from here: https://pypi.python.org/pypi/marisa-trie

Unfortunately it's a static data structure, so you cannot modify it after building, but it fully support unicode, serialization to disk, and all sorts of value types.

>>> from marisa_trie import RecordTrie
>>> rt = RecordTrie(">I", [(u'今天天气真好', (111,)), (u'今天好', (222,)), (u'今天', (444,))])
>>> for x in rt.items():
...     print x[0], x[1]
...
今天天气真好 (111,)
今天好 (222,)
今天 (444,)

(Note that I am using Python 2.7 in this example, hence the u'' and printing in a loop.)

EDIT

If you absolutely must use datrie.Trie, you can exploit this in a rather dumb way:

def encode(s):
    return ''.join('%08x' % ord(x) for x in s)

def decode(s):
    return ''.join(chr(int(s[n:n+8], 16)) for n in range(0, len(s), 8))

>>> trie = datrie.Trie('0123456789abcdef')
>>> trie[encode('今天天气真好')] = 111
>>> trie[encode('今天好')] = 222
>>> trie[encode('今天')] = 444
>>> [decode(x) for x in trie.keys()]
['今天', '今天天气真好', '今天好']

I used 8 because 32 is the maximum bit-width of any utf8-encoded character. You could save space by computing max(ord(x) for x in text) and using that as the padding. Or you could come up with your own encoding scheme that uses at most 255 char values. This was just a very fast and inefficient solution.

Of course, this sort of defeats the purpose of using a trie...